不爱吃鸭脖
jinhua
2023-07-13
目录

代码随想录

# 动态规划

# 动态规划基础

# 技巧

  • 直接考虑最后一步，dp[i] = Math.min(dp[i - 1],dp[i - 2]);

# 斐波那契数列

  • f(n) = f(n - 1) + f(n - 2)
  • dp,O(n),O(n)
  • dp,O(n),O(1)
  • 递归，O(2^n),O(n)

# 爬楼梯

  • 与斐波那契雷同,每次可以上1-2个台阶，上到顶楼需要多少种方法
  • dp[i]，表示爬到第i层有dp[i]中爬法
  • 使用最小代价爬楼梯
  • 支付当前楼梯的体力值，向上爬一到两个楼梯
  • dp[i],表示爬到台阶i，所消耗的最小体力值dp[i]

# 不同路径

  • 机器人只能向下或向右移动，走到右下角的路径数
  • dp[i][j] 到达(i,j)的路径数为dp[i][j]
  • dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  • 二维：O(m * n),O(m * n)
  • 一维：O(m * n)(m)

# 不同的路径2

  • 左上角到右下角，总共的路径数，但是中间有障碍物

# 整数拆分

  • 正整数拆分为两个正整数的和，积最大
  • dp[i] 表示整数i拆分为两个正整数的积最大值为dp[i]
  • 数论，O(n),O(1)
  • dp[i] = max(dp[j] * dp[i - j], j * (i - j)),O(n ^ 2),O(n)

# 不同二叉搜索树

  • n个节点组成的二叉搜索树的种类有多少种
  • dp[i] 表示i个节点二叉搜索树的种类数为dp[i]
  • dp[i] += dp[j - 1] + dp[i - j],O(n ^ 2),O(n)

# 01背包

# 模板

int N; // 物品数量
int V; // 背包体积
int[] dp = new int[N + 1];
for (int i = 0; i < N; i++) {
    for (int j = V; j >= v[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
    }
}   
return dp[V];
1
2
3
4
5
6
7
8
9

就是放不放这个物品

# 分割等和子集

  • 数组 拆分 两个子集，子集和得相等
  • dp[j],表示体积j下，对应的最大价值为dp[j]
  • O(n^2),O(n)

# 最后一块石头的重量2

  • 两个数，相等就粉碎，不相等，大数-小数重新放到数组
  • dp[j]表示容量为j的背包，最多石头重量为dp[j]
  • o(n * m),O(m)

# 目标和

  • 数组nums[]中的数，正负和为S
  • 其实就是在找和为(target + sum) / 2的组合
  • dp[j] , 和为j共有dp[j]种方法
  • dp[j] = dp[j] + dp[j - nums[i]],O(n * n),O(n)

# 一和零

  • m个0，n个1，字符串strs的最大子集大小
  • dp[i][j]表示最多有i个0，j个1的最大子集大小为dp[i][j]
  • dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1)
  • O(kmn),O(mn)

# 完全背包

# 模板

int N; // 物品数量
int V; // 背包体积
int[] dp = new int[N + 1];
for (int i = 0; i < N; i++) {
    for (int j = v[i]; j <= V;j++) {
        dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
    }
}   
return dp[V];
1
2
3
4
5
6
7
8
9

# 零钱兑换2

  • 组成总金额为5的硬币组合数
  • dp[j]组成总金额为j的组合方式为dp[j]
  • dp[j] += dp[j - coin[i]] ,O(nm)O(m)

# 组合总和4

  • 组成目标和target的排列个数
  • dp[j]表示组成目标和为j的排列数为dp[j]
  • dp[j] += dp[j - coin[i]]
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
1
2

# 爬楼梯

  • 每次可以爬1或2个台阶，爬到n阶的方法数
  • dp[i]表示i阶方式数为dp[i]
  • dp[i] += dp[i - j] ,O(nm),O(n)

# 零钱兑换

  • 凑成总和为amount的最少硬币组合数，硬币数量无限
  • dp[i] 表示组合成amount为i的最少硬币组合数为dp[i]
  • dp[j] = min(dp[j - nums[i]]+ 1, dp[j]),O(mn)O(m)

# 完全平方数

  • 给定一个正整数n,返回和为n的完全平方数的最少数量
  • dp[j]:和为j的完全平方数的最少数量为dp[j]
  • dp[i] = min(dp[i], dp[i - jj] + 1), O(n根号n),O(n)

# 单词拆分

  • wordDict数组中的字符串是否可以组合成 字符串s
  • dp[i],dp[i] = true表示字符串长度为i时可以拆分为字典中出现的单词
  • if(w.contains(s.substring(j,i)) && dp[j]) dp[i] = true

# 打家劫舍问题

# 打家劫舍1

  • nums[i],不能取相邻的数，取的数的和的最大值
  • dp[i]表示到第i号房屋，最大的收益为dp[i]
  • dp[i] = max(dp[i - 1], dp[i - 2] +nums[i]);O(n),O(n)

# 打家劫舍2

  • 在1的基础上，加了个条件，第一个与最后一个相连
  • 分情况考虑一下就是说：把环破坏掉，包含头、不包含尾；包含尾，不包含头
  • max(res1, res2),O(n),O(n)

