AlgorithmClassification

Article Directory
  1. 1. 相关网址
  2. 2. 模版
    1. 2.1. leetcode提交模版
  3. 3. 动态规划
    1. 3.1. 5. 最长回文子串
    2. 3.2. 45. 跳跃游戏 II
    3. 3.3. 22. 括号生成
    4. 3.4. 53. 最大子数组和
    5. 3.5. 4434 二分查找 搜索插入位置
    6. 3.6. 300. 最长递增子序列 (LIS)
    7. 3.7. 926. 将字符串翻转到单调递增
    8. 3.8. 1143. 最长公共子序列 (LCS)
    9. 3.9. 1713. 得到子序列的最少操作次数
    10. 3.10. 91. 解码方法
    11. 3.11. 213. 打家劫舍 II
    12. 3.12. 375. 猜数字大小 II
    13. 3.13. 464. 我能赢吗
      1. 3.13.1. 记忆化搜索(用map或者dp前面的数据) + 状态压缩(1~n,且n比较小,那么用一个二进制表示)
  4. 4. 单调栈
    1. 4.1. 496. 下一个更大元素 I
    2. 4.2. 503. 下一个更大元素 II
    3. 4.3. 456. 132 模式
    4. 4.4. 2104. 子数组范围和
    5. 4.5. 42. 接雨水
  5. 5.
    1. 5.1. 678. 有效的括号字符串
  6. 6. BFS
    1. 6.1. 297. 二叉树的序列化与反序列化
    2. 6.2. 完全二叉树序列化反序列化模版归纳
    3. 6.3. 230. 二叉搜索树中第K小的元素
    4. 6.4. 397. 整数替换
    5. 6.5. 17. 电话号码的字母组合
    6. 6.6. 513. 找树左下角的值
    7. 6.7.
  7. 7. 多源BFS
    1. 7.1. 417. 太平洋大西洋水流问题
    2. 7.2. 1020. 飞地的数量
    3. 7.3. 1765. 地图中的最高点
    4. 7.4. 1162. 地图分析
  8. 8. DFS
    1. 8.1. 297. 二叉树的序列化与反序列化
    2. 8.2. 652. 寻找重复的子树
    3. 8.3. 寻找完全相同的最大高度的子树
    4. 8.4. 965. 单值二叉树
    5. 8.5. 993. 二叉树的堂兄弟节点
  9. 9. 回溯
    1. 9.1. 感觉回溯在很多时候,也可以使用那个 二叉树的层序遍历 的做法。(好像就是广度搜索,另一个是深度 + 回溯)
    2. 9.2. 90. 子集 II
    3. 9.3. 39. 组合总和
    4. 9.4. 40. 组合总和 II
    5. 9.5. 剑指 Offer II 082. 含有重复元素集合的组合
    6. 9.6. 剑指 Offer II 081. 允许重复选择元素的组合
    7. 9.7. 剑指 Offer II 083. 没有重复元素集合的全排列
    8. 9.8. 剑指 Offer II 084. 含有重复元素集合的全排列
    9. 9.9. 797. 所有可能的路径
    10. 9.10. 131. 分割回文串
      1. 9.10.1. 回溯 + 动态规划预处理

算法分类

相关网址

liuyubobobo/Play-with-Algorithm-Interview

liweiwei1419

CodeTop

SharingSource/**LogicStack-LeetCode**宫水三叶

模版

leetcode提交模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package leetcode.editor.cn;

public class MySolution {
public static void main(String[] args) {
Solution solution = new MySolution().new Solution();
// TO TEST...

}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public void method(int x) {

}
}
//leetcode submit region end(Prohibit modification and deletion)
}

动态规划

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
33
34
35
36
37
38
39
40
41
42
43
44
45
// 从长度较短的字符串向长度较长的字符串进行转移的,因此一定要注意动态规划的循环顺序。
// 考虑使用动态规划
// dp[i][j]表示从i到j字符串是否是回文,然后向外扩散,当然边界是长度为1和为2的子串
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
boolean[][] dp = new boolean[len][len];
int ansBegin = 0, ansLen = 1; // 初始化,一个字符

// 考虑边界
if (len < 2) {
return s;
}
for (int i = 0; i < dp.length; i++) {
dp[i][i] = true;
}

// 这个是从小到大的
char[] chars = s.toCharArray();
for (int L = 2; L <= len; L++) {
for (int i = 0; i < len - L + 1; i++) {
int j = i + L - 1;

// 若只有两个
if (chars[i] == chars[j]) {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i+1][j-1];
}
} else {
dp[i][j] = false;
}

// 若是,则看长度是否是最大的
if (dp[i][j] && ansLen < j - i + 1) {
ansBegin = i;
ansLen = j - i + 1;
}
}
}

return s.substring(ansBegin, ansBegin + ansLen);
}
}

45. 跳跃游戏 II

22. 括号生成

53. 最大子数组和

注意:此处用$f(i)$代表以第$i$个数结尾的「连续子数组的最大和」

4434 二分查找 搜索插入位置

这个不是动态规划,是二分,为了下面的 最长递增子序列的 动态+贪心+二分算法 的基础。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 注意,记忆这一个,简单一点
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length-1;

// 返回第一个>=target的
while(left <= right) {
int mid = left + ((right - left) >> 2);
// 本来若nums中全部不同,那么只会有一个相等,那么单独判断下,如果有很多相等,而且要放到相等的后面,那么还是left = mid + 1;
// 一样的,如果要放大相等的最前面,那么等号放到right = right-1中去
if (nums[mid] == target) {
left = mid; // 因为最终left是结果,所以直接这样了,当然此处return mid也是可以的
break;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}

// 因为while中使用的是<=,所以在不是等于的情况下,最终形态left = right + 1
// 即,nums[right] < target < nums[left],所以要插入的位置就是在left处
// 因为left初始化是0,所以插入0的位置也是可以的(right=-1);插入nums.length也是可以的,right没动过的情况下。
return left;
}
}

300. 最长递增子序列 (LIS)

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// 方法一:动态
// 这道题目数据量只有2500,所以可以不用贪心
class Solution {
// 动态规划
// dp[i]代表0~i中最长递增子序列长度
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int ans = 1;

// 边界
Arrays.fill(dp, 1);

for (int i=1; i<nums.length; i++) {
for (int j=0; j<i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ans = Math.max(ans, dp[i]);
}

// 最后的答案是dp[i]中最大的一个
return ans;
}
}

// 方法二:动态+贪心+二分
// 若数据量比如有10e5,那么只用动态O(n^2)会超时,所以需要加入贪心+二分
// 另外再使用一个数组g,g[i]表示长度为i的最长升序子序列的末尾元素的最小值
// 可以知道g[i]其实是单调递增的
// 然后再更新dp[i]的时候,如果nums[i]>g[len],直接加到g数组的末尾;
// 否则,只要找到g中g[k-1] < nums[i] < g[k],第一个比num[i]小的g[k-1],并更新g[k] = nums[i],(因为加入后,k-1是要+1的)
package leetcode.editor.cn;

import java.util.*;

public class P300LongestIncreasingSubsequence {
public static void main(String[] args) {
Solution solution = new P300LongestIncreasingSubsequence().new Solution();
// TO TEST...
System.out.println(solution.lengthOfLIS(new int[]{7,7,7,7,7,7,7}));
}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
// 动态规划
// dp[i]代表0~i中最长递增子序列长度
public int lengthOfLIS(int[] nums) {
int[] g = new int[nums.length+1];
int len = 1;

// 边界
g[len] = nums[0]; // g[1]需要放入

// 递推
for (int i=1; i<nums.length; i++) {
int left = 1, right = len; // g是从1~nums.length的,所以这么写,如果0~len-1就写0-len-1
// 需要找到第一个比nums[i]小的,然后加到这一串子序列上去,这串子序列的长度+1
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (g[mid] == nums[i]) {
left = mid; // 若相同的不能加入,就是mid,否则等号且是放到最右边的话还是left=mid+1
break;
} else if (g[mid] > nums[i]) {
right = mid - 1;
} else {
left = mid + 1;
}
}

// 因为while是有=号的,所以最终形成的是g[right] < nums[i] < g[left]
len = Math.max(left, len);
g[left] = nums[i];
}

// 最后的答案是g的长度
return len;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}

926. 将字符串翻转到单调递增

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
61
62
63
64
/**
* 通过找在s中到最长的不下降子序列,长度为len,然后总len-此len即可
* 注意此处是序列,不需要连续,只要顺序相同
* 由于长度为10e5,所以单纯动态不够,需要加上贪心二分
* g[i]代表最长子序列长度为i的时候,末尾元素的最小值
* 可以得知g[i]是单调递增的
*/
class Solution {
public int minFlipsMonoIncr(String s) {
int n = s.length();
int[] g = new int[n + 1]; // 因为长度可以从1~n
int gLen = 1;

// 边界,最开始长度为1的时候,是第一个字符
g[gLen] = s.charAt(0) - '0';

for (int i = 1; i < s.length(); i++) {
int left = 1, right = gLen; // g的有效数组是,1~size,最两个极端要么加到1,要么加到length+1
int num = s.charAt(i) - '0';
while (left <= right) {
int mid = left + ((right - left) >> 1);
// 本来若nums中全部不同,那么只会有一个相等,那么单独判断下,如果有很多相等,而且要放到相等的后面,那么还是left = mid + 1;
// 一样的,如果要放大相等的最前面,那么等号放到right = right-1中去
if (g[mid] <= num) {
left = mid + 1;
} else {
right = mid - 1;
}
}

g[left] = num; // 找到了g[left-1] < num < g[left]的,num加入left-1 + 1的g中
gLen = Math.max(gLen, left);
}

return n - gLen;
}
}



