代码随想录Day 36|滑铁卢了,leetcode题目:1049.最后一块石头的重量、494.目标和、474.一和零

本文主要是介绍代码随想录Day 36|滑铁卢了,leetcode题目:1049.最后一块石头的重量、494.目标和、474.一和零,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

提示:DDU,供自己复习使用。欢迎大家前来讨论~

文章目录

  • 动态规划
  • 一、题目
    • 题目一:1049.最后一块石头的重量II
      • 解题思路:
    • 题目二:494.目标和
      • 动态规划 (二维dp数组)
      • #动态规划 (一维dp数组)
    • 题目三: 474.一和零
      • 解题思路:
  • 总结


动态规划

有点难了,之前差的有点多,找时间补

一、题目

题目一:1049.最后一块石头的重量II

leetcode题目链接

解题思路:

本题:

想象一下,你有一堆苹果,你要把它们分成两堆,使得这两堆苹果的总数尽可能接近。但是,你每次只能从这堆苹果里拿出两个来,然后放一个苹果回去,这个新放回去的苹果是那两个苹果的重量差。这个过程重复进行,直到你不能再拿出两个苹果为止。

现在,我们一步步来看这个过程:

  1. 开始:你有一堆苹果,比如【31, 26, 33, 21, 40】。

  2. 第一次比较:你拿出最重的两个苹果,40和21,它们的重量差是19,你把这个重量差19放回去,苹果堆变成了【19, 26, 31, 33】。

  3. 第二次比较:你再拿出两个苹果,比如31和19,它们的重量差是12,你把这个重量差12放回去,苹果堆变成了【12, 26, 33】。

  4. 第三次比较:你继续拿出两个苹果,比如33和12,它们的重量差是21,你把这个重量差21放回去,苹果堆变成了【21, 26】。

  5. 第四次比较:现在你只有两个苹果了,你拿出26和21,它们的重量差是5,你把这个重量差5放回去,苹果堆变成了。

  6. 结束:现在你只剩下一个苹果了,这个过程就结束了。这个最后的苹果重量5,就是两堆苹果重量差的最小值。

  7. 分组:回头看,你实际上是在尝试找到两堆苹果,一堆是【31, 26, 21】,另一堆是【40, 33】。这两堆苹果的总重量分别是78和74,它们的差值就是4,这是你通过比较苹果重量差得到的结果。

  8. 找平衡:这个过程就像是在找两堆苹果,让它们的总重量尽可能接近。这就像是你有一个天平,你想要两边放的苹果重量差不多,这样天平才能平衡。

所以,通过两两比较苹果的重量差,你实际上是在尝试找到两堆苹果,让它们的总重量尽可能接近。这个过程就像是在解决一个找平衡的问题,也就是我们说的01背包问题。这个问题的关键是找到一种方法,让两堆苹果的总重量尽可能接近,这样天平才能平衡。

本题物品的重量为stones[i],物品的价值也为stones[i]。

对应着01背包里的物品重量weight[i]和 物品价值value[i]。

接下来进行动规五步曲:

  1. 确定dp数组以及下标的含义

dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]

可以回忆一下01背包中,dp[j]的含义,容量为j的背包,最多可以装的价值为 dp[j]。

相对于 01背包,本题中,石头的重量是 stones[i],石头的价值也是 stones[i] ,可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”

  1. 确定递推公式

01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

  1. dp数组如何初始化

既然 dp[j]中的j表示容量,那么最大容量(重量)是多少呢,就是所有石头的重量和。

因为提示中给出1 <= stones.length <= 30,1 <= stones[i] <= 1000,所以最大重量就是30 * 1000 。

而我们要求的target其实只是最大重量的一半,所以dp数组开到15000大小就可以了。

当然也可以把石头遍历一遍,计算出石头总重量 然后除2,得到dp数组的大小。

这里就直接用15000了。

接下来就是如何初始化dp[j]呢,因为重量都不会是负数,所以dp[j]都初始化为0就可以了,这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖。

代码为:

vector<int> dp(15001, 0);
  1. 确定遍历顺序

如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!

代码如下:

for (int i = 0; i < stones.size(); i++) { // 遍历物品for (int j = target; j >= stones[i]; j--) { // 遍历背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}
}
  1. 举例推导dp数组

举例,输入:[2,4,1,1],此时target = (2 + 4 + 1 + 1)/2 = 4 ,dp数组状态图如下:

1049.最后一块石头的重量II

最后dp[target]里是容量为target的背包所能背的最大重量。

那么分成两堆石头,一堆石头的总重量是dp[target],另一堆就是sum - dp[target]。

在计算target的时候,target = sum / 2 因为是向下取整,所以sum - dp[target] 一定是大于等于dp[target]的

那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

