[位运算]leetcode2401：最长优雅子数组(medium)

题目：

---

题解：

思路：暴力枚举 + 位运算

• 由于优雅子数组中的各元素从高位到最低位最多有 31 个 ‘1’，因此优雅子数组的长度最多为 31，这样我们就可以使用暴力枚举所有的优雅子数组了。从遍历到的元素 a[i]，向前进行扩展优雅子数组的长度，保留子数组长度的最大值即为最终答案了。
• 对于优雅子数组中各元素两两想与的结果为 0 的话，我们使用 ‘|’ 运算来简化判断。由于优雅子数组各元素想与的结果为 0，因此我们可以使用 ‘|’ 运算来保留这些元素的二进制位，然后与当前元素想与的结果是否为 0 来进行前移。具体实现可参考代码。

---

代码如下：

class Solution {
public:
    int longestNiceSubarray(vector<int>& a) {
        int res=0,n=a.size();
        for(int i=0;i<n;++i)
        {
            // 由于优雅子数组中每个元素在 01 二进制上每一位上至多存在一位，且这些位不重叠
            // 因此我们可以将优雅子数组中的所有元素使用 '|' 运算存起来，方便判断当前元素与后面优雅子数组中的所有的元素想与的结果是否为 0
            int x=0,j=i;
            while(j>=0 and (x&a[j])==0){
                x|=a[j--];
            }
            res=max(res,i-j);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17