// 或者动态规划
/**
* 通过动态规划
* dp[i][0]代表i这一位到0需要的次数,那么前面的需要全为0
* dp[i][1]代表i这一位要变到1需要的次数,那么可以是dp[i][0] 和dp[i][1]的比较
* 由于dp[i]只和dp[i-1]有关,所以也可以不用数组,只要维护前面状态的两个数值即可
*/
class Solution {
public int minFlipsMonoIncr(String s) {
int len = s.length();
int[][] dp = new int[len][2];

// 边界
dp[0][0] = s.charAt(0) == '0' ? 0 : 1;
dp[0][1] = s.charAt(0) == '0' ? 1 : 0;

for (int i = 1; i < len; i++) {
dp[i][0] = dp[i-1][0] + s.charAt(0) == '0' ? 0 : 1;
dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]) + s.charAt(0) == '0' ? 1 : 0;
}

return Math.max(dp[len-1][0], dp[len-1][1]);
}
}

1143. 最长公共子序列 (LCS)

注意:当两个数组求公共子序列时(LCS),当有一个数组元素各不相同时,可以转为(LIS)

具体做法是,先map存储target中的元素和下标,然后一个个遍历arr(此处需要存的是元素不重复的下标

若和target有公共元素(与map中是有contains该key),list中存储该公共元素的target中的下标

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
/**
* 使用dp
* dp[i][j]代表text1[0~i-1],text2[0~j-1]的公共最长子序列,注意此处的关系
* 注意此处题目中的子序列不用连续,顺序一样就好
*/
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length(), len2 = text2.length();
int[][] dp = new int[len1+1][len2+1];

// 边界
for (int i = 0; i < len1; i++) {
dp[i][0] = 0;
}
for (int i = 0; i < len2; i++) {
dp[0][i] = 0;
}

// 此处因为dp有0的边界,所以都从1开始,而text都应该从0开始的,所以后面-1
for (int i = 1; i <= len1; i++) {
char c1 = text1.charAt(i-1);
for (int j = 1; j <= len2; j++) {
char c2 = text2.charAt(j-1);
if (c1 == c2) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}

return dp[len1][len2];
}
}

1713. 得到子序列的最少操作次数

参考链接:【面试高频系列】LCS 问题与 LIS 问题的相互关系,以及 LIS 问题的最优解证明

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
/**
* 可以求出公共子序列,然后target的len减去 公共子序列的len即可
* 当两个数组求公共子序列时(LCS),当有一个数组元素各不相同时,可以转为(LIS)
* 具体做法是,先map存储target中的元素和下标,然后一个个遍历arr(此处需要存的是元素不重复的下标)
* 若和target有公共元素(与map中是有contains该key),list中存储该公共元素的target中的下标
* 注意,list中的元素顺序是按照arr来的,而存储的是target的下标
*/
class Solution {
public int minOperations(int[] target, int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> list = new ArrayList<>();

for (int i = 0; i < target.length; i++) {
map.put(target[i], i);
}
for (int i = 0; i < arr.length; i++) { // 按照arr顺序,存储两个共有的元素的,target中的下标
int num = arr[i];
if (map.containsKey(num)) {
list.add(map.get(num));
}
}

// 然后对list进行LIS,最长递增子序列,无重复,不用考虑连续相同
if (list.size() == 0) {
return target.length;
}

int[] g = new int[list.size()+1];
int gLen = 1;

// 边界
g[gLen] = list.get(0);

for (int i = 1; i < list.size(); i++) {
int num = list.get(i);
int left = 1, right = gLen;

while (left <= right) {
int mid = left + ((right - left) >> 1);
if (g[mid] == num) {
left = mid;
break;
} else if (g[mid] > num) {
right = mid - 1;
} else {
left = mid + 1;
}
}

g[left] = num;
gLen = Math.max(gLen, left);
}

return target.length - gLen;
}
}

91. 解码方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int numDecodings(String s) {
// 加个空格哨兵,可以减少前导零
s = ' ' + s;
int n = s.length();
int[] dp = new int[s.length()];

// 边界
dp[0] = 1;

for (int i=1; i<n; i++) {
int a = s.charAt(i) - '0';
int b = (s.charAt(i-1) - '0') * 10 + a; // 在i=1的时候,肯定不满足,所以不会运行到下一个if,所以没关系

if (a >= 1 && a <= 9) {
dp[i] = dp[i-1];
}
if (b >= 10 && b <= 26) {
dp[i] += dp[i-2];
}

}

return dp[n-1];
}
}

213. 打家劫舍 II

一维数组也可以的嗷!

198和213,我觉得还是官方题解比较好一点,建议不要看下面的。

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 {
/**
动态规划
由于有选和不选两种状态,所以需要二维动态规划
还有第一间的问题,第一间选和不选,使用两次动态规划完成
*/
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) { return 0; }
if (n == 1) { return nums[0]; }

int[][] dp = new int[n][n];

// 第一间不选,dp[0][0]和dp[0][1]都是0
for (int i=1; i<=n-2; i++) { // 最后一间,需要根据第一件单独判断
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = dp[i-1][0] + nums[i];
}
// 因为第一间不选,所以最后一间根据最后第二件来就好
// 此处最后一件不选,dp[n-1][0]不用考虑,因为选了之后的考虑了
int a = Math.max(dp[n-2][0]+nums[n-1], dp[n-2][1]);

// 第一件可以选,然后最后的判断只要判断选的就好了,因为不选的已经在上面了
dp[0][0] = 0; dp[0][1] = nums[0];
for (int i=1; i<=n-2; i++) { // 最后一间,需要根据第一件单独判断
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = dp[i-1][0] + nums[i];
}
// 第一件选,最后一件肯定不选
int b = Math.max(dp[n-2][0], dp[n-2][1]);

return Math.max(a, b);
}
}

375. 猜数字大小 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
// 使用动态规划
// dp[i][j]表示i到j之间能选择的确保的最小金额
public int getMoneyAmount(int n) {
int[][] dp = new int[n+2][n+2]; // 这里+1还不够,因为下面r最大为nn,然后i+1为n+1,其实要到[n+1]了

// 边界,全为0即可

// 然后dp,可以看出需要从小的,到大的,所以从lenlen=2开始
for (int step=2; step<=n; step++) {
for (int l=1; l<=n-step+1; l++) {
int r = l + step - 1;

dp[l][r] = Integer.MAX_VALUE;
for (int i=l; i<=r; i++) { // 遍历l~r中的所有
int cur = Math.max(dp[l][i-1], dp[i+1][r]) + i;
dp[l][r] = Math.min(cur, dp[l][r]);
}
}
}

return dp[1][n];
}
}

464. 我能赢吗