以上分析完毕,C++代码如下:

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(15001, 0);int sum = 0;for (int i = 0; i < stones.size(); i++) sum += stones[i];int target = sum / 2;for (int i = 0; i < stones.size(); i++) { // 遍历物品for (int j = target; j >= stones[i]; j--) { // 遍历背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[target] - dp[target];}
};
  • 时间复杂度:O(m × n) , m是石头总重量(准确的说是总重量的一半),n为石头块数
  • 空间复杂度:O(m

题目二:494.目标和

动态规划 (二维dp数组)

假设加法的总和为x,那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = target

x = (target + sum) / 2

此时问题就转化为,装满容量为x的背包,有几种方法

这里的x,就是bagSize,也就是我们后面要求的背包容量。

大家看到(target + sum) / 2 应该担心计算的过程中向下取整有没有影响。

这么担心就对了,例如sum是5,target是2 的话其实就是无解的,所以:

(C++代码中,输入的S 就是题目描述的 target)
if ((target + sum) % 2 == 1) return 0; // 此时没有方案

同时如果target 的绝对值已经大于sum,那么也是没有方案的。

if (abs(target) > sum) return 0; // 此时没有方案

因为每个物品(题目中的1)只用一次!

这次和之前遇到的背包问题不一样了,之前都是求容量为j的背包,最多能装多少。

本题则是装满有几种方法。其实这就是一个组合问题了。

  1. 确定dp数组以及下标的含义

先用 二维 dp数组求解本题,dp[i][j]:使用 下标为[0, i]的nums[i]能够凑满j(包括j)这么大容量的包,有dp[i][j]种方法。

  1. 确定递推公式

先手动推导一下,这个二维数组里面的数值。

先只考虑物品0,如图:

img

(这里的所有物品,都是题目中的数字1)。

装满背包容量为0 的方法个数是1,即 放0件物品。

装满背包容量为1 的方法个数是1,即 放物品0。

装满背包容量为2 的方法个数是0,目前没有办法能装满容量为2的背包。

接下来 考虑 物品0 和 物品1,如图:

img

装满背包容量为0 的方法个数是1,即 放0件物品。

装满背包容量为1 的方法个数是2,即 放物品0 或者 放物品1。

装满背包容量为2 的方法个数是1,即 放物品0 和 放物品1。

其他容量都不能装满,所以方法是0。

接下来 考虑 物品0 、物品1 和 物品2 ,如图:

img

装满背包容量为0 的方法个数是1,即 放0件物品。

装满背包容量为1 的方法个数是3,即 放物品0 或者 放物品1 或者 放物品2。

装满背包容量为2 的方法个数是3,即 放物品0 和 放物品1、放物品0 和 物品 2、 放物品1 和 物品2。

装满背包容量为3的方法个数是1,即 放物品0 和 物品1 和 物品2。

通过以上举例,我们来看 dp[2][2] 可以有哪些方向推出来。

如图红色部分:

img

dp[2][2] = 3,即 放物品0 和 放物品1、放物品0 和 物品 2、放物品1 和 物品2, 如图所示,三种方法:

img

容量为2 的背包,如果不放 物品2 有几种方法呢

有 dp[1][2] 种方法,即 背包容量为2,只考虑物品0 和 物品1 ,有 dp[1][2] 种方法,如图:

img

容量为2 的背包, 如果放 物品2 有几种方法呢

首先 要在背包里 先把物品2的容量空出来, 装满 刨除物品2容量 的背包 有几种方法呢?

刨除物品2容量后的背包容量为 1。

此时装满背包容量为1 有 dp[1][1] 种方法,即: 不放物品2,背包容量为1,只考虑物品 0 和 物品 1,有 dp[1][1] 种方法。

如图:

img

有录友可能疑惑,这里计算的是放满 容量为2的背包 有几种方法,那物品2去哪了?

在上面图中,你把物品2补上就好,同样是两种方法。

dp[2][2] = 容量为2的背包不放物品2有几种方法 + 容量为2的背包不放物品2有几种方法

所以 dp[2][2] = dp[1][2] + dp[1][1] ,如图:

img

以上过程,抽象化如下:

  • 不放物品i:即背包容量为j,里面不放物品i,装满有dp[i - 1][j]中方法。
  • 放物品i: 即:先空出物品i的容量,背包容量为(j - 物品i容量),放满背包有 dp[i - 1][j - 物品i容量] 种方法。

本题中,物品i的容量是nums[i],价值也是nums[i]。

递推公式:dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

考到这个递推公式,我们应该注意到,j - nums[i] 作为数组下标,如果 j - nums[i] 小于零呢?

说明背包容量装不下 物品i,所以此时装满背包的方法值 等于 不放物品i的装满背包的方法,即:dp[i][j] = dp[i - 1][j];

所以递推公式:

if (nums[i] > j) dp[i][j] = dp[i - 1][j]; 
else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

1
2

  1. dp数组如何初始化

先明确递推的方向,如图,求解 dp[2][2] 是由 上方和左上方推出。

img

那么二维数组的最上行 和 最左列一定要初始化,这是递推公式推导的基础,如图红色部分:

img

关于dp[0][0]的值,在上面的递推公式讲解中已经讲过,装满背包容量为0 的方法数量是1,即 放0件物品。

那么最上行dp[0][j] 如何初始化呢?

dp[0][j]:只放物品0, 把容量为j的背包填满有几种方法。

只有背包容量为 物品0 的容量的时候,方法为1,正好装满。

其他情况下,要不是装不满,要不是装不下。

所以初始化:dp[0][nums[0]] = 1 ,其他均为0 。

表格最左列也要初始化,dp[i][0] : 背包容量为0, 放物品0 到 物品i,装满有几种方法。

都是有一种方法,就是放0件物品。

即 dp[i][0] = 1

  1. 确定遍历顺序

在明确递推方向时,我们知道 当前值 是由上方和左上方推出。

那么我们的遍历顺序一定是 从上到下,从左到右。

因为只有这样,我们才能基于之前的数值做推导。

例如下图,如果上方没数值,左上方没数值,就无法推出 dp[2][2]。

img

那么是先 从上到下 ,再从左到右遍历,例如这样:

for (int i = 1; i < nums.size(); i++) { // 行,遍历物品for (int j = 0; j <= bagSize; j++) { // 列,遍历背包}
}

还是先 从左到右,再从上到下呢,例如这样:

for (int j = 0; j <= bagSize; j++) { // 列,遍历背包for (int i = 1; i < nums.size(); i++) { // 行,遍历物品}
}

其实以上两种遍历都可以! (但仅针对二维DP数组是这样的)

这一点我在 01背包理论基础 (opens new window)中的 遍历顺序部分讲过。

这里我再画图讲一下,以求dp[2][2]为例,当先从上到下,再从左到右遍历,矩阵是这样:

img

当先从左到右,再从上到下遍历,矩阵是这样:

img

这里大家可以看出,无论是以上哪种遍历,都不影响 dp[2][2]的求值,用来 推导 dp[2][2] 的数值都在。

  1. 举例推导dp数组

输入:nums: [1, 1, 1, 1, 1], target: 3

bagSize = (target + sum) / 2 = (3 + 5) / 2 = 4

dp数组状态变化如下:

img

这么大的矩阵,我们是可以自己手动模拟出来的。

在模拟的过程中,既可以帮我们寻找规律,也可以帮我们验证 递推公式加遍历顺序是不是按照我们想象的结果推进的。

最后二维dp数组的C++代码如下:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<vector<int>> dp(nums.size(), vector<int>(bagSize + 1, 0));// 初始化最上行if (nums[0] <= bagSize) dp[0][nums[0]] = 1; // 初始化最左列,最左列其他数值在递推公式中就完成了赋值dp[0][0] = 1; int numZero = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] == 0) numZero++;dp[i][0] = (int) pow(2.0, numZero);}// 以下遍历顺序行列可以颠倒for (int i = 1; i < nums.size(); i++) { // 行,遍历物品for (int j = 0; j <= bagSize; j++) { // 列,遍历背包if (nums[i] > j) dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];}}return dp[nums.size() - 1][bagSize];}
};

