1、最大数

1.1、题目描述

给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。

注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

  • 示例 1:

    1
    2
    输入:nums = [10,2]
    输出:"210"
  • 示例 2:

    1
    2
    输入:nums = [3,30,34,5,9]
    输出:"9534330"

1.2、解题思路

使用排序的方法来解决这道题,解题思路就是分析传入数组的每一个元素,让最高位的值最大

  • 对于没有相同数字开头的输入,我们直接比较这些输入的最高位大小,然后将最高位大的数放在结果高位上即可,例如:{45,56,81,76,123}
  • 对于拥有相同数字开头的输入的字符串,我们需要比较它们评价后得到的结果大小来决定这两个元素的前后顺序,比如 {3,30,34} 中,由于 330 > 303 ,所以结果中 3 应该排在 30 前面;同时由于 3430 > 3034 ,所以结果中 34 应该排在 30 前面;又由于 343 > 334 ,所以结果中 34 应该排在 3 前面,于是我们得到结果为 {34330}

我们可以构建一个特殊的堆来完成这个操作,这个堆的顺序不再由元素数值的大小确定,而是表示这个元素在堆中的优先级,比如说,在上面的例子中,由于结果中数字的出现顺序为 34、 3、 30 ,所以 34 应该在堆中的优先级最大。

1.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public String largestNumber(int[] nums) {
// 构造一个堆,传入一个比较器
// 比较规则为,如果 x + y > y + x ,那么 x 优先级高,否则 y 优先级高
PriorityQueue<String> heap = new PriorityQueue<>((pre, next) -> (next + pre).compareTo(pre + next));
// 将 数组元素加入到堆中,然后堆顶放的元素就是优先级最高的元素
for (int num : nums) {
heap.add(String.valueOf(num));
}
String result = "";
while (heap.size() > 0) {
result += heap.poll();
}
// 判断结果是否为 0 ,如果
return result.charAt(0) == '0' ? "0" : result;
}

2、旋转数组

2.1、题目描述

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

  • 示例 1:
1
2
3
4
5
6
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

2.2、解题思路

  • 方法一

我们可以将数组右边需要调换位置的元素看为一组,而左边其他元素看为一组,以示例一为例,它旋转后的结果为 [5,6,7,1,2,3,4] ,要做到这一点,我们只需要

  1. 将左边这一组的元素看为一个整体,进行逆序,左边元素变为 [4,3,2,1]

  2. 将右边这一组的元素看为一个整体,进行逆序,右边元素变为 [7,6,5]

  3. 最后将整个数组整体进行一次逆序操作即可,变为 [5,6,7,1,2,3,4]

  • 方法二
  1. 如果左部分数组和右部分数组一样长,那么只需要将两部分元素中下标相同的元素进行交换即可

比如说在 [1,2,3,4,5,6] 中,只需要将左部分第 i 个元素和右部分第 i 个元素进行交换即可

  1. 如果左部分数组长度大于右部分数组长度,此时以右侧短的部分为主,将右侧数据与左部分数据中最左边的数据一一对应交换

比如说在 [1,2,3,4,5,6] 中,此时 k 为 2 ,现在需要将 1 和 5 交换,然后 2 与 6 交换。

进行交换后,交换过后的 5 和 6 元素不变,因为它们已经确定了自己的位置,而剩下的 [1,2,3,4] 按照上面的规则进行交换

  1. 如果右部分数组长度大于左部分数组长度,那么此时以左侧短的为主,左侧元素交换后不改变位置。

2.3、解题代码

  • 方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void rotate(int[] nums, int k) {
int length = nums.length;
// 防止 k 超出数组长度
k = k % length;
reverse(nums, 0, length - k - 1);
reverse(nums, length - k, length - 1);
reverse(nums, 0, length - 1);
}

private void reverse(int[] nums, int left, int right) {
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}

3、岛屿数量

3.1、题目描述

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成

此外,你可以假设该网格的四条边均被水包围。

其实就是在问有多少连成一片的 “1”

  • 示例:
1
2
3
4
5
6
7
输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出:3

示例中有三片连在一起的 “1” ,分别是左上角的 4 个 1 ,中间的单独一个 1 和右下角的两个 1 ,所以返回 3

3.2、解题思路

  • 感染过程
  1. 遍历二维数组中的每一个元素,如果当前遍历到的元素是 1 ,那么进入感染过程,感染过程会将这个位置的上下左右的 1 元素都变为 2

示例中,当遍历到 {0,0} 中的 1 时,它会将它上下左右的 1 元素都变为 2 元素,同时分别向它的上下左右元素进行递归。

  1. 进行递归, {0,1} 元素、{1,0} 元素也会将它的上下左右是 1 的元素都变为 2

  2. 在遍历过程中,如果遍历到一个 1 ,那么证明找到了一个感染入口,此时让 count++ 即可

