本文主要是介绍算法刷题记录 Day37，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法刷题记录 Day37
Date: 2024.04.03
lc 474. 一和零
// 优化为二维数组
class Solution {public:int findMaxForm(vector<string>& strs, int m, int n) {int s_lens = strs.size();vector<pair<int, int>> nums; //(0的个数, 1的个数)for(int i=0; i<s_lens; i++){string tmp = strs[i];int count_0 = 0;int count_1 = 0;for(int j=0; j<tmp.size(); j++){if(tmp[j] == '0')count_0++;elsecount_1++;}nums.push_back(make_pair(count_0, count_1));}// dp[j][k]表示可以容纳j个0和k个1的背包，最多容纳的字符串个数。vector<vector<int>> dp(m+1, vector<int>(n+1, 0));// dp[j][k] = max(dp[j][k], dp[j-nums[i].first][k-nums[i].second]);// dp初始化为0即可。for(int i=0; i<s_lens; i++){int count_zero = nums[i].first;int count_one = nums[i].second;for(int j=m; j>=count_zero; j--){for(int k=n; k>=count_one; k--){dp[j][k] = max(dp[j][k], dp[j-count_zero][k-count_one]+1);}}}return dp[m][n];}
};// 三维数组
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int s_lens = strs.size();vector<pair<int, int>> nums; //(0的个数, 1的个数)for(int i=0; i<s_lens; i++){string tmp = strs[i];int count_0 = 0;int count_1 = 0;for(int j=0; j<tmp.size(); j++){if(tmp[j] == '0')count_0++;elsecount_1++;}nums.push_back(make_pair(count_0, count_1));}// dp[i][j][k]表示从前i个中取子集，重量小于等于(j,k)的最大价值(子集长度);// dp[i][j][k] = for(i) dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-nums[i].first][k-nums[i].second]+1);vector<vector<vector<int>>> dp(s_lens, vector<vector<int>>(m+1, vector<int>(n+1, 0)));// dp初始化:对第0个数中，j,k均符合条件的赋值1for(int j=0; j<=m; j++){for(int k=0; k<=n; k++){if(j>=nums[0].first && k>=nums[0].second)dp[0][j][k] = 1;}}for(int i=1; i<s_lens; i++){for(int j=0; j<=m; j++){for(int k=0; k<=n; k++){if(j<nums[i].first || k<nums[i].second)dp[i][j][k] = dp[i-1][j][k];else{dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-nums[i].first][k-nums[i].second]+1);}}}}return dp[s_lens-1][m][n];}
};
lc 494. 目标和*（没理解dp初始化部分）
// 2. dp
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// 将数组拆分为两个子集left和right，我们希望找到left+right=sum,left-right=target;// 由此，我们希望找到right = (sum - target) / 2;// 问题转化为数组中能组成right的子集个数。// 转为背包问题：// dp[i][j] 表示从[0, i]整数中取值，能取到j的不同集合的总数；// dp[i][j] = for(int i=0; i<n; i++) dp[i-1][j-nums[i]];int sum = 0;for(auto& num: nums)sum += num;if((sum - target) % 2 == 1 || sum < target)return 0;int right = (sum - target) / 2;int n = nums.size();vector<vector<int>> dp(n+1, vector<int>(right+1, 0));// dp初始化dp[0][0] = 1;for(int i=1; i<=n; i++){for(int j=0; j<=right; j++){ dp[i][j] = dp[i-1][j];if(j >= nums[i-1])dp[i][j] += dp[i-1][j-nums[i-1]];}}return dp[n][right];}
};// 1. 回溯
class Solution {
private:int res = 0;
public:void backTracking(vector<int>& nums, int& t, int cur_idx, int cur_v){if(cur_v == t)res++;if(cur_v > t) //非负整数数组 剪枝return;if(cur_idx == nums.size())return;for(int i=cur_idx; i<nums.size(); i++){backTracking(nums, t, i+1, cur_v+nums[i]);}return;}int findTargetSumWays(vector<int>& nums, int target) {// 将数组拆分为两个子集left和right，我们希望找到left+right=sum,left-right=target;// 由此，我们希望找到right = (sum - target) / 2;// 问题转化为数组中能组成right的个数。int sum = 0;for(auto& num: nums)sum += num;if((sum - target) % 2 == 1 || sum < target)return 0;int t = (sum - target) / 2;backTracking(nums, t, 0, 0);return res;}
};
lc 1049. 最后一块石头的重量 II
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {// 转换为背包问题：从一组石头中，选出最接近但不超过一半重量的石头。int n = stones.size();int count = 0;for(auto& stone: stones){count += stone;}int half_count = count / 2;vector<int> dp(half_count+1, 0);for(int i=0; i<n; i++){for(int j=half_count; j>=stones[i]; j--){dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);}}return (count - 2*dp[half_count]);}
};
这篇关于算法刷题记录 Day37的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
