1、反转链表

1、题目描述

给定单链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。

2、解题思路

  • 由于递归反转链表的空间复杂度为 O(n),故本题使用迭代的方式来完成反转链表
  • 在遍历链表时,将当前节点的 next 指针指向前一个节点,由于单链表中的节点无法得知前一个节点,所以我们需要使用一个 prev 变量存储当前节点的前一个结点,同时,由于我们需要将当前节点的 next 指向前一个节点,那么为了防止当前节点后续节点丢失,所以我们需要用一个变量来保存当前节点的下一个节点。

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
// prev 表示当前遍历节点的前一个节点,初始化为 null ,因为 head 的前一个节点为 null,而 cur 表示当前正在遍历的节点
ListNode prev = null, cur = head;
while (cur != null) {
// 使用一个临时变量保存当前节点的下一个节点
ListNode next = cur.next;
// 让当前节点的next指向前一个节点
cur.next = prev;
// 让 prev 移动到当前节点的位置
prev = cur;
// 让 cur 指向链表的下一个位置,继续遍历
cur = next;
}
// 最后返回 prev ,因为退出循环时 cur 为空
return prev;
}

2、K 个一组反转链表

1、题目描述

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表,k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

  • 示例一

image.png

1
2
输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]
  • 示例二

image.png

1
2
输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

2、解题思路

  • 先反转以 head 为开头的前 k 个元素
  • 然后以第 k + 1 个元素作为 head ,继续递归调用 reverseGroup 函数
  • 将上述结果连接起来
  • 如果剩下的元素不足 k 个,那么就保持不变

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 ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null) return head;
// 我们反转区间 [begin, end) 的节点
ListNode begin = head, end = head;
// 如果节点不足 k 个,那么就不需要反转
for (int i = 0;i < k;i++) {
if (end == null) return head;
end = end.next;
}
// 反转前 k 个元素,即 [begin, end)
// 反转后,得到的链表以 newHead 为头,以 begin 为尾
ListNode newHead = reverseInRange(begin, end);
// 所以让 尾部节点的 next 指向后续链表
// 递归反转后将后续链表连接起来
begin.next = reverseKGroup(end, k);
return newHead;
}

/**
* 在范围内反转链表
*/
private ListNode reverseInRange(ListNode begin, ListNode end) {
if (begin == end || begin.next == end) return begin;
ListNode prev = null, cur = begin;
while (cur != end) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}

3、两两交换链表中的节点

1、题目描述

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

  • 示例一

image.png

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

2、解题思路

  • 在这道题中,由于我们需要将相邻节点两两交换,那么最终得到的链表的头节点将会与题目所给的头节点不同,对于这种头节点会发生改变的问题,我们可以创建一个虚拟头节点,即 ListNode virtual = head.next
  • 创建一个 ListNode 类型的变量 now ,我们记 nownow 之前的链表为已经翻转完毕的链表
  • 创建一个 ListNode 类型的变量 left ,它表示 now 的下一个节点,同时创建一个 ListNode 类型的变量 right ,它表示 now 的下下个节点

image.png

  • 接下来我们进行节点的交换,让 now.next = right ,然后 让 left.next = right.next ,最后让 right.next = left

image.png

  • 这样做完之后,我们重新按照指针编排链表,就可以看到链表已经变为了 x -> 2 -> 1 -> 3 -> 4 ,然后我们更新 now 指针,将 now 移动到 left 的位置,然后重复上面的步骤即可。
  • 最后返回 virtualHead.next 即可。

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
public ListNode swapPairs(ListNode head) {
// base case
if (head == null || head.next == null) return head;
// 创建一个虚拟头节点,让它的 next 域指向 head
ListNode virtualHead = new ListNode(Integer.MAX_VALUE);
virtualHead.next = head;
// 其中 left 表示 now 的下一个节点,而 right 表示 now 下下个节点,这里不再这里赋值,因为可能会报空指针
ListNode now = virtualHead, left = null, right = null;
while (now.next != null && now.next.next != null) {
left = now.next;
right = now.next.next;
// 进行交换
//1 让 now 的 next 指向 right
now.next = right;
//2 让 left 的 next 指向 right 的下一个节点,因为最后的关系是 now -> right -> left -> xxx
left.next = right.next;
//3 让 right 的 next 指向 left
right.next = left;
//4 最后让 now 指向 left
now = left;
}
// 最后返回虚拟头节点的下一个节点
return virtualHead.next;
}

4、合并二叉树

1、题目描述

给你两棵二叉树: root1 和 root2 。

想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

  • 示例一

image.png

1
2
输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出:[3,4,5,5,4,null,7]
  • 示例二
1
2
输入:root1 = [1], root2 = [1,2]
输出:[2,2]

2、解题思路

  • 递归 + 前序遍历来解决这个问题,其实这道题使用什么顺序的递归都没有问题
  • 确定终止条件

当传入的树有一棵为空时,就应该结束递归

  1. 如果 root1 为空,那么合并的结果就是 root2
  2. 如果 root2 为空,那么合并的结果就是 root1
  • 让 root2 的 val 合并到 root1 的 val 中
  • 最后分别递归左右子树,让 root1 的左子树、右子树与 root2 的左子树、右子树合并

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// 如果 root1 为空,那么当前两棵树的合并结果为 root2
if (root1 == null) return root2;
// 同理
if (root2 == null) return root1;
// 执行本层的合并逻辑,这里我们以 root1 为主
root1.val += root2.val;
// 让 root1 的左子树为两棵树左子树的合并结果
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
// 返回 root1 ,它是合并结果
return root1;
}

5、最长回文子串

1、题目描述

给你一个字符串 s,找到 s 中最长的回文子串。

  • 示例一
1
2
3
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
  • 示例二
1
2
输入:s = "cbbd"
输出:"bb"

2、解题思路

  • 使用动态规划解题
  1. 明确 dp 数组的含义

我们需要创建一个二维的 boolean 数组,它的长度和宽度均为 s.length() ,其中 dp[i][j] 表示子串 s[i, j] 是否为回文串

  1. 初始化 dp 数组

字符串中任意一个字符都可以看为一个回文字符串,即 dp[i][i] = true

  1. 状态转移方程

对于 dp[i][j] ,当 s.charAt(i) == s.charAt(j) 时,有 dp[i][j] = dp[i + 1][j - 1]

s.charAt(i) != s.charAt(j) 时,有 dp[i][j] = false

  1. 我们需要使用一个变量来保存最长回文子串

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
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return "";
int len = s.length();
if (len < 2) return s;
boolean[][] dp = new boolean[len][len];
// 初始化 dp 数组
for (int i = 0;i < len;i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
int maxLength = 1;
String result = s.substring(0, 1);
for (int i = len - 1;i >= 0;i--) {
for (int j = i + 1;j < len;j++) {
if (charArray[i] == charArray[j]) {
if (j == i + 1) {
// 如果 j == i + 1 且 i , j 指针指向的字符相等,那么直接可以将 dp[i][j] 置为 true
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && j - i + 1 > maxLength) {
maxLength = j - i + 1;
result = s.substring(i, j + 1);
}
}
}
return result;
}

6、求最大公共前缀

1、题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""

  • 示例一
1
2
输入:strs = ["flower","flow","flight"]
输出:"fl"
  • 示例二
1
2
3
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。

2、解题思路

  • 我们以字符串数组中的第一个字符串为准,使用一个全局变量保存最长公共前缀长度的值,然后循环遍历字符串数组,然后获取第一个字符串与后续字符串的公共前缀长度,然后更新全局变量的值。

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
if (strs.length == 1) return strs[0];
char[] firstCharArray = strs[0].toCharArray();
int longestCommonPrefixLength = Integer.MAX_VALUE;
for (int i = 1;i < strs.length;i++) {
char[] tempArray = strs[i].toCharArray();
int index = 0;
while (index < firstCharArray.length && index < tempArray.length) {
if (firstCharArray[index] != tempArray[index]) {
break;
}
index++;
}
longestCommonPrefixLength = Math.min(longestCommonPrefixLength, index);
if (longestCommonPrefixLength == 0) {
return "";
}
}
return strs[0].substring(0, longestCommonPrefixLength);
}

7、链表排序

1、题目描述

给定链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表

2、解题思路

  • 使用归并排序解决这道题

按照归并排序的思路进行操作,使用快慢指针来寻找链表的中点

  • 使用小顶堆来解决这个问题

使用一个小顶堆,将链表节点依次加入到小顶堆中,然后再将节点逐个从堆中弹出。

3、解题代码

  • 使用小顶堆来解决这个问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
while (head != null) {
ListNode next = head.next;
head.next = null;
minHeap.add(head);
head = next;
}
ListNode result = new ListNode();
ListNode cur = result;
while (minHeap.size() > 0) {
cur.next = minHeap.poll();
cur = cur.next;
}
return result.next;
}
  • 使用归并排序
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
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
// 寻找中点
ListNode fast = head, slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 退出时,慢指针指向中点位置
ListNode temp = slow.next;
// 将链表分为两部分,即[head, mid(slow)] 和 [temp, ...]
slow.next = null;
// 向下递归,分治
ListNode left = sortList(head);
ListNode right = sortList(temp);
// 向上合并
// 虚拟头节点
ListNode virtualHead = new ListNode();
ListNode cur = virtualHead;
while (left != null && right != null) {
if (left.val < right.val) {
cur.next = left;
left = left.next;
} else {
cur.next = right;
right = right.next;
}
cur = cur.next;
}
// 退出时一定有一个指针为空(left、right),同时另外一截不为空的链表一定也是有序的,所以直接接在后面就可以了
cur.next = (left == null) ? right : left;
return virtualHead.next;
}

8、验证回文字符串 II

1、题目描述

给定一个非空字符串 s最多删除一个字符。判断是否能成为回文字符串。

  • 示例一
1
2
输入: s = "aba"
输出: true
  • 示例二
1
2
输入: s = "abc"
输出: false

2、解题思路

  • 使用双指针解决这道题

