贪心算法
什么是贪心？
我们找到每个阶段的局部最优，最终推导出全局的最优解
贪心的2个极端
贪心的套路
分发饼干
https://leetcode.cn/problems/assign-cookies/description/
java'
BASH
chmod 777 /home/jokerak/data摆动序列
https://leetcode.cn/problems/wiggle-subsequence/description/
java
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
// 大于0
int count = 1;
int pre = 0;
int next = 0;
for (int i = 0; i < n - 1; i++) {
next = nums[i + 1] - nums[i];
if ((pre >= 0 && next < 0) || (pre <= 0 && next > 0)) {
count++;
// 这里为啥放在这里更新是为了解决单调有平坡的情况
pre = next;
}
}
return count;
}最大子数组和
https://leetcode.cn/problems/maximum-subarray/
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
java
public int maxSubArray(int[] nums) {
int sum = 0;
int max = nums[0];
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum > max) {
max = sum;
}
// 如果当前和小于0，则重置为0。从0开始
if (sum < 0) {
sum = 0;
}
}
return max;
}下面使用动态规划的
题目要我们找出和最大的连续子数组的值是多少，「连续」是关键字，连续很重要，不是子序列。
题目只要求返回结果，不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划」解决。
定义动态规划数组很重要。
java
public int maxSubArray(int[] nums) {
int sum = 0;
// 1. 创建一个动态规划数组 dp。dp[i] 表示以 nums[i] 结尾的子数组的最大和。
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
// 2. dp[i] = max(dp[i-1] + nums[i], nums[i])
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
// 3. 更新 sum
sum = Math.max(sum, dp[i]);
}
return sum;
}买卖股票的最佳时机 II
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
贪心-就是只寻找递增部分
java
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
int minIndex = 0;
boolean isBuy = false;
for (int i = 0; i < prices.length - 1; i++) {
// 只找寻递增的部分。并累加利润
if (prices[i] < prices[i + 1]) {
// 如果没有买，则记录最小值
if (!isBuy) {
// System.out.println("没有买：开始买 index :" + (i + 1));
minIndex = i;
isBuy = true;
}
} else if (prices[i] > prices[i + 1]) {
// 如果已经买了，则直接卖掉
if (isBuy) {
// System.out.println("已经买：卖掉 index :" + (i + 1));
maxProfit += prices[i] - prices[minIndex];
isBuy = false;
}
}
}
// 如果之前买过了，则计算利润
if (isBuy) {
// System.out.println("之前买过了：卖掉 maxProfit:" + (prices[prices.length - 1] - prices[minIndex]));
maxProfit += prices[prices.length - 1] - prices[minIndex];
}
// 表示一直递增，则不卖
return maxProfit;
}
}动态规划
跳跃游戏
https://leetcode.cn/problems/jump-game/description/
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
覆盖范围是否能把终点的范围给覆盖掉
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
java
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] canJump = new boolean[n + 1];
for (int i = 0; i < n; i++) {
canJump[i] = false;
}
canJump[0] = true;
for (int i = 0; i < n-1; i++) {
int l = nums[i];
if (canJump[i]) {
for (int j = i + 1; j <= i + l && j < n; j++) {
canJump[j] = true;
}
}
if(canJump[n - 1]){
return true;
}
}
return canJump[n - 1];
}跳跃游戏2
https://leetcode.cn/problems/jump-game-ii/
使用贪心算法
java
public int jump(int[] nums) {
int n = nums.length;
int result = 0;
int next = 0;
int current = 0;
for (int i = 0; i < n - 1; i++) {
// 找到当前位置可以跳到的最远位置
next = Math.max(nums[i] + i, next);
// 当前位置可以跳到最远位置
if (i == current) {
result++;
current = next;
if (current >= n - 1) {
break;
}
}
}
return result;
}动态规划
java
public int jump(int[] nums) {
int n = nums.length;
// 创建dp数组, dp[i]表示从0到i的最小步数
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < n; i++) {
// 遍历dp数组, 更新dp[i+nums[i]]的值
for (int j = i + 1; j <= i + nums[i] && j < n; j++) {
dp[j] = Math.min(dp[j], dp[i] + 1);
}
}
return dp[n - 1];
}k次取反后最大化的数组和
https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
加油站
java
public int canCompleteCircuit(int[] gas, int[] cost) {
if (gas.length == 0) {
return 0;
}
int sum = 0;
int start = 0;
int total = 0;
for (int i = 0; i < gas.length; i++) {
sum += gas[i] - cost[i];
total += gas[i] - cost[i];
if (sum < 0) {
sum = 0;
start = i + 1;
}
}
if (total < 0) {
return -1;
}
return sum >= 0 ? start : -1;
}分发糖果
https://leetcode.cn/problems/candy/description/
java
public int candy(int[] ratings) {
int n = ratings.length;
int sum = 0;
int[] candys = new int[n + 1];
// 首先假设每个孩子至少分配到1个糖果。 从前一个孩子到当前孩子（含当前孩子），如果当前孩子的评分比前一个孩子高，那么当前孩子的糖果数量比前一个孩子多 1 个。。保证了左边的糖果
for (int i = 0; i < n; i++) {
// 当前孩子的糖果数量比前一个孩子多 1 个
if (i > 0 && ratings[i] > ratings[i - 1]) {
candys[i] = candys[i - 1] + 1;
} else {
candys[i] = 1;
}
}
for (int i = n - 1; i >= 0; i--) {
// 如果当前孩子的评分比后一个孩子高，那么当前孩子的糖果数量比后一个孩子多 1 个。同时确保右边的糖果
if (i < n - 1 && ratings[i] > ratings[i + 1]) {
candys[i] = Math.max(candys[i], candys[i + 1] + 1);
}
sum += candys[i];
}
return sum;
}柠檬水找零
https://leetcode.cn/problems/lemonade-change/description/
java
class Solution {
int num5 = 0;
int num10 = 0;
public boolean lemonadeChange(int[] bills) {
if (bills.length <= 0 || bills[0] != 5) {
return false;
}
for (int i = 0; i < bills.length; i++) {
if (!charge(bills[i])) {
return false;
}
}
return true;
}
/**
* @param a a表示支付的钱数
* @return
*/
public boolean charge(int a) {
if (a == 5) {
num5++;
return true;
}
if (a == 10) {
if (num5 > 0) {
num5--;
num10++;
return true;
}
}
if (a == 20) {
if (num10 > 0 && num5 > 0) {
num10--;
num5--;
return true;
}
if (num5 >= 3) {
num5 -= 3;
return true;
}
}
return false;
}
}根据身高重建队列
https://leetcode.cn/problems/queue-reconstruction-by-height/description/
java
// 406. 根据身高重建队列
public int[][] reconstructQueue(int[][] people) {
// 首先进行排序// 身高降序，k升序。
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] == o2[0]) {
return o1[1] - o2[1];
}
// 身高降序
return o2[0] - o1[0];
}
});
List<int[]> list = new ArrayList<>();
for (int[] person : people) {
list.add(person[1], person);
}
return list.toArray(new int[list.size()][]);
}用最少数量的剑引爆气球
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
java
public int findMinArrowShots(int[][] points) {
// 首先正对象数组进行排序
Arrays.sort(points, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int count = 1;
int right = points[0][1];
for (int i = 0; i < points.length - 1; i++) {
// 如果当前区段的右边界大于等于下一个区间的左边界，则说明两个区间有重叠部分，需要合并
if (right >= points[i + 1][0]) {
right = Math.min(right, points[i + 1][1]);
} else {
// 如果当前区间的右边界小于下一个区间的左边界，则说明两个区间不相交，需要射箭
right = points[i + 1][1];
count++;
}
}
return count;
}无重叠区间
https://leetcode.cn/problems/non-overlapping-intervals/
java
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
int count = 0;
//
int right = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
// 说明：当前区间的起始位置小于当前区间的结束位置，则说明当前区间不可以加入结果集
if (intervals[i][0] < right) {
// 当前区间的开始位置比上个区间的右边界小，说明有重合
count++;
right = Math.min(right, intervals[i][1]);
} else {
// 说明：当前区间的起始位置大于当前区间的结束位置，则说明当前区间可以加入结果集
right = intervals[i][1];
}
}
return count;
}划分字母区间
https://leetcode.cn/problems/partition-labels/description/
java
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
// 创建一个数组，记录每个字符出现的最后位置
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - 'a'] = i;
}
List<Integer> ans = new ArrayList<>();
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, last[s.charAt(i) - 'a']);
if (i == end) {
ans.add(end - start + 1);
start = i + 1;
}
}
return ans;
}合并区间
https://leetcode.cn/problems/merge-intervals/description/
java
public int[][] merge(int[][] intervals) {
// 先对左边界进行排序
Arrays.sort(intervals,Comparator.comparingInt(a -> a[0]));
List<int[]> res = new ArrayList<>();
int[] cur = intervals[0];
for (int i = 1; i < intervals.length; i++) {
// 1表示右边界，0表示左边界。
if (cur[1] >= intervals[i][0]) {
// 表示有重合
cur[1] = Math.max(cur[1], intervals[i][1]);
} else {
// 没有重合
res.add(cur);
cur = intervals[i];
}
}
res.add(cur);
return res.toArray(new int[res.size()][]);
}单调自增的数字
https://leetcode.cn/problems/monotone-increasing-digits/description/
java
public int monotoneIncreasingDigits(int n) {
List<Integer> list = get(n);
int result = 0;
for (int i = list.size() - 1; i >= 0; i--) {
result += list.get(i) * Math.pow(10, i);
}
return result;
}
public List<Integer> get(int n) {
List<Integer> list = new ArrayList<>();
while (n > 0) {
list.add(n % 10);
n = n / 10;
}
for (int i = 0; i < list.size() - 1; i++) {
if (list.get(i) < list.get(i + 1)) {
for (int j = i; j >= 0; j--) {
list.set(j, 9);
}
list.set(i + 1, list.get(i + 1) - 1);
}
}
return list;
}监督二叉树
https://leetcode.cn/problems/binary-tree-cameras/description/
java
private int count = 0;
public int minCameraCover(TreeNode root) {
if (root == null) {
return 0;
}
int res = monotoneIncreasingDigits(root);
if (res == 0) {
count++;
}
return count;
}
// 0无覆盖，1有摄像头,2有覆盖
private int monotoneIncreasingDigits(TreeNode root) {
if (root == null) {
return 2;
}
int left = monotoneIncreasingDigits(root.left);
int right = monotoneIncreasingDigits(root.right);
// 如果左右阶段都有覆盖，则当前节点无覆盖
if (left == 2 && right == 2) {
return 0;
}
// 左右至少有一个无覆盖，则当前节点有摄像头
if (left == 0 || right == 0) {
count++;
return 1;
}
// 左右至少有一个摄像头，则当前节点有覆盖
return 2;
}最小相邻交换至奇偶交换
https://leetcode.cn/problems/minimum-adjacent-swaps-to-alternate-parity/description/
java
class Solution {
public int minSwaps(int[] nums) {
// 分别统计基数还是偶数
int odd = 0;
int even = 0;
int oddSum = 0;
int evenSum = 0;
// 这里只需要把偶数放到改去的位置，就能保证最小
for (int i = 0; i < nums.length; i++) {
if (nums[i] % 2 == 1) {
// 如果把奇数放在 0,2,4,6,8,10 等位置（首位放基数)
oddSum += Math.abs(i - (2 * odd));
odd++;
} else {
// 如果把偶数放在 0,2,4,6,8,10 等位置(首位放偶数)
evenSum += Math.abs(i - (2 * even));
even++;
}
}
// 如果个数为奇数，奇偶绝对值只能是1
if (nums.length % 2 == 1) {
if (Math.abs(odd - even) != 1) {
return -1;
}
if (odd > even) {
// 如果奇数较大，偶数较小，则第一个数字为奇数
return oddSum;
} else {
// 如果偶数较大，奇数较小，则第一个数字为偶数
return evenSum;
}
} else {
if (Math.abs(odd - even) != 0) {
return -1;
}
// 如果个数为偶数，奇偶绝对值只能是0
return Math.min(oddSum, evenSum);
}
}
}动态规划
基础
定义dp数组以及下列的含义。dp数组里面的值的意思
dp初始化
递推公式
遍历顺序
打印dp数组
爬楼梯
斐波那契数列
使用最小花费爬楼梯
java
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length];
// 第0和第1个台阶的初始值。因为我们可以从下标为0和下标为1的台阶开始爬楼梯，所以初始值分别为cost[0]和cost[1]
dp[0] = cost[0];
dp[1] = cost[1];
// 状态转移方程
for (int i = 2; i < cost.length; i++) {
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
}
// 返回计算结果
return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
}不同路径
https://leetcode.cn/problems/unique-paths/description/
java
public int uniquePaths(int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
if (m == 1 || n == 1) {
return 1;
}
// 定义dp数据。dp[i][j]表示从(0,0)到(i,j)有多少种路径
int[][] dp = new int[m][n];
// 先初始化数据。
for (int i = 0; i < m; i++) {
// 先遍历行
for (int j = 0; j < n; j++) {
// 初始化第一行和第一列
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
// 状态转移方程 每次只能向下或者向右移动一步。所以结果为上一行和左一行之和
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}不同路径2
java
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
if (obstacleGrid[i][0] == 1) {
break;
}
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
if (obstacleGrid[0][i] == 1) {
break;
}
dp[0][i] = 1;
}
if (m == 1 || n == 1) {
return dp[m - 1][n - 1];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}整数拆分
java
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; i++) {
// 固定dp[i] 然后枚举dp[i-j]的值。
for (int j = 1; j <= i / 2; j++) {
// 这里是比较的dp[i]和dp[i-j] * dp[j]
int max = Math.max(j * (i - j), j * dp[i - j]);
dp[i] = Math.max(dp[i], max);
}
}
return dp[n];
}不同的二叉搜索树
https://leetcode.cn/problems/unique-binary-search-trees/description/
java
public int numTrees(int n) {
// 当节点数为0时，结果为1
int[] dp = new int[n + 1];
if (n <= 1) {
return 1;
}
if (n == 2) {
return 2;
}
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
// 当 n=3时，有3种情况
// 当头节点为1时，结果= 左子树个数为0 * 右子树个数为2
// 当头节点为2时，结果= 左子树个数为1 * 右子树个数为1
// 当头节点为3时，结果= 左子树个数为2 * 右子树个数为0
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}背包
01 背包
有n种物品每种物品只有一个，每个物品有自己的价值和重量。目前有一个背包只能装重量为m的背包。
问：能装最多的价值的是多少？
完全背包
有n种物品每种物品有无限个
多重背包
有n种物品，每种物品的个数各不相同
递推公式的确定
bash
Dp[i][j] 表示 放第i个物品后，背包重量为j的最大价值不放物品i
bash
dp[i-1][j]放物品i
bash
dp[i-1][j-weight[i]]+value[i]dp数组初始化
01背包-滚动数组
物品0 1 15
物品1 3 20
物品2 4 30
背包最大重量为4
dp[j]数组含义；容量为j的背包，能够接受的最大价值
不放物品[i]
bash
dp[j]放物品i
bash
dp[j-weight[i]]+value[i]初始化
bash
dp[0]=0二维数组该怎么初始化
为啥一维数组，遍历的时候，
只能先遍历物品，再遍历背包，如果二者颠倒的话，会不会存在问题。
为啥二维数组遍历的时候，什么顺序都可以。
分割等和集
把一个集合分成2个子集，使得一个子集等于另一个子集的一半
比如[1,5,11,5].哪些元素能够变成一个子集
可以抽象成01背包。dp[j] 容量为J
java
public boolean canPartition(int[] nums) {
int sum = 0;
int target = 0;
// 问题简化成，现在有一个背包，背包容量为sum/2，背包中可以放入nums中的任意物品，问是否可以完全装满背包。01背包
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (sum % 2 != 0) {
return false;
}
target = sum / 2;
int dp[] = new int[target + 1];
// 先遍历物品
for (int i = 0; i < nums.length; i++) {
// 先遍历背包。倒叙遍历的目的：倒序遍历，是为了保证dp[j]的值，是j-nums[i]时，已经计算好的。
for (int j = target; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return target == dp[target];
}最后一块石头的重量 II
https://leetcode.cn/problems/last-stone-weight-ii/
java
public int lastStoneWeightII(int[] stones) {
if (stones.length == 1) {
return stones[0];
}
int sum = 0;
for (int i = 0; i < stones.length; i++) {
sum += stones[i];
}
// System.out.println(sum);
// dp数组定义：dp[i] 表示：当容量为 i 时，背包中物品的 最大价值
int[] dp = new int[sum / 2 + 1];
// 初始化dp数组
// printArray(dp);
int res = Integer.MAX_VALUE;
// 先遍历物品
for (int i = 0; i < stones.length; i++) {
// 后遍历背包
for (int j = sum / 2; j >= stones[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
// printArray(dp);
for (int i = sum / 2; i >= 0; i--) {
res = Math.min(res, sum - 2 * dp[i]);
}
return res;
}494 目标和
https://leetcode.cn/problems/target-sum/
java
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
int n = nums.length;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
// left 为正数的集合，right 为负数的集合
// 根据计算公式。left + right = sum
// left - right = target
// 所以推出 left = (sum + target) / 2
if ((sum + target) % 2 != 0) {
return 0;
}
// 正数之和不能小于0
if (sum < Math.abs(target)) {
return 0;
}
int left = (sum + target) / 2;
System.out.println(left);
// 这里定义一个二维的dp数组，含义：dp[i][j] 表示在前 i 个数字中，和为 j 的方案数。
int[][] dp = new int[n + 1][left + 1];
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
// 填入第一个数字，为啥初始化成1。 前i个数字中，和为0的方案只有1种，就是不选这个数字。
// dp[i][0] = 1;
// j表示和
for (int j = 0; j <= left; j++) {
// 如果当前数字小于等于j，那么可以选择或者不选择当前数字
// System.out.println("i:" + i + " j:" + j);
if (j - nums[i] >= 0) {
// 含义：dp[i-1][j] 表示前i-1个和为j的方案数目之和(即不选该数值)+ 或者 选完该数值+ dp[i-1][j-nums[i]]
// 比如 现在 i=10 nums[i]=8 和为12 ，则dp[10][12] = dp[9][12] + dp[9][4]。表示 前9个数字中，和为12的方案数之和。以及 前9个数字中，和为4的方案数之和。
dp[i + 1][j] = dp[i][j] + dp[i][j - nums[i]];
} else {
// 当前数字大于j，只能不选当前数字
dp[i + 1][j] = dp[i][j];
}
}
}
// printArray(dp);
return dp[n][left];
}一和零
https://leetcode.cn/problems/ones-and-zeroes/description/
java
public int findMaxForm(String[] strs, int m, int n) {
int num = strs.length;
// 创建二维数组,含义为: dp[i][j]=方案数。其中有0个0和1的方案数。i表示0的个数，j表示1的个数
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i < num; i++) {
// 获取当前字符串中0的个数
int zero = find0(strs[i]);
// 获取当前字符串中1的个数
int one = strs[i].length() - zero;
for (int j = m; j >= zero; j--) {
for (int k = n; k >= one; k--) {
// 这里很关键，这里要取两个数中的最大值
dp[j][k] = Math.max(dp[j][k], dp[j - zero][k - one] + 1);
}
}
printArray(dp);
}
return dp[m][n];
}
public int find0(String str) {
int count = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '0') {
count++;
}
}
return count;
}完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。这就是完全背包问题
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
背包最大重量为4。
物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
首先再回顾一下01背包的核心代码：
java
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}朴素写法
动态规划数组定义：
使用二维数组f[i][j]，其中f[i][j]表示考虑前i件物品，当背包容量为j时的最大价值。
状态转移方程：
cpp
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k)这个方程考虑了不选取当前物品和选取当前物品k次两种情况下的最大价值，并取这些情况的最大值更新DP数组。
循环遍历：
- 外层循环遍历所有物品，中层循环遍历所有可能的背包容量。
- 内层循环遍历每个物品的可能选取次数
k（即物品i可以被选取0次、1次、2次，直到k * v[i]超过当前背包容量j）。 - 对于每种情况，更新
f[i][j]为max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k)，表示考虑选取k次物品i时的最大价值。
java
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= m; j++)
{
for (int k = 0; k * v[i] <= j; k++)
{
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
}
}
}接下来，就可以进行优化了
零件兑换2
https://leetcode.cn/problems/coin-change-ii/
java
public int change(int amount, int[] coins) {
// 定义：dp[i][j] 表示使用前 i 个硬币组成 j 金额有多少种方法
int[][] dp = new int[coins.length + 1][amount + 1];
//
// 初始化
for (int i = 0; i <= coins.length; i++) {
dp[i][0] = 1;
}
// 状态转移方程。先遍历物品
for (int i = 1; i <= coins.length; i++) {
// 再遍历背包
for (int j = 0; j <= amount; j++) {
if (j - coins[i - 1] >= 0) {
// 这里表示背包容量 j 可以通过前 i 个物品组成的方法。包括2类。第一类，不使用第i个物品，但是价值为 j 的方法数。第二类，使用第 i 个物品，但是价值为 j-coins[i] 的方法数。
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[coins.length][amount];
}377-组合总和4
https://leetcode.cn/problems/combination-sum-iv/description/
java
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];
}
}322零钱兑换
https://leetcode.cn/problems/coin-change/description/
java
public int coinChange(int[] coins, int amount) {
// 定义数组。装满容量为j的最小硬币数.
int[] dp = new int[amount + 1];
// 初始化数组 容量为0的需要填充的最小硬币数目为0
// Arrays.sort(coins);
dp[0] = 0;
// 其他容量因为比较的是最小值，所以初始化数组为正无穷大
for (int i = 1; i <= amount; i++) {
dp[i] = amount + 1;
}
// 先遍历背包
for (int i = 1; i <= amount; i++) {
// 再遍历物品。这样子才能实现完全背包
for (int j = 0; j < coins.length; j++) {
// 如果容量大于物品的容量，则表示该物品可以放入背包
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
// printArray(dp);
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}279-完全平方数
https://leetcode.cn/problems/perfect-squares/description/
这题和零钱兑换基本上属于一样的题目。
转换下思路。现在给一个容量为n的背包，然后给我们1，4，9，16... 这样子价值的物品，问装满容量为n的背包需要最小的物品个数
java
public int numSquares(int n) {
// 含义：dp[i]表示i的完全平方数的个数
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
// 先遍历背包
for (int i = 1; i <= n; i++) {
// 再遍历物品
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
// printArray(dp);
}
return dp[n];
}139-单词拆分
https://leetcode.cn/problems/word-break/description/
java
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] f = new boolean[n + 1];
f[0] = true;
for (int i = 1; i <= n; i++) {
// 遍历所有子串
for (int j = 0; j < i; j++) {
// 状态转移方程
if (f[j] && wordDict.contains(s.substring(j, i))) {
f[i] = true;
}
}
}
return f[n];
}198-打家劫舍
https://leetcode.cn/problems/house-robber/description/
java
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n + 1];
if (n == 0) {
return 0;
}
if (n == 1) {
return nums[0];
}
if (n == 2) {
return Math.max(nums[0], nums[1]);
}
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
// dp[i-1] 就是不偷窃的最大金额，dp[i-2] + nums[i-1] 就是偷窃的最大金额
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
// printArray(dp);
return dp[n - 1];
}213-打家劫舍
https://leetcode.cn/problems/house-robber-ii/description/
java
public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
} else if (nums.length == 2) {
return Math.max(nums[0], nums[1]);
} else if (nums.length == 3) {
return Math.max(nums[0], Math.max(nums[1], nums[2]));
}
int n = nums.length;
int[] dp = new int[n + 1];
// 情况1
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n - 1; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
// printArray(dp);
// 情况2
int result = dp[n - 2];
System.out.println("result:" + result);
dp[0] = nums[1];
dp[1] = Math.max(nums[1], nums[2]);
for (int i = 3; i < n; i++) {
dp[i - 1] = Math.max(dp[i - 2], dp[i - 3] + nums[i]);
}
result = Math.max(result, dp[n - 2]);
// printArray(dp);
return result;
}337-打家劫舍 III
https://leetcode.cn/problems/house-robber-iii/description/
java
public int rob(TreeNode root) {
int[] a = sum(root);
return Math.max(a[0], a[1]);
}
public int[] sum(TreeNode root){
int[] a = new int[2];
if(root == null){
return a;
}
int[] left = sum(root.left);
int[] right = sum(root.right);
// 第一个数表示当前节点偷，第二个数表示当前节点不偷
// 如果当前节点偷了，那么左右子节点就不能偷了。
a[0] = left[1] + right[1] + root.val;
// 如果当前节点不偷了，那么左右子节点可以偷或者不偷。
a[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return a;
}买卖股票的最佳时机
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
java
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2];
// 初始化 0表示不持有股票 1表示持有股票
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < prices.length; i++) {
// 第i天不持有股票。 等于（昨天不持有股票，今天不买入股票)和(昨天持有股票，今天卖出股票)
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
// 第i天持有股票，等于(昨天持有股票，今天不买入股票)和(昨天不持有股票，今天买入股票)
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[prices.length - 1][0];
}122-买卖股票的最佳时机2
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
java
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < prices.length; i++) {
// 0表示不持有股票，1表示持有股票。
// 当天 不持有股票= 前一天不持有股票和前一天持有股票，加上当天股票价格
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
// 当天 持有股票= 前一天持有股票和前一天不持有股票，减去当天股票价格
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[prices.length - 1][0];买卖股票的最佳时机3
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
java
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[prices.length][5];
// 0-表示不操作，1-表示第一次持有，2-表示第一次卖出，3-表示第二次持有，4-表示第二次卖出
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 0;
for (int i = 1; i < prices.length; i++) {
// 不操作
dp[i][0] = dp[i - 1][0];
// 第一次持有
dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
// 第一次卖出。第一次持有+当前价格，或者 保持第一次卖出，
dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
// 第二次持有。第二次持有/第一次卖出-当前价格，或者保持第二次持有
dp[i][3] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3]);
// 第二次卖出。第二次卖出+当前价格，或者保持第二次卖出
dp[i][4] = Math.max(dp[i - 1][3] + prices[i], dp[i - 1][4]);
}
return Math.max(dp[n - 1][4], dp[n - 1][2]);
}买卖股票的最佳时机4
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
java
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (n <= 1) {
return 0;
}
// 表示第i天持有股票第k个股票
int[][] buyer = new int[n][k + 1];
// 表示第i天不持有第k个股票
int[][] seller = new int[n][k + 1];
// 初始化
buyer[0][0] = 0;
seller[0][0] = 0;
for (int j = 1; j <= k; j++) {
buyer[0][j] = -prices[0];
seller[0][j] = 0;
}
// System.out.println("第1天");
// printArray(buyer);
// printArray(seller);
// 开始进行递归迭代
for (int i = 1; i < n; i++) {
for (int j = 1; j <= k; j++) {
// 第i天持有第j个股票 = 前一天持有第j个股票或者前一天不持有第j-1个股票，并且今天买入
buyer[i][j] = Math.max(buyer[i - 1][j], seller[i - 1][j - 1] - prices[i]);
// 第i天不持有第j个股票 = 前一天不持有第j个股票或者前天持有第j个股票，并且今天卖出
seller[i][j] = Math.max(seller[i - 1][j], buyer[i - 1][j] + prices[i]);
}
// System.out.println("第" + (i + 1) + "天");
// printArray(buyer);
// printArray(seller);
}
return seller[n - 1][k];
}
}java
public int maxProfit(int[] prices) {
int n = prices.length;
// 动态规划。多加个冷冻期
int[][] dp = new int[prices.length][4];
// 0：持有股票，1：保持卖出股票的状态, 2:具体卖出股票 3：冷冻期
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
dp[0][3] = 0;
for (int i = 1; i < prices.length; i++) {
// 持有股票的情况。= 前一天持有股票 或者 前一天是冷冻期的股票，但是买入
dp[i][0] = Math.max(Math.max(dp[i - 1][0], dp[i - 1][3] - prices[i]), dp[i - 1][1] - prices[i]);
// 保持卖出股票状态，
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
// 具体卖出股票
dp[i][2] = dp[i - 1][0] + prices[i];
// 冷冻期=只能是卖出股票的状态
dp[i][3] = dp[i - 1][2];
printArray(dp);
}
return Math.max(Math.max(dp[n - 1][0], dp[n - 1][1]), Math.max(dp[n - 1][2], dp[n - 1][3]));
}300-最长递增子序列
https://leetcode.cn/problems/longest-increasing-subsequence/
java
public int lengthOfLIS(int[] nums) {
// 定义数组：dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度
int[] dp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
// 为啥可以跳跃，是因为不是最长的递增子序列
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Arrays.stream(dp).max().getAsInt();
}674-最长连续递增子序列
https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/
java
public int findLengthOfLCIS(int[] nums) {
// 定义：dp[i] 表示以 nums[i] 结尾的最长连续递增子序列的长度
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int res = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
}
res = Math.max(res, dp[i]);
// printArray(dp);
}
return res;
}718-最长重复子数组
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
java
public int findLength(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
// 数组定义：dp[i][j] 表示 nums1[0...i-1] 和 nums2[0...j-1] 的最长公共子序列的长度
int[][] dp = new int[n + 1][m + 1];
int result = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 如果当前的元素相等，则直接开始比较
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
result = Math.max(result, dp[i][j]);
}
}
return result;
}95-最长公共子序列
https://leetcode.cn/problems/longest-common-subsequence/description/
java
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
// 创建二维数组,含义：dp[i][j]表示text1[0...i-1]和text2[0...j-1]的最长公共子序列的长度
int[][] dp = new int[m + 1][n + 1];
int result = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 当元素相同的时候
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 当元素不相同的时候
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
result = Math.max(result, dp[i][j]);
}
}
return result;
}1035-不想交的线
https://leetcode.cn/problems/uncrossed-lines/
java
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[][] dp = new int[m + 1][n + 1];
int result = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
result = Math.max(result, dp[i][j]);
}
}
return result;
}53 最大子数组和
https://leetcode.cn/problems/maximum-subarray/
java
392-判断子序列
https://leetcode.cn/problems/is-subsequence/description/
java
public boolean isSubsequence(String s, String t) {
if (s.length() > t.length()) {
return false;
}
int m = 0;
int n = 0;
while (m < s.length() && n < t.length()) {
if (s.charAt(m) == t.charAt(n)) {
m++;
n++;
} else {
n++;
}
}
return m == s.length();
}不同的子序列
https://leetcode.cn/problems/21dk04/description/
java
class Solution {
public int numDistinct(String s, String t) {
int m = s.length();
int n = t.length();
// 函数定义：dp[i][j]表示s的前i-1个字符和t的前j-1个字符匹配的个数
int[][] dp = new int[m + 1][n + 1];
// 初始化
for (int i = 0; i <= m; i++) {
dp[i][0] = 1;
}
for (int j = 1; j <= n; j++) {
dp[0][j] = 0;
}
int res=0;
// 开始递推
for (int i = 1; i <=m; i++) {
for (int j = 1; j <=n; j++) {
// 如果字符串相等
if (s.charAt(i-1) == t.charAt(j-1)) {
// 这里最关键。
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}else {
dp[i][j]= dp[i - 1][j];
}
}
res = Math.max(res, dp[i][n]);
}
return res;
}
}583.两个字符串的删除操作
java
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// 定义二维数组，含义：dp[i][j] 表示 word1 的前 i-1 个字符和 word2 的前 j-1 个字符的最小编辑距离
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
// int result = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 最关键的是这里，字符串不相等的情况下，3 种操作中选择一种最小的
// 删除word1中 i - 1 字符串。或者插入word2中 j-1个字符串
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
// result = Math.min(result, dp[i][j]);
}
}
return dp[m][n];
}
}72-编辑距离
https://leetcode.cn/problems/edit-distance/description/
java
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
}
}
return dp[m][n];
}647-回文子串
java
public int countSubstrings(String s) {
int n = s.length();
// dp[i][j] 表示 s[i..j] 是否为回文串
int[][] f = new int[n][n];
if (n == 1) {
return 1;
}
// 初始化矩阵
for (int i = 0; i < n; i++) {
f[i][i] = 1;
}
int count = 0;
// 状态转移方程。关键是遍历顺序
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
// 如果当前字符相同
if (s.charAt(i) == s.charAt(j)) {
if (j - i <= 1) {
f[i][j] = 1;
} else {
// 状态转移方程
f[i][j] = f[i + 1][j - 1];
}
}
count += f[i][j];
}
}
printArray(f);
return count;
}516-最长回文子序列
https://leetcode.cn/problems/longest-palindromic-subsequence/description/
java
public int longestPalindromeSubseq(String s) {
int n = s.length();
// 数组定义 ： f[i][j] 表示 s[i..j] 是否为回文串
int[][] f = new int[n][n];
// 从下往上遍历
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (i == j) {
f[i][j] = 1;
// 如果字符串相等
} else if (s.charAt(i) == s.charAt(j)) {
f[i][j] = f[i + 1][j - 1] + 2;
} else {
f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
}
}
}
// 返回结果
return f[0][n - 1];
}构造题-硬币面值还原(455周赛)
https://leetcode.cn/problems/inverse-coin-change/description/
java
public List<Integer> findCoins(int[] numWays) {
int[] dp = new int[numWays.length + 1];
int money = numWays.length;
List<Integer> res = new ArrayList<>();
while (true) {
boolean flag = false;
for (int i = 0; i < numWays.length; i++) {
// 找到第一个为1的数字，表示该数字就是对应的硬币
if (numWays[i] - dp[i + 1] == 1) {
System.out.println("找到硬币：" + (i + 1));
res.add(i + 1);
flag = true;
break;
}
}
// 如果没有找到，则结束循环
if (!flag) {
// 没有找到的情况下，需要判断dp和numsWays是否相等.。如果相等，则返回res。如果不相等，则表示没有结果
for (int i = 0; i < numWays.length; i++) {
if (dp[i + 1] != numWays[i]) {
return new ArrayList<>();
}
}
return res;
}
// dp全部变成0
for (int i = 0; i < dp.length; i++) {
dp[i] = 0;
}
dp[0] = 1;
// 开始根据硬币数量，更新dp数组。
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j <= money; j++) {
// 如果背包的容量大于等于硬币数量，则更新dp[j]
if (j >= res.get(i)) {
dp[j] += dp[j - res.get(i)];
}
}
}
printArray(dp);
}
}
private void printArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
/**
* 打印二维数组
*
* @param a
*/
private void printArray(int[][] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}
System.out.println();
}最长回文子串(⭐)
java
public String longestPalindrome(String s) {
// 暴力解法
int n = s.length();
int maxLen = 1;
int begin = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (j - i + 1 > maxLen && validPalindromic(s, i, j)) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
private boolean validPalindromic(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}java
public String longestPalindrome(String s) {
int n = s.length();
int maxLen = 1;
int begin = 0;
if (n < 2) {
return s;
}
// 定义状态数组 dp[i][j] 表示 s[i...j] 是否是回文串
boolean[][] dp = new boolean[n][n];
// 对角线上赋值为 true。如果长度为1的串，则肯定是回文串
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int j = 1; j < n; j++) {
// 长度为2的串 判断是否相等。如果相等则肯定是回文串
dp[j - 1][j] = s.charAt(j - 1) == s.charAt(j);
if (dp[j - 1][j] && maxLen < 2) {
maxLen = 2;
begin = j - 1;
}
// 状态转移方程
for (int i = 0; i < j - 1; i++) {
// 状态转移方程 s[i...j] ，如果 aba为回文串，则 b aba b 为回文串。首尾多加一个。
dp[i][j] = dp[i + 1][j - 1] && (s.charAt(i) == s.charAt(j));
if (dp[i][j] && maxLen < j - i + 1) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}划分数组得到最小的XOR
https://leetcode.cn/contest/weekly-contest-456/problems/partition-array-to-minimize-xor/
https://leetcode.cn/problems/split-array-largest-sum/description/
图论
图的种类
有向，无向，权值
出度和入度都是针对有向图来说
连通分量- 图里面最大的强连通子图分量
图的存储
图的遍历
- bfs
- Dfs