如何在国外做网站,制作移动网站公司,网站发帖功能怎么做,上海网站seo优化组合数问题 我们思考一下#xff0c;如果要把数组分割成两个子集#xff0c;并且两个子集的元素和相等#xff0c;是否等价于在数组中寻找若干个数使之和等于所有数的一半#xff1f;是的#xff01; 因此我们可以想到#xff0c;两种方式#xff1a; ①回溯的方式找到t…
组合数问题 我们思考一下如果要把数组分割成两个子集并且两个子集的元素和相等是否等价于在数组中寻找若干个数使之和等于所有数的一半是的 因此我们可以想到两种方式 ①回溯的方式找到target但是回溯是阶乘级别的算法这里会超时。 ②从前往后遍历形象说明定义n个集合dp[i]dp[i]表示前i个数的可能组合值则有dp[i]{dp[i-1],dp[i-1]i}dp[i-1]i指的是i加上dp[i-1]中的所有元素得到的集合。同时由于长度最长200数值最大为100因此数的范围最大为1i20000因此最多只有20000个不同的数。因此dp最大为2W个数所以我们可以用集合实现并且时间复杂度满足要求O(nums.length*nums.length*max(nums[i])) class Solution {
public:bool canPartition(vectorint nums) {int sum0;for(auto i:nums) sumi;if(sum1||nums.size()1) return false;//只有偶数总和可以sum1;unordered_setint Set;vectorint temp;for(auto i:nums){if(isum) return true;for(auto itSet.cbegin();it!Set.cend();it){int cur*iti;if(cursum) return true;if(cursum) temp.emplace_back(cur);//sum的没意义}for(auto j:temp) Set.insert(j);temp.clear();Set.insert(i);}return false;}
};
遇到的问题 在循环遍历的过程中往容器中插入元素会导致容器迭代器end()和size()时刻发生变化。与此同时有的容器比如vector和string往后面增加元素超过容量capacity可能会导致拷贝从而整个迭代器失效。因此在使用循环并且需要添加元素时想使用迭代器需要额外注意 比如本题是先将所需增加的放入到一个vector中的。 我们不能企图使用临时“指针”迭代器iend()然后遍历到it!i这是错误的因为i一直指向的仍然是end()而不是end()当时指向的位置换句话说end()不是一个具体的位置而是一个抽象的位置。 int tmpSet.size();
for(auto itSet.cbegin();tmp!0;it,--tmp){ int cur*iti;if(cursum) return true;temp.emplace_back(cur);Set.insert(cur);
} 这样做仍然是错误的实际上我们在往非顺序容器中插入元素时容器的数据结构会发生变化因此导致it可能并非按照原来的想法遍历所以是错误的 唯一正确且安全的方式是如果需要在遍历的时候同时添加元素最好不要使用迭代器迭代器可以很好的遍历元素或者按迭代器范围赋值。但是边添加边遍历问题非常大。 因此对于无序容器只能使用迭代器的情况下使用临时容器存储是非常必要的对于顺序容器可以使用下标的情况下使用下标更好。 动态规划 这道题实际上和0-1背包问题很像即从n个物品中拿出一部分使得其值刚好等于target。意识到这一点我们可以定义动态转移方程 dp[i][k]max(dp[i-1][k-nums[i]],dp[i-1][k]); dp[0][nums[0]]1; //dp[i][k]表示拿前i个物品是否可以达到重量k。 这实际上和方法一组合数问题是异曲同工的方法一使用集合实现那么如果方法一使用的是数组实现呢那么数组中标记为1的实际上就是方法二的状态了 class Solution {
public:bool canPartition(vectorint nums) {int sum0;for(auto i:nums) sumi;if(sum1||nums.size()1) return false;sum1;vectorvectorint dp(nums.size(),vectorint(sum1,0));//超过sum实际上就不用看了if(nums[0]sum)dp[0][nums[0]]1;for(int i1;inums.size();i){for(int j1;jsum;j){dp[i][j]dp[i-1][j];if(j-nums[i]0)dp[i][j]max(dp[i-1][j-nums[i]],dp[i-1][j]);}if(nums[i]sum)dp[i][nums[i]]1;}return dp[nums.size()-1][sum];}
};
由于只用到前面的值很显然我们可以降维优化。
class Solution {
public:bool canPartition(vectorint nums) {int sum0;for(auto i:nums) sumi;if(sum1||nums.size()1) return false;sum1;vectorint dp(sum1,0);//超过sum实际上就不用看了if(nums[0]sum)dp[nums[0]]1;for(int i1;inums.size();i){for(int jsum;jnums[i];--j){dp[j]max(dp[j],dp[j-nums[i]]);}}return dp[sum];}
};