一个指针从头开始,一个指针从尾巴开始,当两个指针指向的字符不等时,此时我们再给它一次机会

  • 创建一个方法,这个方法用于判断字符串下标范围处于 [left, right] 的那部分子串是否为严格的回文串
  • s.charAt(left) == s.charAt(right) 时,此时让左指针右移动,右指针左移
  • s.charAt(left) != s.charAt(right) 时,此时我们再给它一次机会,判断 s[left + 1,right] 或者 s[left, right - 1] 中是否有一个为回文串,如果有,那么返回 true ,否则返回 false

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 boolean validPalindrome(String s) {
if (s == null || s.length() <= 1) return true;
int left = 0, right = s.length() - 1;
while (left < right) {
// 如果两个指针指向的字符相等,那么让左指针右移,右指针左移
if (s.charAt(left) == s.charAt(right)) {
left++;
right--;
} else {
// 如果不等,那么再给它一次机会。
return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
}
}
return true;
}
public boolean isPalindrome(String s, int left, int right) {
if (s == null || s.length() <= 1 || left >= right) return true;
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
left++;
right--;
} else {
return false;
}
}
return true;
}

9、回文链表

1、题目描述

给定一个链表的头节点 head 请判断其是否为回文链表。

如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的。

  • 示例一
1
2
输入: head = [1,2,3,3,2,1]
输出: true
  • 示例二
1
2
输入: head = [1,2]
输出: false

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
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// 找到链表中点,使用快慢指针
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 退出时,slow的下一个节点就是后半部分链表的头节点。
ListNode temp = slow.next;
slow.next = null;
temp = reverseList(temp);
slow.next = temp;
// 进行比较
fast = head;
slow = temp;
while (slow != null) {
if (slow.val != fast.val) {
return false;
}
slow = slow.next;
fast = fast.next;
}
return true;
}

// 用于反转链表的方法
private ListNode reverseList(ListNode node) {
if (node == null || node.next == null) return node;
ListNode prev = null, cur = node;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}

10、有效的山脉数组

1、题目描述

给定一个整数数组 arr,如果它是有效的山脉数组就返回 true,否则返回 false

让我们回顾一下,如果 arr 满足下述条件,那么它是一个山脉数组:

  • arr.length >= 3
  • 0 < i < arr.length - 1 条件下,存在 i 使得:
    • arr[0] < arr[1] < ... arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

2、解题思路

  • 使用双指针,一个从左往右找最高点,一个从右往左找最高点,然后判断两个指针找到的最高点是不是同一个,如果是,返回 true,否则返回 false

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean validMountainArray(int[] arr) {
if (arr == null || arr.length < 3) return false;
int left = 0, right = arr.length - 1;
// 当满足 arr[left] 小于 arr[left + 1] 时,不是证明此时的 left 不是最高峰的下标,所以 left++
while (left <= arr.length - 2 && arr[left] < arr[left + 1]) {
left++;
}
// 同理,所以 right--;
while (right >= 1 && arr[right] < arr[right - 1]) {
right--;
}
// 这里需要判断 left 和 right 是否越界,比如说 [0,1,2,3,4,5,6,7,8,9] ,这种情况下,它不是山脉数组,但 left == right == len - 1
return left > 0 && right < arr.length - 1 && left == right;
}

11、数组中的最长山脉

1、题目描述

把符合下列属性的数组 arr 称为 山脉数组

  • arr.length >= 3
  • 0 < i < arr.length - 1 条件下,存在 i 使得:
    • arr[0] < arr[1] < ... arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给出一个整数数组 arr,返回最长山脉子数组的长度。如果不存在山脉子数组,返回 0

  1. 示例一
1
2
3
输入:arr = [2,1,4,7,3,2,5]
输出:5
解释:最长的山脉子数组是 [1,4,7,3,2],长度为 5
  1. 示例二
1
2
3
输入:arr = [2,2,2]
输出:0
解释:不存在山脉子数组。

2、解题思路

  • 使用动态规划求解这道题,这道题其实与接雨水差不多
  • 我们创建两个数组,即从左到右依次升高的数组,称为 increase ,其中 increase[i] 表示数组元素 arr[i] 左边小于它且连续的元素个数,比如说 [1,2,3,4,3,2,1]increase[3] 的值为 3 ,它表示数组元素 4 左边有三个递增且连续小于它的数
  • 同理,我们创建一个从左往右依次递减的数组 decrease ,其中 decrease[i] 表示数组元素 arr[i] 右边小于它且连续的元素个数。
  • 遍历数组中的元素,我们遍历的范围为 [1, len - 2] ,因为和接雨水差不多,第一个和最后一个元素不可能作为山峰的顶点存在。

increase[i]decrease[i] 均不为 0 时,我们才计算 arr[i] 作为顶点的山脉长度,以 arr[i] 作为顶点的山脉长度 lendecrease[i] + increase[i] + 1 ,其中 1 表示 arr[i] 这个元素的固有长度。

当这两个值有一个为空时,直接值为 0 即可。

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
public int longestMountain(int[] arr) {
if (arr == null || arr.length < 3) return 0;
int len = arr.length;
// 创建一个数组,其中第一个为从左往右依次递增的数组
int[] increase = new int[len];
// 第二个数组为从左往右依次递减的数组
int[] decrease = new int[len];
// 初始化 increase 数组和 decrease 数组
for (int i = 1;i < len;i++) {
// 如果当前元素的上一个元素小于当前元素,那么可以将当前元素放到以 arr[i - 1] 为结尾的递增序列中
if (arr[i - 1] < arr[i]) {
increase[i] = increase[i - 1] + 1;
}
}
for (int i = len - 2;i >= 0;i--) {
if (arr[i] > arr[i + 1]) {
decrease[i] = decrease[i + 1] + 1;
}
}
int max = 0;
// 遍历数组元素,寻找最长山脉
for (int i = 1;i <= len - 2;i++) {
int curSize = 0;
// 只有当 increase[i] 和 decrease[i] 均不为空时,山脉长度才有效
if (increase[i] != 0 && decrease[i] != 0) {
curSize = decrease[i] + increase[i] + 1;
}
max = Math.max(curSize, max);
}
return max;
}

12、买卖股票的最佳时机 III

1、题目描述

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

  • 示例一
1
2
3
4
输入:prices = [3,3,5,0,0,3,1,4]
输出:6
解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3
  随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3
  • 示例二
1
2
3
4
5
输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
  注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。  
  因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

2、解题思路

  • 确定 dp 数组的含义

dp[i][j] 中 i 表示第 i 天,j 为 [0 - 4] 五个状态,dp[i][j] 表示第 i 天状态 j 所剩的最大现金。

  1. 0 没有操作
  2. 第一次买入
  3. 第一次卖出
  4. 第二次买入
  5. 第二次卖出
  • 确定递推公式
  1. 达到 dp[i][1] 状态,有两个具体操作

操作一:第 i 天第一次买入股票,那么 dp[i][1] = dp[i - 1][0] - prices[i]

操作二:第 i 天没有操作,在第 i - 1 天已经买入了,那么 dp[i][1] = dp[i - 1][1]

  1. 达到 dp[i][2] 状态,有两个操作:

操作一:第 i 天卖出股票,此时 dp[i][2] = dp[i - 1][1] + prices[i]

操作二:第 i 天不操作,在第 i - 1 天已经卖出了,那么 dp[i][2] = dp[i - 1][2]

  1. 同理有 dp[i][3] = Math.max(dp[i - 1][3], dp[i][2] - prices[i])dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]
  • 初始化 dp 数组

初始化 dp[0][0] = 0dp[0][1] = -prices[0]dp[0][3] = -prices[0]

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int length = prices.length;
// 创建 dp 数组
int[][] dp = new int[length][5];
// 初始化 dp 数组
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (int i = 1;i < length;i++) {
dp[i][0] = dp[i - 1][0];
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[length - 1][4];
}
  • 使用滚动变量进行优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int length = prices.length;
// 创建 dp 数组
int[] dp = new int[5];
// 初始化 dp 数组
dp[1] = -prices[0];
dp[3] = -prices[0];
for (int i = 1;i < length;i++) {
dp[1] = Math.max(dp[1], dp[0] - prices[i]);
dp[2] = Math.max(dp[2], dp[1] + prices[i]);
dp[3] = Math.max(dp[3], dp[2] - prices[i]);
dp[4] = Math.max(dp[4], dp[3] + prices[i]);
}
return dp[4];
}

13、买卖股票的最佳时机 IV

1、题目描述

给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

  • 示例一
1
2
3
输入:k = 2, prices = [2,4,1]
输出:2
解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2
  • 示例二
1
2
3
4
输入:k = 2, prices = [3,2,6,5,0,3]
输出:7
解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4
随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3

2、解题思路

  • 我们可以按照上题的思路来解,初始化一个 prices.length2 * k + 1 列的二维数组
  • 初始化 dp 数组,当列数 j 满足 j % 2 == 1 时, dp[0][j] 初始化为 -prices[0] ,否则初始化为 0
  • 状态转移数组,当列数 j 满足 j % 2 == 1 时,此时证明我们需要买入股票,此时 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);当列数 j % 2 == 0 时,此时证明我们要卖出股票,此时 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i])

最后我们返回二维数组中最后一个元素,表示我们进行了 k 次交易后所能获取的最大收益。

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
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length == 0) return 0;
int len = prices.length;
// 创建一个 dp 数组
int[][] dp = new int[len][2 * k + 1];
// 初始化 dp 数组,我们需要初始化 dp[0][1]、 dp[0][3] ... dp[2 * k + 1]
for (int i = 1;i < 2 * k + 1;i += 2) {
dp[0][i] = -prices[0];
}
// 进行状态转移
for (int i = 1;i < len;i++) {
dp[i][0] = dp[i - 1][0];
for (int j = 1;j < 2 * k + 1;j++) {
if (j % 2 == 1) {
// 买入
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
} else {
// 卖出
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
}
}
}
return dp[len - 1][2 * k];
}
  • 优化空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length == 0) return 0;
int len = prices.length;
// 创建一个 dp 数组
int[] dp = new int[2 * k + 1];
// 初始化 dp 数组,我们初始化 dp[i] 的值(i % 2 == 1)
for (int i = 1;i < 2 * k + 1;i += 2) {
dp[i] = -prices[0];
}
// 进行状态转移
for (int i = 1;i < len;i++) {
for (int j = 1;j < 2 * k + 1;j++) {
if (j % 2 == 1) {
// 买入
dp[j] = Math.max(dp[j], dp[j - 1] - prices[i]);
} else {
// 卖出
dp[j] = Math.max(dp[j], dp[j - 1] + prices[i]);
}
}
}
return dp[2 * k];
}

14、圆圈中最后剩下的数字

1、题目描述

0,1,···,n-1 这 n 个数字排成一个圆圈,从数字 0 开始,每次从这个圆圈里删除第 m 个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。

