可视化网站开发工具有哪些,百度云盘,用python做网站我那些,网页定制哪家不错题目#xff1a;分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。 初步想法排序后双指针#xff0c;发现不行 class Solution {
public:bool canPartition(vectorint…题目分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 初步想法排序后双指针发现不行 class Solution {
public:bool canPartition(vectorint nums) {if(nums.size()2){return false;}sort(nums.begin(),nums.end());int left0,rightnums.size()-1;int left_sumnums[left],right_sumnums[right];while(leftright-1){if(left_sumright_sum){right--;right_sum nums[right];}else{left;left_sum nums[left];}}coutleft_sum right_sumendl;return left_sumright_sum;}
};//nums [2,2,1,1]只要找到集合里能够出现 sum / 2 的子集总和就算是可以分割成两个相同元素和子集了。可以用回溯暴力搜索出所有答案的但最后超时了也不想再优化了放弃回溯直接上01背包吧。 背包问题有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。背包问题有多种背包方式常见的有01背包、完全背包、多重背包、分组背包和混合背包等等。 确定dp数组以及下标的含义:dp[j] 表示 容量为j的背包所背的物品价值最大可以为dp[j]。 确定递推公式:01背包的递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]);相当于背包里放入数值那么物品i的重量是nums[i]其价值也是nums[i]。所以递推公式dp[j] max(dp[j], dp[j - nums[i]] nums[i]); dp数组如何初始化首先dp[0]一定是0。 class Solution {
public:bool canPartition(vectorint nums) {// int sum0;// vectorint dp(10001,0);// for(auto i:nums){// sumi;// }// if(sum % 2 1){// return false;// }// int half_sum sum/2;// for(int i0;inums.size();i){// for(int jhalf_sum;jnums[i];j--){// dp[j]max(dp[j],dp[j-nums[i]]nums[i]);// }// }// if(dp[half_sum]half_sum){// return true;// }// return false;
};不太好理解但是可以用二维的数组横坐标为sum/2的试探纵坐标为元素的探索 class Solution {
public:bool canPartition(vectorint nums) {if(nums.size()2){return false;}int sum0;for(int i:nums){sumi;}if(sum%21){return false;}int target sum/2;vectorvectorbool dp(nums.size(),vectorbool(target1,false));if(nums[0]target){dp[0][nums[0]] true;}for(int i1;inums.size();i){for(int j0;jdp[0].size();j){dp[i][j] dp[i-1][j];if(nums[i]j){dp[i][j]true;continue;}if(nums[i]j){dp[i][j] dp[i-1][j] || dp[i-1][j-nums[i]];}}if(dp[i][target]true){return true;}}return false;}
};题目最后一块石头的重量 II 有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下如果 x y那么两块石头都会被完全粉碎如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。 本题物品的重量为stones[i]物品的价值也为stones[i]。对应着01背包里的物品重量weight[i]和 物品价值value[i]。 确定dp数组以及下标的含义dp[j]表示容量这里说容量更形象其实就是重量为j的背包最多可以背最大重量为dp[j]。 确定递推公式01背包的递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]);本题则是dp[j] max(dp[j], dp[j - stones[i]] stones[i]); dp数组如何初始化因为重量都不会是负数所以dp[j]都初始化为0就可以了这样在递归公式dp[j] max(dp[j], dp[j - stones[i]] stones[i]);中dp[j]才不会初始值所覆盖。 确定遍历顺序如果使用一维dp数组物品遍历的for循环放在外层遍历背包的for循环放在内层且内层for循环倒序遍历 那么分成两堆石头一堆石头的总重量是dp[target]另一堆就是sum - dp[target]。在计算target的时候target sum / 2 因为是向下取整所以sum - dp[target] 一定是大于等于dp[target]的。那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。 class Solution {
public:int lastStoneWeightII(vectorint stones) {int sum0;for(int i:stones){sum i;}int target sum / 2;int dp[1501] {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];}
};时间复杂度O(m × n) , m是石头总重量准确的说是总重量的一半n为石头块数空间复杂度O(m) 首先对于背包的所有问题中01背包是最最基础的其他背包也是在01背包的基础上稍作变化。 确定dp数组以及下标的含义dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。 确定递推公式dp[i][j] max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] value[i]); dp数组如何初始化 确定遍历顺序01背包二维dp数组在遍历顺序上外层遍历物品 内层遍历背包容量 和 外层遍历背包容量 内层遍历物品 都是可以的 举例背包最大重量为4。物品为【物品0115】【物品1320】【物品2430】对应的dp数组的数值如图
题目目标和 给你一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 或 - 然后串联起所有整数可以构造一个 表达式 例如nums [2, 1] 可以在 2 之前添加 ‘’ 在 1 之前添加 ‘-’ 然后串联起来得到表达式 “2-1” 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 假设加法的总和为x那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) targetx (target sum) / 2此时问题就转化为装满容量为x的背包有几种方法。这里的x也就是我们后面要求的背包容量。 确定dp数组以及下标的含义dp[j] 表示填满j包括j这么大容积的包有dp[j]种方法其实也可以使用二维dp数组来求解本题dp[i] [j]使用 下标为[0, i]的nums[i]能够凑满j包括j这么大容量的包有dp[i] [j]种方法。 确定递推公式只要搞到nums[i]凑成dp[j]就有dp[j - nums[i]] 种方法。 dp数组如何初始化在初始化的时候dp[0] 一定要初始化为1因为dp[0]是在公式中一切递推结果的起源如果dp[0]是0的话递推结果将都是0。 class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum0;for(int i:nums){sumi;}if(abs(target)sum){return 0;}if((targetsum) 1){return 0;}int left(targetsum)/2;vectorint dp(left1,0);dp[0]1;for(int i0;inums.size();i){for(int jleft;jnums[i];j--){dp[j]dp[j-nums[i]];}}return dp[left];}
};时间复杂度O(n × m)n为正数个数m为背包容量空间复杂度O(m)m为背包容量 class Solution {
public:int count0;void track(vectorint nums,int target,int sum,int start){if(startnums.size()){if(sumtarget){count;}}else{track(nums,target,sumnums[start],start1);track(nums,target,sum-nums[start],start1);}} int findTargetSumWays(vectorint nums, int target) {track(nums,target,0,0);return count;}
};//回溯时间复杂度 O ( 2 n ) O(2^n) O(2n)其中 n 是数组 nums \textit{nums} nums 的长度。回溯需要遍历所有不同的表达式共有 2 n 2^n 2n 种不同的表达式每种表达式计算结果需要 O(1) 的时间因此总时间复杂度是 。空间复杂度O(n)其中 n 是数组 nums 的长度。空间复杂度主要取决于递归调用的栈空间栈的深度不超过 n。 构建一个二维数组进行存放好理解一些 记数组的元素和为 sum添加 - 号的元素之和为 neg则其余添加 的元素之和为 sum−neg得到的表达式的结果为 (sum−neg)−negsum−2⋅negtarget由于数组 nums 中的元素都是非负整数neg 也必须是非负整数所以上式成立的前提是 sum−target 是非负偶数。若不符合该条件可直接返回 0。若上式成立问题转化成在数组 nums 中选取若干元素使得这些元素之和等于 neg计算选取元素的方案数。我们可以使用动态规划的方法求解。定义二维数组 dp其中 dp [ i ] [ j ] \textit{dp}[i][j] dp[i][j] 表示在数组 nums 的前 i 个数中选取元素使得这些元素之和等于 j 的方案数。假设数组 nums 的长度为 n则最终答案为 $ \textit{dp}[n][\textit{neg}]$。 class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum0;for(int num:nums){sumnum;}int diffsum-target;if(diff0 || diff%2!0){return 0;}int nnums.size(),negdiff/2;vectorvectorint dp(n1,vectorint(neg1));dp[0][0]1;for(int i1;in;i){int tempnums[i-1];for(int j0;jneg;j){dp[i][j]dp[i-1][j];if(jtemp){dp[i][j]dp[i-1][j-temp];}}}return dp[n][neg];}
};题目一和零 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的长度该子集中 最多 有 m 个 0 和 n 个 1 。如果 x 的所有元素也是 y 的元素集合 x 是集合 y 的 子集 。 **本题中strs 数组里的元素就是物品每个物品都是一个**确定dp数组dp table以及下标的含义dp[i][j]最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。 确定递推公式dp[i][j] 可以由前一个strs里的字符串推导出来strs里的字符串有zeroNum个0oneNum个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]。 dp数组如何初始化为0 class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m1,vectorint(n1,0));for(string str:strs){int one_count0,zero_count0;for(char c:str){if(c0){zero_count;}else{one_count;}}for(int im;izero_count;i--){for(int jn;jone_count;j--){dp[i][j] max(dp[i-zero_count][j-one_count]1,dp[i][j]);}}}return dp[m][n];}
};时间复杂度: O(kmn)k 为strs的长度空间复杂度: O(mn)。经典的背包问题只有一种容量不同这道题有两种容量即选取的字符串子集中的 0 和 1 的数量上限。
完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品都有无限个也就是可以放入背包多次求解将哪些物品装入背包里物品价值总和最大。完全背包和01背包问题唯一不同的地方就是每种物品有无限件。
题目零钱兑换 II 给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。假设每一种面额的硬币有无限个。题目数据保证结果符合 32 位带符号整数。 但本题和纯完全背包不一样**纯完全背包是凑成背包最大价值是多少而本题是要求凑成总金额的物品组合个数**注意题目描述中是凑成总金额的硬币组合数组合不强调元素之间的顺序排列强调元素之间的顺序。 确定dp数组以及下标的含义:dp[j]凑成总金额j的货币组合数为dp[j] 确定递推公式:dp[j] 就是所有的dp[j - coins[i]]考虑coins[i]的情况相加。所以递推公式dp[j] dp[j - coins[i]]; 所以递推公式dp[j] dp[j - coins[i]];首先dp[0]一定要为1dp[0] 1是 递归公式的基础。如果dp[0] 0 的话后面所有推导出来的值都是0了。dp[0]1还说明了一种情况如果正好选了coins[i]后也就是j-coins[i] 0的情况表示这个硬币刚好能选此时dp[0]为1表示只选coins[i]存在这样的一种选法。 class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount1,0);dp[0]1;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}// for(auto i:dp){// coutiendl;// }return dp[amount];}
};时间复杂度: O(mn)其中 m 是amountn 是 coins 的长度空间复杂度: O(m) 在求装满背包有几种方案的时候认清遍历顺序是非常关键的。 如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。
题目组合总和 Ⅳ 给你一个由 不同 整数组成的数组 nums 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。 本题题目描述说是求组合但又说是可以元素相同顺序不同的组合算两个组合**其实就是求排列**组合不强调顺序(1,5)和(5,1)是同一个组合。排列强调顺序(1,5)和(5,1)是两个不同的排列。本质是本题求的是排列总和而且仅仅是求排列总和的个数并不是把所有的排列都列出来。把排列都列出来的话只能使用回溯算法爆搜。 确定dp数组以及下标的含义dp[i]: 凑成目标正整数为i的排列个数为dp[i] 确定递推公式dp[i]考虑nums[j]可以由 dp[i - nums[j]]不考虑nums[j] 推导出来。 dp数组如何初始化因为递推公式dp[i] dp[i - nums[j]]的缘故dp[0]要初始化为1这样递归其他dp[i]的时候才会有数值基础。 确定遍历顺序个数可以不限使用说明这是一个完全背包。个数可以不限使用说明这是一个完全背包。 如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。 用示例中的例子推导一下 class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target1,0);dp[0]1;for(int i0;itarget1;i){for(int j0;jnums.size();j){if(i-nums[j]0 dp[i] INT_MAX-dp[i-nums[j]]){// C测试用例有两个数相加超过int的数据所以需要在if里加上dp[i] INT_MAX - dp[i - num]。dp[i] dp[i-nums[j]];}}}return dp[target];}
};