3.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
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rowSize = grid.length;
int colSize = grid[0].length;
int result = 0;
for (int i = 0;i < rowSize;i++) {
for (int j = 0;j < colSize;j++) {
if (grid[i][j] == '1') {
result++;
infect(grid, i, j, rowSize, colSize);
}
}
}
return result;
}

private void infect(char[][] grid, int i, int j, int rowSize, int colSize) {
// 如果下标越界或者当前位置的元素不是 1 ,那么证明不是感染的对象,直接返回
if (i < 0 || i >= rowSize || j < 0 || j >= colSize || grid[i][j] != '1') return;
// 将感染入口的元素置为 2
grid[i][j] = '2';
// 分别向上下左右进行感染
infect(grid, i - 1, j, rowSize, colSize);
infect(grid, i + 1, j, rowSize, colSize);
infect(grid, i, j - 1, rowSize, colSize);
infect(grid, i, j + 1, rowSize, colSize);
}

4、肯尼迪数

4.1、题目描述

编写一个算法来判断一个数 n 是不是快乐数,快乐数的定义如下

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
  • 如果 可以变为 1,那么这个数就是快乐数。

如果 n 是快乐数就返回 true ;不是,则返回 false 。

  • 示例

image-20211101205845228

4.2、解题思路

  • 找出过程中重复的数字避免进入无限循环
  1. 初始化一个 Set 对象,将 n 加入到 Set
  2. 将 n 替换为它每个位置上的数字的平方和,并将其加入 Set
  3. 重复这个过程,一直到新出现的数字等于 1 时,返回 true
  4. 当新出现的数字已经存在于 Set 时,返回 false

4.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
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
// 先将 n 加入到集合中
set.add(n);
while (n != 1) {
n = bitSquareSum(n);
if (!set.add(n)) {
// 如果添加失败,证明陷入了死循环
return false;
}
}
// 退出时,代表此时 n = 1 ,此时传入的 n 是一个快乐数
return true;
}

/**
* 编写一个方法,用于返回各个位置上的数的平方和
* @param x
* @return
*/
private int bitSquareSum(int x) {
int sum = 0, cur;
while (x > 0) {
// 求当前低位的数
cur = x % 10;
// 让 sum 加上当前低位的平方和
sum += cur * cur;
// 砍去当前低位
x /= 10;
}
return sum;
}

5、寻找重复数

5.1、题目描述

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1n 之间(包括 1n),可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ,找出 这个重复的数

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

  • 示例 1:

    1
    2
    输入:nums = [1,3,4,2,2]
    输出:2
  • 示例 2:

    1
    2
    输入:nums = [3,1,3,4,2]
    输出:3

5.2、解题思路

  • 题目给的数组中,数字都在 1 - n 之间,我们可以将数组下标与其对应的值勾连成一个链表

例如在右边所给的数组 {5,3,4,6,7,4,1,8,2} 中

  1. 0 下标对应的值为 5 ,故此时得到一个链表为 0->5
  2. 5 下标对应的值为 4 ,故此时链表为 0 -> 5 -> 4
  3. 4 下标对应的值为 7 ,故此时链表为 0 -> 5 -> 4 -> 7
  4. 以此类推,得到链表为 0 -> 5 -> 4 -> 7 -> 8 -> 2 -> 4

当又得到 4 时,我们可以假设此时 2 的 next 指向了前面的 4 元素,即形成了一个环,这样,原题就给我们转换为了一个查找链表第一个入环节点的问题

5.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int findDuplicate(int[] nums) {
if (nums == null || nums.length < 2) return -1;
int slow = 0;
int fast = 0;
while (true) {
// 慢指针每次走一步
slow = nums[slow];
// 快指针每次走两步
fast = nums[nums[fast]];
if (slow == fast) break;
}
// 让快指针回到头部
fast = 0;
while (slow != fast) {
fast = nums[fast];
slow = nums[slow];
}
return slow;
}

6、丢失的数字

6.1、题目描述

给定一个包含 [0, n]n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

  • 示例 1:

    1
    2
    3
    输入:nums = [3,0,1]
    输出:2
    解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。

6.2、解题思路

  • 使用一个 Set 来存储数组中所有的值,然后遍历 [0,n] 范围的数,查找不存在于 Set 中的数即可

6.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int missingNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) set.add(num);
// 我们要查找的范围为 [0, nums.length] 这 nums.length + 1 个数
// 比如说 [3,0,1] ,这时候我们要查找的范围为 [0 - 3] ,范围为 4
int range = nums.length + 1;
for (int i = 0;i < range;i++) {
// 如果在遍历过程中发现 set 没有当前遍历的元素,那么直接返回
if (!set.contains(i)) {
return i;
}
}
return -1;
}

7、移动零

7.1、题目描述

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序

  • 示例:

    1
    2
    输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]

7.2、解题思路