例如,0、1、2、3、4 这 5 个数字组成一个圆圈,从数字 0 开始每次删除第 3 个数字,则删除的前 4 个数字依次是 2、0、4、1,因此最后剩下的数字是 3。

  • 示例一
1
2
输入: n = 5, m = 3
输出: 3
  • 示例二
1
2
输入: n = 10, m = 17
输出: 2

2、解题思路

  • 构造环形链表解决这道题
  • 使用一个 ArrayList 来模拟约瑟夫问题
  1. 创建一个 ArrayList,将 [0, n - 1] 放入到 ArrayList 中

  2. 使用公式计算出当前需要剔除出列表中的元素下标 index ,其中 index = (index + m - 1) % size ,其中 size 为当前列表中的元素个数

  3. 将列表中下标为 index 的元素剔除,反复执行 2 直到列表只剩下最后一个元素

  4. 返回最后一个元素即可

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int lastRemaining(int n, int m) {
// 创建一个 ArrayList ,存放 [0, n - 1]
List<Integer> list = new ArrayList<>();
for (int i = 0;i < n;i++) {
list.add(i);
}
// 从第一个人开始
int index = 0;
// 当 list 中剩余元素大于一时,根据公式剔除列表中的元素
while (list.size() > 1) {
// 计算要删除的下标 index
// 计算公式为 (index + m - 1) % list.size()
index = (index + m - 1) % list.size();
// 移除待删除的下标
list.remove(index);
}
// 最后返回列表中仅存的一个元素即可
return list.get(0);
}

15、使用队列实现栈

1、题目描述

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

  • 实现 MyStack 类:
    • void push(int x) 将元素 x 压入栈顶。
    • int pop() 移除并返回栈顶元素。
    • int top() 返回栈顶元素。
    • boolean empty() 如果栈是空的,返回 true ;否则,返回 false
  • 注意:
    • 你只能使用队列的基本操作 —— 也就是 push to backpeek/pop from frontsizeis empty 这些操作。
    • 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

2、解题思路

  • 使用两个队列实现栈

这道题与使用两个栈实现队列不一样,当我们将一个队列的数据导入另外一个队列时,数据的顺序没有发生改变,这是因为队列是先进先出的数据结构。

如果使用两个队列来模拟栈,那么第一个栈是用于模拟栈,而第二个栈是用于临时存储元素的

  1. 向栈中加入元素

image.png

当我们要向栈中加入元素时,我们直接将新元素添加到队列二中,比如说我们要向栈中加入 3 ,然后如果此时队列一不为空,那么我们需要更新 top 指向的值为新加入的值,而后依次从队列一弹出元素,然后加入到队列二中,最后调换队列一和队列二,此时队列一中就模拟了栈的元素顺序。

如果加入元素后队列一为空,那么直接交换队列一和队列二的引用即可。

image.png

  1. 向栈中弹出元素

我们直接从队列一中弹出队首元素即可,然后我们需要更新一下 top 的值为队列的首部元素。

  1. 查看栈顶元素 top()

直接返回 top 值即可

  1. 查看队列是否为空 isEmpty()

直接查看当前队列一是否为空即可。

  • 使用一个队列来模拟栈
  1. 添加元素

如果此时队列为空,那么直接将元素加入到队列中

image.png

如果此时队列不为空,那么先将元素 x 从尾部加入到队列中,然后将 x 之前的所有元素依次从队列中弹出,然后按照顺序从尾部加入到队列中

image.png

  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
class MyStack {
private Queue<Integer> firstQueue;
private Queue<Integer> secondQueue;

public MyStack() {
firstQueue = new LinkedList<>();
secondQueue = new LinkedList<>();
}

public void push(int x) {
//1 将新元素直接加入到队列二中
secondQueue.add(x);
//2 如果队列一不为空,那么需要从队列一中的元素依次弹出,然后放入到队列二中
while (!firstQueue.isEmpty()) {
secondQueue.add(firstQueue.poll());
}
//3 不论如何都需要交换队列一和队列二的引用
Queue<Integer> temp = firstQueue;
firstQueue = secondQueue;
secondQueue = temp;
}

public int pop() {
// 由于队列一此时模拟了栈的元素顺序,所以只需要弹出队列一的队首即可
return firstQueue.poll();
}

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

public boolean empty() {
return firstQueue.isEmpty();
}
}
  • 使用一个队列来模拟栈
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
class MyStack {
private Queue<Integer> queue;

public MyStack() {
queue = new LinkedList<>();
}

public void push(int x) {
//1 先将元素直接入列
queue.add(x);
// 如果队列此时只有一个元素,那么直接返回,什么都不做
if (queue.size() == 1) {
return;
}
// 否则需要将新元素之前的所有元素依次弹出放入,然后按照顺序放入到尾部
// 这里需要先记录队列的值,我们需要用这个值来判断本次需要调整多少个值
int size = queue.size();
while (size > 1) {
queue.add(queue.poll());
size--;
}
}

public int pop() {
return queue.poll();
}

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

public boolean empty() {
return queue.isEmpty();
}
}

16、最长无重复子串

1、题目描述

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度

  • 示例一
1
2
3
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3
  • 示例二
1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1

2、解题思路

  • 当我们遍历到第 i 个字符时,我们设 dp[i] 表示以第 i 个位置为结尾的最长无重复子串的长度
  • dp[i] 取决于什么?它取决为以 i - 1 个字符为结尾最长无重复子串的长度与 char[i] 的上一次出现的位置,这两个条件我们需要求一个最大值,也就是离 i 更近的情况。

我们使用一个哈希表来记录当前字符 char[i] 在字符串中上一次出现的位置

  • 由于 dp[i] 只与 dp[i - 1] 有关,所以我们可以用一个变量来滚动更新即可。

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
Map<Character, Integer> map = new HashMap<>();
int pre = -1, cur = 0, maxLength = 0, len = s.length();
char[] array = s.toCharArray();
for (int i = 0;i < len;i++) {
int index = map.getOrDefault(array[i], -1);
// 求 pre 的值
pre = Math.max(index, pre);
// 求当前以第 i 个字符为结尾的最长无重复子串长度
cur = i - pre;
// 更新最大长度
maxLength = Math.max(maxLength, cur);
// 还要更新哈希表中第 i 个字符的最新位置
map.put(array[i], i);
}
return maxLength;
}

17、对称二叉树

1、题目描述

给你一个二叉树的根节点 root , 检查它是否轴对称。

  • 示例

image.png

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

2、解题思路

  • 如果当前传入的 root 为空,那么直接返回 true
  • 如果当前 root 的左右子树均为空,那么返回 true ,如果左右子树不全为空,那么返回 false
  • 然后我们需要分别递归判断左子树的右子树和右子树的左子树是否对称,左子树的左子树和右子树的右子树是否对称

3、解题代码

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

private boolean isSymmetric(TreeNode left, TreeNode right) {
// 如果两个节点均为空,返回 true
if (left == null && right == null) return true;
if (left == null && right != null) return false;
if (left != null && right == null) return false;
if (left.val != right.val) return false;
// 递归判断左子树的右子树和右子树的左子树是否对称,然后判断右子树的右子树和左子树的左子树是否对称
return isSymmetric(left.right, right.left) && isSymmetric(left.left, right.right);
}

18、树的子结构

1、题目描述

输入两棵二叉树 A 和 B,判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构)

B 是 A 的子结构, 即 A 中有出现和 B 相同的结构和节点值。

2、解题思路

如果 B 是 A 的子结构,那么必须满足以下三种情况其中之一

  • A 的根节点的值和 B 的根节点的值相等,同时 B 的左子树是 A 的左子树的子结构且 B 的右子树是 A 的右子树的子结构

  • A 的根节点的值与 B 的根节点的值不相等,但是 B 是 A 的左子树或者 A 的右子树的子结构

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isSubStructure(TreeNode A, TreeNode B) {
// 如果 A 树和 B 树有一个为空,那么直接返回 false ,因为题目约定空树不是任何一棵树的子结构
if (A == null || B == null) return false;
//1 A 的根节点和 B 的根节点相同的情况,这种情况下依次比较它们的子节点
//2 A 的根节点和 B 的根节点不相同的情况,这个时候使用 A 的左子树与 B 树进行对比
//3 A 的根节点和 B 的根节点不相同的情况,这个时候使用 A 的右子树与 B 树进行对比
return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}

private boolean isSub(TreeNode A, TreeNode B) {
// 如果 B 为空,那么此时证明 B 中的节点已经完全匹配完毕
if (B == null) return true;
// 如果遍历过程中 B 还没为空,而 A 已经为空了,那么直接返回 false
if (A == null) return false;
// 如果 A 和 B 均不为空,但是此时 A B 节点的值不同,那么证明不匹配
if (A.val != B.val) return false;
// 如果当前 A 和 B 两个节点的值是匹配的,那么我们还需要递归判断左子树和右子树是否匹配
return isSub(A.left, B.left) && isSub(A.right, B.right);
}

19、回文子串

1、题目描述

给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

  • 示例
1
2
3
输入:s = "aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

2、解题思路

  • 确定 dp 数组的含义

我们定义一个二维的 dp 数组,其中 dp[i][j] 表示字符串 s[i, j] 是否为回文子串

  • 初始化 dp 数组

每一个字符都是一个回文字符串

  • 状态转移方程
  1. s.charAt(i) == s.charAt(j) ,如果此时 j - i == 1,那么 dp[i][j] = true ,此时我们就找到了一个回文子串,否则 dp[i][j] = dp[i + 1][j - 1]
  2. s.charAt(i) != s.charAt(j)dp[i][j] = false
  • 遍历顺序

由于 dp[i][j]dp[i + 1][j - 1] 有关,所以对于 i ,我们需要从后往前遍历,而对于 j 我们需要正向遍历。

  • 结果统计

使用一个 result 变量统计结果,当 dp[i][j] = true 时,result +=1

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
public int countSubstrings(String s) {
if (s == null || s.length() == 0) return 0;
int len = s.length();
boolean[][] dp = new boolean[len][len];
int result = 0;
// 初始化 dp 数组
for (int i = 0;i < len;i++) {
dp[i][i] = true;
result++;
}
for (int i = len - 1;i >= 0;i--) {
for (int j = i + 1;j < len;j++) {
if (s.charAt(i) == s.charAt(j)) {
if (j - i <= 1) {
// 此时让 result ++
result++;
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) {
result++;
dp[i][j] = true;
}
}
}
}
return result;
}

20、O(1) 时间插入、删除和获取随机元素 - 允许重复