# 打家劫舍3

  • 金额是以树的形式存储的
  • 递归
  • 偷父节点，不偷父节点两种情况，O(n^2),O(n)
  • 优化版：记忆化递归，计算完的结果放到map.put(root,res),递归的时候，判断一下map里面是否有该key,O(n),O(logn)
  • 树形dp,
  • res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
  • res[1] = root.val + left[0] + right[0];

# 股票系列问题

# 买卖股票的最佳时机

  • prices数组某一天买入股票，某一天卖出股票，返回最大利润
  • 暴力，找最优间距，O(n^2),O(1)
  • 贪心，左边找到最小值，右边找到最大值，差值为最大利润，O(n),O(1)
  • 动态规划,dp[i][0]表示第i点持有股票的最大值，dp[i][1]表示第i点未持有股票的最大值
  • dp[i][0] = max(dp[i - 1][0], -price[i]),dp[i][1]=max(dp[i - 1][1], dp[i - 1][0] + price[i]),O(n),O(n)
  • dp优化，滚动数组，空间复杂度O(1)

# 买卖股票的最佳时机2

  • 可以进行多次交易
  • 动态规划，dp[i][0] = max(dp[i - 1][0],dp[i - 1][1] - price[i]),dp[i][1] = max(dp[i - 1][1],dp[i - 1][0] + price[i]),O(n),O(n)
  • 优化版，滚动数组，O(n),O(1)

# 买卖股票的最佳时机3

  • 最多可以完成两笔交易
  • 定义5中状态0，1，2，3，4，O(n),O(n * 5)
  • 优化 滚动数组，O(n),O(1)

# 买卖股票的最佳时机4

  • 最多完成 k 笔交易

# 最佳买卖股票的时机含冷冻期

  • 多次交易，冷冻期一天
  • dp,分的状态更多

# 买卖股票含手续费

  • 可以多次交易，每次买入卖出只需支付一次手续费
  • 买卖股票2的基础上
  • 卖出时，支付fee,dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + price[i] - fee)
  • 买入时支付fee,O(n),O(n)
  • 优化，滚动数组，O(n),O(1)

# 子序列问题

# 最长递增子序列

  • 一个整数数组，最长递增子序列的长度
  • dp[i]，表示以下标i结尾，最长递增子序列的长度为dp[i]
  • dp[i] = max(dp[i],dp[j] + 1),O(n^2),O(n)

# 最长连续递增子序列

  • 最长连续递增子序列的长度
  • dp[i]，表示以下标i结尾，最长连续递增子序列长度为dp[i]
  • dp[i] = dp[i - 1] + 1;O(n),O(n)
  • 贪心，遍历一次，O(n),O(1)

# 最长重复子数组

  • 返回两个数组中最长公共的、长度最长的子数组长度
  • dp[i][j]，表示以i - 1结尾的A，和以j - 1结尾的B，最长重复子数组dp[i][j]
  • dp[i][j] = dp[i - 1][j - 1] + 1, O(n * m), O(n * m)
  • 优化，滚动数组，O(n*m),O(m)

# 最长公共子序列

  • 返回两个字符串最长公共子序列的长度
  • dp[i][j],以text1[i - 1]结尾的子串与text2[j - 1]结尾的子串，最长公共子串为dp[i][j]
  • 相等：dp[i][j] = dp[i - 1][j - 1] + 1,不相等：dp[i][j] = max(dp[i -1][j],dp[i][j - 1])O(m * n),O(m * n)

# 不相交的线

  • A[i] == B[j]的不相交的线最多有多少条
  • dp[i][j]表示以A[i - 1]结尾的子序列与B[j - 1]结尾的子序列，最长公共子序列为dp[i][j]
  • 与最长公共子序列一致

# 最大子数组和

  • 找到一个最大和的连续子数组
  • dp[i]:以nums[i]为结尾的最大连续子数组和为dp[i]
  • dp[i] = max(nums[i],dp[i - 1] + nums[i]),O(n),O(n)

# 判断子序列

  • s是否为t的子序列
  • dp[i][j]表示以s[i- 1]结尾和 t[j-1]结尾子序列长度为dp[i][j]
  • 思路就是直接求它们的最长公共子序列，最后最长公共子序列等于s.length()就是true,O(mm)O(nm)

# 不同的子序列

  • 字符串s中 字符串t出现的次数
  • dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
  • if '相等', dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];if '不等',dp[i - 1][j]

# 两个字符串的删除操作

  • word1变为word2的最少步数，只能进行删除
  • dp[i][j]，i-1,j-1最少步数为dp[i][j]
  • if '相等'，dp[i][j] = dp[i - 1][j - 1]; else min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

# 编辑距离

  • word1 变为 word2的最少步数
  • dp[i][j]表示word1,i-1、word2,j-1,最近编辑距离为dp[i][j]
  • if '相等'，dp[i][j] = dp[i - 1][j - 1];if '不相等',dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;O(nm),O(nm)

# 回文子串

  • 一个字符串里面有多少个回文子串
  • 布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