记忆化搜索(用map或者dp前面的数据) + 状态压缩(1~n,且n比较小,那么用一个二进制表示)

单调栈

一但要求下一个更大的元素,就是用单调栈解,力扣题库相似的题目都是这个解法。

注意,单调栈从前往后 和 从后往前,栈里面最后的元素不一样,而且,while里面的内容也有点区别。

注意下面496和503的两种写法,都是找下一个最大的,一个从前往后找,一个从后往前找,但是考虑的逻辑就不一样了。

从前往后的话,若找下一个大的,那么从栈底到栈顶也是从大到小(一样),但是ans给值情况从前往后在while里面,从后往前在while下面,while下面的话因为每个for存一个是全的,但是需要考虑栈底没有元素的时候存什么;而从前往后的再while里面所以存的时候肯定栈里面有数据而且ans不能保存存完全,所以最开始的时候需要给数组一个全部的初始值。

自己总结的规律:①不论是从左往右还是从右往左,不论是求比当前值小的左边第一个,还是比当前值小的右边的第一个,如果是小的,那么栈里面从底部到上面就是从小到大的,放入的时候如果栈最上面的比当前的大,那么就拿出来。

然后再考虑,是在while里面放呢,还是在while的外面for的里面放。

其实这个也有规律,②要求比当前值小的左边的,那么从左往右就是放在while外面for里面,当前值小的右边的第一个,那么从右边往前。③注意等号问题

所以以后分两步:①要求小的,那么单调栈从下到上是从小到大;②求当前值的左边第一个小的,那么从左往右,就可以一个个看。

496. 下一个更大元素 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 下一个最大元素,使用单调栈
*/
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
// 现将nums2倒序遍历,越底下越大
Deque<Integer> stack = new ArrayDeque<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = nums2.length-1; i >= 0; i--) {
int num = nums2[i];
while (!stack.isEmpty() && stack.peek() <= num) {
stack.pop();
}

map.put(num, stack.isEmpty() ? -1 : stack.peek()); // nums2中当前的值的下一个最大值
stack.push(num);
}

int[] ans = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
ans[i] = map.get(nums1[i]);
}

return ans;
}
}

503. 下一个更大元素 II

数组中无重复元素的话,可以map存储值,但是此处只能存下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 下一个更大的元素,使用单调栈
* 注意,此处一个数组,存下标,本来数组中无重复元素的话,可以map存储值,但是此处只能存下标
* 因为循环,可以把数组拉成2倍,但是此处不需要拉伸,直接循环取模
*/
class Solution {
public int[] nextGreaterElements(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>();
int[] ans = new int[nums.length];

Arrays.fill(ans, -1);
int n = nums.length;
for (int i = 0; i < 2 * n - 1; i++) {
int num = nums[i % n];
while (!stack.isEmpty() && nums[stack.peek()] < num) {
ans[stack.pop()] = nums[i % n];
}
stack.push(i % n);
}

return ans;
}
}

456. 132 模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 是有后面的大小的问题,可考虑单调栈
*/
class Solution {
public boolean find132pattern(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>();

int numsk = Integer.MIN_VALUE;
// numsk 是ijk,numsk是中间第二大的那个值
// 从后往前遍历
// numsk看作是所有出栈元素中最大的,因为出栈元素(单调递减排,小于当前num的要出栈),所以出栈元素的话,栈里面肯定有比他大的numsj(而且j下标肯定是在k前面)
for (int i = nums.length-1; i >= 0; i--) {
// 如果此时找到一个nums[i] < numsk
// 则因为从后往前i<j<k,且numsi < numsk < numsj
if (nums[i] < numsk) { return true; }
while (!stack.isEmpty() && stack.peek() < nums[i]) {
numsk = Math.max(numsk, stack.pop());
}
stack.push(nums[i]);
}

return false;
}
}

2104. 子数组范围和

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
/**
* 使用单调栈,存下标
* 注意此处从后往前判断的时候,不存在需要存下标n
* 以及相等的时候,若下标小,算其逻辑小于
*/
class Solution {
public long subArrayRanges(int[] nums) {
Deque<Integer> minStack = new ArrayDeque<>();
Deque<Integer> maxStack = new ArrayDeque<>();
int n = nums.length;
int[] minLeft = new int[n];
int[] maxLeft = new int[n];
int[] minRight = new int[n];
int[] maxRight = new int[n];

for (int i = 0; i < nums.length; i++) {
int num = nums[i];
while (!minStack.isEmpty() && nums[minStack.peek()] > num) {
minStack.pop();
}
minLeft[i] = minStack.isEmpty() ? -1 : minStack.peek();
minStack.push(i);

while (!maxStack.isEmpty() && nums[maxStack.peek()] <= num) {
maxStack.pop();
}
maxLeft[i] = maxStack.isEmpty() ? -1 : maxStack.peek();
maxStack.push(i);
}

minStack.clear();
maxStack.clear();
for (int i = nums.length-1; i >= 0; i--) {
int num = nums[i];
while (!minStack.isEmpty() && nums[minStack.peek()] >= num) {
minStack.pop();
}
minRight[i] = minStack.isEmpty() ? n : minStack.peek();
minStack.push(i);

while (!maxStack.isEmpty() && nums[maxStack.peek()] < num) {
maxStack.pop();
}
maxRight[i] = maxStack.isEmpty() ? n : maxStack.peek();
maxStack.push(i);
}

long ans = 0;
for (int i = 0; i < n; i++) {
ans += (long) (maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
ans -= (long) (minRight[i] - i) * (i - minLeft[i]) * nums[i];
}

return ans;
}
}

42. 接雨水

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
/**
* 使用单调栈
* 单调递减排,然后若当前的大于栈顶,则证明可以接雨水
*/
class Solution {
public int trap(int[] height) {
Deque<Integer> stack = new ArrayDeque<>();
int ans = 0;

for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) { // 单调递减排
int top = stack.pop();
if (stack.isEmpty()) { // 如果空了,接不了
break;
}

int left = stack.peek(); // 此时left top i三个能接雨水
int length = Math.min(height[left], height[i]) - height[top];
int width = i - left - 1;
ans += width * length;
}
stack.push(i);
}

return ans;
}
}

678. 有效的括号字符串

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
class Solution {
/**
使用栈来做,
由于还有*,使用两个栈表
*/
public boolean checkValidString(String s) {
// 一个存储括号,另外一个存储*
Deque<Integer> stack1 = new ArrayDeque<>();
Deque<Integer> stack2 = new ArrayDeque<>();

char[] chars = s.toCharArray();
for (int i=0; i<chars.length; i++) {
char c = chars[i];

if (c == '(') {
stack1.offerLast(i);
} else if (c == '*') { // 先把右括号弄完,再来处理*号
stack2.offerLast(i);
} else {
if (!stack1.isEmpty()) {
stack1.pollLast(); // 减去一个左括号
} else if (!stack2.isEmpty()) { // 没有左括号,加上星号
stack2.pollLast();
} else {
return false;
}
}
}

// 若能到这里,右边括号肯定没有了
// 所以把左括号和星号匹配掉,但是做括号一定要在星号前面,所以stack都要存储下标
// 剩余*是没关系的,一定要把左边括号匹配完全
while (!stack1.isEmpty()) {
int leftIndex = stack1.pollLast();
if (stack2.isEmpty()) {
return false;
}

int rightIndex = stack2.pollLast();
if (leftIndex >= rightIndex) {
return false;
}
}

return true;
}
}

BFS

对于层序遍历,使用BFS

对于层序遍历的序列化和非序列化,使用BFS;当然DFS先序遍历的,也可以。

