今日学习记录
1. 含上限元素的子序列和leetcode.3685
关键词：背包 双指针
问题分析：
- 内层就是 0-1 背包选择所有符合条件的数相加能等于 k
- 外层要满足元素中的元素不能大于题目中的 x,要求这个满足要求的 x 的数组
核心思路
- 先解决外层,找这个 x,我一开始误以为答案是单调的,所以想到二分来缩小搜索范围,但是数据似乎没有我想到的那么好,实际上是不存在单调,所以我认为就是暴力枚举,可以很明显的看到,0-1 背包本质就是搜索+回溯,光是内层时间复杂度就已经很高了,但是我尽量的去优化内层,还是超时了,现在看来,我并没有理解背包的本质,只是一味的搜索,在已知外层必定是枚举后,注重内层数据
- 首先还是有规律的,比如当 x 已经大于满足的数对,那么后面无论 x 怎么增大都不会影响答案,后面的搜索可以省去,但是要数据集中处理增加搜索效率,不如先排序(O(logn))
- 其实最重要的地方就是这个以 x 为界限,把 k 当成一个集合,我要从这个集合中挑出和为 k 的数,那么这些数有大有小,由于大于 x 的数都会变成 x,所以我们考虑,当数组中发现有大于 x 的数之前看能不能选出符合条件的数,那么第二种就是选择比 x 大的数,将其替换成 x,再从比 x 小的数中找到 k-x 的集合,这就是递归,从主问题向子问题分解,这就是这道题的最核心思想,想到这就完全弄懂了
vector<bool> subsequenceSumAfterCapping(vector<int>& nums, int k) {
ranges::sort(nums);
int n = nums.size();
vector<bool> arr(n);
vector<bool > f(k+1);
f[0] = true;
//枚举x
//对于数组中与x相等的,没有选或不选,直接检查,相等的一直都是一样的
//数组中的值是不变的,但是数组是单调递增的,x增大也是递增的,所以可以直接i=0全局
int i = 0;
for(int x = 1;x<=n;x++){
//排序后会有临界值,大于x和小于x,所以才单独处理等于x的数
//在小于k的数中找,找了再减去,再在k-nums[i]中找
while(i<n&&nums[i]==x){
for(int j = k;j>=nums[i];j--){
//选还是不选
f[j] = f[j]||f[j-nums[i]];
}
i++;
}
//i选完了,选比x大的数了
for(int j = 0;j<=min(n-i,k/x);j++){
if(f[k-j*x]){
arr[x-1] = true;
break;
}
}
}
return arr;
}- 还能再优化,使用 bitset 来进行进一步优化
vector<bool> subsequenceSumAfterCapping(vector<int>& nums, int k) {
ranges::sort(nums);
int n = nums.size();
vector<bool> arr(n);
bitset<4001> f = 1;
f[0] = true;
//枚举x
//对于数组中与x相等的,没有选或不选,直接检查,相等的一直都是一样的
//数组中的值是不变的,但是数组是单调递增的,x增大也是递增的,所以可以直接i=0全局
int i = 0;
for(int x = 1;x<=n;x++){
//排序后会有临界值,大于x和小于x,所以才单独处理等于x的数
//在小于k的数中找,找了再减去,再在k-nums[i]中找
while(i<n&&nums[i]==x){
f |= f<<nums[i];
i++;
}
//i选完了,选比x大的数了
for(int j = 0;j<=min(n-i,k/x);j++){
if(f[k-j*x]){
arr[x-1] = true;
break;
}
}
}
return arr;
}**最终代码：
学到的点：
- 背包问题更深入理解
- 理解核心思维,而并非基础算法