3.数组中重复的数字

排序遍历

可以直接将数组排序,然后进行循环遍历,就可以找到数组中重复的数字了。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);
for (int i = 1;i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
return nums[i];
}
}
return 0;
}
}

Set去重

可以将该数组丢到Set集合里去重,若是添加失败就代表该数字重复,直接返回就好了。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i : nums) {
if (!set.add(i)) {
return i;
}
}
return 0;
}
}

哈希表

跟Set差不多,添加到哈希表之前,先判断一下是否有该键,然后要是有就直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int findRepeatNumber(int[] nums) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i : nums) {
if (map.containsKey(i)) {
return i;
}
map.put(i,i);
}
return 0;
}
}

原地置换(类似桶排序)

遍历数组,将每一个数放在与它等值的下标下,因为题目说了数字都在1~n - 1,所以当该下标出现了与它一样的数字,代表这个数字是重复的。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int findRepeatNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while(nums[i] != i) {
if(nums[i] == nums[nums[i]]) return nums[i];
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return 0;
}
}

衍生题

题目详情可以参考https://www.acwing.com/problem/content/description/15/

这里可以使用上述的哈希和Set集合来进行查找,或者在创建一个数组,然后使用桶排序找出重复的元素。

因为必定会有一个重复的,可以理解为数组中间会出现一个环,所以可以当成寻找链表的环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int duplicateInArray(int[] nums) {
// 快慢指针寻找相遇点
int fast = 0
int slow = 0;
while (fast == 0 || fast != slow) {
fast = nums[nums[fast]];
slow = nums[slow];
}
// 寻找入环点
fast = 0;
while (fast != slow) {
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
}

还有就是利用分治的思想来解。类似二分查找的思想。

利用数值将数组分成两半,如果一边坑的个数小于数的个数,代表重复的数字就在那半边,所以缩小区间,直到找到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int duplicateInArray(int[] nums) {
int l = 1;
int r = nums.length - 1;
while (l < r) {
int mid = l + r >> 1; // 分成两个区间[l, mid]和[mid + 1, r]
int count = 0;
// 统计[l, mid]的个数
for(int i : nums)
{
if(l <= i && i <= mid)
count++;
}
// 个数若是大于坑位,代表该区间有重复的数字,然后调整区间
if(count > mid - l + 1)
r = mid;
else
l = mid + 1;
}
return l;
}
}

4.二维数组中的查找

数组遍历

直接将这个二维数组遍历,暴力破解。

1
2
3
4
5
6
7
8
9
10
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
for (int[] i : matrix) {
for (int j : i) {
if (j == target) return true;
}
}
return false;
}
}

二维查找

根据递增的单调性,可以从最右上角一个个进行排除,寻找对应的值。可以从右下角向左下角进行遍历(反过来也可以)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) return false;
int i = 0;
// 从最后一列开始,排除最后一列小于给定值的行
int j = matrix[0].length - 1;
while(i < matrix.length && j >= 0) {
if (matrix[i][j] == target) return true;
// 如果值大于给定值,代表当前行不存在给定值,所以遍历下一行
if (matrix[i][j] > target) j--;
else i++;
}
return false;
}
}

5.替换空格

replaceAll

String类里就自带一个替换的方法了,所以可以直接进行替换。

1
2
3
4
5
class Solution {
public String replaceSpace(String s) {
return s.replaceAll(" ","%20");
}
}

遍历字符串

直接遍历字符串,出现了空格就替换,不然就不替换。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public String replaceSpace(String s) {
StringBuilder res = new StringBuilder();
char[] str = s.toCharArray();
for (char c : str) {
if (c == ' ') res.append("%20");
else res.append(c);
}
return res.toString();
}
}

要是不能用动态的增加字符串,就只能先遍历一遍字符串,然后判断答案的长度,然后在创建一个新的数组,然后依次放入新数组就好了。

6. 从尾到头打印链表

反转链表后输出