# 最长回文子序列

  • 一个字符串里面的最长的 回文子序列长度
  • dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
  • 遍历顺序从下往上，从左往右，O(n^2),O(n^2) 输出dp[0][s.length() - 1]

# 单调栈

# 模板

Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        // res[stack.peek()] = i - stack.pop();
        // 处理逻辑
    }
    stack.push(i);
}
1
2
3
4
5
6
7
8

# 每日温度

  • 数组nums[],想要得到一个数组，res[],res[i]表示在nums中比nums[i]大的最近的nums[j]，res[i] = j - i
  • 单调栈思路就是，如果st[top] >= nums[i],st.push(nums[i]); else 就st.pop,res[x] = i - x;O(n),O(n)

# 下一个最大的元素1

  • nums1 是 nums2 的子集，在nums2中找到下一个比它大的数
  • 单调栈，O(n)O(n)

# 下一个最大的元素2

  • 在1的基础上可以循环的搜索
  • 搜索两次，对i%size,单调栈，O(n),O(n)

# 接雨水

  • 柱子接到的雨水的面积
  • 单调栈，O(n),O(n)

# 柱形图里的最大矩形

  • 柱形图最大面积
  • 先找左边界，再找有边界，最后计算面积的最大值，O(n^2)O(n)

# 二叉树

# 二叉树的前序遍历

  • 递归
  • 参数返回值：traversal(TreeNode root, List res)
  • 终止条件：if (root == null) return
  • 每层的逻辑：

# 二叉树的前序遍历

  • 迭代
  • 栈，入栈顺序中，右，左
  • O(n),O(h),h为二叉树的高度

# 二叉树的中序遍历

  • 迭代
  • 栈，入栈顺序 左、右
  • O(n),O(h)

# 二叉树的后序遍历

  • 迭代
  • 栈，入栈顺序 中 左 右,再将结果列表反转一下
  • O(n),O(h)

# 二叉树的层序遍历

  • 层序遍历返回二叉树所有节点
  • 队列，O(n),O(n)

# 反转二叉树

  • 反转二叉树每个节点的左右孩子
  • 递归，参数返回值：TreeNode main(TreeNode root); 确定终止条件;确定单层递归逻辑
  • 迭代，栈 入栈顺序：中右左
  • BFS，队列，中 左右

# 对称二叉树

  • 判断二叉树是不是镜像对称
  • 递归，终止条件将各种情况考虑充分；递归逻辑：镜像对称逻辑
  • 迭代，队列

# 完全二叉树的节点个数

  • 一般二叉树、满二叉树
  • 递归
  • 迭代

# 平衡二叉树

# 二叉树的所有路径

  • 返回根节点到叶子节点的所有路径
  • 递归 + 回溯

# 左叶子之和

  • 计算左叶子之和
  • 递归，后序遍历，左右中
  • 迭代法，前序遍历

# 找左下角的值

  • 最后一行最左边的值
  • 递归，直接前序遍历，遍历到 最左边 且深度发生变化的节点，就是目标节点
  • 迭代，全局变量，只存每行的第一个节点的val值

# 回溯算法

# 模板

List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> main(int n, int k) {
    backTracking(n, k, startIndex);
    return result;
}
public void backTracking(int n, int k, int startIndex) {
    // 终止条件
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = startIndex; i <= n; i++) {
        path.add(i);
        backTracking(n, k, i + 1);
        path.removeLast();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 组合问题

# 组合

  • 输入n,k;n为1到n中取值，k为取几个值进行组合
  • 回溯，O(n * n!); O(n)
  • 剪枝优化，i <= n - (k - path.size()) + 1

# 组合总和1

  • nums[],无重复数字,目标和target,nums[]中元素可以重复使用，找出目标和为target的所有组合
  • 回溯,O(n*n!);O(n)
  • 剪枝优化,O(n*n!);O(n)

# 组合总和2

  • 有重复数字，不能重复使用元素，找出所有组合
  • 使用标记数组，i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false 同层中有没有使用过；used[i - 1] == true,不同层有没有使用过
  • 不使用标记数组， i > start && nums[i] == nums[i - 1]

# 组合总和3

  • k个数相加和为n，不能重复
  • 回溯，O(n*n!);O(n)
  • 剪枝，O(n * n!);O(n)

# 分割问题

# 分割回文串

  • 字符串s,分割成一些子串，每个子串都是回文串
  • 回溯

# 子集问题

# 子集

  • 给定一组不含重复元素的数组nums[],返回所有可能的子集

# 子集2

  • 给定一个含重复元素的数组nums[],返回所有子集
  • 使用标记数组
  • 不使用标记数组

# 排列问题

# 全排列

  • 没有重复数字的序列，返回可能的全排列
  • 使用标记数组
  • 不使用标记数组

# 全排列2

  • 序列中有重复数字，返回可能的全排列
  • 使用标记数组
  • 不使用标记数组

# 棋盘问题

# N皇后

# 解数独

刷题笔记

←

最近更新
01
实习技术
08-24
02
sql
07-28
03
git命令
07-26
更多文章>
Theme by Vdoing | Copyright © 2019-2023 Evan Xu | MIT License