题目链接2871. 将数组分割成最多数目的子数组中等算法原理解法贪心位运算4ms击败37.50%时间复杂度O(N)①与运算性质与运算的数越多最终结果越小②那么基于①子数组的AND≥整个数组的AND③记整个数组的AND为a根据②如果分割出超过一个数组那么得分至少为2a此时2aa因此我们会选择不分割答案为1④因此得出结论如果a0那么只能分割出1个数组nums数组本身⑤如果a0那么我们就可以分割出尽量多的AND0的子数组咋分⑥从左往右遍历只要发现AND0就立即分割因为不立即分割的话当前多AND了一个数后面就会少AND一个数后面AND的概率就小了其实是贪心的思想⑦需要注意的是如果最后一段子数组的AND0这一段可以直接合并到前一个AND0的子数组中JAVA代码class Solution { //2871. 将数组分割成最多数目的子数组 public int maxSubarrays(int[] nums) { int ret0; //-1的二进制11……1和任何数与运算都等于那个数 int a-1; for(int x:nums){ ax; if(a0){ ret;//分割 a-1; } } //如果ret0说明所有数的 AND0答案为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 ret0; for(int i0;inums.length;i){//枚举子数组右端点i int or0; int ji; //nums[i]与子数组中的任意元素AND均为0 while(j0(ornums[j])0) or|nums[j--];//加到子数组中 retMath.max(ret,i-j); } return ret; } }class Solution { //2401. 最长优雅子数组 //解法二滑动窗口 public int longestNiceSubarray(int[] nums) { int ret0; int or0; int left0; for(int right0;rightnums.length;right){ //出窗口 while((ornums[right])0) or^nums[left]; //进窗口 or|nums[right]; //更新 retMath.max(ret,right-left1); } return ret; } }