Leetcode每日一题 —— 3702. 按位异或非零的最长子序列

SomeBottle 2026-08-15 09:49 1

思路

如果整个数组的元素异或得到 0，那去掉一个元素必然会得到非零，因此符合要求的子序列长度要不是数组长度 n，要不是 n-1。

还有一种特殊情况，全 0 数组，这个时候无论如何都不可能非零。

代码

class Solution {

public:

    int longestSubsequence(vector<int>& nums) {

        // 按位异或非零，即至少有一个位不能出现偶数次

        // 找的是子序列，不是连续子序列

        // 我可以取所有元素的异或，如果为 0，去掉一个元素必然是非零的

        // 如果全为 0，则就是 0

        bool allZero = true;

        int n = nums.size();

        int ex = 0;

        for (int num : nums) {

            if (num != 0) {

                allZero = false;

            }

            ex ^= num;

        }

        if (allZero) {

            return 0;

        }

        // 如果整个数组元素异或为 0 就去掉一个

        return ex == 0 ? n - 1 : n;

    }

};

最新回复 (2)

Lvvvv 08-15 11:02

1楼

一样思路

class Solution {

public:

    int longestSubsequence(vector<int>& nums) {

        auto maxv = *max_element(nums.begin(),nums.end());

        if(maxv == 0) {

            return 0;

        }

        auto res = 0;

        int n = nums.size();

        for(const auto& it : nums) {

            res ^= it;

        }

        return res ? n : n - 1;

    }

};

CPython 08-15 13:40

2楼

开始滑动窗口失败,又想成了前后缀分解,还是不行,结果无力战胜

class Solution:

    def longestSubsequence(self, nums: List[int]) -> int:

        cur = 0

        n = len(nums)

        ok = False

        for x in nums:

            if x:

                ok = True

            cur ^= x

        if not ok:

            return 0

        if cur:

            return n

        return n - 1

* 帖子来源Linux.do

附近帖子