297. 二叉树的序列化与反序列化

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
61
public class Codec {
/**
此处使用层序遍历实现,但是不是完全的二叉树的序列
*/
// Encodes a tree to a single string.
TreeNode emptyNode = new TreeNode(-2000);
public String serialize(TreeNode root) {
if (root == null) {
return "";
}

StringBuffer str = new StringBuffer();
Deque<TreeNode> queue = new ArrayDeque<>();

queue.offerLast(root);
while(!queue.isEmpty()) {
TreeNode node = queue.pollFirst();
// 此处为了让空的时候,出来null而不是-2000
if (node == emptyNode) {
str.append("null,");
continue; // 这是与下面的完全二叉树不同的地方
}
str.append(String.valueOf(node.val) + ",");
queue.offerLast(node.left == null ? emptyNode : node.left);
queue.offerLast(node.right == null ? emptyNode : node.right);
}
str.deleteCharAt(str.length() - 1); // 注意,此处删除最后一个逗号

return str.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("")) {
return null;
}

String[] strs = data.split(",");
Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
queue.offerLast(root); // 注意,比如此处不加入,那么下面没有判断isempty的情况下,pollFirst拿到的是null

for (int i=1; i<strs.length; i += 2) { // 数组中的拿完即可
TreeNode node = queue.pollFirst();
// 数组中后面的两个,正好是其左右节点
// null的话不用赋值,因为节点本身创建出来,他的左右就是null
if (!strs[i].equals("null")) {
TreeNode leftNode = new TreeNode(Integer.parseInt(strs[i]));
node.left = leftNode;
queue.offerLast(leftNode);
}
if (!strs[i+1].equals("null")) {
TreeNode rightNode = new TreeNode(Integer.parseInt(strs[i+1]));
node.right = rightNode;
queue.offerLast(rightNode);
}
}

return root;
}
}

完全二叉树序列化反序列化模版归纳

leetcode中的模版方法中,树直接给TreeNode的,但是如果机试输入的是二叉树的层序遍历,那么需要自己反序列化成树。

注意,下面的序列化和反序列化,是按照完全二叉树的层序遍历来的。

即:序列化时,n层2^n-1个,null全部算进去的;不过反序列化时,除了最后一层,上面层的都是满的,上面层就算下面两个都是null的null,也要写,这是与上面那个序列化与反序列化的区别,上面那个在2997中不会超内存,这个在297中会。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
package leetcode.editor.cn;

/**
* @author Jcwang
*/

import java.util.*;

public class TemplateTreeDeserialize {
public static void main(String[] args) {
TemplateTreeDeserialize mySolution = new TemplateTreeDeserialize();
Solution solution = mySolution.new Solution();
// TO TEST...
TreeUtil treeUtil = mySolution.new TreeUtil();

System.out.println(solution.solve(treeUtil.deserialize("xxx,x,xxx,null,x")));
}

public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}

public final class TreeUtil {
public int getHeight(TreeNode node, int height) {
if (node == null) {
return height;
}

int leftHeight = getHeight(node.left, height + 1);
int rightHeight = getHeight(node.right, height + 1);
return Math.max(leftHeight, rightHeight);
}

TreeNode emptyNode = new TreeNode(-2000);

// Decodes your encoded data to tree.
// 序列化的时候,是完全的2的n-1次方的,但是此处非序列化的时候不一定2的n-1次方的,个数可能少一点
public TreeNode deserialize(String data) {
if (data.equals("")) {
return null;
}

String[] strs = data.split(",");
TreeNode[] nodes = new TreeNode[strs.length];
for (int i = 0; i < strs.length; i++) {
nodes[i] = strs[i].equals("null") ? emptyNode : new TreeNode(Integer.parseInt(strs[i]));
}

for (int i = 0; i < nodes.length / 2; i++) { // 0~n/2之间是有子节点的
if (nodes[i] == emptyNode) {
continue;
} // 虽然不加也没事儿,但是避免一些无用的计算
int leftIndex = 2 * i + 1; // 注意左边是2i+1,因为是从0开始的,若从1开始就是2i和2i+1
int rightIndex = 2 * i + 2;

if (nodes[leftIndex] == emptyNode) {
nodes[i].left = null;
} else {
nodes[i].left = nodes[leftIndex];
}
if (rightIndex < nodes.length) { // 注意这里面可能会出边界,最后只有一个左子树
if (nodes[rightIndex] == emptyNode) {
nodes[i].right = null;
} else {
nodes[i].right = nodes[rightIndex];
}
}
}

return nodes[0];
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}

StringBuilder str = new StringBuilder();
Deque<TreeNode> queue = new ArrayDeque<>();

// 此处使用高度,表明序列到完全二叉树就可以了,在下面那一行全为null的不会再序列化了
int allNum = (int) Math.pow(2, getHeight(root, 0)) - 1, count = 0;
queue.offerLast(root);
while (!queue.isEmpty()) {

TreeNode node = queue.pollFirst();
// 此处为了让空的时候,出来null而不是-2000
if (node == emptyNode) { // 此处只是比较引用,所以那个值在范围内也没事
str.append("null,"); // 此处让emptyNode之后还是能再挂emptyNode,因为要完全二叉树
} else {
str.append(node.val + ",");
}
if (++count >= allNum) {
break;
} // 达到了完全二叉树了

queue.offerLast(node.left == null ? emptyNode : node.left);
queue.offerLast(node.right == null ? emptyNode : node.right);
}
str.deleteCharAt(str.length() - 1); // 注意,此处删除最后一个逗号

return str.toString();
}
}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int solve(TreeNode root) {
return root.val;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}

// // 另外一个使用队列的deserialize算法
// public TreeNode deserialize(String data) {
// if (data.equals("")) {
// return null;
// }
//
// String[] strs = data.split(",");
// Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
// TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
// queue.offerLast(root); // 注意,比如此处不加入,那么下面没有判断isempty的情况下,pollFirst拿到的是null
// int count = 0;
// for (int i=1; i<strs.length; i += 2) { // strs数组中的拿完即可
// TreeNode node = queue.pollFirst();
// // 注意,如果是类似只有左子树,四层的情况,那么第一个左节点的右节点的下面都是空,不把emptyNode放入会有问题的
// // 数据大了会超出内存的
// // if (emptyNode == node) {
// // continue;
// // }
//
// // 数组中后面的两个,正好是其左右节点
// // null的话不用赋值,因为节点本身创建出来,他的左右就是null
// if (!strs[i].equals("null")) {
// TreeNode leftNode = new TreeNode(Integer.parseInt(strs[i]));
// node.left = leftNode;
// queue.offerLast(leftNode);
// } else {
// queue.offerLast(emptyNode);
// }
// if (i+1 < strs.length && !strs[i+1].equals("null")) { // 此处需要判断下右节点是否出界
// TreeNode rightNode = new TreeNode(Integer.parseInt(strs[i+1]));
// node.right = rightNode;
// queue.offerLast(rightNode);
// } else {
// queue.offerLast(emptyNode);
// }
//
// // 297序列化与反序列化好想还是会超时
// count += 2;
// if (count >= strs.length) { break; }
// }
//
// return root;
// }
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
// DFS
public class Codec {

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
String a = serialize1(root);
System.out.println(a);
return a;
}

public String serialize1(TreeNode node) {
if (node == null) {
return "null";
}

// 注意此处right后面不需要逗号
return node.val + "," + serialize1(node.left) + "," + serialize1(node.right);
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] datas = data.split(",");
List<String> list = new ArrayList(Arrays.asList(datas));

return deserialize1(list);
}

public TreeNode deserialize1(List<String> list) {
if (list.get(0).equals("null")) {
list.remove(0);
return null;
}

TreeNode node = new TreeNode(Integer.valueOf(list.get(0)));
list.remove(0);
node.left = deserialize1(list);
node.right = deserialize1(list);

return node;
}
}

230. 二叉搜索树中第K小的元素

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
package leetcode.editor.cn;

import com.sun.source.tree.Tree;

import java.util.*;

public class P230KthSmallestElementInABst {
public static void main(String[] args) {
P230KthSmallestElementInABst mySolution = new P230KthSmallestElementInABst();
Solution solution = mySolution.new Solution();
// TO TEST...
TreeUtil treeUtil = mySolution.new TreeUtil();
System.out.println(solution.kthSmallest(treeUtil.deserialize("3,1,4,null,2"), 1));
}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int kthSmallest(TreeNode root, int k) {
int curIndex = 0;
Deque<TreeNode> stack = new ArrayDeque<>(); // 中序遍历用的是栈
while (root != null || !stack.isEmpty()) {
while (root != null) { // 中序遍历先遍历左边,需要把最左边的加入
stack.offerLast(root);
root = root.left;
}
TreeNode node = stack.pollLast();
if (++curIndex == k) {
return node.val;
}
root = node.right;
}

return -1;
}
}
//leetcode submit region end(Prohibit modification and deletion)

