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
class Solution {
public int duplicateInArray(int[] nums) {
int l = 1;
int r = nums.length - 1;
while (l < r) {
int mid = l + r >> 1;
// 记录小于中间值的数的个数
int count = 0;
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;
}

}

14.1 剪绳子

动态规划

这一题刚开始给我的想法是使用动态规划去解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int cuttingRope(int n) {
if (n == 1 || n == 2) return 1;
if (n == 3) return 2;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for (int i = 4; i <= n; i++) {
int max = 0;
// j >i / 2就会出现重复了,所以就不需要那部分的数据比较了
for (int j = 1; j <= i / 2; j++) {
max = Math.max(max,dp[j] * dp[i - j]);
}
dp[i] = max;
}
return dp[n];
}
}

贪婪算法

搬用题解关于该题的解释。

  1. 任何大于1的数都可由2和3相加组成。
  2. 因为都能有2和3组成,所以当3的数量越多,乘积越大。当剩余的绳子长度大于等于5,尽可能剪长度为3的绳子。
  3. 有一个特例。当剩余的绳子长度等于4,就将绳子剪为两段2。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int cuttingRope(int n) {
if (n == 1 || n == 2) return 1;
if (n == 3) return 2;
int res = 1;
while (n > 4) {
res *= 3;
n -= 3;
}
return res * n;
}
}

14.2 剪绳子2

这题将数据量变大了很多,使用动态规划就会很麻烦,所以用刚刚的贪婪算法,修改一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int cuttingRope(int n) {
if (n == 1 || n == 2) return 1;
if (n == 3) return 2;
long res = 1;
while (n > 4) {
res *= 3;
res %= 1000000007;
n -= 3;
}
return (int)(res * n % 1000000007);
}
}

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;
}
}
}

26. 树的子结构

首先要先找到A中与B节点的头节点相等的点,然后递归判断A与B的左子树与右子树,看是否结构与节点值相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A == null || B == null) return false;
// 寻找A节点中与B节点头节点相等的节点
return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
// 判断A与B是否是同一个结构
public boolean dfs(TreeNode A, TreeNode B){
if(B == null) return true;
if(A == null) return false;
return A.val == B.val && dfs(A.left, B.left) && dfs(A.right, B.right);
}
}

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. 包含min函数的栈

找到最小元素其实并不难,这题难的地方是调用minpushpop的时间复杂度都要为O(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
class MinStack {

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

/** initialize your data structure here. */
public MinStack() {
}

public void push(int x) {
stack1.push(x);
if (stack2.isEmpty() || stack2.peek() >= x) {
stack2.push(x);
}
}

public void pop() {
int pop = stack1.pop();
if (pop <= stack2.peek()) {
stack2.pop();
}
}

public int top() {
return stack1.peek();
}

public int min() {
return stack2.peek();
}
}

31. 栈的压入和弹出序列

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

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;
}
}

40. 最小的k个数

暴力解法

直接排序取前k个数行了。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0) return new int[0];
Arrays.sort(arr);
int[] mink = new int[k];
for (int i = 0; i < k; i++) {
mink[i] = arr[i];
}
return mink;
}
}

快速排序

堆排序

48. 最长不含重复字符的子字符串

这题两重循环的暴力解很大概率会超时,所以就不用暴力解了。

这里最好的方法就是滑动窗口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (len <= 1) return len;
int l = 0, max = 0;
Map<Character,Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
// 如果已经存在重复的字符,就更新窗口的左边界让字符串不重复
if (map.containsKey(s.charAt(i))) {
// 重新定义窗口左边界
l = Math.max(l, map.get(s.charAt(i)) + 1);
}
// 更新(添加)map里字符的坐标
map.put(s.charAt(i),i);
// 计算最大值
max = Math.max(max, i - l + 1);
}
return max;
}
}

49. 丑数

使用动态规划,主要是凑成最小的丑数,然后一个个凑到第N个,就是用2,3,5的公倍数从小凑到N。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; i++) {
int min = Math.min(Math.min(dp[p2] * 2,dp[p3] * 3),dp[p5] * 5);
if (min % 2 == 0) p2++;
if (min % 3 == 0) p3++;
if (min % 5 == 0) p5++;
dp[i] = min;
}
return dp[n - 1];
}
}

61. 扑克牌的顺子

首先确定答案的约束。

  1. 抽到的五张牌是不是连续的。
  2. 抽到的五张牌是不重复的。
  3. 大小王可以换为任意一张牌,可以存在重复的0

