V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
csfreshman
V2EX  ›  程序员

leetcode 137 问题讨论

  •  
  •   csfreshman · 2021-06-04 00:14:41 +08:00 · 1990 次点击
    这是一个创建于 1268 天前的主题,其中的信息可能已经有所发展或是发生改变。

    刷 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<int>& 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;
        }
    };
    
    12 条回复    2021-06-05 01:31:28 +08:00
    Yvette
        1
    Yvette  
       2021-06-04 01:03:18 +08:00
    不等价,你的位运算里用的 i 不是同一个 i
    junksheng
        2
    junksheng  
       2021-06-04 01:05:10 +08:00 via Android   ❤️ 1
    你的 i ?
    jinliming2
        3
    jinliming2  
       2021-06-04 01:14:39 +08:00
    方法二里的 i 是哪来的?
    beidounanxizi
        4
    beidounanxizi  
       2021-06-04 01:37:07 +08:00
    这道题 是 真值表的变形 数字电子逻辑设计 据说?
    放弃吧 最佳复杂度是 O(N)
    还有算比较好理解的 但是复杂度就高了 N²
    Xs0ul
        5
    Xs0ul  
       2021-06-04 02:01:02 +08:00   ❤️ 1
    @beidounanxizi #4 从抽象代数的角度来说,真值表版本用的异或是有限域 F_2 上的加法(可以理解为相加以后再对 2 取余数)。这题只要变成 F_3 上的加法就可以了,也就是相加对 3 取余
    Edcwsyh
        6
    Edcwsyh  
       2021-06-04 09:08:45 +08:00
    为什么嵌套循环里还要用 'i'.....
    yehoshua
        7
    yehoshua  
       2021-06-04 09:36:06 +08:00 via Android
    你嵌套两个 i 就有奇怪,这应该是比较低级错误了属于基础方面问题。建议加强下语言基础。
    xuanbg
        8
    xuanbg  
       2021-06-04 14:49:21 +08:00
    两重循环的变量都是 i ???你这个 i 到底是哪个 i ?
    csfreshman
        9
    csfreshman  
    OP
       2021-06-05 00:37:25 +08:00
    @Yvette 确实是,内层循环 i 不应该变的,改成 j 就好了,感谢老铁。
    csfreshman
        10
    csfreshman  
    OP
       2021-06-05 00:38:18 +08:00
    @junksheng 不,是你得 i
    内层 for i 改成 j 就好了,还是右移 i 位。
    csfreshman
        11
    csfreshman  
    OP
       2021-06-05 00:38:33 +08:00
    @yehoshua 感谢指出,已解决
    junksheng
        12
    junksheng  
       2021-06-05 01:31:28 +08:00 via Android
    @csfreshman 就是说你的第二个 i 啊😯
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2831 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 07:22 · PVG 15:22 · LAX 23:22 · JFK 02:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.