public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}

public final class TreeUtil {
public int getHeight(TreeNode node, int height) {
if (node == null) {
return height;
}

int leftHeight = getHeight(node.left, height + 1);
int rightHeight = getHeight(node.right, height + 1);
return Math.max(leftHeight, rightHeight);
}

TreeNode emptyNode = new TreeNode(-2000);

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("")) {
return null;
}

String[] strs = data.split(",");
TreeNode[] nodes = new TreeNode[strs.length];
for (int i = 0; i < strs.length; i++) {
nodes[i] = strs[i].equals("null") ? emptyNode : new TreeNode(Integer.parseInt(strs[i]));
}

for (int i = 0; i < nodes.length / 2; i++) { // 0~n/2之间是有子节点的
if (nodes[i] == emptyNode) {
continue;
} // 虽然不加也没事儿,但是避免一些无用的计算
int leftIndex = 2 * i + 1; // 注意左边是2i+1,因为是从0开始的,若从1开始就是2i和2i+1
int rightIndex = 2 * i + 2;

if (nodes[leftIndex] == emptyNode) {
nodes[i].left = null;
} else {
nodes[i].left = nodes[leftIndex];
}
if (rightIndex < nodes.length) { // 注意这里面可能会出边界,最后只有一个左子树
if (nodes[rightIndex] == emptyNode) {
nodes[i].right = null;
} else {
nodes[i].right = nodes[rightIndex];
}
}
}

return nodes[0];
}

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}

StringBuilder str = new StringBuilder();
Deque<TreeNode> queue = new ArrayDeque<>();

// 此处使用高度,表明序列到完全二叉树就可以了,在下面那一行全为null的不会再序列化了
int allNum = (int) Math.pow(2, getHeight(root, 0)) - 1, count = 0;
queue.offerLast(root);
while (!queue.isEmpty()) {

TreeNode node = queue.pollFirst();
// 此处为了让空的时候,出来null而不是-2000撒打算打算阿斯顿爱上啊打算打算
if (node == emptyNode) { // 此处只是比较引用,所以那个值在范围内也没事
// str.append("null,");
} else {
str.append(node.val + ",");
}
if (++count >= allNum) {
break;
} // 达到了完全二叉树了

queue.offerLast(node.left == null ? emptyNode : node.left);
queue.offerLast(node.right == null ? emptyNode : node.right);
}
str.deleteCharAt(str.length() - 1); // 注意,此处删除最后一个逗号

return str.toString();
}
}
}

397. 整数替换

注意第二个算法中,用了一个hashmap,记录n到这个数字num的当最小次数,可以减少重复次数

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
61
62
63
64
65
66
67
68
69
70
71
// 我自己的方法,使用了层级的概念
class Solution {
/**
使用BFS,每一层要么偶数的一个,要么奇数的两个,然后每过一层记录+1
第一个到达1的层就是最小的
*/
public int integerReplacement(int n) {
if (n == 1) {
return 0;
}

Deque<Long> queue = new ArrayDeque<Long>();
int minNum = 0;

queue.offerLast((long)n);
while (!queue.isEmpty()) {
minNum += 1;
int size = queue.size();
for (int i=0; i<size; i++) {
long num = queue.pollFirst();
if (num % 2 == 0) {
num /= 2;
if (num == 1) {
return minNum;
} else {
queue.offerLast(num);
}
} else {
if (num - 1 == 1) {
return minNum;
} else {
queue.offerLast(num - 1);
}
if (num + 1 == 1) {
return minNum;
} else {
queue.offerLast(num + 1);
}
}
}
}

return minNum; // 此处肯定不会到达
}
}

// 三叶的方法,没有使用层这个概念
// 同样使用「哈希表」记录步数,防止重复处理。
// 记录n到这个数字num的当最小次数
class Solution {
public int integerReplacement(int n) {
if (n == 1) return 0;
Map<Long, Integer> map = new HashMap<>();
Deque<Long> d = new ArrayDeque<>();
d.addLast(n * 1L);
map.put(n * 1L, 0);
while (!d.isEmpty()) {
long t = d.pollFirst();
int step = map.get(t);
long[] ns = t % 2 == 0 ? new long[]{t / 2} : new long[]{t + 1, t - 1};
for (long x : ns) {
if (x == 1) return step + 1;
if (!map.containsKey(x)) {
map.put(x, step + 1);
d.addLast(x);
}
}
}
return -1;
}
}

17. 电话号码的字母组合

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 {
public List<String> letterCombinations(String digits) {
// 先用类似于层序遍历的做法做一下,因为长度最多为4,所以不会超时,但是其实效率还是比较低的
Deque<String> queue = new ArrayDeque<String>();

if (digits.length() == 0) {
return new ArrayList<String>();
}

// 第一个,自己放入
char[][] mapping = new char[][]{{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'}, {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'}, {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}};
for (char c: mapping[digits.charAt(0) - '2']) {
queue.offerLast("" + c);
}

for (int i=1; i<digits.length(); i++) {
int size = queue.size();

for (int j=0; j<size; j++) {
String temp = queue.pollFirst();
for (char c: mapping[digits.charAt(i) - '2']) {
queue.offerLast(temp + c);
}
}
}

List<String> ans = new ArrayList<>();
while (!queue.isEmpty()) {
ans.add(queue.pollFirst());
}

return ans;
}
}

513. 找树左下角的值

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
用广度,每一次记录循环第一个
*/
public int findBottomLeftValue(TreeNode root) {
TreeNode ansNode = null;
Deque<TreeNode> queue = new ArrayDeque<>();

queue.offerLast(root);
while (!queue.isEmpty()) {
ansNode = queue.peekFirst();

int size = queue.size();
for (int i=0; i<size; i++) {
TreeNode temp = queue.pollFirst();
if (temp.left != null) { queue.offerLast(temp.left); }
if (temp.right != null) { queue.offerLast(temp.right); }
}
}

return ansNode.val;
}
}

// 或者层序遍历,然后从右边往左边放,最后一个就是,这样的话不需要那个for循环了,因为用不到。
class Solution {
public int findBottomLeftValue(TreeNode root) {
int ret = 0;
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode p = queue.poll();
if (p.right != null) {
queue.offer(p.right);
}
if (p.left != null) {
queue.offer(p.left);
}
ret = p.val;
}
return ret;
}
}

多源BFS

417. 太平洋大西洋水流问题

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
61
class Solution {
/**
* 从四周往里面,然后四周的点每个都可能流出,所以多源BFS
*/
int m, n;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
m = heights.length; n = heights[0].length;
boolean[][] pac = new boolean[m][n];
boolean[][] atl = new boolean[m][n];

// 初始化四周
for (int i = 0; i < m; i++) {
pac[i][0] = true;
bfs(heights, pac, new int[]{i, 0});
atl[i][n-1] = true;
bfs(heights, atl, new int[]{i, n-1});
}
for (int i = 0; i < n; i++) {
pac[0][i] = true;
bfs(heights, pac, new int[]{0, i});
atl[m-1][i] = true;
bfs(heights, atl, new int[]{m-1, i});
}

List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pac[i][j] && atl[i][j]) {
List<Integer> pos = new ArrayList<>();
pos.add(i);
pos.add(j);
list.add(pos);
}
}
}

return list;
}

int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public void bfs(int[][] heights, boolean[][] ocean, int[] pos) {
Deque<int[]> queue = new ArrayDeque<>();

queue.offerLast(pos);
while (!queue.isEmpty()) {
int[] cur = queue.pollFirst();
int x = cur[0], y = cur[1];

for (int i = 0; i < 4; i++) {
int newX = x + dir[i][0];
int newY = y + dir[i][1];
if (newX >= 0 && newX<m && newY >= 0 && newY < n &&
heights[newX][newY] >= heights[x][y] &&
!ocean[newX][newY]) {
ocean[newX][newY] = true;
queue.offerLast(new int[]{newX, newY});
}
}
}
}
}