#动态规划 (一维dp数组)

将二维dp数组压缩成一维dp数组,重复利用每一行,就是将二维数组压缩成一行。

dp[i][j] 去掉 行的维度,即 dp[j],表示:填满j(包括j)这么大容积的包,有dp[j]种方法。

  1. 确定递推公式

二维DP数组递推公式: dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

去掉维度i 之后,递推公式:dp[j] = dp[j] + dp[j - nums[i]] ,即:dp[j] += dp[j - nums[i]]

这个公式在后面在讲解背包解决排列组合问题的时候还会用到!

  1. dp数组如何初始化

在上面 二维dp数组中,我们讲解过 dp[0][0] 初始为1,这里dp[0] 同样初始为1 ,即装满背包为0的方法有一种,放0件物品。

  1. 确定遍历顺序

在动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中,我们系统讲过对于01背包问题一维dp的遍历。

遍历物品放在外循环,遍历背包在内循环,且内循环倒序(为了保证物品只使用一次)。

  1. 举例推导dp数组

输入:nums: [1, 1, 1, 1, 1], target: 3

bagSize = (target + sum) / 2 = (3 + 5) / 2 = 4

dp数组状态变化如下:

img

大家可以和 二维dp数组的打印结果做一下对比。

一维DP的C++代码如下:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<int> dp(bagSize + 1, 0);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
};
  • 时间复杂度:O(n × m),n为正数个数,m为背包容量
  • 空间复杂度:O(m),m为背包容

