C++ 子数组位运算结果 题型

或运算898. 子数组按位或操作 - 力扣LeetCode我们直接看题意思很明显就是找出所有子数组然后将子数组各个数相或得到的结果有多少个不同。这里我们首先想到的就是直接把所有子数组求出来在或起来但显然有很多的重复计算。我们在算[1,2] 和[1,2,3]时完全可以直接用[1,2]的结果继续算。因此有了优化思路。这里我直接告诉优化的思路参考了LogTrick 入门教程 - 知乎。可以将子数组分成以i下标开始的子数组。例如在数组[4,3,2,1,0]中我们可以将结果分成以4,3,2,1,0下标为开始的子数组。那么我们如何完整求出所有以i下标开始的子数组呢那也很好求了我们只要让以i开始的后面数挨个或在i下标的数组上每次计算后就统计这样就能将所有情况统计到了。这里我们直接给代码方便大家理解我说的逻辑int subarrayBitwiseORs(vectorint arr) { unordered_setintst;//去重 int lenarr.size(); for(int l 0; l len ; l){ st.insert(arr[l]);//只有一个数也要统计 for(int r l-1;r0; --r){ arr[r] arr[r]|arr[l];//看不懂的可以看下面的注释 st.insert(arr[r]); } } return st.size(); } // 3 2 1 0 // 3 //下标在0 // 3|2 2 //下标在1 // 3|2|1 2|1 1 //2 // 3|2|1|0 2|1|0 1|0 0 //3这样就能统计全部的结果了。但是也有问题时间复杂度是O(n²)我们再看题目要求它要统计的是所有不同的数。我们看注释表。例如看2|12|1 2意思就是这次的1不起作用那么我们对前面的3|2|1是否起作用呢答案是也不起作用另前面的式子等于 n|2|1 因为2|12不起作用所以根本不影响n。因此我们可以提前结束int subarrayBitwiseORs(vectorint arr) { unordered_setintst; int lenarr.size(); for(int l 0; l len ; l){ st.insert(arr[l]); for(int r l-1;r0 (arr[r]|arr[l])!arr[r]; --r){ arr[r] arr[r]|arr[l]; st.insert(arr[r]); } } return st.size(); }那么时间复杂度是多少呢如果每次arr[r] | arr[l]都能不等于arr[l]那么说明至少产生了一个新的位置1如果每次都是至少置1而int的位数去除符合位最多只有31次。因此可以说明是常数级别粗糙的看成O(n)。那么这个方式可以用到相同情况的题目上2411. 按位或最大的最小子数组长度 - 力扣LeetCode这里大家可以先自己做一下因为思路差不多就不多赘述。class Solution { public: vectorint smallestSubarrays(vectorint nums) { int num0,len nums.size(); vectorpairint,intret(len); for(int i0;ilen;i){ ret[i]{nums[i],1}; for(int j i-1;j0((nums[j]|nums[i])!nums[j]);--j){ nums[j]|nums[i]; if(nums[j]ret[j].first)ret[j]{nums[j],i-j1}; } } vectorintans; for(auto[_,k]:ret)ans.emplace_back(k); return ans; } };3171. 找到按位或最接近 K 的子数组 - 力扣LeetCodeclass Solution { public: int minimumDifference(vectorint nums, int k) { int ret 0x3f3f3f3f,lennums.size(); for(int i0;ilen;i){ ret min(abs(k-nums[i]),ret); for(int ji-1;j0((nums[j]|nums[i])!nums[j]);--j){ nums[j]|nums[i]; ret min(abs(k-nums[j]),ret); } } return ret; } };与运算那么我们能否推而广之用到与运算的这种求子数组运算值的呢可以的int AND(vectorint arr) { int lenarr.size(); for(int l 0; l len ; l){ for(int r l-1;r0(arr[r]arr[l])!arr[r]; --r){ arr[r] arr[r]arr[l]; st.insert(arr[r]); } } return ...; } // 0 1 2 // 0 // 01 1 // 012 12 2如果出现arr[l]arr[r] arr[r] 说明arr[l]集合更大且r左边的集合会更小完全用不到arr[l]。因此可以提前退出。时间复杂度依旧最坏情况O(n)*31粗糙来看就是O(n)。