1020. 飞地的数量

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
61
62
63
64
65
class Solution {
/**
把能走通的都变成true
然后从四周往里面延伸
需要多源BFS
*/
int[][] grid;
int m, n;
int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int numEnclaves(int[][] grid) {
this.grid = grid;
this.m = grid.length;
this.n = grid[0].length;

for (int i=0; i<m; i++) {
if (grid[i][0] == 1) {
bfs(new int[]{i, 0});
}
if (grid[i][n-1] == 1) {
bfs(new int[]{i, n-1});
}
}
for (int i=0; i<n; i++) {
if (grid[0][i] == 1) {
bfs(new int[]{0, i});
}
if (grid[m-1][i] == 1) {
bfs(new int[]{m-1, i});
}
}

int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
ans += 1;
}
}
}

return ans;
}

public void bfs(int[] pos) {
Deque<int[]> queue = new ArrayDeque<>();

grid[pos[0]][pos[1]] = 0;
queue.offerLast(pos);
while (!queue.isEmpty()) {
int[] newPos = queue.pollFirst();
int x = newPos[0], y = newPos[1];

for (int[] dir: dirs) {
int newX = x + dir[0];
int newY = y + dir[1];

if (newX >= 0 && newX < m && newY >= 0 && newY < n &&
grid[newX][newY] == 1) {
grid[newX][newY] = 0;
queue.offerLast(new int[]{newX, newY});
}
}
}
}
}

1765. 地图中的最高点

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
/**
自己的想法,从水域出发
多源BFS
注意,这个多源是一下子水域的全部加到队列,先0,在1,在2这样,而不是先把一个弄完
注意,此处是让ans先为-1代表没有访问过,自然数就代表访问过了,就减少了visited这个数组
*/
class Solution {
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public int[][] highestPeak(int[][] isWater) {
int m = isWater.length, n = isWater[0].length;
int[][] ans = new int[m][n];
for (int i = 0; i < m; ++i) {
Arrays.fill(ans[i], -1); // -1 表示该格子尚未被访问过
}
Queue<int[]> queue = new ArrayDeque<int[]>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (isWater[i][j] == 1) {
ans[i][j] = 0;
queue.offer(new int[]{i, j}); // 将所有水域入队
}
}
}
while (!queue.isEmpty()) {
int[] p = queue.poll();
for (int[] dir : dirs) {
int x = p[0] + dir[0], y = p[1] + dir[1];
if (0 <= x && x < m && 0 <= y && y < n && ans[x][y] == -1) {
ans[x][y] = ans[p[0]][p[1]] + 1;
queue.offer(new int[]{x, y});
}
}
}
return ans;
}
}

1162. 地图分析

麻麻的,官方题解这样做也超时。。。🙈

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
61
62
63
64
65
66
67
68
class Solution {
/**
考虑多源BFS
曼哈顿距离,BFS的深度
注意,在每一个BFS中,需要判断是否便利过,这样速度更快
然后,ans初始值等于-1,然后后面没有数据,就是-1了.(bfs中没有找到也要return-1)
*/
int[][] grid;
int m, n;
int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

public int maxDistance(int[][] grid) {
m = grid.length;
n = grid[0].length;
this.grid = grid;

int ans = -1;

for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (grid[i][j] == 0) {
ans = Math.max(bfs(new int[]{i, j}), ans);
}
}
}

return ans;
}

public int bfs(int[] pos) {
boolean[][] vis = new boolean[m][n];
Deque<int[]> queue = new ArrayDeque<>();
queue.offerLast(pos);
vis[pos[0]][pos[1]] = true;

int dis = 0;
while (!queue.isEmpty()) {
dis += 1;

int size = queue.size();
for (int i=0; i<size; i++) {
int[] newPos = queue.pollFirst();

int x = newPos[0];
int y = newPos[1];

for (int[] dir: dirs) {
int newX = x + dir[0];
int newY = y + dir[1];

if (newX >= 0 && newX < m &&
newY >= 0 && newY < n &&
!vis[newX][newY]) {

queue.offerLast(new int[]{newX, newY});
vis[newX][newY] = true;
if (grid[newX][newY] == 1) {
return dis; // 找到陆地,返回
}
}
}
}

}

return -1;
}
}

DFS

297. 二叉树的序列化与反序列化

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
public class Codec {

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
List<String> list = new ArrayList<>();
dfs(root, list);
System.out.println(list.toString());
return list.toString();
}
public void dfs(TreeNode node, List<String> list) {
if (node == null) {
list.add("null");
return;
}

list.add(String.valueOf(node.val));
dfs(node.left, list);
dfs(node.right, list);
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String a = data.substring(1, data.length()-1);
String[] strs = a.split(", ");
List<String> list = new ArrayList<String>(Arrays.asList(strs));
System.out.println(list.get(0));
return DeserializeDfs(list);
}
public TreeNode DeserializeDfs(List<String> list) {
if (list.get(0).equals("null")) {
list.remove(0);
return null;
}

TreeNode node = new TreeNode(Integer.parseInt(list.get(0)));
list.remove(0);
node.left = DeserializeDfs(list);
node.right = DeserializeDfs(list);

return node;
}

}

652. 寻找重复的子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 只需要序列化,注意这里面DFS的序列化,写得比我上面的好很多,下次记得用这里面的
// 每得到的一次结果,放入map中
// 若次数等于2的时候,加入
class Solution {
Map<String, Integer> count;
List<TreeNode> ans;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
count = new HashMap();
ans = new ArrayList();
collect(root);
return ans;
}

public String collect(TreeNode node) {
if (node == null) return "#";
String serial = node.val + "," + collect(node.left) + "," + collect(node.right);
count.put(serial, count.getOrDefault(serial, 0) + 1);
if (count.get(serial) == 2)
ans.add(node);
return serial;
}
}

寻找完全相同的最大高度的子树

在一棵二叉树中找出完全相同的两颗子树()子树层数>=2,若存在多棵,返回层数最大的,不存在返回-1

未验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
package leetcode.editor.cn;

/**
* 在一棵二叉树中找出完全相同的两颗子树()子树层数>=2
* 若存在多棵,返回层数最大的,不存在返回-1
*/

import java.util.*;

public class 寻找完全相同的子树 {
public static void main(String args[]) {
寻找完全相同的子树 mySolution = new 寻找完全相同的子树();
Solution solution = mySolution.new Solution();
TreeUtil treeUtil = mySolution.new TreeUtil();
// System.out.println(solution.findMaxDepthTree(treeUtil.deserialize("1,2,3,1,null,2,null,null,null,null,null,1,null,null,null")));
System.out.println(solution.findMaxDepthTree(treeUtil.deserialize("1,4,3,1,null,2,null,null,null,null,null,1,null,null,null")));
}

public class Solution {
Map<String, Integer> map; // 第一个是序列化树,第二个是出现的次数
int maxDepth = 1; // 最大深度的子树,表示后面的一定要大于1,则至少是2
TreeNode nullNode = new TreeNode(-2000);
TreeNode ans = nullNode;
public String findMaxDepthTree(TreeNode root) {
map = new HashMap<>();
dfs(root);
if (nullNode == ans) { return "-1"; }

return new TreeUtil().serialize(ans);
}

// 序列化,也就是最后的输出了,不需要上面的编码
public String dfs(TreeNode node) {
// 注意,此处用的先序遍历,如果也是层序遍历的化,可以直接当作结果用了
// 但是子树相同,貌似层序是不行的吧。
if (node == null) { return "null"; }
String serial = node.val + "," + dfs(node.left) + "," + dfs(node.right);
map.put(serial, map.getOrDefault(serial, 0) + 1);
if (map.get(serial) >= 2) {
int height = new TreeUtil().getHeight(node, 0);
if (maxDepth < height) {
maxDepth = height;
ans = node;
}
}

return serial;
}
}

public class TreeNode {
int val;
TreeNode left;
TreeNode right;

public TreeNode(int val) {
this.val = val;
}

public TreeNode() {

}
}

public final class TreeUtil {
public int getHeight(TreeNode node, int height) {
if (node == null) {
return height;
}

int leftHeight = getHeight(node.left, height + 1);
int rightHeight = getHeight(node.right, height + 1);
return Math.max(leftHeight, rightHeight);
}

TreeNode emptyNode = new TreeNode(-2000);

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("")) {
return null;
}

String[] strs = data.split(",");
TreeNode[] nodes = new TreeNode[strs.length];
for (int i = 0; i < strs.length; i++) {
nodes[i] = strs[i].equals("null") ? emptyNode : new TreeNode(Integer.parseInt(strs[i]));
}

for (int i = 0; i < nodes.length / 2; i++) { // 0~n/2之间是有子节点的
if (nodes[i] == emptyNode) {
continue;
} // 虽然不加也没事儿,但是避免一些无用的计算
int leftIndex = 2 * i + 1; // 注意左边是2i+1,因为是从0开始的,若从1开始就是2i和2i+1
int rightIndex = 2 * i + 2;

if (nodes[leftIndex] == emptyNode) {
nodes[i].left = null;
} else {
nodes[i].left = nodes[leftIndex];
}
if (rightIndex < nodes.length) { // 注意这里面可能会出边界,最后只有一个左子树
if (nodes[rightIndex] == emptyNode) {
nodes[i].right = null;
} else {
nodes[i].right = nodes[rightIndex];
}
}
}

return nodes[0];
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}

