1.数组
力扣：41.缺失的第一个正数 1次：未通过
2.二叉树
力扣：543.二叉树的直径 1次：通过
力扣：98.验证二叉搜索树 1次：未通过
力扣：437. 路径总和 III 1次：未通过
力扣：124. 二叉树中的最大路径和 1次：通过
3.栈
力扣：155. 最小栈 1次：通过
力扣：394. 字符串解码 1次：未通过
力扣：84. 柱状图中最大的矩形 1次：未通过
力扣：496. 下一个更大元素 I : 解法：单调栈
4.滑动窗口
力扣：239. 滑动窗口最大值 1次：通过
力扣：76. 最小覆盖子串 1次：未通过
5.哈希
力扣： 49. 字母异位词分组 1次：未通过
6.一维动态规划
力扣： 139. 单词拆分 1次：通过
力扣： 322. 零钱兑换
力扣： 300. 最长递增子序列
力扣： 152. 乘积最大子数组
7.多维动态递归
力扣：120. 三角形最小路径和
力扣：5. 回文字符串
力扣：97.交错字符串
力扣：32. 最长有效括号
力扣：5. 最长回文子串
8. 动态规划
8.1 01背包问题
8.1.1 力扣：474. 最长回文子串(中等)
外层遍历物品，内层遍历背包，这个题背包有两个维度：第一个维度 ‘1’ 的个数，第二个维度是 ‘0’ 的个数。
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for(String str : strs){
// 外层循环遍历物品
int oneNum = 0, zeroNum = 0;
for(char c : str.toCharArray()){
if(c == '1'){
oneNum++;
}else{
zeroNum++;
}
}
// 内层循环两个维度, 遍历 1 和 0 的个数，由于两个维度都无关，先遍历那个维度都可以
for(int i = m; i >= zeroNum; i--){
for(int j = n; j >= oneNum; j--){
dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
8.2 完全背包问题
首先完全背包问题和 01 背包问题的区别是：
- 完全背包物品可以使用多次，所以递推公式为:
dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]) - 01 背包的物品仅可以使用一次，所以递推公式为:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
8.2.1 力扣：518. 零钱兑换 II(中等)
由于完全背包是从当前行的左侧和上一行相同位置递推的到所以很容易写为一维dp数组
public class Solution {
public int change(int amount, int[] coins) {
// 每个下标 amount 凑成金额的种类数
int[] dp = new int[amount + 1];
// 初始化
dp[0] = 1;
// 递推
for(int i = 0; i < coins.length; i++) {
// 外层循环遍历物品
for(int j = coins[i]; j <= amount; j++) {
// 内层循环遍历背包
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}
8.2.2 力扣：377. 组合总和 Ⅳ(中等)
分析：这道题求解组合总数，如果要是列出组合，需要用回溯爆搜，但是求个数的话可以使用dp，问题是完全背包问题，但是遍历顺序需要修改为先遍历物品再遍历背包，保证每个背包容量都可以考虑到所有物品存放的情况，代码如下：
public class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
// 后遍历背包
for (int j = 0; j < nums.length; j++) {
// 先遍历物品
if(i >= nums[j]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
}
9.数学题：
力扣 50.Pow(x, n)
力扣 149. 直线上最多的点数
10.二分查找
力扣 4. 寻找两个正序数组的中位数
力扣 153. 寻找旋转排序数组中的最小值
11.堆
力扣 295. 数据流的中位数
力扣 215. 数组中的第K个最大元素
力扣 347. 前 K 个高频元素
12.链表
力扣 25. K 个一组翻转链表
力扣 148. 排序链表
13. 回溯算法
13.1 力扣：93. 复原 IP 地址(中等)
经典回溯算法：本题需要考虑的是docCount 点的个数，首先将字符串通过StringBuilder的构造函数传入进入，然后再在 sb 当中添加点，进入dfs首先判断是否已经有三个点了有三个点的话判断最后一段是否符合结果。还有本次算法使用了 StringBuilder 的insert函数在指定位置插入指定字符。还有下一次dfs要跳过两个位置。
public class Solution {
List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
StringBuilder sb = new StringBuilder(s);
dfs(sb, 0, 0);
return res;
}
private void dfs(StringBuilder sb, int start, int docCount) {
// 已经插入三个点，判断最后一段是否合法
if(docCount == 3){
if(check(sb, start, sb.length() - 1)){
res.add(sb.toString());
}
return;
}
for(int i = start; i < sb.length(); i++){
// 如果当前这一段符合规定
if(check(sb, start, i)){
sb.insert(i + 1, '.');
// 向后跳两个位置
dfs(sb, i + 2, docCount + 1);
sb.deleteCharAt(i + 1);
}
}
}
// 判断在 sb 当中当前子串转化为数字是否合法
private boolean check(StringBuilder sb, int start, int end){
if(start > end){
return false;
}
// 最后一段不只一位的情况下，0开头是不合适的
if(sb.charAt(start) == '0' && start != end){
return false;
}
int num = 0;
for(int i = start; i <= end; i++){
num = num * 10 + sb.charAt(i) - '0';
if(num > 255){
return false;
}
}
return true;
}
}
14. 技巧
力扣 31. 下一个排列