这里最简单的解法就是将链表反转,然后在打印链表了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int[] reversePrint(ListNode head) {
if (head == null) return new int[0];
ListNode newhead = reverse(head);
List<Integer> list = new ArrayList<>();
while(newhead != null) {
list.add(newhead.val);
newhead = newhead.next;
}
int[] res = new int[list.size()];
for (int i = 0; i< list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
public ListNode reverse(ListNode head) {
if (head.next == null) return head;
ListNode newhead = reverse(head.next);
head.next.next = head;
head.next = null;
return newhead;
}
}

递归遍历

这里可以使用类似后序遍历的操作,先递归进去然后添加值,这样就类似栈了,直接从后到前输出。或者这里定义一个栈也可以进行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
List<Integer> list = new ArrayList<>();
public int[] reversePrint(ListNode head) {
if (head == null) return new int[0];
reverse(head);
int[] res = new int[list.size()];
for (int i = 0; i< list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
public void reverse(ListNode head) {
if (head == null) return;
reverse(head.next);
list.add(head.val);
}
}

反向输出

其实可以看到,其实从前遍历,然后反向输出就行了,其实并不用一定是正向的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {

public int[] reversePrint(ListNode head) {
if (head == null) return new int[0];
List<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
int[] res = new int[list.size()];
for (int i = 0; i< list.size(); i++) {
res[i] = list.get(list.size() - i - 1);
}
return res;
}

}

两次遍历

第一次遍历链表,判断数组的个数,然后从后往前赋值就好了。之前的解法也可以改为先进行一次遍历后再赋值,这样就不用使用list集合了,效率太低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {

public int[] reversePrint(ListNode head) {
if (head == null) return new int[0];
ListNode node = head;
int size = 0;
while(node != null) {
size++;
node = node.next;
}
int[] res = new int[size];
for (int i = size - 1; i > -1;i--) {
res[i] = head.val;
head = head.next;
}
return res;
}
}

7.重建二叉树

这题主要是要划分区间,划分好左子树和右子树的区间。

前序遍历的区间可以分为三个。根的值,左子树的值,右子树的值。

中序遍历的区间可以分为三个。左子树的值,根的值,右子树的值。

所以可以用前序遍历的第一个值创建节点,然后遍历前序遍历的数组,用中序遍历的数组来判断是否达到根的值。

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
class Solution {

private int ino = 0;
private int pre = 0;

public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, Integer.MIN_VALUE + 1);
}

private TreeNode build(int[] preorder, int[] inorder, long stop) {
if (pre >= preorder.length) return null;
// 判断该子树是否碰到根
if (inorder[ino] == stop) {
ino++;
return null;
}
TreeNode node = new TreeNode(preorder[pre++]);
// 左子树的范围,到当前节点值,即到子树的根值(按前序遍历的数组)
node.left = build(preorder,inorder,node.val);
// 右子树的范围,从当前节点到最后
node.right = build(preorder,inorder,stop);

return node;
}

}

上面是通过前序遍历和中序遍历去创建一颗二叉树,接下来是通过中序遍历和后序遍历来创建一个二叉树,其实差不多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution { 

private int ino = 0;
private int pos = 0;

public TreeNode buildTree(int[] inorder, int[] postorder) {
pos = postorder.length - 1;
ino = inorder.length - 1;
return build(inorder,postorder,Integer.MIN_VALUE - 1);
}

public TreeNode build(int[] inorder, int[] postorder,long stop) {
if (pos == -1) return null;
if (inorder[ino] == stop) {
ino--;
return null;
}
TreeNode node = new TreeNode(postorder[pos--]);
node.right = build(inorder,postorder,node.val);
node.left = build(inorder,postorder,stop);
return node;
}

}

8.二叉树的下一个节点

题目详情可以参考https://www.acwing.com/problem/content/31/

这里就是直接找下一个节点就好了。

于是会有两种情况。

  1. 当前节点有右子树。那么该节点的下一个节点就是右子树里的最左子节点。
  2. 当前节点没有右子树,那就要追溯回原来第一个是其father左儿子的节点。
    • 该节点是父节点的左孩子,这样下一个节点就是它的father
    • 该节点是父孩子的右孩子,这样下一个节点就是该左子树的父节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public TreeNode inorderSuccessor(TreeNode p) {
// 存在右子树的情况
if (p.right != null) {
p = p.right;
while(p.left != null) p = p.left;
return p;
}
// 不存在右子树的情况
while(p.father != null && p == p.father.right) p = p.father;

return p.father;
}
}