题目三: 474.一和零

没太明白,期待二刷

解题思路:

本题中strs 数组里的元素就是物品,每个物品都是一个!

而m 和 n相当于是一个背包,两个维度的背包

理解成多重背包的同学主要是把m和n混淆为物品了,感觉这是不同数量的物品,所以以为是多重背包。

但本题其实是01背包问题!

只不过这个背包有两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。

开始动规五部曲:

  1. 确定dp数组(dp table)以及下标的含义

dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]

2.确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我们在遍历的过程中,取dp[i][j]的最大值。

所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此时大家可以回想一下01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现,字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。

这就是一个典型的01背包! 只不过物品的重量有了两个维度而已。

  1. dp数组如何初始化

    因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。

  2. 确定遍历顺序

01背包一定是外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历!

那么本题也是,物品就是strs里的字符串,背包容量就是题目描述中的m和n。

代码如下:

for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}
}

5.举例推导dp数组

以输入:[“10”,“0001”,“111001”,“1”,“0”],m = 3,n = 3为例

最后dp数组的状态如下所示:

474.一和零

以上动规五部曲分析完毕,C++代码如下:

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};
  • 时间复杂度: O(kmn),k 为strs的长度
  • 空间复杂度: O(mn)

C++: 使用三维数组的版本

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int num_of_str = strs.size();vector<vector<vector<int>>> dp(num_of_str, vector<vector<int>>(m + 1,vector<int>(n + 1, 0)));/* 	dp[i][j][k] represents, if choosing items among strs[0] to strs[i] to form a subset, what is the maximum size of this subset such that there are no more than m 0's and n 1's in this subset. Each entry of dp[i][j][k] is initialized with 0transition formula:using x[i] to indicates the number of 0's in strs[i]using y[i] to indicates the number of 1's in strs[i]dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j - x[i]][k - y[i]] + 1)*/// num_of_zeros records the number of 0's for each str// num_of_ones records the number of 1's for each str// find the number of 0's and the number of 1's for each str in strsvector<int> num_of_zeros;vector<int> num_of_ones;for (auto& str : strs){int count_of_zero = 0;int count_of_one = 0;for (char &c : str){if(c == '0') count_of_zero ++;else count_of_one ++;}num_of_zeros.push_back(count_of_zero);num_of_ones.push_back(count_of_one);}// num_of_zeros[0] indicates the number of 0's for str[0]// num_of_ones[0] indiates the number of 1's for str[1]// initialize the 1st plane of dp[i][j][k], i.e., dp[0][j][k]// if num_of_zeros[0] > m or num_of_ones[0] > n, no need to further initialize dp[0][j][k], // because they have been intialized to 0 previouslyif(num_of_zeros[0] <= m && num_of_ones[0] <= n){// for j < num_of_zeros[0] or k < num_of_ones[0], dp[0][j][k] = 0for(int j = num_of_zeros[0]; j <= m; j++){for(int k = num_of_ones[0]; k <= n; k++){dp[0][j][k] = 1;}}}/*	if j - num_of_zeros[i] >= 0 and k - num_of_ones[i] >= 0:dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j - num_of_zeros[i]][k - num_of_ones[i]] + 1)  else:dp[i][j][k] = dp[i-1][j][k]*/for (int i = 1; i < num_of_str; i++){int count_of_zeros = num_of_zeros[i];int count_of_ones = num_of_ones[i]; for (int j = 0; j <= m; j++){for (int k = 0; k <= n; k++){if( j < count_of_zeros || k < count_of_ones){dp[i][j][k] = dp[i-1][j][k];}else{dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j - count_of_zeros][k - count_of_ones] + 1);}}}}return dp[num_of_str-1][m][n];}
};

总结

  • 今天学习的内容,学的很泛,没太明白
  • 坚持进度吧

这篇关于代码随想录Day 36|滑铁卢了,leetcode题目:1049.最后一块石头的重量、494.目标和、474.一和零的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1144512

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

烟火目标检测数据集 7800张 烟火检测 带标注 voc yolo

一个包含7800张带标注图像的数据集,专门用于烟火目标检测,是一个非常有价值的资源,尤其对于那些致力于公共安全、事件管理和烟花表演监控等领域的人士而言。下面是对此数据集的一个详细介绍: 数据集名称:烟火目标检测数据集 数据集规模: 图片数量:7800张类别:主要包含烟火类目标,可能还包括其他相关类别,如烟火发射装置、背景等。格式:图像文件通常为JPEG或PNG格式;标注文件可能为X

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists