侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【双指针, 位运算】最长优雅子数组

GabrielxD
2022-09-04 / 0 评论 / 0 点赞 / 63 阅读 / 659 字 / 正在检测是否收录...

题目

6169. 最长优雅子数组


给你一个由 整数组成的数组 nums

如果 nums 的子数组中位于 不同 位置的每对元素按位 **与(AND)**运算的结果等于 0 ,则称该子数组为 优雅 子数组。

返回 最长 的优雅子数组的长度。

子数组 是数组中的一个 连续 部分。

**注意:**长度为 1 的子数组始终视作优雅子数组。

示例 1:

输入:nums = [1,3,8,48,10]
输出:3
解释:最长的优雅子数组是 [3,8,48] 。子数组满足题目条件:
- 3 AND 8 = 0
- 3 AND 48 = 0
- 8 AND 48 = 0
可以证明不存在更长的优雅子数组,所以返回 3 。

示例 2:

输入:nums = [3,1,5,11,13]
输出:1
解释:最长的优雅子数组长度为 1 ,任何长度为 1 的子数组都满足题目条件。

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题

方法一:双指针 位运算

思路

维护最长优雅子数组长度(maxLen)一个子数组的开始指针(start),和结束指针(i)。

  • 结束指针从数组开头向后枚举:
    • 每到一个元素再向前扫描 nums[i-1] ~ nums[start] 区间:
      • 如果与 nums[i] 做与运算都为 0 的话就说明可以把 nums[i] 加入子数组。
      • 如果到某个元素 nums[j]nums[i] 做与运算不为 0 的话,说明 nums[i] 不能加入原子数组了,但是可以从 nums[j+1] 开始构造新数组(把开始指针置为 j)。
        这时如果 i - j - i > maxLen 的话就可以更新一下 maxLen
        因为 nums[i] 也已经不能加入刚才的子数组了,再向前扫描也没有意义,可以直接 break 掉,进行下一次外层循环。

枚举完后最后一个子数组的长度还没更新,所以返回 n - startmaxLen 中较大的一个。

代码

class Solution {
    public int longestNiceSubarray(int[] nums) {
        int n = nums.length, start = 0, maxLen = 1;
        for (int i = 0; i < n; ++i) {
            int curr = nums[i];
            for (int j = i - 1; j >= start; --j) {
                if ((curr & nums[j]) != 0) {
                    maxLen = Math.max(maxLen, i - start);
                    start = j + 1;
                    break;
                }
            }
        }
        return Math.max(maxLen, n - start);
    }
}
class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int n = nums.size(), start = 0, max_len = 1;
        for (int i = 0; i < n; ++i) {
            int curr = nums[i];
            for (int j = i - 1; j >= start; --j) {
                if (curr & nums[j]) {
                    max_len = max(max_len, i - start);
                    start = j + 1;
                    goto out;
                }
            }
            out:;
        }
        return max(max_len, n - start);
    }
};
0

评论区