9.用两个栈实现队列

这里先来分析一下这两个栈的作用。栈是先进后出的数据结构,而队列是先进先出的,所以无法进行互通,引入第二个栈是用来存储第一个栈中出栈的元素,这样第二个栈的元素就是第一个栈元素的倒序了,直接出栈就是最先进来的元素了。

入队就直接压入第一个栈中就可以了。

主要是要探讨出队的情况。

  1. 当第二个栈中还有元素的时候,代表这些元素是最先进入的元素,所以直接出栈就是之前最先入队的元素了。
  2. 当第二个栈和第一个栈都没有元素了,那就证明队列为空。
  3. 当第二个栈没有元素,第一个栈有元素,那就直接将第一个栈的元素全部出栈压入第二栈,实现倒序。
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
40
41
42
43
44
45
46
47
48
49
50
51
52
class MyQueue {

Stack<Integer> stack1 = new Stack();
Stack<Integer> stack2 = new Stack();

/** Initialize your data structure here. */
public MyQueue() {}

/** Push element x to the back of queue. */
public void push(int x) {
stack1.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (!stack2.isEmpty()) return stack2.pop();
if (!stack1.isEmpty()) {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
return -1;
}

/** Get the front element. */
public int peek() {
if (!stack2.isEmpty()) return stack2.peek();
if (!stack1.isEmpty()) {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.peek();
}
return -1;
}

/** Returns whether the queue is empty. */
public boolean empty() {
if (stack1.isEmpty() && stack2.isEmpty()) return true;
else return false;
}
}

/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/

10.斐波那契数列

剑指Offer这题的斐波那契数列是结果取模的,因为返回的是int,除了这个需要注意的,其他的和经常的解法差不多了。

递归

可以考虑直接递归,但一般都会超时。

1
2
3
4
5
6
7
class Solution {
public int fib(int n) {
if (n < 0) return 0;
if (n == 1 || n == 2) return 1;
return (fib(n - 1) + fib(n - 2)) % 1000000007;
}
}

dp数组的递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {

public int fib(int n) {
int[] memo = new int[n + 1];
Arrays.fill(memo,0);
return dp(memo,n);
}

public int dp(int[] memo,int n) {
if (n < 0) return 0;
if (n == 1 || n == 2) return 1;
if (memo[n] != 0) return memo[n];
memo[n] = (dp(memo,n - 1) + dp(memo,n - 2)) % 1000000007;
return memo[n];
}

}

迭代解法

这里是可以考虑dp数组的迭代解法的,但是这里只是一次性达到答案,不会回头了,所以记录之前的状态并没有什么意思,所以可以创建临时变量保存需要的临时变量就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int fib(int n) {
if (n <= 0) return 0;
if (n == 1 || n == 2) return 1;
int a = 1;
int b = 1;
for (int i = 3;i <= n; i++) {
int c = (a + b) % 1000000007;
a = b;
b = c;
}
return b;
}
}

青蛙跳台阶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int numWays(int n) {
if (n <= 1) return 1;
if (n == 2) return 2;
int a = 1;
int b = 1;
for (int i = 2;i <= n;i++) {
int c = (a + b) % 1000000007;
a = b;
b = c;
}
return b;
}
}

11.旋转数组的最小数字

排序

可以直接排序在取第一个。

1
2
3
4
5
6
class Solution {
public int minArray(int[] numbers) {
Arrays.sort(numbers);
return numbers[0];
}
}

不递增

找到第一个不递增的数字那就是最小的数字了。

1
2
3
4
5
6
7
8
class Solution {
public int minArray(int[] numbers) {
for (int i = 0;i < numbers.length - 1; i++) {
if (numbers[i] > numbers[i + 1]) return numbers[i + 1];
}
return numbers[0];
}
}

二分查找