1、题目描述

RandomizedCollection 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素,以及删除随机元素。

实现 RandomizedCollection 类:

  • RandomizedCollection() 初始化空的 RandomizedCollection 对象。
  • bool insert(int val) 将一个 val 项插入到集合中,即使该项已经存在。如果该项不存在,则返回 true ,否则返回 false
  • bool remove(int val) 如果存在,从集合中移除一个 val 项。如果该项存在,则返回 true ,否则返回 false 。注意,如果 val 在集合中出现多次,我们只删除其中一个。
  • int getRandom() 从当前的多个元素集合中返回一个随机元素。每个元素被返回的概率与集合中包含的相同值的数量 线性相关

您必须实现类的函数,使每个函数的 平均 时间复杂度为 O(1)

注意: 生成测试用例时,只有在 RandomizedCollection至少有一项 时,才会调用 getRandom

  • 示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
输出
[null, true, false, true, 2, true, 1]

解释
RandomizedCollection collection = new RandomizedCollection();// 初始化一个空的集合。
collection.insert(1);// 向集合中插入 1 。返回 true 表示集合不包含 1 。
collection.insert(1);// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
collection.insert(2);// 向集合中插入 2 ,返回 true 。集合现在包含 [1,1,2] 。
collection.getRandom();// getRandom 应当有 2/3 的概率返回 1 ,1/3 的概率返回 2 。
collection.remove(1);// 从集合中删除 1 ,返回 true 。集合现在包含 [1,2] 。
collection.getRandom();// getRandom 应有相同概率返回 1 和 2 。

2、解题思路

  • 为了使得在 O(1) 时间内随机获取一个元素,我们可以讲数放在一个列表中,这样获取随机元素时,就可以通过随机生成下标,从而随机得到一个元素
  • 但列表的随机删除不是 O(1) 的,但元素在列表中的顺序是无关紧要的,所以在删除元素时,我们可以讲被删除的元素与列表中的最后一个元素交换位置,然后就可以在 O(1) 时间内,从列表中删除元素
  • 所以我们需要维护数值在列表中的下标集合,对于数组 num 来说,它在 nums 中的下标集合为 Set(num)
  • 在删除时,我们找出 num 出现的其中一个下标 i ,并将 nums[i]nums[nums.length - 1] 交换位置,随后讲 i 从 Set(num) 中移除,并将原有的 nums[nums.length - 1] 替换为 i 。

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
53
54
55
56
57
58
59
60
class RandomizedCollection {
/**
* 用于存放值与其在 nums 中的下标集合
*/
private Map<Integer, Set<Integer>> ids;
/**
* 用于存放元素 num
*/
private List<Integer> nums;

public RandomizedCollection() {
ids = new HashMap<>();
nums = new ArrayList<>();
}

/**
* 添加元素
*/
public boolean insert(int val) {
//1 讲元素加入到 nums 中
nums.add(val);
// 添加该元素在nums中的下标
Set<Integer> indexSet = ids.getOrDefault(val, new HashSet<>());
indexSet.add(nums.size() - 1);
ids.put(val, indexSet);
// 第二次添加一样的数时返回 false
return indexSet.size() == 1;
}

public boolean remove(int val) {
// 如果 ids 中没有对应的 key ,那么证明没有该元素,直接返回 false
if (!ids.containsKey(val)) return false;
// 使用迭代器遍历 val 的所有下标
Set<Integer> indexSet = ids.get(val);
// 获取 val 的第一个下标
int firstIndex = indexSet.iterator().next();
// 获取 nums 中的最后一个数
int lastNum = nums.get(nums.size() - 1);
// 讲最后一个数放在 i 位置,实际上这样已经讲 val 移除
nums.set(firstIndex, lastNum);
// 由于 firstIndex 位置不再是 val ,那么 val 下标应该讲 firstIndex 移除
Set<Integer> lastNumIndexSet = ids.get(lastNum);
indexSet.remove(firstIndex);
lastNumIndexSet.remove(nums.size() - 1);
// 如果 firstIndex 不是最后一个位置,那么把它加入到集合中
if (firstIndex < nums.size() - 1) {
lastNumIndexSet.add(firstIndex);
}
if (indexSet.isEmpty()) {
ids.remove(val);
}
// 最后移除最后一个元素
nums.remove(nums.size() - 1);
return true;
}

public int getRandom() {
return nums.get((int)(Math.random() * nums.size()));
}
}

21、岛屿数量

1、题目描述

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

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

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

  • 示例一
1
2
3
4
5
6
7
输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","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

2、解题思路

image.png

  • 二叉树的 DFS
1
2
3
4
5
6
7
8
9
void traverse(TreeNode root) {
// 判断 base case
if (root == null) {
return;
}
// 访问两个相邻结点:左子结点、右子结点
traverse(root.left);
traverse(root.right);
}

可以看到,二叉树的 DFS 有两个要素,即访问子节点判断终止条件

  1. 访问子节点:二叉树本身就是一个递归定义的节奏,它的左右子树也是一颗二叉树
  2. 判断终止条件:当前节点为空时,递归结束
  • 网格的 DFS

对于网格的 DFS ,我们可以对照着二叉树的 DFS 写出它的两个要素:

  1. 相邻节点:一个网格一般来说有上下左右四个相邻节点,即格子 (r, c) 拥有 (r - 1, c)(r + 1, c)(r, c - 1)(r, c + 1)

image.png

  1. 终止条件

当当前所处位置处于网格边界时,此时我们需要停止搜索,我们可以写出网格递归的框架代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private void dfs(char[][] grid, int row, int column) {
if (!inArea(grid, row, column)) {
// 到达终止条件
return;
}
// 如果当前节点不是陆地节点,直接返回,证明岛屿已经遍历完毕
if (grid[row][column] != '1') {
return;
}
// 在本层逻辑中加入避免重复遍历的判断语句,将当前格子设置为已遍历
grid[row][column] = 2;
// 访问相邻节点
dfs(grid, row - 1, column);
dfs(grid, row + 1, column);
dfs(grid, row, column - 1);
dfs(grid, row, column + 1);
}

private boolean inArea(char[][] grid, int row, int column) {
return (row > -1 && row < grid.length) &&
(column > -1 && column < grid[0].length);
}
  • 如何避免重复遍历?

在这道题中,我们需要在所有值为 1 的陆地格子上进行遍历,当我们遍历到陆地格子时,将对应的值改为 2 ,这样当我们遇到 2 的时候,就知道这是遍历过的格子了。也就是说,每个格子可能取三个值:

  1. 0 —— 海洋格子
  2. 1 —— 陆地格子(未遍历过)
  3. 2 —— 陆地格子(已遍历过)

在代码中,我们在当前层处理逻辑中加入避免重复判断的语句:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void dfs(char[][] grid, int row, int column) {
if (!inArea(grid, row, column)) {
// 到达终止条件
return;
}
// 如果当前节点不是陆地节点,直接返回,证明岛屿已经遍历完毕
if (grid[row][column] != '1') {
return;
}
// 在本层逻辑中加入避免重复遍历的判断语句,将当前格子设置为已遍历
grid[row][column] = 2;
// 访问相邻节点
dfs(grid, row - 1, column);
dfs(grid, row + 1, column);
dfs(grid, row, column - 1);
dfs(grid, row, column + 1);
}
  • 对于这道题,我们循环遍历 grid 数组,当我们发现有一个格子的值为 1 时,我们就让岛屿数量 +1,因为每一次 dfs 都会将同一个岛屿的所有陆地都值为 2 ,所以每遍历到一个 1 ,就证明找到了一个新岛屿

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
class Solution {
private int result;
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
result = 0;
for (int i = 0;i < grid.length;i++) {
for (int j = 0;j < grid[0].length;j++) {
if (grid[i][j] == '1') {
// 当遍历到一个值为 1 的格子时,直接让岛屿数目 ++ ,因为 dfs 算法会将该岛屿的全部 1 均遍历过一次且变为 2
dfs(grid, i, j);
result++;
}
}
}
return result;
}
private void dfs(char[][] grid, int row, int column) {
if (!inArea(grid, row, column)) {
// 到达终止条件
return;
}
// 如果当前节点不是陆地节点,直接返回,证明岛屿已经遍历完毕
if (grid[row][column] != '1') {
return;
}
// 在本层逻辑中加入避免重复遍历的判断语句,将当前格子设置为已遍历
grid[row][column] = 2;
// 访问相邻节点
dfs(grid, row - 1, column);
dfs(grid, row + 1, column);
dfs(grid, row, column - 1);
dfs(grid, row, column + 1);
}

private boolean inArea(char[][] grid, int row, int column) {
return (row > -1 && row < grid.length) &&
(column > -1 && column < grid[0].length);
}
}

22、缺失的第一个正数

1、题目描述

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

  • 示例一
1
2
输入:nums = [1,2,0]
输出:3
  • 示例二
1
2
输入:nums = [3,4,-1,1]
输出:2
  • 示例三
1
2
输入:nums = [7,8,9,11,12]
输出:1

2、解题思路

3、解题代码

1

23、全排列

1、题目描述

1
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
  • 示例
1
2
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

2、解题思路

  • 使用回溯算法解决这道题,我们使用一个 used 数组来标志 nums 中的某个元素已经被用过
  • 在我们遍历到某个元素时,如果 used[i] 为 true ,那么直接跳过本次循环,在回溯时需要将 used[i] 置为 false

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
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums == null || nums.length == 0) return result;
used = new boolean[nums.length];
backtracking(nums);
return result;
}


private void backtracking(int[] nums) {
//1 base case ,创建递归推出条件
if (nums.length == path.size()) {
result.add(new ArrayList<>(path));
return;
}
//2 遍历 nums 中的数字
for (int i = 0;i < nums.length;i++) {
// 如果当前元素已经用过,那么跳过本次循环
if (used[i]) {
continue;
}
// 将当前元素加入到结果中
path.addLast(nums[i]);
// 将当前元素置为已使用过
used[i] = true;
// 继续进行递归
backtracking(nums);
// 撤销
path.removeLast();
used[i] = false;
}
}
}

24、组合总和

1、题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

  • 示例
1
2
3
4
5
6
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
23 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7
仅有这两种组合。

