哪家外贸网站做的好,做一个网站的详细教学,微信公众号做网站,北京交通管制信息网站刷题记录 *1049. 最后一块石头的重量 II*494. 目标和474. 一和零 *1049. 最后一块石头的重量 II
leetcode题目地址
本题与分割等和子集类似#xff0c;要达到碰撞最后的石头重量最小#xff0c;则尽可能把石头等分为两堆。
时间复杂度#xff1a; O ( m ∗ n ) O(m * n)… 刷题记录 *1049. 最后一块石头的重量 II*494. 目标和474. 一和零 *1049. 最后一块石头的重量 II
leetcode题目地址
本题与分割等和子集类似要达到碰撞最后的石头重量最小则尽可能把石头等分为两堆。
时间复杂度 O ( m ∗ n ) O(m * n) O(m∗n) 空间复杂度 O ( n ) O(n) O(n)
// c
class Solution {
public:int lastStoneWeightII(vectorint stones) {int sum 0;for(int i0; istones.size(); i){sum stones[i];}int target sum/2;vector dp(target1, 0);for(int i0; istones.size(); i){for(int jtarget; jstones[i]; j--){dp[j] max(dp[j], dp[j-stones[i]]stones[i]);}}return sum - dp[target] - dp[target];}
};*494. 目标和
leetcode题目地址
nums中元素初始均为正先求其和sum。若|target|sum则无解。
需要推导出递推公式设“”数之和为X则“-”数之和就是sum-X其中sum和target为已知。 可得递推公式 X − ( s u m − X ) t a r g e t X-(sum-X) target X−(sum−X)target 解得 X ( t a r g e t s u m ) / 2 X (target sum) / 2 X(targetsum)/2
因此 (target sum) % 2 ! 0时 无解。
一维dp数组记录背包容量为j时可以组成target的方案数量。
例如target 5
当前已有1则有dp[4]种方案当前已有2则有dp[3]种方案当前已有k则有dp[target-k]种方案
时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m) 空间复杂度 O ( n ) O(n) O(n)
// c
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;for(int i0; inums.size(); i){sum nums[i];}if(fabs(target)sum) return 0;if((sumtarget)%2!0) return 0;vectorint dp((targetsum)/21, 0);dp[0] 1;for(int i0; inums.size(); i){for(int j(targetsum)/2; jnums[i]; j--){dp[j] dp[j-nums[i]]; }}return dp[(targetsum)/2];}
};474. 一和零
leetcode题目地址
使用二维dp数组横纵坐标分别代表0和1的背包容量即dp[i][j]代表至多包含i个0和j个1的最多子串个数。
状态转移方程 d p [ i ] [ j ] m a x ( d p [ i ] [ j ] , d p [ i − z e r o N u m ] [ j − o n e N u m ] 1 ) dp[i][j] max( dp[i][j], dp[i-zeroNum][j-oneNum]1 ) dp[i][j]max(dp[i][j],dp[i−zeroNum][j−oneNum]1)
时间复杂度 O ( m ∗ n ∗ k ) O(m*n*k) O(m∗n∗k) 空间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)
// c
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorint zeros(strs.size(), 0);vectorint ones(strs.size(), 0);for(int i0; istrs.size(); i){for(int j0; jstrs[i].size(); j){if(strs[i][j] 0) zeros[i];else ones[i];}}vectorvectorint dp(m1, vectorint(n1, 0));for(int k0; kstrs.size(); k){for(int im; izeros[k]; i--){for(int jn; jones[k]; j--){dp[i][j] max(dp[i][j], dp[i-zeros[k]][j-ones[k]]1);}}}return dp[m][n];}
};