StringBuilder str = new StringBuilder();
Deque<TreeNode> queue = new ArrayDeque<>();

// 此处使用高度,表明序列到完全二叉树就可以了,在下面那一行全为null的不会再序列化了
int allNum = (int) Math.pow(2, getHeight(root, 0)) - 1, count = 0;
queue.offerLast(root);
while (!queue.isEmpty()) {

TreeNode node = queue.pollFirst();
// 此处为了让空的时候,出来null而不是-2000撒打算打算阿斯顿爱上啊打算打算
if (node == emptyNode) { // 此处只是比较引用,所以那个值在范围内也没事
// str.append("null,");
} else {
str.append(node.val + ",");
}
if (++count >= allNum) {
break;
} // 达到了完全二叉树了

queue.offerLast(node.left == null ? emptyNode : node.left);
queue.offerLast(node.right == null ? emptyNode : node.right);
}
str.deleteCharAt(str.length() - 1); // 注意,此处删除最后一个逗号

return str.toString();
}
}
}

965. 单值二叉树

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package leetcode.editor.cn;

import java.util.*;

public class P965UnivaluedBinaryTree {
public static void main(String[] args) {
Solution solution = new P965UnivaluedBinaryTree().new Solution();
TreeUtil treeUtil = new P965UnivaluedBinaryTree().new TreeUtil();
// TO TEST...
// System.out.println(solution.isUnivalTree(treeUtil.deserialize("1,1,1,1,1,null,1")));
System.out.println(solution.isUnivalTree(treeUtil.deserialize("2,2,2,5,2")));
}

//leetcode submit region begin(Prohibit modification and deletion)

class Solution {
int val = 0;
public boolean isUnivalTree(TreeNode root) {
val = root.val;
return dfs(root);
}

public boolean dfs(TreeNode node) {
if (node == null) { return true; }


if (node.val != val) {
return false;
}
return dfs(node.left) && dfs(node.right);
}
}
//leetcode submit region end(Prohibit modification and deletion)

public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}

public final class TreeUtil {
public int getHeight(TreeNode node, int height) {
if (node == null) {
return height;
}

int leftHeight = getHeight(node.left, height + 1);
int rightHeight = getHeight(node.right, height + 1);
return Math.max(leftHeight, rightHeight);
}

TreeNode emptyNode = new TreeNode(-2000);

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("")) {
return null;
}

String[] strs = data.split(",");
TreeNode[] nodes = new TreeNode[strs.length];
for (int i = 0; i < strs.length; i++) {
nodes[i] = strs[i].equals("null") ? emptyNode : new TreeNode(Integer.parseInt(strs[i]));
}

for (int i = 0; i < nodes.length / 2; i++) { // 0~n/2之间是有子节点的
if (nodes[i] == emptyNode) {
continue;
} // 虽然不加也没事儿,但是避免一些无用的计算
int leftIndex = 2 * i + 1; // 注意左边是2i+1,因为是从0开始的,若从1开始就是2i和2i+1
int rightIndex = 2 * i + 2;

if (nodes[leftIndex] == emptyNode) {
nodes[i].left = null;
} else {
nodes[i].left = nodes[leftIndex];
}
if (rightIndex < nodes.length) { // 注意这里面可能会出边界,最后只有一个左子树
if (nodes[rightIndex] == emptyNode) {
nodes[i].right = null;
} else {
nodes[i].right = nodes[rightIndex];
}
}
}

return nodes[0];
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}

StringBuilder str = new StringBuilder();
Deque<TreeNode> queue = new ArrayDeque<>();

// 此处使用高度,表明序列到完全二叉树就可以了,在下面那一行全为null的不会再序列化了
int allNum = (int) Math.pow(2, getHeight(root, 0)) - 1, count = 0;
queue.offerLast(root);
while (!queue.isEmpty()) {

TreeNode node = queue.pollFirst();
// 此处为了让空的时候,出来null而不是-2000撒打算打算阿斯顿爱上啊打算打算
if (node == emptyNode) { // 此处只是比较引用,所以那个值在范围内也没事
// str.append("null,");
} else {
str.append(node.val + ",");
}
if (++count >= allNum) {
break;
} // 达到了完全二叉树了

queue.offerLast(node.left == null ? emptyNode : node.left);
queue.offerLast(node.right == null ? emptyNode : node.right);
}
str.deleteCharAt(str.length() - 1); // 注意,此处删除最后一个逗号

return str.toString();
}
}
}

993. 二叉树的堂兄弟节点

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
/**
* 此处,需要得到该值的父节点,所以传入父节点就好,而不是说在本方法中判断子节点的值
* 当然判断子节点的值是可以的,但是操作起来会繁杂很多
*/
class Solution {
TreeNode xParNode = null;
TreeNode yParNode = null;
int xDepth, yDepth;
boolean xFound = false, yFound = false;
int x, y;
public boolean isCousins(TreeNode root, int x, int y) {
this.x = x;
this.y = y;

dfs(root,0, null);

return (xDepth == yDepth) && (xParNode != yParNode);
}
public void dfs(TreeNode node, int depth, TreeNode parNode) { // 因为要该值的父节点,所以传入父节点
if (node == null) {
return;
}

if (node.val == this.x) {
xParNode = parNode;
xFound = true;
xDepth = depth + 1;
}
if (node.val == this.y) {
yParNode = parNode;
yFound = true;
yDepth = depth + 1;
}

if (xFound && yFound) {
return;
}

dfs(node.left, depth + 1, node);

if (xFound && yFound) {
return;
}

dfs(node.right, depth + 1, node);
}
}

回溯

感觉回溯在很多时候,也可以使用那个 二叉树的层序遍历 的做法。(好像就是广度搜索,另一个是深度 + 回溯)

比如笔试过程中的,五个队伍两两比赛,每一次都能得到五个队伍的结果,五个队伍的结果从小到大排序之后,结果不重复的个数。

那我笔试过程中的做法是,通过在每一队比较完成的放入队列中,然后下一次两外两个比的时候,将队列里面的全部取出来,取出来的每一个都加上这次两两比较的情况,然后放入队列中,然后后面的再比,重复的使用set去重。

注意回溯的时候,将一个个ArrayList放入的时候,记得new ArrayList,因为浅拷贝,如果是int[]的话,记得.clone()

Gnw45UuxdMmr2Ee

90. 子集 II

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
/**
回溯,选择的时候回溯(dfs出来之后需要删除之前添加的),不选择的时候也回溯
* 使用回溯,为了不重复,使用set<List>
* 由于答案中不能包含相同的方案,因此我们可以先对原数组进行排序,
* 从而确保所有爆搜出来的方案,都具有单调性,然后配合 Set 进行去重。
* 注意此处需要list的单调性的,因为set判断是否相同是需要顺序也相同的
*/
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<Integer> list = new ArrayList<>();
Set<List<Integer>> ans = new HashSet<>();

dfs(list, ans, 0, nums);
return new ArrayList<>(ans);
}

/**
*
* @param cur 代表当前决策的索引
*/
public void dfs(List<Integer> list, Set<List<Integer>> ans, int cur, int[] nums) {
if (nums.length == cur) {
ans.add(new ArrayList<>(list));
return;
}

// 此处当前位置的元素添加
list.add(nums[cur]);
dfs(list, ans, cur+1, nums);
// 回溯删除,继续往下决策
list.remove(list.size()-1);


dfs(list, ans, cur+1, nums);
}
}