2、解题思路

  • 使用回溯算法
  1. 确定递归结束条件:当 path 中的和为 target 时,我们将当前结果 path 放入到最终结果中
  2. 每遍历到一个数组中的元素,我们都将其放入到 path 中,案后让 sum += nums[i] ,然后继续往下一层进行递归,然后我们需要撤销,让 sum -= nums[i] ,同时将 nums[i] 从 path 中移除。

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
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) return result;
// 需要对数组进行排序
Arrays.sort(candidates);
// 进行递归
backtracking(candidates, 0, target, 0);
return result;
}
private void backtracking(int[] candidates, int startIndex, int target, int sum) {
// 声明递归终止条件
if (sum == target) {
// 如果 sum 等于 target ,那么证明我们就找到了一个答案
result.add(new ArrayList<>(path));
return;
}
// 遍历数组,进行递归
for (int i = startIndex;i < candidates.length;i++) {
// 如果 sum + candidates[i] > target 就终止遍历
if (sum + candidates[i] > target) break;
// 选择第 i 个元素加入到 path 中
sum += candidates[i];
path.addLast(candidates[i]);
// 进行递归,这里从 i 开始,表示当前选中的元素在下一次遍历中依然可以被使用
backtracking(candidates, i, target, sum);
// 撤销
path.removeLast();
sum -= candidates[i];
}
}
}

25、判断一棵二叉树是否为搜索二叉树和完全二叉树

1、题目描述

给定一棵二叉树,已知其中的节点没有重复值,请判断该二叉树是否为搜索二叉树完全二叉树

2、解题思路

  • 判断二叉树是否为搜索二叉树,可以使用递归或者判断中序遍历序列来判断
  • 判断一棵树是否为完全二叉树,可以使用层序遍历的方式来解答,在层序遍历中保存一个 pre 指针指向当前遍历节点 cur 的前一个节点,如果 pre 为空且当前遍历节点 cur 不为空,那么直接返回 false
  • 我们不需要判断当前节点的左右节点是否存在,因为我们需要将二叉树中的 null 节点保存

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
public boolean[] judgeIt (TreeNode root) {
if (root == null || (root.left == null && root.right == null)) return new boolean[] {true, true};
boolean[] result = new boolean[2];
result[0] = isBST(root, null, null);
result[1] = isComplete(root);
return result;
}

private boolean isBST(TreeNode root, Integer min, Integer max) {
if (root == null) return true;
// 如果最小值大于等于当前根节点的值,那么直接返回 false
if (min != null && min >= root.val) return false;
if (max != null && max <= root.val) return false;
// 分别向左向右进行递归,将 root 的值作为 左子树递归的最大值传递进去,同时将 root 的值作为右子树递归的最大值传入
return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
}
// 判断是否为完全二叉树
private boolean isComplete(TreeNode root) {
if (root == null) return false;
Queue<TreeNode> queue = new LinkedList<>();
TreeNode pre = root;
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0;i < size;i++) {
TreeNode cur = queue.poll();
// 如果 pre 为空且 cur 不为空
if (pre == null && cur != null) return false;
// 如果 cur 不为空,那么将 cur 的左右子树加入到队列中
if (cur != null) {
queue.add(cur.left);
queue.add(cur.right);
}
// 让 pre 移动到下一个位置
pre = cur;
}
}
return true;
}

26、二叉树的直径

1、题目描述

给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

  • 示例
1
2
3
4
5
6
7
给定二叉树:
1
/ \
2 3
/ \
4 5
输出:返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

2、解题思路

  • 以某个点为中心的直径就是这个点左右子树的深度之和,使用一个 result 全局变量保存最大直径
  • 创建一个方法,这个方法用于求解某棵树的深度,然后在方法中,我们要更新 result 的值

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
int result;
public int diameterOfBinaryTree(TreeNode root) {
result = 1;
depth(root);
// 最后结果需要减去一
return result - 1;
}

private int depth(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
int left = depth(root.left);
int right = depth(root.right);
// 在这里,更新 result 的最大值
result = Math.max(result, left + right + 1);
return Math.max(left, right) + 1;
}
}

27、最长公共前缀

1、题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""

  • 示例
1
2
输入:strs = ["flower","flow","flight"]
输出:"fl"

2、解题思路

  • 我们以第一个字符串为基准,然后分别获取其他字符串与第一个字符串的公共前缀
  • 然后使用一个变量来保存所有字符串的最长公共前缀长度,需要与 strs[i]strs[0] 的最长公共前缀长度取最小值

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 String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
if (strs.length == 1) return strs[0];
char[] firstCharArray = strs[0].toCharArray();
int maxPrefixLen = Integer.MAX_VALUE;
char[] tempCharArray = null;
int index = 0;
for (int i = 1;i < strs.length;i++) {
// 初始化 index
index = 0;
tempCharArray = strs[i].toCharArray();
while (index < tempCharArray.length && index < firstCharArray.length) {
// 如果有字符不相等,那么直接退出
if (firstCharArray[index] != tempCharArray[index]) {
break;
}
index++;
}
// 更新当前最大的最长公共前缀,这里需要取最小值
maxPrefixLen = Math.min(maxPrefixLen, index);
// 如果 maxPrefixLen 为 0 ,那么证明此时数组内的最长公共前缀为 ""
if (maxPrefixLen == 0) return "";
}
// 否则返回最长公共前缀
return strs[0].substring(0, maxPrefixLen);

}

28、 逆序打印不可变链表

1、题目描述

给您一个不可变的链表,使用下列接口逆序打印每个节点的值:

ImmutableListNode : 描述不可变链表的接口,链表的头节点已给出。
您需要使用以下函数来访问此链表( 您 不能 直接访问 ImmutableListNode ):

1
2
ImmutableListNode.printValue():打印当前节点的值。
ImmutableListNode.getNext():返回下一个节点。

输入只用来内部初始化链表。您不可以通过修改链表解决问题。也就是说,您只能通过上述 API 来操作链表。

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

2、解题思路

  • 使用递归来解决这道题
  1. 当当前结点存在 next 结点时,直接进行递归,将当前结点的 next 传入
  2. 当当前结点不存在 next 结点时,直接打印当前结点即可
  • 不可变的 Node 结点定义如下:
1
2
3
4
5
6
7
8
/**
* // This is the ImmutableListNode's API interface.
* // You should not implement it, or speculate about its implementation.
* interface ImmutableListNode {
* public void printValue(); // print the value of this node.
* public ImmutableListNode getNext(); // return the next node.
* };
*/

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public void printLinkedListInReverse(ImmutableListNode head) {
// 当 head 存在下一个结点时,标识当前 head 不是最后一个结点,此时进行递归
if(head.getNext()!=null){
printLinkedListInReverse(head.getNext());
}
// 如果是最后一个结点,那么会直接输出
// 其他结点在跳出递归后,会执行这里的输出语句
head.printValue();
}

}
/**
* // This is the ImmutableListNode's API interface.
* // You should not implement it, or speculate about its implementation.
* interface ImmutableListNode {
* public void printValue(); // print the value of this node.
* public ImmutableListNode getNext(); // return the next node.
* };
*/

29、最接近 target 的值

1、题目描述

给出一个数组,在数组中找到两个数,使得它们的和最接近目标值但不超过目标值,返回它们的和

  • 示例
1
2
3
输入: target = 15 和 array = [1,3,5,11,7]
输出: 14
解释: 11+3=14
  • 示例二
1
2
3
输入: target = 16 和 array = [1,3,5,11,7]
输出: 16
解释: 11+5=16

2、解题思路

  • 使用双指针解决这道题,我们先将数组进行排序,然后右指针指向数组的最后一个元素,左指针指向第一个元素
  • 我们使用一个变量 diff 来表示当前指针指向元素之和与 target 的差值,当 nums[left] + nums[right] <= target 时,我们更新 diff 的值,然后让 left++ 。
  • nums[right] > target 时,让 right– ,此时我们不更新 diff 的值
  • 最后返回 target - diff 即可。

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int closestTargetValue(int target, int[] array) {
if (array == null || array.length == 0) return -1;
Arrays.sort(array);
int left = 0, right = array.length - 1, diff = Integer.MAX_VALUE;
while (left < right) {
if (array[left] >= target) {
break;
}
if (array[left] + array[right] <= target) {
diff = Math.min(diff, target - (array[left] + array[right]));
left++;
} else if (array[left] + array[right] > target) {
right--;
}
}
if (diff == Integer.MAX_VALUE) {
return -1;
}
return target - diff;
}

30、小于 n 的最大数

1、题目描述

给定一个数 n,如 23121,给定一组数 A,{2, 4, 9},返回用 A 可以组成的小于 n 的最大数,A 不为空,答案 22999,

2、解题思路

  • 使用贪心完成这道题,我们创建一个 flag 标识用于标识当前结果的前 n 位是否小于所给值得前 n 位,从最高位开始计算,flag 初始化为 false
  • 我们使用两层循环来解决这个问题,如果此时 flag 为 true ,那么证明当前结果已经小于所给值,此时我们只需要当前结果剩下的位数中全部拼接上数组中的最大值即可。

比如说所给数为 100 ,数组为 {2,4,9} ,当 flag 为 true 时,我们直接组装两次 9 ,即返回 99

  • 当所给值的某一位在数组中出现时,那么直接用数组中的那一个数

当所给书为 23121 ,所给数组为 {2,4,9} 时,由于所给的第一位在数组中有出现,所以直接用数组中的数

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
public static String minValue(int[] nums, int value) {
Arrays.sort(nums);
boolean flag = false;
String valueStr = String.valueOf(value);
StringBuilder result = new StringBuilder();
for (int i = 0;i < valueStr.length();i++) {
int current = valueStr.charAt(i) - '0';
for (int j = 0;j < nums.length;j++) {
if (flag) {
// 如果已经确定当前结果小于 value ,那么剩下的几位全部使用最大值
result.append(nums[nums.length - 1]);
// 直接退出,因为不用与数组其他的元素进行对比了,可以比较下一位了
break;
} else if (current == nums[j]) {
// 如果发现当前结果的第 i 位刚好等于 nums[j] ,那么直接将 nums[j] 拼接到结果中
result.append(nums[j]);
break;
} else if (current < nums[j]) {
// 如果发现当前位小于 nums[j] ,那么尝试拼接前一位,并将 flag 置为 true
// 这里的 nums[j - 1] 一定小于 current
if (j - 1 >= 0) {
result.append(nums[j - 1]);
}
flag = true;
break;
}
}
}
return result.toString();
}

31、盛最多水的容器

1、题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0)(i, height[i])

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

  • 示例

image.png

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