使用 left 指针与 right 指针两个指针来解决这个问题,开始时,将左指针和右指针都指向 0 位置

  • 其中左指针 left 指向已经处理好的序列的下一个位置,即下一个可以被非 0 元素占据的位置
  • 右指针 right 用来遍历数组,如果遍历到非 0 元素,那么让左右指针指向的元素进行交换,同时左右指针同时右移
  • 如果遍历到 0 ,那么让右指针直接右移即可。

7.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void moveZeroes(int[] nums) {
int left = 0,right = 0;
while (right < nums.length) {
// 如果此时右指针指向的元素不为 0 ,那么需要和 left 指针指向的元素进行交换
// 然后让 left 右移,指向下一个可以被非 0 元素占据的位置
if (nums[right] != 0) {
swap(nums, left, right);
left++;
}
// 无论如何, right 都必须右移
right++;
}
}
private void swap(int[] nums, int i, int j) {
if (nums == null || i == j) return;
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

8、Morris 遍历

8.1、什么是 Morris 遍历 ?

  • 对于一般的遍历算法,我们都是利用栈来存储之后需要再次访问的节点。

  • 最差情况下,我们需要存储整个二叉树中所有的节点,所以空间复杂度为 O(n) ,而 Morris 遍历则是将空间复杂度降到 O(1) 级别。

Morris遍历用到了线索二叉树的概念,其实就是利用了叶子节点的左右空指针来存储某种遍历前驱节点或者后继节点。因此没有使用额外的空间。

8.2、算法思想

  • 创建一个变量 curcur 表示当前节点,一开始,cur 来到整棵树的根节点,即 root
  • 如果 cur 没有左子节点,那么 cur 直接向右移动(cur = cur.right)
  • 如果 cur 有左子节点,那么找到它左子树的最右节点,将这个节点记为 mostRight
  1. 如果 mostRight 的右指针为空,那么让 mostRight 指向当前节点 curmostRight.right = cur),然后让当前节点 cur 向左移(cur = cur.left
  2. 如果 mostRight 的右指针指向当前节点 cur ,为什么会出现这种情况?

这是因为我们在进行 Morris 算法的过程中会改动树的结构,这种情况下,我们将 mostRight.right 置为空(mostRight.right = null),然后将当前节点右移(cur = cur.right

  • cur 为空时,流程结束

8.3、举例说明

以下面的二叉树为例,我们称 cur 节点到达二叉树的顺序为 Morris 序

image-20211102204533069

  • 初始化 cur 节点为根节点 root,此时 Morris 序列为 {1}
  • 由于 cur 存在左子树,所以我们找到 cur 左子树的最右节点,即 mostRight 此时指向 5 的位置,将 5 的右指针指向当前节点,即让 5 的右指针指向 1 ,此时 cur 向左移,指向 2 ,此时 Morris 序列为 {1,2}

image-20211102205115546

  • 由于 cur 存在左子树,所以我们找到 cur 左子树的最右节点 mostRight,让 mostRight.right 指向 cur,同时 cur 左移来到 4 位置,此时 Morris 序列为 {1,2,4}

image-20211102205205056

  • 由于此时 cur 没有左子节点,所以 cur 直接向右移动,此时 cur 来到 2 位置,此时 Morris 序列为 {1,2,4,2}

image-20211102205433144

  • 此时 cur 节点存在左树,所以找到 mostRight 为 4 ,发现此时它的 right 指针指向了 cur ,那么我们让 mostRight 的右指针指向空(还原树结构),同时让 cur 向右移,来到 5 的位置,此时 Morris 序列为 {1,2,4,2,5}
  • 由于此时 cur 没有左子树,所以 cur 直接右移, cur 从 5 变为 1 ,此时 Morris 序列为 {1,2,4,2,5,1}
  • 由于此时 cur 存在左子树,所以找到 cur 左子树中最右的节点 5 ,由于它的右指针指向 cur ,所以将 5 的右指针直接置为空(还原树结构),同时让 cur 右移,此时 Morris 序列为 {1,2,4,2,5,1,3}
  • 此时由于 cur 存在左子树,那么找到它左子树上的最右节点 mostRight (6) ,让 mostRight 的右指针指向 cur ,然后左移,此时 Morris 序列为 {1,2,4,2,5,1,3,6}
  • cur (6)没有左子树向右移,来到 3 ,此时 Morris 序列为 {1,2,4,2,5,1,3,6,3},又因为此时 mostRight 的右指针不为空,所以还原树结构,让 cur 来到 7 ,此时 Morris 序列为 {1,2,4,2,5,1,3,6,3,7}

8.4、Morris 序的规律

  • 如果一个节点存在左树,那么在 Morris 序中一定出现两次,这是因为该节点会被它的 mostRight 的下一次向右移动遍历到

比如说 8.3 中的 1 、 2 、 3 节点均出现了两次

  • 如果一个节点不存在左树,那么在 Morris 序中一定出现一次,一个节点如果往右走,那么再也不会回头(要不往右下角走,要不往上面走)

8.5、代码实现

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
public static void morris(TreeNode root) {
if (root == null) return;
// cur 节点,用于表示二叉树当前节点,初始化为 root
TreeNode cur = root;
// 当前节点左子树的最右节点
TreeNode mostRight = null;
while (cur != null) {
//1 判断 cur 有没有左子树
mostRight = cur.left;
// 如果 mostRight 不为空,那么证明 cur 有左子树
if (mostRight != null) {
// 如果有左子树,那么需要找到当前节点左子树的最右(真实)节点
while (mostRight.right != null && mostRight.right != cur) {
// 如果 mostRight 右子树不为空且不为当前节点,那么直接右移
mostRight = mostRight.right;
}
// 退出时, mostRight 就是当前节点真实的最右节点
if (mostRight.right == null) {
// 让 mostRight 的右指针指向当前节点
mostRight.right = cur;
// cur 向左移
cur = cur.left;
continue;
} else {
// 如果 mostRight 的右指针不为空,那么证明这棵子树被动过,此时需要还原
mostRight.right = null;
}
}
// 如果没有子树,那么直接让 cur 向右移动
cur = cur.right;
}
}

8.6、Morris 遍历实现先序遍历

  • 当一棵树存在左子树时,它会被遍历到两次,先序遍历就是只在第一次遍历中打印节点,得到的顺序就是先序遍历

对于那些没有左子树的节点,那么直接输出即可,因为这种节点只会被遍历到一次,而对于那些存在左子树的节点,我们只需要在第一次遍历时打印。

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
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
// 表示当前正在遍历的节点,初始化为 root
TreeNode cur = root;
// 表示当前正在遍历的节点左子树上的最右节点,初始化为 null
TreeNode mostRight = null;
// 当 cur 为空时,循环结束
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
// 如果 mostRight 不为空,那么证明存在左子树
// 那么先找到 cur 左子树上的最右节点
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
// 如果它的右指针为空,证明第一次遍历,我们需要将 mostRight 的右指针指向当前节点,然后让 cur 左移
mostRight.right = cur;
// 第一次遍历,进行收集
result.add(cur.val);
cur = cur.left;
continue;
} else {
// 那么它的右指针不为空,证明是第二次遍历,我们需要将 mostRight 的右指针断开,然后让 cur 右移
mostRight.right = null;
}
} else {
// 如果 cur 的左子树为空,直接收集
result.add(cur.val);
}
// 对于遍历到第二次的节点,它需要右移,对于遍历一次的节点也需要右移,所以写在这里
cur = cur.right;
}
return result;
}