39. 组合总和

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
class Solution {
Set<List<Integer>> set = new HashSet<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {

List<Integer> list = new ArrayList<Integer>();
dfsTrace(list, 0, target, candidates, 0);

return new ArrayList<>(set);
}

public void dfsTrace(List<Integer> list, int sum, int target, int[] candidates, int curIndex) {
if (sum == target) {
List<Integer> temp = new ArrayList<>(list);
Collections.sort(temp);
set.add(temp);
return;
}
if (sum > target || curIndex >= candidates.length || set.size() >= 150) {
return;
}

// 要么当前这个不选择
dfsTrace(list, sum, target, candidates, curIndex + 1);

// 要么当前这个选择,然后后面可以继续选择
list.add(candidates[curIndex]);
dfsTrace(list, sum + candidates[curIndex], target, candidates, curIndex);
list.remove(list.size() - 1);
}
}

40. 组合总和 II

剑指 Offer II 082. 含有重复元素集合的组合

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
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// 可以使用dfs+回溯,先将队列排序,然后深度的时候记录重复数字的个数,这样就不需要用set去重复了
// 或者不记录,使用set去重应该也可以
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();

Arrays.sort(candidates);
dfsTrace(candidates, target, 0, ans, path, 0);

return ans;
}

public void dfsTrace(int[] candidates, int target, int sum, List<List<Integer>> ans, List<Integer> path, int curIndex) {
if (sum == target) {
ans.add(new ArrayList<>(path));
return;
}

// 退出条件
if (sum >= target || curIndex >= candidates.length) {
return;
}

// 查询有多少个一样的
int same = 1;
for (int i=curIndex+1; i<candidates.length; i++) {
if (candidates[i] == candidates[curIndex]) {
same += 1;
}
}

// 进行回溯递归
// 1 不选择,直接dfsTrace
dfsTrace(candidates, target, sum, ans, path, curIndex + same); // 注意此处的curIndex + same

// 2 选择,但是按照次数选择
for (int i=0; i<same; i++) {
path.add(candidates[curIndex]);
sum += candidates[curIndex];
dfsTrace(candidates, target, sum, ans, path, curIndex + same); // 注意此处的curIndex + same
}
for (int i=0; i<same; i++) {
path.remove(path.size()-1);
sum -= candidates[curIndex];
}
}
}

剑指 Offer II 081. 允许重复选择元素的组合

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 {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// 一样回溯
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();

dfsTrace(candidates, target, target, ans, path, 0);

return ans;
}

public void dfsTrace(int[] candidates, int target, int res, List<List<Integer>> ans, List<Integer> path, int curIndex) {
if (res == 0) {
ans.add(new ArrayList<>(path));
return;
}

// 退出条件
if (res < 0 || curIndex >= candidates.length) {
return;
}

// 进行回溯
// 1 一个都不选择
dfsTrace(candidates, target, res, ans, path, curIndex + 1);

// 2 一次次选多个相同的
for (int i=1; i * candidates[curIndex] <= res; i++) {
path.add(candidates[curIndex]);
dfsTrace(candidates, target, res - i * candidates[curIndex], ans, path, curIndex + 1);
}
for (int i=1; i * candidates[curIndex] <= res; i++) {
path.remove(path.size() - 1);
}
}
}

剑指 Offer II 083. 没有重复元素集合的全排列

基于选择的回溯(还需要借助set来知道这个数有没有被选择过就行了),基于交换的回溯(两两交换来完成,更快)

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 {
public List<List<Integer>> permute(int[] nums) {
// 使用基于交换的回溯来完成
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();

for (int num: nums) {
path.add(num);
}

dfsTrace(nums, path, ans, 0, n);

return ans;
}

public void dfsTrace(int[] nums, List<Integer> path, List<List<Integer>> ans, int curIndex, int n) {
if (curIndex == n) {
ans.add(new ArrayList<>(path));
return;
}

// 返回条件
// 不交换,都是在不交换的时候才输出的
dfsTrace(nums, path, ans, curIndex + 1, n);

// 交换
for (int i=curIndex+1; i<n; i++) {
Collections.swap(path, curIndex, i);
dfsTrace(nums, path, ans, curIndex + 1, n);
Collections.swap(path, curIndex, i); // 换回来
}
}
}

剑指 Offer II 084. 含有重复元素集合的全排列

当然用set去重复也可以,但是这样的话,还是比较浪费时间的。

此处选择基于选择的排序。

要解决重复问题,我们只要设定一个规则,保证在填第 idx 个数的时候重复数字只会被填入一次即可。而在本题解中,我们选择对原数组排序,保证相同的数字都相邻,然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」。

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
class Solution {
boolean[] vis;

public List<List<Integer>> permuteUnique(int[] nums) {
// 基于选择的回溯
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
vis = new boolean[n];

Arrays.sort(nums);
dfsTrace(nums, path, ans, 0, n);

return ans;
}

public void dfsTrace(int[] nums, List<Integer> path, List<List<Integer>> ans, int curIndex, int n) {
if (curIndex == n) {
ans.add(new ArrayList<>(path));
return;
}

// 返回条件,无

for (int i=0; i<n; i++) {
// 第curIndex个不能填入重复的,由于排序,所以是从左往右第一个没有被填过的
// 此处的意思是i-1没有填写过,而且相同,所以肯定是填写了i-1的
if (vis[i] || i > 0 && !vis[i-1] && nums[i-1] == nums[i]) {
continue;
}

path.add(nums[i]);
vis[i] = true;
dfsTrace(nums, path, ans, curIndex + 1, n);
path.remove(path.size() - 1);
vis[i] = false;
}
}
}

797. 所有可能的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
// 使用广度优先搜索
// 但是此处想使用回溯试一试
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<Integer>();
path.add(0);

dfsTrace(ans, graph.length - 1, graph, path, 0);

return ans;
}

public void dfsTrace(List<List<Integer>> ans, int target, int[][] graph, List<Integer> path, int cur) {
if (cur == target) {
ans.add(new ArrayList<>(path));
return;
}

for (int des: graph[cur]) {
path.add(des);
dfsTrace(ans, target, graph, path, des);
path.remove(path.size() - 1);
}
}
}

131. 分割回文串

回溯 + 动态规划预处理

【宫水三叶】为什么只需要对第一个字符进行「爆搜」

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
class Solution {
/**
这道题目求所有的分割方案,所以考虑使用回溯+dfs的方法
在0~i-1已经有的了的情况下,后面的i~n-1使用i, i~i+1, i~i+2, ..., i~n-1这样的方法加入
当然加入的需要本身就是回文串,所以首先使用动态规划来预处理,回文串
*/
public List<List<String>> partition(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
char[] chars = s.toCharArray();

List<List<String>> anss = new ArrayList<>();
List<String> ans = new ArrayList<>();

// 动态规划考虑子串是否是回文串
for (int step = 1; step <= n; step++) {
for (int i=0; i<n-step+1; i++) {
if (step == 1) {
dp[i][i] = true;
} else if (step == 2) {
dp[i][i+1] = chars[i] == chars[i+1];
} else {
dp[i][i+step-1] = chars[i] == chars[i+step-1] && dp[i+1][i+step-2];
}
}
}

dfsTrace(anss, ans, n, s, 0, dp);

return anss;
}

// 传入的cur索引是还没有选择的,因为一开始main函数中先传入0还没有选进去,所以下面函数里刚判断的时候只要cur==n就行了
// 然后那个for循环需要关注首先cur这个所有也是要加入的,然后一个字符的情况也是要考虑的。
public void dfsTrace(List<List<String>> anss, List<String> ans, int n, String s, int cur, boolean[][] dp) {
if (cur == n) {
anss.add(new ArrayList<>(ans));
return;
}

for (int i=cur; i<n; i++) {
if (dp[cur][i]) {
ans.add(s.substring(cur, i+1));
dfsTrace(anss, ans, n, s, i+1, dp);
ans.remove(ans.size() - 1);
}
}
}
}

Author: Jcwang

Permalink: http://example.com/2022/06/07/AlgorithmClassification/