二分查找最主要的就是划分区间,需要先分析一下怎样确定好区间。

  1. 中间的数大于最右边的数,代表期间不会单调递增,直接进入右边的区间
  2. 中间的数小于最右边的数,代表期间是单调递增的,直接进入左边的区间
  3. 要是中间的数与最右边的数相等,那就缩进一下区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int minArray(int[] numbers) {
int l = 0;
int r = numbers.length - 1;
while (l < r) {
int mid = l + r >> 1;
if (numbers[mid] > numbers[r]) {
l = mid + 1;
} else if (numbers[mid] < numbers[r]) {
r = mid;
} else {
r -= 1;
}
}
return numbers[l];
}
}

12.矩阵中的路径

经典的dfs和回溯。

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
class Solution {
public boolean exist(char[][] board, String word) {
if (board == null) return false;
int row = board.length;
int col = board[0].length;
// 标记是否经过的数组
boolean[][] isVisited = new boolean[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
// 遍历每个点,确定dfs的起点
if (board[i][j] == word.charAt(0) && dfs(board,word,0,i,j,isVisited)) return true;
}
}
return false;
}

public boolean dfs(char[][] board,String word,int n,int x,int y,boolean[][] isVisited){
if (board[x][y] != word.charAt(n)) return false;
if (n == word.length() - 1) return true;
// 标记经过
isVisited[x][y] = true;
// 偏移数组,上下左右
int[] dx = {0,0,-1,1};
int[] dy = {-1,1,0,0};
// 按上下左右开始偏移
for (int i = 0; i < 4; i++) {
int lx = x + dx[i];
int ly = y + dy[i];
// 保证下一步没有越界而且没有经过
if (lx >= 0 && lx < board.length && ly >= 0 && ly < board[0].length && !isVisited[lx][ly]) {
if (dfs(board,word,n + 1,lx,ly,isVisited)) return true;
}
}
// 取消标记,回溯
isVisited[x][y] = false;
return false;
}
}

13.机器人的运动范围

dfs

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
class Solution {
public int movingCount(int m, int n, int k) {
if (m == 0 || n == 0) return 0;
boolean[][] isVisited = new boolean[m][n];
return dfs(0,0,k,isVisited);
}

public int dfs(int i,int j,int k,boolean[][] isVisited) {
if (i < 0 || i >= isVisited.length || j < 0 || j >= isVisited[0].length || isVisited[i][j] || !isAllowed(i,j,k)) return 0;
isVisited[i][j] = true;
// 上下左右
return dfs(i-1,j,k,isVisited) + dfs(i+1,j,k,isVisited) + dfs(i,j-1,k,isVisited) + dfs(i,j+1,k,isVisited) + 1;
}
// 判断是否合法
public boolean isAllowed(int m, int n, int k) {
int sum = 0;
while (m != 0) {
sum += m % 10;
m = m / 10;
}
while (n != 0) {
sum += n % 10;
n = n / 10;
}
if (sum <= k) return true;
else return false;
}
}

看看别人的发现判断是否合法不用这么麻烦,还可以优化一下,所以变成下面这样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int movingCount(int m, int n, int k) {
if (m == 0 || n == 0) return 0;
boolean[][] isVisited = new boolean[m][n];
return dfs(0,0,k,isVisited);
}

public int dfs(int i,int j,int k,boolean[][] isVisited) {
if (i < 0 || i >= isVisited.length || j < 0 || j >= isVisited[0].length || isVisited[i][j] || (i/10+i%10+j/10+j%10)>k) return 0;
isVisited[i][j] = true;
return dfs(i-1,j,k,isVisited) + dfs(i+1,j,k,isVisited) + dfs(i,j-1,k,isVisited) + dfs(i,j+1,k,isVisited) + 1;
}

}

从0,0开始,其实只用向右和向下就可以走完全部的格子了,所以可以去掉向左和向上的dfs。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int movingCount(int m, int n, int k) {
if (m == 0 || n == 0) return 0;
boolean[][] isVisited = new boolean[m][n];
return dfs(0,0,k,isVisited);
}