8.7、Morris 遍历实现中序遍历

  • 在中序遍历中,我们只需要让那些会被遍历到两次的节点(存在左子树),在第二次被遍历到时打印,而对于那些只会被遍历到一次的节点,直接打印,这样得到的序列就是中序遍历序列

当一个节点要向右移动时,进行收集 / 打印,得到的序列就是中序遍历序列。

对于一个存在左子树的节点,它会在第二次遍历时将 mostRight 置为空,然后让 cur 向右移动,此时就是第二次遍历,所以打印;

对于一个不存在左子树的节点,在遍历到这类节点后会直接右移,所以直接打印即可;

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
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
TreeNode cur = root;
TreeNode mostRight = null;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
}
}
// 右移时,进行收集
result.add(cur.val);
cur = cur.right;
}
return result;
}

8.8、Morris 遍历实现后序遍历

  • 对于那些拥有左子树的节点,我们在第二次访问该节点逆序打印该节点左树的右边界
  • 最后单独逆序打印整个树的右边界

何为右边界?下图中划线的节点就是这棵树的右边界

image-20211103201057569

  1. 其中穿过 4 的线为节点 2 的右边界
  2. 穿过 2 5 节点的线为 1 的右边界,穿过 6 的线为 3 的右边界,穿过 1 3 7 的线为整棵树的右边界
  3. 其中,逆序表示打印顺序从右下角 –> 左上角

以下面的树为例,它的 Morris 序列为: {1,2,4,2,5,1,3,6,3,7}

image-20211103200757961

  1. 第二次遍历到 2 时,逆序打印它的右边界,只有 4 ,故后序序列此时为 {4}
  2. 第二次遍历到 1 时,逆序打印 1 的右边界,此时后序序列变为 {4,5,2}
  3. 第二次遍历到 3 时,逆序打印 3 的右边界,此时后序序列变为 {4,5,2,6}
  4. 最后逆序打印整个树的右边界,此时后序序列变为 {4,5,2,6,7,3,1},我们得到了最终解

如何逆序打印整棵树的右边界,我们忽略整棵树右边界上 TreeNode 节点的左指针,将其想象为一条单链表,然后进行单链表反转即可。

  1. 方法一,反转单链表

这个方法是为了逆序输出某棵树的右边界而编写的,将该右边界看为一个单链表

1
2
3
4
5
6
7
public TreeNode reverseNode(TreeNode root) {
if (root == null || root.right == null) return root;
TreeNode reverse = reverseNode(root.right);
root.right.right = root;
root.right = null;
return reverse;
}
  1. 方法二,收集右边界的逆序节点,然后将该节点再次逆序回来,恢复结构
1
2
3
4
5
6
7
8
9
public void collectRightEdge(TreeNode root, List<Integer> result) {
TreeNode tail = reverseNode(root);
TreeNode cur = tail;
while (cur != null) {
result.add(cur.val);
cur = cur.right;
}
reverseNode(tail);
}
  1. 方法三,使用 Morris 序得到后序遍历结果
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
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
TreeNode cur = root;
TreeNode mostRight = null;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
collectRightEdge(cur.left, result);
}
}
cur = cur.right;
}
// 在最后,进行一次收集。收集整棵树的右边界
collectRightEdge(root, result);
return result;
}

9、二叉树的最小高度

9.1、题目描述

给定一棵树,请找出距离它的根节点到它任一叶子节点的最短距离。

9.2、解题思路

  • 递归解
  1. 如果 root 为空,那么返回 0

  2. 如果 root 的左右子树均为空,那么返回 1

  3. 如果 root 的左子树为空,那么我们设它的右子树的最小高度为 minRight ,返回 minRight + 1

  4. 如果 root 的右子树为空,那么我们设它的左子树的最小高度为 minLeft ,返回 minLeft + 1

  5. 如果 root 的左右子树均不为空,那么结果为 Math.min(minRight,minLeft) + 1

9.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public int minLength(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
int minLeft = Integer.MIN_VALUE;
if (root.left != null) {
minLeft = minLength(root.left);
}
int minRight = Integer.MIN_VALUE;
if (root.right != null) {
minRight = minLength(root.right);
}
return 1 + Math.min(minLeft, minRight);
}

10、判断一棵树是不是合法的 BST

10.1、题目描述

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树,有效 二叉搜索树定义如下:

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

10.2、解题思路

之前使用过递归来完成过这道题,这次使用 Morris 遍历完成这道题目

  • 对于一棵二叉树来说,如果它的中序序列是第一个递增序列,那么证明它是一棵合法的 BST
  • 在一个节点即将向右移时,进行比对,使用一个值 pre 来表示中序序列中的前一个值
  1. 如果 pre 的值大于当前节点的值,那么直接返回 false
  2. 如果整个遍历中都没有出现 1 中情况,那么证明这棵树是 BST

10.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
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
TreeNode cur = root;
TreeNode mostRight = null;
Integer pre = null;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
}
}
// 在这里进行对比,如果 pre 为空,那么直接将当前节点的值赋给 pre
// 如果不为空,那么判断 pre 的值与当前值的关系,如果 pre < cur.val ,那么继续循环
// 否则直接返回 false
if (pre != null && pre >= cur.val) return false;
pre = cur.val;
cur = cur.right;
}
return true;
}

11、奇偶链表

11.1、题目描述

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

  • 示例
1
2
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

11.2、解题思路

  • 将输入链表分流为两个链表,第一个链表存放序号为奇数的节点,第二个链表存放序号为偶数的节点,最后将存放着偶数节点的链表挂在存放着奇数节点的链表的尾部即可。
  1. 定义一个奇数头和一个偶数头,然后遍历输入链表
  2. 如果当前遍历元素的序号为奇数,那么将该元素放在奇数链表中,否则挂在偶数链表中
  3. 最后将偶数链表挂在奇数链表最后

如何确定当前遍历元素的序号?使用一个全局变量 count 判断即可。

  • 以下面链表来说明这道题

image-20211104210203651

  1. 初始化奇数链表的头 oddHead 指向第一个元素

  2. 初始化偶数链表的头 evenHead 指向第二个元素

  3. oddHead.next = oddHead.next.next ,即将第一个元素与第三个元素连接起来,同时让 oddHead= oddHead.next 让奇数的下一个节点向后移动,偶数链表同理

  4. 最后将两个链表合并即可

11.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) return head;

// 初始化奇 / 偶数链表头
ListNode odd = head;
ListNode even = head.next;
// 用一个变量来表示偶数链表的头,最后一步只需要让奇数链表的尾部的next指向这个节点即可
ListNode evenHead = head.next;
// 如果当前偶数节点为空,那么跳出循环
// 如果当前偶数节点的 next 为空,那么也可以跳出循环,因为此时已经不需要再进行连接了
while (even != null && even.next != null) {
odd.next = odd.next.next;
odd = odd.next;
even.next = even.next.next;
even = even.next;
}
odd.next = evenHead;
return head;
}

12、递增的三元子序列

12.1、题目描述

  • 给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。

  • 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。

  • 示例 1

1
2
3
输入:nums = [1,2,3,4,5]
输出:true
解释:任何 i < j < k 的三元组都满足题意
  • 示例 2
1
2
3
输入:nums = [5,4,3,2,1]
输出:false
解释:不存在满足题意的三元组

12.2、解题思路

  • 使用一个变量 min 表示当前数组内出现的最小值,使用一个变量 second 表示当前数组内出现的次小值,遍历数组过程中维护这两个值,当发现有元素比 second 大时就可以判断存在递增子序列
  • min 一定要在 second 之前
  • 举例说明

以数组 [5,4,1,3,2] 举例说明

  1. 初始化 minsecond 均为 Integer.MAX_VALUE
  2. 遍历数组,当遍历到元素 5 时,由于此时 5 < Integer.MAX_VALUE ,将 min 更新为 Integer.MAX_VALUE
  3. 遍历到元素 4 时,将 min 更新为 4 ;遍历到元素 1 时,将 min 更新为 1 ;
  4. 遍历到元素 3 时,此时由于 min 的值小于 3 且 3 < second 当前值,所以将 3 更新为次小值,即 second = 3
  5. 当遍历到 2 时,由于此时 min < 2 < second ,所以直接跳过,遍历结束,返回 false

如果以数组 [5,4,1,3,2,6] 为例,那么在遍历到 6 时,由于此时 6 大于 second ,所以返回 true

12.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length < 3) return false;
int min = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int num : nums) {
if (num <= min) {
min = num;
} else if (num <= second) {
second = num;
} else {
// 如果走到这里,就说明此时有一个值大于 second ,找到了递增三元子序列
return true;
}
}
return false;
}

13、二叉搜索树的公共祖先

13.1、题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

13.2、解题思路

  • 与之前做过的二叉树最近公共祖先相同,我们判断要寻找的两个节点是否分布在 root 的异侧,如果是,返回 root ,否则就需要进行递归查找。
  • 题目给的是一棵二叉搜索树,于是当两个节点不是分布在 root 异侧时,我们只需要向那两个节点所在的一边进行递归即可。
  • 如何判断两个节点是否在异侧?

我们可以通过 (root.val - p.val) * (root.val - q.val) 的值来判断,如果

  1. 这个值大于 0 ,那么证明 pq 在同一侧,这是因为此时 (root.val - p.val)(root.val - q.val) 的值同号
  2. 这个值等于 0,那么证明 pq 中有一个节点为 root ,此时直接返回 root 即可
  3. 这个值小于 0,那么证明 pq 异侧
  • pq 处于一侧时,我们需要判断当前这两个节点在哪一侧,然后再对那一侧进行递归

13.3、解题代码

1
2
3
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return ((root.val - p.val) * (root.val - q.val) <= 0) ? root : lowestCommonAncestor((root.val - p.val < 0) ? root.right : root.left, p, q);
}

14、盛最多水的容器

14.1、题目描述

给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

  • 示例 1:

img

1
2
3
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

14.2、解题思路

  • 使用双指针解决这道题
  1. 初始化左指针 left 指向 0 ,右指针 right 指向数组的最后一个元素
  2. 在双指针进行移动的过程中,容器能装的水的值为 (right - left) * min(arr[left], arr[right])
  3. 如果 arr[left] 小于 arr[right] ,则我们需要让 left 向中间移动;反之则需要移动 right
  • 树状数组

