今日学习记录
1. 3171. 找到按位或最接近 K 的子数组
关键词：LogTrick 滑窗 栈
核心思路
1.LogTrick
首先你要知道 or,就是|的性质,即集合的合并,把数组中的每个元素看作不同的集合,那么|的操作就是把对应集合中的元素合并起来
外层循环还是从左边开始,但是对于内循环,我们先定义数组的状态(定义以当前为结尾的数组中是否有符合的),由于我们要的主要信息在右边,所以从右边开始遍历(我们假如从左边开始遍历,由于我不知道下一个元素到底会不会改变整个的大小,所以只能每个枚举,而从右边遍历)
那么对于接下来就是先单纯暴力
int minimumDifference(vector<int>& nums, int k) {
int ans = INT_MAX;
int n = nums.size();
for(int i = 0;i<n;i++){
int num = nums[i];
ans = min(ans,abs(num-k));
for(int j = i-1;j>=0;j--){
nums[j] |= num;
ans = min(ans,abs(nums[j]-k));
}
}
return ans;
}那么对于这个代码肯定是不行的,那么在哪里会终止代码的循环,就是不同的 num 可能会导致前面的数据相同,即已经包含过了该 num,所以直接跳过
int minimumDifference(vector<int>& nums, int k) {
int ans = INT_MAX;
int n = nums.size();
for(int i = 0;i<n;i++){
int num = nums[i];
ans = min(ans,abs(num-k));
for(int j = i-1;j>=0;j--){
//说明nums[j]包含了num
if((nums[j]|num)==nums[j]) break;
nums[j] |= num;
ans = min(ans,abs(nums[j]-k));
}
}
return ans;
}滑动窗口+栈
首先,为什么我觉得难,被什么卡住了,我们先来看别的一道题,把题目中的位运算去掉,就求子数组和与 k 的绝对值最小差,那么就是一个经典不定滑窗题目,把右边的元素累加到窗口中,直到大于 k 了在缩小窗口使窗口中的数更小接近 k,此时就可以找到 k 左右的两个相邻数,当窗口滑完,ans 每次更新最小值就是答案; 那么,这道题其实就是加了一个异或运算,异或之后只会更大,同累加右边元素只会更大一样的逻辑,可是有一个关键性的问题,就是当我们缩小窗口的时候,加法的逆元是减法,直接减去左边的元素就行,可是异或没有逆元运算啊; 这就是这道题的核心难点,既然不能运算,就要预处理去除左边元素的情况,
class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
int n = nums.size();
int ans = INT_MAX,bottom = 0,right_or = 0;
for(int left = 0,right = 0;right<nums.size();right++){
right_or |= nums[right];
while(left<=right&&(nums[left]|right_or)>k){
ans = min(ans,(nums[left]|right_or)-k);
left++;
if(bottom<left){
for(int i = right-1;i>=left;i--){
nums[i] |= nums[i+1];
}
bottom = right;
right_or = 0;
}
}
if(right>=left) ans = min(ans,k-(nums[left]|right_or));
}
return ans;
}
};**最终代码：
int minimumDifference(vector<int>& nums, int k) {
int ans = INT_MAX;
int n = nums.size();
for(int i = 0;i<n;i++){
int num = nums[i];
ans = min(ans,abs(num-k));
for(int j = i-1;j>=0;j--){
//说明nums[j]包含了num
if((nums[j]|num)==nums[j]) break;
nums[j] |= num;
ans = min(ans,abs(nums[j]-k));
}
}
return ans;
}学到的点：
- LogTrick
- 滑动窗口+栈的运用