public int dfs(int i,int j,int k,boolean[][] isVisited) {
if (i >= isVisited.length || j >= isVisited[0].length || isVisited[i][j] || (i/10+i%10+j/10+j%10)>k) return 0;
isVisited[i][j] = true;
return dfs(i+1,j,k,isVisited) + dfs(i,j+1,k,isVisited) + 1;
}

}

15.二进制中1的个数

用方法

有个方法是可以算出二进制中1的个数。

1
2
3
4
5
public class Solution {
public int hammingWeight(int n) {
return Integer.bitCount(n);
}
}

位运算

通过数字与1的与运算,来判断最后一个二进制的数是不是1,是的话与运算会返回1,就这样逐个判断二进制1的个数。

1
2
3
4
5
6
7
8
9
10
public class Solution {
public int hammingWeight(int n) {
int res = 0;
while(n != 0) {
res += n & 1;
n >>>= 1;
}
return res;
}
}

还有一个就是用n & (n - 1)来判断,这样的与运算会消去二进制中最右边的1。

1
2
3
4
5
6
7
8
9
10
11
public class Solution {

public int hammingWeight(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
}

n & (n - 1)还能用来判断是不是2的幂。

16.数值的整数次方

这里直接使用相乘的算法会超时,所以用到了快速幂的写法。这里需要注意的点是n为负数的时候,int的负数会比正数多一个,力扣上正好用到了这个边界−2147483648,所以需要用long类型来存储。

快速幂的迭代写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public double myPow(double x, int n) {
if (n == 0) return 1;
long a = n;
double res = 1.0;
if (n < 0) {
x = 1 / x;
a = -a;
}
while (a > 0) {
if ((a & 1) == 1) res *= x;
x = x * x;
a = a >> 1;
}
return res;
}
}

快速幂的递归写法

1
2
3
4
5
6
7
8
class Solution {
public double myPow(double x, int n) {
if (n == 0) return 1;
if (n == -1) return 1 /x;
if ((n & 1) == 1) return myPow(x * x,n >> 1) * x;
else return myPow(x * x,n >> 1);
}
}

18.删除链表的节点

这里可以直接查到那个需要删除的节点,然后改变链表的指向就好了。

迭代写法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head == null) return null;
if (head.val == val) return head.next;
ListNode node = head;
while (head.next.val != val) {
head = head.next;
}
head.next = head.next.next;
return node;
}
}

递归写法

1
2
3
4
5
6
7
8
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head == null) return null;
if (head.val == val) return head.next;
head.next = deleteNode(head.next,val);
return head;
}
}

21.调整数组顺序使奇数位于偶数前面

这题一看题目就是有点像快排的思想,双指针遍历就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int[] exchange(int[] nums) {
if (nums.length == 0) return new int[0];
int pre = 0;
int cur = nums.length - 1;
while (cur > pre) {
while (nums[pre] % 2 != 0 && pre < cur) pre++;
while (nums[cur] % 2 == 0 && pre < cur) cur--;
int temp = nums[pre];
nums[pre] = nums[cur];
nums[cur] = temp;
}
return nums;
}
}

22.链表中倒数第K个节点

快慢指针

这题用快慢指针还是很简单的,先让快指针走N步,然后快慢指针一起走,当快指针都到链表尾部,那么慢指针就是倒数第K个节点了。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
while (k-- > 0) fast = fast.next;
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}

24.反转链表

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode node = cur.next;
cur.next = pre;
pre = cur;
cur = node;
}
return pre;
}
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(head);
}
public ListNode reverse(ListNode head) {
if (head == null || head.next == null) return head;
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
}

25.合并两个排序的链表

迭代

这个只要遍历就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l2 == null) return l1;
if (l1 == null) return l2;
ListNode res = new ListNode();
ListNode node = res;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
node.next = new ListNode(l2.val);
l2 = l2.next;
node = node.next;
} else {
node.next = new ListNode(l1.val);
l1 = l1.next;
node = node.next;
}
}
if (l1 == null) node.next = l2;
if (l2 == null) node.next = l1;
return res.next;
}
}

递归

