7. Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
题目：给定一个数字x，返回其镜像数字。
思路：x mod 10 取余，sum累加余数，并在每次累加之前自乘10，x = x / 10，当x为0时，返回sum。注意当sum超过int范围时，返回0。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int reverse(int x) {
int sum = 0;
while(x != 0){
int cur = x % 10;
x = x / 10;
if((long)sum * 10 > Integer.MAX_VALUE || (long)sum * 10 < Integer.MIN_VALUE) return 0;
sum = sum * 10 + cur;
}
return sum;
}
}
771. Jewels and Stones
You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in Sis a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
Example 1:
Input: J = "aA", S = "aAAbbbb"
Output: 3
Example 2:
Input: J = "z", S = "ZZ"
Output: 0
题目：给定一个字符串J，其中每个字符代表珠宝，给定一个字符串S，其中每个字符代表石头；若S中的字符出现在J中，则该字符视为珠宝，返回S中的珠宝数。
思路：依次判断S中的字符是否在J中。
1
2
3
4
5
6
7
8
9
10
class Solution {
public int numJewelsInStones(String J, String S) {
int count = 0;
char[] charS = S.toCharArray();
for(char s : charS){
if(J.indexOf(s) != -1) count += 1;
}
return count;
}
}
74. Search a 2D matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
题目：在一个矩阵中找出target。矩阵满足横向递增，，且每一行的第一个数字都比前一行的最后一个数字大，即纵向也是递增的。
思路：以右下角为起始搜索点，若此处比target大，则网上搜索；若比target小，则往右搜索。
判断最左：当i = 0时，左孩子不为空，则left = 0；左孩子为空，右孩子不为空，则left = 1；
判断最右：当i = len - 1时，右孩子不为空，则right = 2 * i + 1；左孩子不为空，右孩子为空，则right = 2 * i
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0].length == 0 || matrix == null) return false;
int rlen = matrix.length, clen = matrix[0].length;
int i = rlen - 1, j = 0;
while(i >= 0 && j <= clen - 1){
if(matrix[i][j] > target) i--;
else if(matrix[i][j] < target) j++;
else return true;
}
return false;
}
}
662. Maximum Width of Binary Tree
Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.
The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.
Example 1:
Input:
1
/ \
3 2
/ \ \
5 3 9
Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
Example 2:
Input:
1
/
3
/ \
5 3
Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
Example 3:
Input:
1
/ \
3 2
/
5
Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
Example 4:
Input:
1
/ \
3 2
/ \
5 9
/ \
6 7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).
题目：返回一棵二叉树的最大宽度。
思路：二叉树用数组表示时，其的每个节点的下标，都可以由其父节点表示。若父节点下标为i，则左孩子下标为 2*i，右孩子为2*i+1。根据这个性质，利用树的宽度遍历方法，同时记录每个节点的下标，每遍历一层，计算最右节点与最左节点的差+1，表示盖层的宽度。返回最大宽度即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.ArrayList;
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) return 1;
int max = Integer.MIN_VALUE, layer = -1;
ArrayList<TreeNode> q = new ArrayList<TreeNode>();
ArrayList<Integer> loc = new ArrayList<Integer>();
q.add(root);
loc.add(1);
while(!q.isEmpty()){
int len = q.size();
for(int i = 0; i < len; i++){
TreeNode tmp = tmp = q.remove(0);
int tmpLoc = loc.remove(0);
if(tmp.left != null) {
q.add(tmp.left);
loc.add(tmpLoc * 2);
}
if(tmp.right != null) {
q.add(tmp.right);
loc.add(tmpLoc * 2 + 1);
}
}
if(loc.size() > 0) max = Math.max(max, loc.get(loc.size() - 1) - loc.get(0) + 1);
}
return max;
}
}
35. Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
题目：在数组中找出target的位置，若 target不在数组中，返回插入位置。
思路：排序数组，用二分查找，若不存在，则返回start位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int searchInsert(int[] nums, int target) {
if(nums.length == 0 || nums == null) return 0;
int start = 0, end = nums.length - 1;
while(start <= end){
int mid = (start + end) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) start = mid + 1;
else if(nums[mid] > target) end = mid - 1;
}
return start;
}
}