技术解析

leetcode 137 问题讨论
0
2021-06-04 00:08:14
idczone

刷 leetcode 时,遇到如下问题,使用 C++ 我之前认为如下两种写法应该是等价的,但实际上不是: 方法 1:

for(int i = 0;i < nums.size();i++)
{
	sum += ((nums[i] >> i)&1);
}

方法二:

for(auto num:nums)
{
   sum += ((num >> i)&1);
}

方法二符合预期,也能正确 AC,我开始写的是方法 1 (三刷之前收藏的 200 题),始终不能 AC,看了答案写成方法二就 ok 了,这到底是因为啥?运算符优先级?我加括号括起来还是不对. 完整代码:

class Solution {
public:
    int singleNumber(vector& nums) {
        int size = nums.size();
        int抗投诉服务器 ans = 0;
        for(int i = 0;i < 32;i++)
        {
            int sum = 0;
            for(auto num:nums)
            {
                sum += ((num >> i)&1);
            }

            if(sum % 3)
                ans |= (1 << i);
        }
        return ans;
    }
};

不等价,你的位运算里用的 i 不是同一个 i

你的 i ?

方法二里的 i 是哪来的?

这道题 是 真值表的变形 数字电子逻辑设计 据说?
放弃吧 最佳复杂度是 O(N)
还有算比较好理解的 但是复杂度就高了 N²

从抽象代数的角度来说,真值表版本用的异或是有限域 F_2 上的加法(可以理解为相加以后再对 2 取余数)。这题只要变成 F_3 上的加法就可以了,也就是相加对 3 取余

为什么嵌套循环里还要用 'i'.....

你嵌套两个 i 就有奇怪,这应该是比较低级错误了属于基础方面问题。建议加强下语言基础。

数据地带为您的网站提供全球顶级IDC资源
在线咨询
专属客服