递归的解法挺简洁的,但是可能会有点绕。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l2 == null) return l1;
if (l1 == null) return l2;
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next,l2);
return l1;
} else {
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}

27.二叉树的镜像

1
2
3
4
5
6
7
8
9
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) return null;
TreeNode node = new TreeNode(root.val);
node.left = mirrorTree(root.right);
node.right = mirrorTree(root.left);
return node;
}
}

28.对称的二叉树

这题递归主要是要理清思路。将左子树和右子树传入,然后比较值,在将左子树的左子树和右子树的右子树,右子树的左子树和左子树的右子树放入递归判断就好了。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return issymmetric(root.left,root.right);
}
public boolean issymmetric(TreeNode left,TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
if (left.val != right.val) return false;
return issymmetric(left.left,right.right) && issymmetric(left.right,right.left);
}
}

29.顺时针打印矩阵

这题和那题螺旋矩阵差不多,最主要的就是遍历的边界的界定,这还是有点麻烦的。

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
class Solution {
public int[] spiralOrder(int[][] matrix) {
int rows = matrix.length;
if (rows == 0) return new int[0];
int cols = matrix[0].length;
if (cols == 0) return new int[0];
int[] res = new int[rows * cols];
int count = 0;
int up = 0,down = rows - 1,left = 0,right = cols - 1;
while (count < rows * cols) {
// 向右,遍历完,上边界下移
for (int i = left; i <= right; i++) res[count++] = matrix[up][i];
up++;
// 向下,遍历完,右边界左移
for (int i = up; i <= down; i++) res[count++] = matrix[i][right];
right--;
// 向左,遍历完,下边界上移
for (int i = right; i >= left && up <= down; i--) res[count++] = matrix[down][i];
down--;
// 向上,遍历完,左边界右移
for (int i = down; i >= up && left <= right; i--) res[count++] = matrix[i][left];
left++;
}
return res;
}
}

30. 栈的压入和弹出序列

这题要先理清思路,首先要将压入序列压入栈,直到和弹出序列的第一个元素一样后,就要弹出直到和弹出序列不一样了在压入栈。这样直到压入序列遍历完了之后,要是栈为空的话,那就代表这个弹出序列不对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int count = 0;
for(int i : pushed) {
stack.push(i);
while(!stack.isEmpty() && stack.peek() == popped[count]) {
stack.pop();
count++;
}
}
return stack.isEmpty();
}
}

32.1.从上到下打印二叉树

这题就是层序遍历就可以了,要注意的就是确定数组的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int[] levelOrder(TreeNode root) {
int count = pro(root);
if (count == 0) return new int[0];
int[] res = new int[count];
count = 0;
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
while (!deque.isEmpty()) {
TreeNode node = deque.poll();
res[count++] = node.val;
if (node.left != null) deque.offer(node.left);
if (node.right != null) deque.offer(node.right);
}
return res;

}

public int pro(TreeNode root) {
if (root == null) return 0;
return pro(root.left) + pro(root.right) + 1;
}
}

32.2.从上到下打印二叉树

这个也是层序遍历,与上一题不一样的是要确定每层的节点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()) {
int size = deque.size();
List<Integer> list = new ArrayList<>();
while(size > 0) {
TreeNode node = deque.poll();
list.add(node.val);
if(node.left != null) deque.offer(node.left);
if(node.right != null) deque.offer(node.right);
size--;
}
res.add(list);
}
return res;
}
}

32.3从上到下打印二叉树

这个就是要记录一下层数,这里的倒序可以分为两种解法。

  1. 倒着加入到数组
  2. 加入到数组后再倒序

两种方法哪个都可以,我就使用了第二种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
int deep = 1;
while(!deque.isEmpty()) {
int size = deque.size();
List<Integer> list = new ArrayList<>();
while(size > 0) {
TreeNode node = deque.poll();
list.add(node.val);
if(node.left != null) deque.offer(node.left);
if(node.right != null) deque.offer(node.right);
size--;
}
if (deep++ % 2 == 0) Collections.reverse(list);
res.add(list);
}
return res;
}
}