E.位运算-与或：2871题+2401题

题目链接：2871. 将数组分割成最多数目的子数组（中等）

算法原理：

解法：贪心+位运算

4ms击败37.50%

时间复杂度O(N)

①与运算性质：与运算的数越多，最终结果越小

②那么基于①，子数组的AND≥整个数组的AND

③记整个数组的AND为a，根据②，如果分割出超过一个数组，那么得分至少为2a，此时2a>a，因此我们会选择不分割，答案为1

④因此得出结论：如果a>0，那么只能分割出1个数组（nums数组本身）

⑤如果a=0，那么我们就可以分割出尽量多的AND=0的子数组，咋分？？

⑥从左往右遍历，只要发现AND=0，就立即分割，因为不立即分割的话，当前多AND了一个数，后面就会少AND一个数，后面AND的概率就小了（其实是贪心的思想）

⑦需要注意的是：如果最后一段子数组的AND>0，这一段可以直接合并到前一个AND=0的子数组中

JAVA代码：

class Solution { //2871. 将数组分割成最多数目的子数组 public int maxSubarrays(int[] nums) { int ret=0; //-1的二进制：11……1，和任何数与运算都等于那个数 int a=-1; for(int x:nums){ a&=x; if(a==0){ ret++;//分割 a=-1; } } //如果ret=0，说明所有数的 AND>0，答案为1 return Math.max(ret,1); } }

题目链接：2401. 最长优雅子数组（中等）

算法原理：

解法一：暴力枚举

3ms击败72.66%

时间复杂度O(n logn)

子数组中任意两个数按位与均为0，意味着子数组所有数的第 i 个比特位，最多只能有一个1，其余均为0，否则必然有两个数的按位与>0

根据鸽巢原理（抽屉原理），本题数据范围下，优雅子数组的长度不会超过30，否则一个int装不下

既然长度不会超过30，那么直接暴力枚举子数组右端点 i 即可，定义 j 往前遍历，只要按位与=0，就更新最大长度

解法二：滑动窗口

3ms击败72.66%

时间复杂度O(N)

滑动窗口专题：一轮复习——C.滑动窗口模型总结

通过前面的分析我们知道：所有数的二进制位是“互不相交”的，没有任何一个位置上有超过1个1

因此我们可以利用或运算维护当前窗口中所有元素的位并集，用类似“状态压缩”的方式，快速判断每个二进制位上是否已经有1

出窗口：只要当前元素nums[right]与or有占位冲突，持续将nums[left]出窗口，直至nums[right]与or没有占位冲突

进窗口：nums[right]与or没有占位冲突后，将nums[right]放进窗口里，对应占位

更新：此时窗口内是符合优雅子数组的定义的，各个二进制位与运算后结果为0，更新最长长度

JAVA代码：

class Solution { //2401. 最长优雅子数组 //解法一：暴力枚举 public int longestNiceSubarray(int[] nums) { int ret=0; for(int i=0;i<nums.length;i++){//枚举子数组右端点i int or=0; int j=i; //nums[i]与子数组中的任意元素AND均为0 while(j>=0&&(or&nums[j])==0) or|=nums[j--];//加到子数组中 ret=Math.max(ret,i-j); } return ret; } }

class Solution { //2401. 最长优雅子数组 //解法二：滑动窗口 public int longestNiceSubarray(int[] nums) { int ret=0; int or=0; int left=0; for(int right=0;right<nums.length;right++){ //出窗口 while((or&nums[right])>0) or^=nums[left++]; //进窗口 or|=nums[right]; //更新 ret=Math.max(ret,right-left+1); } return ret; } }