欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 汽车 > 维修 > 代码随想录算法训练营第42天 [1049. 最后一块石头的重量 II 494. 目标和 474.一和零]

代码随想录算法训练营第42天 [1049. 最后一块石头的重量 II 494. 目标和 474.一和零]

2024/11/30 10:38:21 来源:https://blog.csdn.net/weixin_45612015/article/details/139783212  浏览:    关键词:代码随想录算法训练营第42天 [1049. 最后一块石头的重量 II 494. 目标和 474.一和零]

代码随想录算法训练营第42天 [1049. 最后一块石头的重量 II 494. 目标和 474.一和零]


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

链接: 代码随想录.
思路:石头相撞重量最小,最小的情况就是刚好分为两组大小相同的,这样相撞后重量就为0
所以转化为 重量之和的一半 target容量的背包,尽可能装满,石头的重量和价值都是stones[i]
dp[j] 容量为j的背包最大重量为dp[j]
做题状态:看解析后做出来了

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {//石头相撞重量最小,最小的情况就是刚好分为两组大小相同的,这样重量就为0//所以转化为 重量之和的一半 target容量的背包,尽可能装满,石头的重量和价值都是stones[i]//dp[j] 容量为j的背包最大重量为dp[j]int sum = 0;for(int n : stones){sum+=n;}int target = sum/2;vector<int> dp(target+1,0);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];}
};

二、494. 目标和

链接: 代码随想录.
思路:

将数组中需要添加+的记为left ,需要添加-的记为right
数组元素中的和为sum,数组元素加了符号后的和为targeet
得到 left+right = sum left-right = target
推导得到 left = (sum+target)/2 如果不能整除,肯定没有解,直接返回0
代入一下示例 left = (5+3)/2 = 4
相当于left的和要凑为4
相当于背包容量为4,从nums中取物品装满背包有多少种方式
dp[j] 表示容量为j的背包,有dp[4]种方式
dp[0] = 1
递推公式 dp[j] += dp[j-nums[i]]

做题状态:看解析后做出来了

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// 将数组中需要添加+的记为left ,需要添加-的记为right// 数组元素中的和为sum,数组元素加了符号后的和为targeet// 得到 left+right = sum  left-right = target// 推导得到  left = (sum+target)/2  如果不能整除,肯定没有解,直接返回0// 代入一下示例  left = (5+3)/2 = 4// 相当于left的和要凑为4// 相当于背包容量为4,从nums中取物品装满背包有多少种方式// dp[j] 表示容量为j的背包,有dp[4]种方式// dp[0] = 1//  递推公式  dp[j] += dp[j-nums[i]]int sum = 0;for (int n : nums) {sum += n;}if ((sum + target) % 2 == 1 || abs(target) > sum) {return 0;}int temp = (sum + target) / 2;vector<int> dp(temp + 1);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = temp; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[temp];}
};

三、474.一和零

链接: 代码随想录.
思路:一共有str种物品,要同时满足m个0的背包和n个1的背包
做题状态:看解析后做出来了

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (string str : strs) {int one = 0;int zero = 0;for (char s : str) {if (s == '1') {one++;} else {zero++;}}for (int i = m; i >= zero; i--) {for (int j = n; j >= one; j--) {dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1);}}}return dp[m][n];}
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com