2、解题思路

  • 使用双指针来解决这道题
  • 我们初始化左指针和右指针,其中左指针初始化为 0 ,右指针指向数组最后一个元素,使用一个变量用于存储最大水量
  • 计算当前能存储的水量,计算公式为 water = Math.min(nums[left], nums[right]) * (right - left),然后判断当前水量是否大于最大水量,如果是,那么更新
  • 判断 nums[left]nums[right] 的关系,如果 nums[left] > nums[right] ,那么让 right 左移,以期找到一个更大的 right ,反之亦然

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxArea(int[] height) {
if (height == null || height.length == 0) return 0;
int left = 0, right = height.length - 1, maxWater = Integer.MIN_VALUE, curWater = 0;
while (left < right) {
curWater = Math.min(height[left], height[right]) * (right - left);
maxWater = Math.max(curWater, maxWater);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater == Integer.MIN_VALUE ? 0 : maxWater;
}

32、删除排序链表中的重复元素 II

1、题目描述

给定一个已排序的链表的头 head删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表

  • 示例

image.png

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

2、解题思路

  • 由于链表是有序的,那么我们其实只需要用一次遍历即可解决这个问题
  • 由于链表的头节点也可能是待删除元素,所以我们可以创建一个虚拟头节点
  • 使用一个 cur 结点遍历链表,当发现 cur.next.val == cur.next.next.val 时,这个时候我们需要删除,此时证明 cur.next 和 cur.next.next 都是需要删除的结点,此时我们记录 cur.next.val 的值为 nextVal ,然后循环遍历,删除所有值为 nextVal 的结点
  • 如果 cur.next.val != cur.next.next.val 时,直接让 cur 后移即可。

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
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
// 创建一个虚拟头节点指向 head
ListNode virtualHead = new ListNode(Integer.MIN_VALUE, head);
// 创建一个结点用于遍历链表
ListNode cur = virtualHead;
// 当 cur 的下一个结点与下下个结点存在时进行循环
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
// 如果下一个结点的 val 与下下个结点的 val 相等,表示此时我们需要进行删除
// 获取下一个结点的值
int nextVal = cur.next.val;
// 当 cur.next 不为空且 cur.next 的值为 nextVal 时,那么代表这个 cur.next 是要删除的结点
while (cur.next != null && cur.next.val == nextVal) {
cur.next = cur.next.next;
}
} else {
// 否则我们直接让 cur 右移
cur = cur.next;
}
}
// 最后返回虚拟节点的下一个结点即可
return virtualHead.next;
}

33、长度最小的子数组

1、题目描述

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

  • 示例
1
2
3
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

2、解题思路

  • 使用滑动窗口解决这个问题,我们使用一个 for 循环遍历数组,将 for 循环中的循环变量称为右边界 right,同时我们在数组最左边划定一个左边界 left ,称 [left, right] 为滑动窗口,而 [left, right] 中的和记为 sum
  • 当 sum 小于 target 时,此时我们需要让 right 右移,扩充窗口的大小,从而让数组中的元素和符合题意
  • 当 sum 大于等于 target 时,此时我们就找到了一个解,这个解实际上就是滑动窗口的大小 right - left + 1 ,我们将这个值与全局最优解作比较,选一个小的,然后我们需要保持右边界不动,并尝试缩小 left ,以此达到缩小窗口的目的,可以想一下,比如说当前窗口的元素为 [1, 2, 3] ,而 target 为 5 ,那么如果我们缩小窗口,那么 [2,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
public int minSubArrayLen(int target, int[] nums) {
if (nums == null || nums.length == 0) return 0;
// 创建一个 left 变量用于划定滑动窗口的左边界
int left = 0;
// 创建一个变量用于存储最优解
int result = Integer.MAX_VALUE;
// sum 用于表示滑动窗口中元素和
int sum = 0;
// 使用一个 for 循环,这个循环中的循环变量是窗口的右边界
for (int right = 0;right < nums.length;right++) {
// 当 sum 小于 target 时,此时我们要扩充滑动窗口
// 当右边界向右扩充时,此时我们要将 right 指向的元素加入到 sum 中,sum 表示当前滑动窗口中的元素和
sum += nums[right];
while (sum >= target) {
// 当 sum 大于等于 target 时,此时我们要收集答案
result = Math.min(result, right - left + 1);
// 此时我们尝试缩小窗口大小
sum -= nums[left];
left++;
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}

34、二叉树的右视图

1、题目描述

给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

  • 示例

image.png

1
2
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

2、解题思路

  • 除了使用 BFS 之外,还使用 DFS 解决这道题
  • 我们按照 根节点 -> 右子树 -> 左子树 的顺序访问,可以保证每层都是最先访问最右边的结点,那么我们只需要在进入到树的新一层的时候,收集该层我们遍历到的第一个结点即可。
  • 我们使用一个 depth 全局变量来表示我们当前遍历的深度,当 depth == result.size() 时,我们就可以进行收集。

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
private List<Integer> result;
public List<Integer> rightSideView(TreeNode root) {
result = new ArrayList<>();
dfs(root, 0);
return result;
}

/**
* 进行 dfs 的方法
*/
private void dfs(TreeNode root, int depth) {
if (root == null) return;
// 遍历的顺序是:根右左,如果满足这个条件,那么证明我们此时正在访问本层的第一个结点
// 比如说 depth 为 1 ,此时 result 集合的长度也为 1 ,当我们加入第二层的第一个结点后,集合长度就变为 2 ,此时 depth 和 result 长度就不等了。
if (depth == result.size()) {
// 将当前 root 的值加入
result.add(root.val);
}
// 需要将 depth 的值 + 1,表示我们进到下一层
depth++;
// 按照右左的顺序进行 dfs
dfs(root.right, depth);
dfs(root.left, depth);

}

35、简化路径

1、题目描述

给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 **绝对路径 ** (以 '/' 开头),请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,’//‘)都被视为单个斜杠 ‘/‘ 。 对于此问题,任何其他格式的点(例如,’…’)均被视为文件/目录名称

请注意,返回的 规范路径 必须遵循下述格式:

  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/'
  • 最后一个目录名(如果存在)**不能 **以 '/' 结尾。
  • 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含 '.''..')。

返回简化后得到的 规范路径

  1. 示例一
1
2
3
输入:path = "/home/"
输出:"/home"
解释:注意,最后一个目录名后面没有斜杠。
  1. 示例二
1
2
3
输入:path = "/../"
输出:"/"
解释:从根目录向上一级是不可行的,因为根目录是你可以到达的最高级。

2、解题思路

  • 将所给的字符串通过 split 函数进行分割,这里以 / 作为分割符,当我们进行分割后,我们会得到一个字符串列表,这个字符串列表中只存在以下几种元素
  1. 空字符串,当出现多个连续的 / 时,就会分割出空字符串
  2. 一个点 .:表示当前路径

对于空字符串和一个点的情况,我们实际上可以直接跳过,因为空字符串没有意义,而 . 代表当前目录

  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
public String simplifyPath(String path) {
if (path == null || path.length() == 0) return "";
//1 将字符串通过 / 分割符进行分割,得到一个 String 数组
String[] array = path.split("/");
//2 创建一个栈,这里使用双端队列来模拟栈
Deque<String> stack = new ArrayDeque<>();
//3 遍历数组
for (String item : array) {
if ("..".equals(item)) {
//4 如果遇到 ".." ,那么如果此时栈不为空,就将栈顶元素弹出,表示回退到上一级
if (!stack.isEmpty()) {
stack.pollLast();
}
} else if (item.length() > 0 && !(".".equals(item))) {
stack.offerLast(item);
}
}
//6 使用一个 StringBuilder 用于返回最后结果
StringBuilder result = new StringBuilder();
if (stack.isEmpty()) {
//7 如果栈为空,那么直接返回 "/" 即可
result.append("/");
} else {
//8 如果栈不为空,那么我们需要将栈中元素从栈底依次拼接起来,每个元素之间使用 / 分割,这里可以让元素从双端队列头部弹出
while (!stack.isEmpty()) {
result.append("/").append(stack.pollFirst());
}
}
return result.toString();
}

36、全排列 II

1、题目描述

给定一个可包含重复数字的序列 nums ,**按任意顺序** 返回所有不重复的全排列。

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

2、解题思路

  • 与全排列的思路差不多,但我们要在进行递归时判断,当前 nums[i] 是否与 nums[i - 1] 相等,如果满足 i > 0 && nums[i] == nums[i - 1] && used[i - 1] ,那么直接跳过,因为这个数字在前面已经使用过
  • 在进行全排列之前需要对数组进行排序。

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
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null || nums.length == 0) return result;
used = new boolean[nums.length];
Arrays.sort(nums);
dfs(nums);
return result;
}

private void dfs(int[] nums) {
if (nums.length == path.size()) {
result.add(new ArrayList<>(path));
return;
}
// 进行递归
for (int i = 0;i < nums.length;i++) {
if (i > 0 && nums[i - 1] == nums[i] && used[i - 1]) continue;
// 当 used[i] 为 false 时进行回溯
if (!used[i]) {
path.addLast(nums[i]);
used[i] = true;
dfs(nums);
used[i] = false;
path.removeLast();
}
}
}
}

37、 36 进制加法

1、题目描述

36 进制由 0-9,a-z,共 36 个字符表示。

要求按照加法规则计算出任意两个 36 进制正整数的和,如 1b + 2x = 48 (解释:47+105=152)

  • 示例
1
2
输入: 1b + 2x
输出: 48

2、解题思路

  • 这道题类似于大数相加,本质上就是 36 进制的大数相加。
  • 我们从后往前遍历两个字符串,然后进行相加,最后将数组翻转即可

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
private static int getInt(char ch) {
if (ch >= '0' && ch <= '9') {
return ch - '0';
} else {
return ch - 'a' + 10;
}
}

private static char getChar(int n) {
if (n <= 9) {
return (char) (n + '0');
} else {
return (char) (n - 10 + 'a');
}
}

public static String add36String(String num1, String num2) {
// 进位数
int carry = 0;
int leftPoint = num1.length() - 1, rightPoint = num2.length() - 1;
int x = 0, y = 0;
StringBuilder result = new StringBuilder();
while (leftPoint >= 0 || rightPoint >= 0 || carry > 0) {
x = (leftPoint >= 0) ? getInt(num1.charAt(leftPoint)) : 0;
y = (rightPoint >= 0) ? getInt(num2.charAt(rightPoint)) : 0;
int temp = x + y + carry;
result.append(getChar(temp % 36));
carry = temp / 36;
leftPoint--;
rightPoint--;
}
return result.reverse().toString();
}

38、掷骰子的 N 种方法

1、题目描述

这里有 n 个一样的骰子,每个骰子上都有 k 个面,分别标号为 1k

给定三个整数 n , ktarget返回可能的方式(从总共 kn 种方式中)滚动骰子的数量,使正面朝上的数字之和等于 target 。

答案可能很大,你需要对 10^9 + 7 取模

  • 示例一
1
2
3
4
输入:n = 1, k = 6, target = 3
输出:1
解释:你扔一个有6张脸的骰子。
得到3的和只有一种方法。
  • 示例二
1
2
3
4
输入:n = 2, k = 6, target = 7
输出:6
解释:你扔两个骰子,每个骰子有6个面。
得到7的和有6种方法1+6 2+5 3+4 4+3 5+2 6+1

2、解题思路

  • 使用动态规划解决这个问题,这个问题是一个背包问题
  • 创建一个二维的 dp 数组,我们设 dp[i][j] 表示,用 i 个骰子掷出总和为 j 的方案数
  • 对于前 i 个骰子而言,可能决策的方案有:
    • 第 i 个骰子的结果为 1 ,那么此时有 dp[i][j] = dp[i - 1][j - 1]
    • 第 i 个骰子的结果为 2 ,那么此时有 dp[i][j] = dp[i - 1][j - 2]
    • 第 i 个骰子的结果为 m ,那么此时有 dp[i][j] = dp[i - 1][j - m]

dp[i][j] 为以上所有方案的总和

  • 初始化 dp[0][0] = 1

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int numRollsToTarget(int n, int k, int target) {
int mod = (int)1e9+7;
// 创建一个二维的 dp 数组,其中 dp[i][j] 表示对于前 i 个骰子,有 dp[i][j] 种掷出和为 j 的方案
int[][] dp = new int[n + 1][target + 1];
dp[0][0] = 1;
for (int i = 1;i <= n;i++) {
for (int j = 0;j <= target;j++) {
for (int x = 1;x <= k;x++) {
if (j >= x) {
dp[i][j] += dp[i - 1][j - x];
dp[i][j] %= mod;
}
}
}
}
return dp[n][target];
}

39、二叉树中的最大路径和

1、题目描述

路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ,返回其 最大路径和

  • 示例一

image.png

1
2
3
输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6
  • 示例二

image.png

1
2
3
输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42

2、解题思路

  • 使用递归解决这道题,当传入的 root 为空时,直接返回 0

  • 当我们处于 root 时,我们希望左子树告诉我们以左子节点开始的路径和最大值为多少,同样,我们希望右子树告诉我们以右子节点开始的路径和最大值为多少。

  • 对于 root 来说,有 4 种可能得到最大值

  1. 我自己为一个路径
  2. 我只和左子树合并成为一条路径
  3. 我只和右子树合并成为一条路径
  4. 我同时链接左子树和右子树的路径

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
int pathSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return pathSum;
}

private int dfs(TreeNode root) {
if (root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
//四种选择
//1 独立成线
//2 和左子树成为一条路径、
//3 和右子树称为一条路径
int res = Math.max(root.val, root.val + Math.max(left, right));
//4 以自己为桥梁,同时与左右子树合并
pathSum = Math.max(pathSum, Math.max(res, root.val + left + right));
return res;
}
}

40、单词拆分

1、题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s

注意: 不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

  • 示例一
1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet""code" 拼接成。
  • 示例二
1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
  注意,你可以重复使用字典中的单词。

2、解题思路

  • 使用动态规划解决这道题,我们令 dp[i] 表示 s[0, i - 1] 子串是否能被空格拆分为若干个字典中出现的单词。
  • 状态转移方程:dp[i] = dp[j] && check(s[j, i - 1]) ,也就当 dp[j] = true 时,那我们只需要判断 s[j, i - 1] 是否也在 wordDict 中即可。
  • 初始化 dp 数组,我们令 dp[0] = true

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
int len = s.length();
boolean[] dp = new boolean[len + 1];
// 初始化 dp 数组,其中 dp[i] 表示 s[0, i - 1] 是否能被 wordDict 中的单词拼接出来
dp[0] = true;
for (int i = 1;i <= len;i++) {
for (int j = 0;j < i;j++) {
if (dp[j] && wordSet.contains(s.substring(j, i))) {
dp[i] = true;
}
}
}
return dp[len];
}

41、从根节点到叶节点的路径数字之和

1、题目描述

给定一个二叉树的根节点 root ,树中每个节点都存放有一个 09 之间的数字。

每条从根节点到叶节点的路径都代表一个数字:例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123

计算从根节点到叶节点生成的 所有数字之和叶节点 是指没有子节点的节点。

  • 示例一

image.png

1
2
3
4
5
6
输入:root = [1,2,3]
输出:25
解释:
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此,数字总和 = 12 + 13 = 25
  • 示例二

image.png

1
2
3
4
5
6
7
输入:root = [4,9,0,5,1]
输出:1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此,数字总和 = 495 + 491 + 40 = 1026

2、解题思路

  • 使用深度优先算法解决这个问题,如果遇到一个叶子节点,那么将叶子节点对应的数加到数字之和中。
  • 如果当前节点不是叶子节点,那么计算它子节点对应的数字,然后对子节点进行递归

image.png

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int sumNumbers(TreeNode root) {
return process(root, 0);
}
/**
* 使用 DFS 进行搜索
*/
private int process(TreeNode root, int value) {
// 如果已经到了叶子节点,那么此时直接返回 0
if (root == null) return 0;
// 否则我们要计算和,就是传入的 val * 10 然后再上根节点的值
int sum = value * 10 + root.val;
// 如果该节点为叶子节点
if (root.left == null && root.right == null) {
// 那么直接返回 sum 即可。
return sum;
} else {
return process(root.left, sum) + process(root.right, sum);
}
}

42、二叉树中和为某一值的路径

1、题目描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

  • 示例一

image.png

1
2
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]
  • 示例二

image.png

1
2
输入:root = [1,2,3], targetSum = 5
输出:[]

2、解题思路

  • 使用回溯算法解决这道题,每当我们经过一个叶子节点,我们就让 target 的值减去对应 root 节点的值,这样当 root 为叶子节点且 target 的值为 0 时,此时就可以收集答案
  • 配合前序遍历解决这道题

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 List<List<Integer>> pathSum(TreeNode root, int target) {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
if (root == null) return result;
process(root, target, result, path);
return result;
}

private void process(TreeNode root, int target, List<List<Integer>> result, LinkedList<Integer> path) {
// 如果此时遍历到的 root 为空,那么证明我们越过了叶子节点,此时直接返回
if (root == null) {
return;
}
// 让 target 减去 root 的值
target -= root.val;
// 将 root 的值放入 path 中
path.addLast(root.val);
// 当 target 等于 0 且 root 为叶子节点时,收集答案
if (target == 0 && root.left == null && root.right == null) {
result.add(new ArrayList<>(path));
}
// 进行前序遍历
process(root.left, target, result, path);
process(root.right, target, result, path);
// 移除本层做的事,进行回溯
target += root.val;
path.removeLast();
}

43、最接近的三数之和

1、题目描述

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。

返回这三个数的和,假定每组输入只存在恰好一个解。

  • 示例一
1
2
3
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
  • 示例二
1
2
输入:nums = [0,0,0], target = 1
输出:0

2、解题思路

  • 这道题与三数之和类似,我们将数组排序后,先确定一个数的值,然后再在 [i + 1, end] 中使用双指针选出两个数

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int threeSumClosest(int[] nums, int target) {
int result = nums[0] + nums[1] + nums[2];
int left = -1, right = -1, sum = 0;
Arrays.sort(nums);
for (int i = 0;i < nums.length - 2;i++) {
left = i + 1;
right = nums.length - 1;
while (left < right) {
sum = nums[i] + nums[left] + nums[right];
if (Math.abs(target - result) > Math.abs(target - sum)) {
result = sum;
} else if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
return result;
}
}
}
return result;
}

44、删除字符串中的所有相邻重复项

1、题目描述

给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

  • 示例
1
2
3
4
输入:"abbaca"
输出:"ca"
解释:
例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"

2、解题思路

  • 使用一个栈来解决这个问题,当遍历到的字符与栈顶字符相同时,直接弹出栈顶字符,否则将该字符入栈
  • 最后自底而上收集栈中元素

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public String removeDuplicates(String s) {
if (s == null || s.length() == 0) return "";
Deque<Character> stack = new ArrayDeque<>();
for (char ch : s.toCharArray()) {
if (!stack.isEmpty() && stack.peekLast() == ch) {
stack.pollLast();
} else {
stack.addLast(ch);
}
}
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
result.append(stack.pollFirst());
}
return result.toString();
}

45、柠檬水找零

1、题目描述

在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。

每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。

注意,一开始你手头没有任何零钱。

给你一个整数数组 bills ,其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零,返回 true ,否则返回 false

  • 示例
1
2
3
4
5
6
7
输入:bills = [5,5,5,10,20]
输出:true
解释:
3 位顾客那里,我们按顺序收取 35 美元的钞票。
4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。
5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零,所以我们输出 true

2、解题思路

我们需要维护三种金额的数量,5, 10 和 20,有以下三种情况

  • 情况一:账单是 5,直接收下。
  • 情况二:账单是 10,消耗一个 5,增加一个 10
  • 情况三:账单是 20,优先消耗一个 10 和一个 5,如果不够,再消耗三个 5

由于 10 元只能给 20 找零,所以 5 元更通用。由于 20 元不可能花出去,所以我们只需要在代码中维护 5 元和 10 元的钱数即可,在一次找零后,如果发现 5 元和 10 元的钱数有一个小于 0 ,那么直接返回 false ,整个数组遍历完后,如果钱数均不小于 0 ,则返回 true

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
public boolean lemonadeChange(int[] bills) {
// 我们维护 5 元和 10 元的数量即可
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5) {
// 如果遇到 5 元,那么直接让 5 元钱数 ++
five++;
} else if (bill == 10) {
// 如果遇到 10 元,那么 10 元钱数 + 1,同时5元钱数 - 1
five--;
ten++;
} else {
// 如果遇到 20 元,那么优先消耗 10 + 5,如果 10 小于 0 ,那么消耗 3 * 5
if (ten > 0) {
ten--;
five--;
} else {
five -= 3;
}
}
// 在一次找零后看看有没有钱数小于 0 ,如果有,那么直接返回 false
if (ten < 0 || five < 0) return false;
}
return true;
}

46、最长有效括号

1、题目描述

给你一个只包含 '('')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

  • 示例一
1
2
3
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"
  • 示例二
1
2
3
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"

2、解题思路

  • 使用一个栈来解决这个问题
  1. 将 -1 入栈,用于处理边界条件
  2. 遍历字符串,如果遇到左括号时,就将左括号对应的索引值入栈
  3. 如果遇到右括号时,我们弹出栈顶元素表示匹配了当前右括号
    1. 如果栈为空,那么说明当前的右括号为没有被匹配的右括号,我们将它的下标放入栈中来更新我们之前提到的最后一个没有被匹配的右括号的下标
    2. 如果栈不为空,那么使用当前右括号的下标减去栈顶元素即为以该右括号为结尾的最长有效括号的长度

需要注意的是,如果一开始栈为空,第一个字符为左括号的时候我们会将其放入栈中,这样就不满足提及的「最后一个没有被匹配的右括号的下标」,为了保持统一,我们在一开始的时候往栈中放入一个值为 −1 的元素。

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int longestValidParentheses(String s) {
if (s == null || s.length() <= 1) return 0;
Deque<Integer> stack = new ArrayDeque<>();
stack.addLast(-1);
int maxLength = 0;
for (int i = 0;i < s.length();i++) {
if (s.charAt(i) == '(') {
stack.addLast(i);
} else {
stack.removeLast();
if (stack.isEmpty()) {
stack.addLast(i);
} else {
maxLength = Math.max(i - stack.peekLast(), maxLength);
}
}
}
return maxLength;
}

47、下一个更大元素 II

1、题目描述

给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素

数字 x下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1

  • 示例一
1
2
3
4
5
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2
数字 2 找不到下一个更大的数;
第二个 1 的下一个最大的数需要循环搜索,结果也是 2
  • 示例二
1
2
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

2、解题思路

  • 使用单调栈和循环数组来解决这个问题,当栈为空或者栈顶元素下标对应的值小于当前遍历到的值时,直接将当前元素的下标入栈,否则循环弹出栈顶小于当前值的下标,计算该下标对应的值

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] nextGreaterElements(int[] nums) {
if (nums == null || nums.length == 0) return nums;
Deque<Integer> stack = new ArrayDeque<>();
int[] result = new int[nums.length];
Arrays.fill(result, -1);
int len = nums.length;
for (int i = 0;i < 2 * len - 1;i++) {
while (!stack.isEmpty() && nums[stack.peekLast()] < nums[i % len]) {
// 此时可以结算 nums[stack.peek()] 的下一个最大元素
result[stack.pollLast()] = nums[i % len];
}
stack.addLast(i % len);
}
return result;
}

48、二叉树最大宽度

1、题目描述

给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。

每一层的宽度被定义为两个端点(该层最左和最右的非空节点,两端点间的 null 节点也计入长度)之间的长度。

  • 示例一
1
2
3
4
5
6
7
8
9
10
输入: 

1
/ \
3 2
/ \ \
5 3 9

输出: 4
解释: 最大值出现在树的第 3 层,宽度为 4 (5,3,null,9)。
  • 示例二
1
2
3
4
5
6
7
8
9
10
输入: 

1
/
3
/ \
5 3

输出: 2
解释: 最大值出现在树的第 3 层,宽度为 2 (5,3)。

2、解题思路

  • 使用层序遍历来解决这道题,我们使用一个双向队列来保存节点,同时以节点的值来记录节点在二叉树上的位置
  • 那么每一层的宽度就可以这样计算,使用双端队列中最后一个元素的 val 减去第一个元素的 val ,得到的结果 + 1 就是本层的宽度。
  • 如果 cur 的左子树不为空,那么将左子树的值置为 2 * cur.val + 1,然后加入到双端队列中
  • 如果 cur 的右子树不为空,那么将右子树的值置为 2 * cur.val + 2,然后加入到队列中
  • 我们也可以不改变节点 val 的值,可以通过自定义一个类来解决这个问题,然后使用 position 来保存位置即可。
1
2
3
4
class MyTreeNode {
TreeNode node;
int position;
}

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 int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
int max = 1;
int current = 0;
Deque<TreeNode> queue = new LinkedList<>();
// 使用节点的 val 属性记录其在树中的位置
root.val = 0;
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
// 当前层的宽度的值为最后一个节点的值 - 第一个节点的值 + 1
current = queue.peekLast().val - queue.peekFirst().val + 1;
max = Math.max(current, max);
for (int i = 0;i < size;i++) {
TreeNode cur = queue.pollFirst();
if (cur.left != null) {
cur.left.val = 2 * cur.val + 1;
queue.addLast(cur.left);
}
if (cur.right != null) {
cur.right.val = 2 * cur.val + 2;
queue.addLast(cur.right);
}
}
}
return max;
}

49、螺旋矩阵

1、题目描述

给你一个 mn 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

  • 示例一

image.png

1
2
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]
  • 示例二

image.png

1
2
输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

2、解题思路

  • 我们可以将矩阵看为若干层,首先输出最外层的元素,然后输出次外层的元素,直到输出最内层的元素
  • 对于每层,从左上方开始以顺时针遍历所有元素。假设当前层的左上角位于 (top, left),右下角位于(bottom,right),我们按照以下顺序遍历当前层元素
  1. 从左到右遍历元素,依次为(top,left)到(top,right)
  2. 从上到下遍历元素,依次为(top + 1,right)到(bottom,right)
  3. 如果此时 left < right 且 top < bottom ,则从右到左遍历下侧元素,依次为(bottom,right - 1)到(bottom,left - 1)以及从下到上遍历左侧元素,依次为(bottom,left)到(top + 1,left)
  • 在遍历完一层元素后,收缩矩阵范围,令 left 与 top + 1,同时让 right 与 bottom - 1

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
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix == null || matrix.length == 0) return result;
// 确定左上角与右下角位置
int row = matrix.length, column = matrix[0].length;
int top = 0, bottom = row - 1, left = 0, right = column - 1;
// 当 left 小于等于 right 且 top 小于等于 bottom 时继续循环
while (left <= right && top <= bottom) {
//1 从左到右打印
for (int i = left;i <= right;i++) {
result.add(matrix[top][i]);
}
//2 从上到下打印
for (int i = top + 1;i <= bottom;i++) {
result.add(matrix[i][right]);
}
//3 当 left < right 且 top < bottom 时,打印
if (left < right && top < bottom) {
//4 向右往左打印
for (int i = right - 1;i > left;i--) {
result.add(matrix[bottom][i]);
}
//5 向下往上打印
for (int i = bottom;i > top;i--) {
result.add(matrix[i][left]);
}
}
//6 收缩矩阵
left++;
top++;
right--;
bottom--;
}
return result;
}

50、搜索旋转排序数组

1、题目描述

整数数组 nums 按升序排列,数组中的值 互不相同

在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1

  • 示例一
1
2
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
  • 示例二
1
2
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1

2、解题思路

  • 使用二分查找解决这个问题,在循环中,我们计算判断 nums[mid] 与 target 值的关系
  1. 如果 nums[mid] == target ,那么直接返回 mid
  2. 如果 nums[0] <= nums[mid] ,此时代表 [0, mid] 不包含旋转,是一个完整的有序数组,当 nums[0] <= target <= nums[mid] 时,我们就可以让 right = mid - 1,否则我们需要在 [mid + 1, right] 中查找,也就是让 left = mid + 1
  3. 如果 nums[mid] <= nums[right] ,那么说明 [mid, right] 是有序数组,当 target 的值满足 nums[mid] <= target <= nums[right] 时,则我们应该将搜索范围缩小至 [mid + 1, right],否则在 [left, mid - 1] 中寻找。

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1, mid = -1;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}

51、鸡蛋掉落

1、题目描述

给你 k 枚相同的鸡蛋,并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ,满足 0 <= f <= n ,任何从 高于 f 的楼层落下的鸡蛋都会碎,从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作,你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下(满足 1 <= x <= n)。如果鸡蛋碎了,你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎,则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值最小操作次数 是多少?

  • 示例一
1
2
3
4
5
6
7
输入:k = 1, n = 2
输出:2
解释:
鸡蛋从 1 楼掉落。如果它碎了,肯定能得出 f = 0
否则,鸡蛋从 2 楼掉落。如果它碎了,肯定能得出 f = 1
如果它没碎,那么肯定能得出 f = 2
因此,在最坏的情况下我们需要移动 2 次以确定 f 是多少。
  • 示例二
1
2
输入:k = 2, n = 6
输出:3

2、解题思路

  • 当我们只有一个鸡蛋时,此时我们别无他法,只能一层楼一层楼测试,也就是对 [1, n] 进行线性扫描,所以结果为 n
  • 当我们有无限个鸡蛋时,这个时候我们可以使用二分查找法来解决这个问题,每次都将扫描的范围减半,所以结果为 log(n)
  • 使用动态规划解决这个问题,假设有 k 个鸡蛋 n 层楼,我们创建一个二维的 dp 数组 dp[n + 1][k + 1]
  • 确定 dp 数组的含义,其中 dp[i][j] 表示有 i 层楼 k 个鸡蛋时,确定 f 所需要的最小操作数

3、解题代码

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



## 52、多数元素

### 1、题目描述

> 给定一个大小为 *n* 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 **大于** `⌊ n/2 ⌋` 的元素。
>
> 你可以假设数组是非空的,并且给定的数组总是存在多数元素。
>

* 示例一

```java
输入:[3,2,3]
输出:3
  • 示例二
1
2
输入:[2,2,1,1,1,2,2]
输出:2

2、解题思路

  • 使用摩尔投票法解决这道题
  1. 维护一个候选众数 target 和它出现的次数 count ,初始化时 target 为任意值,而 count 为 0
  2. 遍历数组中的所有元素,对于每个元素 num ,在判断 num 之前,如果 count 等于 0 ,那么将 target 的值赋为 num ,随后判断 num:
    1. 如果 num 与 target 的值相等,那么 count ++
    2. 如果 num 与 target 的值不等,那么 count –
  3. 遍历完 nums 后,target 即为整个数组中的众数。

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int majorityElement(int[] nums) {
if (nums.length == 1) return nums[0];
int target = -1, count = 0;
for (int num : nums) {
if (count == 0) {
target = num;
}
if (num == target) {
count++;
} else {
count--;
}
}
return target;
}