今日学习记录
1. 四的幂leetcode.342
关键词：位运算
问题分析：就是四的幂
核心思路
- 直接递归
if(n==1) return true;
if(n<=0||n%2) return false;
while(n%4==0) n /= 4;
return n==1;- 用 1010101010101 按位与,找到四的幂二进制奇数位上的 1,0x5555555
- 1 = 4^0
- 100 = 4^1
- 10000 = 4^2
- 或者在为 2 的幂的基础上,用数学的角度计算证明
return n>0&& (n&(n-1))==0 && n%3==1;最终代码片段：
return n>0&& (n&(n-1))==0 && (n&0x555555555)>0;学到的点：
- 简单
思考题比如 8 的幂，6 的幂等等
核心思路
- 递归直接解决所有此类问题
- 看特殊二进制位,8 是 1000,,那么就记录每个 4 倍数位子上的 1
- 当底数过大,可以直接枚举做预处理
2. 最优激活顺序得到的最大总和leetcode.3645来源 462 周赛
关键词：数组 贪心 排序 堆(优先队列)
问题分析：
- 分析不了,完全分析不了,根本就看不懂题目,抽象艺术
- 首先,就是要激活对应 limit 元素位子的值,目前活跃元素数量不能大于等于 limit[i],
- 每次激活元素后,活跃元素的数量 x,limit 中所有的<=x 的元素都变为永久非活跃
- 将能激活的值都总和,求总和最大值
核心思路
- 由于都是正数,所以加的值越多越大,肯定是要从 limit 值小的开始激活,这样每次活跃次数会尽可能减少
- 由于每次激活到 x=>limit 时,活跃次数会减去 limit 中对应重复的值的个数,当到 1 时减去活跃次数 1,到 2 时减去活跃次数 2 因为有两个 2,
- {3,3,3,2,2,1} 那如何取值呢,先考虑最坏的情况,如下情况,在活跃数 达 到1的时候所 有 的1都变为永久非活跃,即不能再激活取值,所以继续 考虑2,当取了两个值之后,活跃数 达到2, 所 有2都变为永久非活跃,也就是说最多取两个值 ,3同理,这里会 发现3,2 ,1是互不相关的,可以分组,要取最大值,肯定是每组中的最大值,分组排序,
- 分组排序,怎么储存
- 哈希分组,直接利用哈希表来存储数组
- 因为 limit 是连续有序的,所以可以直接用数组小标来存储数组,二维数组
- 因为要排序还要取前一部分或后一部分,可以用优先队列来做 结果我使用数组分组还超时了?逆天,那么这个题还有难点,就在排序时的优化,怎么去优化
long long ans = 0;
for(int i = 1;i<=n;i++){
auto & arr = gp[i];
ranges::sort(arr);
for(int j = arr.size()-1;j>=arr.size()-i;j--){
ans += arr[j];
}
}
return ans;上述中,我把每组数组拿出来排序,应该是这里有问题,正着超时,反着超内存,比赛时能调出来太难了,调到最后,tmd 就是上面 vector 数组预开销太大了
vector gp(n+1,vector<int>(n+1));我以为在存储的时候要给数组预处理小标空间
vector<vector<int>> gp(n+1);结果其实底层中使用了类似哈希表的键值插入操作,没有的值创建,所以不需要我去预分配内存优先队列做法
最终代码：
long long maxTotal(vector<int>& value, vector<int>& limit) {
int n = value.size();
vector<vector<int>> gp(n+1);
for(int i = 0;i<n;i++){
gp[limit[i]].push_back(value[i]);
}
long long ans = 0;
for(int i = 1;i<=n;i++){
auto & arr = gp[i];
if(arr.size()>i){
ranges::sort(arr,greater());
for(int j = 0;j<i;j++){
ans += arr[j];
}
}
else ans += reduce(arr.begin(),arr.end(),0LL);
}
return ans;
}学到的点：
- 分组排序
- 数组内存优化
3. 全排列leetcode.46
关键词：回溯 dfs
问题分析：
- 就是相同元素数组排列成不同数组
核心思路
- dfs 搜索+回溯,回溯点在要以不同元素为根节点加元素,之前做过 bfs 的回溯
- 复杂度计算 debug 调试就能看到清新的回溯图 以数组{1,2,3}来表示,我们可以把脑袋转 90°看,就是一个个三角,回溯和放入元素是在同一条线里的,所以三角层数递减的时候不计数,三角的层数为 3,每组有多少个三角呢,在排好 1 后 2 和 3 也要进行排序,也要选取谁来当头节点有 2 种选法,那么同理依次往后为{n-1,n-2,n-3,,,,,,,0},总共 N!次,每当数组中为空[]时则遍历完一个节点,共有 n 个节点,所以总的时间复杂度为 NxN!,这个复杂度可不小啊!
递归之前 => [1]
递归之前 => [1, 2]
递归之前 => [1, 2, 3]
递归之后 => [1, 2]
递归之后 => [1]
递归之前 => [1, 3]
递归之前 => [1, 3, 2]
递归之后 => [1, 3]
递归之后 => [1]
递归之后 => []
递归之前 => [2]
递归之前 => [2, 1]
递归之前 => [2, 1, 3]
递归之后 => [2, 1]
递归之后 => [2]
递归之前 => [2, 3]
递归之前 => [2, 3, 1]
递归之后 => [2, 3]
递归之后 => [2]
递归之后 => []
递归之前 => [3]
递归之前 => [3, 1]
递归之前 => [3, 1, 2]
递归之后 => [3, 1]
递归之后 => [3]
递归之前 => [3, 2]
递归之前 => [3, 2, 1]
递归之后 => [3, 2]
递归之后 => [3]
递归之后 => []
输出 => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]最终代码：
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> path;
int n = nums.size();
vector<bool> visted(n,false);//用来记录每次数组遍历情况
auto dfs = [&](this auto&&dfs,int depth)->void{
if(depth==n){
ans.emplace_back(vector<int>(path));
return;
}
for(int i = 0;i<n;i++){//遍历每个节点,
//本来我是想用一个累加值来使每次i从该值开始遍历的
//但是该值是一次性的不好回溯啊
if(!visted[i]){
path.push_back(nums[i]);
visted[i] = true;
dfs(depth+1);
//回溯操作
visted[i] = false;
path.pop_back();
}
}
};
dfs(0);
return ans;
}学到的点：
- 回溯+dfs
- 回溯复杂度普遍很高,所以要使用剪枝等技巧来避免额外的不需要的分支来优化,要能提前预判该分支符不符合条件
4.全排列 IIleetcode.47
关键词：排序 回溯
问题分析：
4. 做了全排列后再做这道题,就是处理如果有重复怎么办
核心思路
- 首先要搞清楚为什么会出现重复,就是因为当头节点相同时,其余元素相同,进行不同排序的结果必然相同,那么只用检测每次的头节点是否出现过,若出现过直接跳过,当然如果只检查每次问题的头节点,那么会变成暴力检索(记录了每次不同数组每个数字的位置就是暴力),还不如直接用 set.
- 固定 path 的长度,来讨论每个数该放到哪个位子,数组中每种不同的一个元素都可以随便放,那么我们要让相同的数据尽可能聚集在一起,所以先排序,再进行覆盖操作不用在回溯,如何判断只有一个数字,直接判断第二个数和第一个相不相等就行,我语言表达能力还是太差了,用灵神的原话来解释把
分类讨论:
- 如果 nums[i] != nums[i-1],那么 nums[i]就是所有等于 nums[i]的数中的第一个数.我们规定.
- 如果相等,则又要分两种讨论
- 如果 nums[i-1]没有填入,则为了避免后续生成重复排序,就不能填 nums[i],(如果先排后面,那么前面的数不好控制,有可能出现重复),直接 continue
- 如果已经填入,则可以随便填
最终代码：
vector<vector<int>> permuteUnique(vector<int>& nums) {
ranges::sort(nums);
int n = nums.size();
vector<vector<int>> ans;
vector<int> path(n);
vector<bool> visted(n,false);//用来记录每次数组遍历情况
auto dfs = [&](this auto&&dfs,int depth)->void{
if(depth==n){
ans.push_back(path);
return;
}
for(int i = 0;i<n;i++){//遍历每个节点,
if(visted[i]||i>0&&nums[i-1]==nums[i]&&!visted[i-1]) continue;
path[depth] = nums[i];
visted[i] = true;
dfs(depth+1);
//回溯操作
visted[i] = false;
}
};
dfs(0);
return ans;
}学到的点：
- 回溯优化排序
- 其中可以直接覆盖而不用每次插入,灵神的代码还是太强了,其实还是有回溯思想,只是优化掉了回溯操作