14.3、解题代码

  • 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxArea(int[] height) {
if (height == null || height.length == 0) return 0;
// 初始化左右指针
int left = 0;
int right = height.length - 1;
int maxWater = 0;
while (left < right) {
maxWater = Math.max(maxWater, Math.min(height[left], height[right]) * (right - left));
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}

15、打家劫舍

15.1、题目描述

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警报装置的情况下,一夜之内能够偷窃到的最高金额

  • 示例 1:

    1
    2
    3
    4
    输入:[1,2,3,1]
    输出:4
    解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
    偷窃到的最高金额 = 1 + 3 = 4 。
  • 示例 2:

    1
    2
    3
    4
    输入:[2,7,9,3,1]
    输出:12
    解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
    偷窃到的最高金额 = 2 + 9 + 1 = 12 。

15.2、解题思路

  • 使用动态规划来解决这道题

在解决这道题时,我们根据从左到右的顺序偷东西,这样的话,我们在考虑是否偷第 n 家时就只需要考虑第 n - i 家的情况就可以了,因为第 n + 1 家还没光顾。

  • 对于每间房子,我们只有两个选择,即偷与不偷,如果我们选择偷第 n 间房子,那么第 n - 1 间房子只能选择不偷
  • 使用一个二维数组来表示状态
1
2
f[0][i]:对前 i 个房子进行偷窃,在第 i 个房子不偷的情况下,所能获得的最大收益
f[1][i]:对前 i 个房子进行偷窃,在第 i 个房子偷窃的情况下,所能获得的最大收益

我们要获得的答案其实就是 max{f[0][n - 1]f[1][n - 1]}

  • 转移方程为
1
2
f[1][i] = f[0][i - 1] + arr[i]:如果偷第 i 间房子,那么第 i - 1 间房子只能不偷,同时需要加上在第 i 间房子中偷得的钱
f[0][i] = max{f[0][i - 1],f[1][i - 1]}
  • 由于第 i 间房子的状态只与第 i - 1 个房子的状态有关,所以我们使用滚动数组进行优化

15.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int rob(int[] nums) {
//1 prev[0] 和 prev[1] 表示上一个房子不偷和偷的状态
int[] prev = new int[2];
//2 curr[0] 和 curr[1] 表示当前房子不偷和偷的状态
int[] curr = new int[2];
// 如果下标为 0 的房子不偷,那么得到的状态为 0
prev[0] = 0;
// 如果偷,那么所获得的总收益为 nums[0]
prev[1] = nums[0];
for (int i = 1;i < nums.length;i++) {
// 如果当前房子不偷,那么当前的状态就可以由 prev[0] 和 prev[1] 得到
curr[0] = Math.max(prev[0], prev[1]);
// 如果偷,那么当前的值等于前一个房子不偷得到的收益 + 当前房子可以获取的钱财
curr[1] = prev[0] + nums[i];
// 进行滚动,这一次的状态是下一次状态的上一次
prev[0] = curr[0];
prev[1] = curr[1];
}
return Math.max(prev[0], prev[1]);
}

16、二叉树结构数目

16.1、题目描述

给定一个正整数 n ,代表二叉树的节点个数。返回能形成多少种不同的二叉树结构

16.2、解题思路

  • 当 n == 0 时,此时只有一种结构,即空树
  • 当 n == 1 时,只有一种树结构;当 n == 2 时,此时有两种树结构
  • 当有 n 个节点时,此时我们分情况进行讨论,我们记一棵有 n 个节点的二叉树有 F(n) 种结构
  1. 如果此时根节点的左子树为空,除 root 节点以外的所有节点都分布在右子树上,那么这种情况下有 F(n - 1) 种二叉树结构
  2. 如果此时根节点的左子树只有一个节点,那么除 root 节点和左子树节点以外的所有节点都会分布在右子树上,这种情况下有 1 * F(n - 2) 种结构,其中 1 为左子树的情况
  3. 同理,如果根节点的左子树有 a 个节点,而右子树有 n - a - 1 个节点,那么这种情况下将会有 F(a) * F(n - a - 1) 种结构

将上面所有的情况累加起来,就是答案

16.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
public int numTrees(int n) {
if (n == 0) return 1;
if (n == 1 || n == 2) return n;
int res = 0;
for (int leftNodeNum = 0;leftNodeNum <= n - 1;leftNodeNum++) {
int leftAns = numTrees(leftNodeNum);
int rightAns = numTrees(n - leftNodeNum - 1);
res += leftAns * rightAns;
}
return res;
}

17、Fizz Buzz

17.1、题目描述

给你一个整数 n ,找出从 1n 各个整数的 Fizz Buzz 表示,并用字符串数组 answer下标从 1 开始)返回结果,其中:

  • answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
  • answer[i] == "Fizz" 如果 i 是 3 的倍数。
  • answer[i] == "Buzz" 如果 i 是 5 的倍数。
  • answer[i] == i 如果上述条件全不满足。
  1. 示例 1:

    1
    2
    输入:n = 3
    输出:["1","2","Fizz"]
  2. 示例 2:

    1
    2
    输入:n = 5
    输出:["1","2","Fizz","4","Buzz"]

17.2、解题思路

  • 如果 i 是 3 的倍数,那么直接往列表中添加一个 Fizz
  • 如果 i 是 5 的倍数,那么直接往列表中添加一个 Buzz
  • 如果是 15 的倍数,那么直接添加 FizzBuzz ,否则添加 i

17.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<String> fizzBuzz(int n) {
List<String> res = new ArrayList<>();
for (int i = 1;i <= n;i++) {
if (i % 15 == 0) {
res.add("FizzBuzz");
} else if (i % 3 == 0) {
res.add("Fizz");
} else if (i % 5 == 0) {
res.add("Buzz");
} else {
res.add(String.valueOf(i));
}
}
return res;
}

18、下一个排列

18.1、题目描述

实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列(即,组合出下一个更大的整数)。

如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)

必须 原地 修改,只允许使用额外常数空间。

18.2、解题思路

  • 从尾到头,找到一个严格降序的数对,即存在两个相邻元素,满足 arr[i] < arr[i + 1]

如果找不到这样的一个数对,那么证明整个数组组成的数呈现一个递减的趋势,此时这个串就是一个最大的串,我们需要将数字重新进行升序排序(旋转数组)

  • 如果能够找到这样的一个数对,那么我们从尾到头,找到第一个下标 j ,满足 i < jarr[i] < arr[j]