这里可以找出一定的规律,抽到的五张牌中最大的减去最小的小于5就可以说明这五张牌是重复的了。

Set去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean isStraight(int[] nums) {
Set<Integer> res = new HashSet<>();
int max = -1, min = 14;
for (int i : nums) {
if (i == 0) continue;
max = Math.max(max,i);
min = Math.min(min,i);
// 如果有重复的就返回false
if (!res.add(i)) return false;
}
return max - min < 5;
}
}

排序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
int count = 0;
for(int i = 0; i < 4; i++) {
// 统计大小王的个数,用于寻找最小的牌
if (nums[i] == 0) count++;
// 若是重复了就直接返回false
else if (nums[i] == nums[i + 1]) return false;
}
// 最大的牌减去最小的牌小于5d
return nums[4] - nums[count] < 5;
}
}

62.圆圈中最后剩下的数字

模拟转圈

直接按照题意进行转圈删除,最后一个剩下没被删除的就是答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int lastRemaining(int n, int m) {
if (n == 1) return 1;
List<Integer> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(i);
}
int k = 0;
while (n > 1) {
k = (k + m - 1) % n;
list.remove(k);
n--;
}
return list.get(0);
}
}

约瑟夫环公式

这题就算典序的约瑟夫环的问题。

约瑟夫环有一个递推公式。

F(n,m) = (f(n - 1,m) + m) % n

F(n,m)表示的是n个人报数,报到m的人会被杀掉,最终胜利者的编号,也就是这题的答案。

1
2
3
4
5
6
7
8
9
10
class Solution {
public int lastRemaining(int n, int m) {
int res = 0;
// f(2,m)是最初的状态,需要加到F(n,m)才是最终答案
for (int i = 2; i <= n; i++) {
res = (res + m) % i;
}
return res;
}
}

63. 股票的最大利润

这题是经典的动态规划题,不过这一题只交易一次。所以只需要找到一个最小的数买进,最大的数卖出就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 1) return 0;
int res = 0, min = prices[0];
for (int i = 1; i < prices.length; i++) {
// 找到一个更小的数就替换
if (prices[i] <= min) {
min = prices[i];
} else {
res = Math.max(res,prices[i] - min);
}
}
return res;
}
}

64. 求1+2+…+n

这题题目是不难的,但是题目的要求让这题变难了,不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

这里运用到了&&短路与的特性,判断了第一个子式后如果是false就不会进行判断第二个子式了。

1
2
3
4
5
6
7
class Solution {
public int sumNums(int n) {
int sum = n;
boolean flag = n > 0 && (sum += sumNums(n - 1)) > 0;
return sum;
}
}

65. 不用加减乘除做加法

不用加减乘除,那就肯定是位运算了。然后就只能看题解了。

^表示两个数无进位的求和,比如16 + 4,无进位求和就是等于10的,相当于进位没有了。

&表示两个数进位的个数,比如6 + 4 ,答案是等于1的,因为进了一位,需要在左移一位才能等于10

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int add(int a, int b) {
// 直到进位数为0,就停止循环
while(b != 0) {
int c = (a & b) << 1;
a ^= b;
b = c;
}
return a;
}
}

66. 构建乘积数组

这题主要是除了当前元素其他元素都相乘,其实就算数左边的元素的乘积与右边元素的乘积的乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int[] constructArr(int[] a) {
if (a.length <= 1) return a;
int[] res = new int[a.length];
int left = 1;
int right = 1;
for(int i = 0; i < a.length; i++) {
res[i] = left;
left *= a[i];
}
for(int i = a.length - 1; i > -1; i--) {
res[i] *= right;
right *= a[i];
}
return res;
}
}

68.1 二叉搜索树的最近公共祖先

这题主要总结节点的情况,该题的节点应该是分为三种的。

  1. p和q都在左子树
  2. p和q都在右子树
  3. p和q一个在左子树,一个在右子树(这种情况的节点就算二叉树的最近公共祖先)

了解了状态这题应该就不难了。

1
2
3
4
5
6
7
8
9
10
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (root.val > p.val && root.val > q.val)
return lowestCommonAncestor(root.left,p,q);
if (root.val < p.val && root.val < q.val)
return lowestCommonAncestor(root.right,p,q);
return root;
}
}

68.2 二叉树的最近公共祖先

这题的分析跟上面的情况一样,只是判断子树的情况不太一样。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == p || root == q || root == null) return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if (left == null) return right;
if (right == null) return left;
if (left != null && right != null) return root;
return null;
}
}