这样的 j 一定是存在的,因为如果这样的数对可以找到,那么 i + 1 位置的元素满足这个条件

  • 交换 arr[i]arr[j] ,然后将 arr[i + 1] 到末尾的这段后缀整个翻转过来

将「大数」换到前面后,需要将「大数」后面的所有数重置为升序升序排列就是最小的排列

123465 为例:首先按照上一步,交换 5 和 4,得到 123564然后需要将 5 之后的数重置为升序,得到 123546。显然 123546 比 123564 更小,123546 就是 123465 的下一个排列

18.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
public void nextPermutation(int[] nums) {
int size = nums.length;
// 初始化 i 下标为 size - 2 ,即将 i 放到倒数第二个元素上
int i = size - 2;
// 从尾到头,寻找一个数对,这个数对满足 nums[i] < nums[i + 1]
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// 循环结束时,我们需要判断是否找到了一个这样的数对
if (i == -1) {
// 如果此时 i 小于 0 ,那么证明数组中不存在这样的一个数对
// 此时直接翻转这个数组即可
reverseNums(nums, 0, size - 1);
return;
}
// 否则证明存在这样一个数对,这里使用一个下标 j 从尾到头寻找一个数
// 这个数满足 i < j 且 arr[i] < arr[j]
int j = size - 1;
while (nums[j] <= nums[i]) {
j--;
}
// 交换 nums[j] 和 nums[i]
swap(nums, i, j);
// 同时翻转 i + 1 后的所有元素
reverseNums(nums, i + 1, size - 1);
}

private void swap(int[] nums, int i, int j) {
if (i == j) return;
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

public void reverseNums(int[] nums, int begin, int end) {
int left = begin;
int right = end;
int temp = 0;
while (left < right) {
temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}

19、打乱数组

19.1、题目描述

给你一个整数数组 nums ,设计算法来打乱一个没有重复元素的数组。

  • Solution(int[] nums) 使用整数数组 nums 初始化对象
  • int[] reset() 重设数组到它的初始状态并返回
  • int[] shuffle() 返回数组随机打乱后的结果

19.2、解题思路

  • 使用随机数
  1. 对于 Math.random() 函数,这个函数会生成一个范围在 [0,1) 上的小数
  2. 如果我们记上面函数返回的结果为 random ,那么我们让 random 乘上一个正整数,这个时候我们就可以得到一个处于 [0,k) 的一个随机小数,我们再将得到的小数转换为 int ,同时让正整数变为 k + 1 ,这样我们最终可以得到一个处于 [0,k] 的随机整数
  3. 我们就得到了一个新函数 f(k),这个函数可以随机返回 [0,k - 1] 范围内的一个整数

如何打乱这个数组?

  1. 调用上面定义的函数 f(k) ,生成一个范围在 [0, k - 1] 间的随机数 i,然后在原有数组中,将数组下标为 i 的元素与最后一个元素交换位置

  2. 调用上面定义的函数 f(k - 1),生成一个范围在 [0, k - 2] 间的随机数 j ,然后在原有数组中,将数组下标为 j 的元素与倒数第二个元素交换位置

  3. 如此往复,直到范围缩小至 0 为止

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

private int[] origin;
private int[] shuffle;
private int size;
public Solution(int[] nums) {
origin = nums;
size = nums.length;
shuffle = new int[size];
for (int i = 0;i < size;i++) {
shuffle[i] = origin[i];
}
}

/**
* 重置数组的方法,直接返回 origin 数组即可
* @return
*/
public int[] reset() {
return origin;
}

public int[] shuffle() {
for (int i = size - 1;i >= 0;i--) {
// 生成一个随机下标
int randomIndex = (int)(Math.random() * (i + 1));
// 将 randomIndex 下标指向的元素与 i 下标的元素进行交换
int temp = shuffle[i];
shuffle[i] = shuffle[randomIndex];
shuffle[randomIndex] = temp;
}
return shuffle;
}
}

20、字符串中的第一个唯一字符

20.1、题目描述

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

  • 示例:

    1
    2
    3
    4
    5
    s = "leetcode"
    返回 0

    s = "loveleetcode"
    返回 2

20.2、解题思路

  • 使用一个长度为 256 数组(ASCII码)来代替哈希表

  • 遍历一遍字符串,将每个字符对应的 ASCII 码和出现的次数记录进表

  • 遍历数组,将第一个值为一的下标返回

20.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
public int firstUniqChar(String s) {
char[] strArray = s.toCharArray();
int[] count = new int[256];
for (int i = 0;i < strArray.length;i++) {
count[strArray[i] - 'a']++;
}
for (int i = 0;i < strArray.length;i++) {
if (count[strArray[i] - 'a'] == 1) return i;
}
return -1;
}