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

面试见闻,关于一个简单题目的算法和复杂度的讨论

  •  
  •   nulIptr · 80 天前 · 1957 次点击
    这是一个创建于 80 天前的主题,其中的信息可能已经有所发展或是发生改变。
    题目是这个:
    给定一个输入 n ,输出一个包含 n 个元素数组,数组中每个元素表示其索引的二进制形式中的数字 1 的个数,请给出对应算法并说明复杂度

    依稀好像看过这个题,不确定到底有没有 o1 的数学解,我就说要是我的话肯定暴力数 0
    面试官说给你提个醒能不能动态规划解这个题
    我说没必要啊暴力数数也不慢,c 语言里面直接读内存,js 里可以位运算展开一下,最差情况也就是 32n 或者 64n 的复杂度。即使是 o1 的数学解也就是把 32n 降到 n ,讨论复杂度的时候本来就省略固定系数的

    然后面试官就结束了提问环境,说我有啥问题要问的没然后结束了面试。

    那么动态规划怎么更高效的解这个题呢?还是说我对 32n 的这个解释是有问题的?
    22 条回复    2024-04-24 12:23:59 +08:00
    vacuitym
        1
    vacuitym  
       80 天前
    面试官要动态规划你就回答动态规划,除非你不会
    nulIptr
        2
    nulIptr  
    OP
       80 天前 via iPhone
    @vacuitym 就这个题来说我还真没想出来怎么动态规划…
    duality
        3
    duality  
       80 天前
    从 0 开始处理,设 A[0] = 0
    For (i = 1 ... n)
    设 i 的最高非零位为 d 位
    A[i] = A[i - (1<<(d-1))] + 1
    kera0a
        4
    kera0a  
       80 天前 via iPhone
    有没有可能都不是算法的问题,面试官只是觉得你不好沟通了。
    会觉得等到要给你需求时你也来一句"没必要啊"怎么办
    现在牛马太多了,一点点不合意就直接下一位了
    finalwave
        5
    finalwave  
       80 天前   ❤️ 1
    DP[ i ] = DP[ floor(i / 2) ] + (i & 1)
    sagaxu
        6
    sagaxu  
       80 天前
    右移一位得到一个更小的数,这个数的 1 的个数已经算好了,加上当前最右位就是当前数字的 1 的个数

    计算量是稍微小了一点点,但是空间从 O(1)变 O(n)了,如果是 10 亿个数呢,100 亿个呢
    Goooooos
        7
    Goooooos  
       80 天前
    @sagaxu 这道题目是返回数组,所以这个结果的空间可以忽略
    Sawyerhou
        8
    Sawyerhou  
       80 天前 via Android
    3 楼的递归是个好思路,说态度问题的也有道理,毕竟直接结束了面试

    毕竟是算法题,暴力解不太合适吧
    MoYi123
        9
    MoYi123  
       80 天前
    2 种可能性,
    1. 你题目理解错了
    2. 面试官 sb
    misdake
        10
    misdake  
       80 天前
    这个题挺有意思,再往底层走还可以问多线程和 cpu 缓存相关的内容,如何优化到极致
    misdake
        11
    misdake  
       80 天前
    如果把统计 1 的数量改成统计所有质因数之和,会更有意思一点
    codegenerator
        12
    codegenerator  
       80 天前
    这题你理解错了,就是个位运算的题目
    但是如果你是面前端,那就是面试官的问题
    main1234
        13
    main1234  
       80 天前
    这里不就是奇数和偶数判断一下么,如果元素为 i ,i 如果是奇数则 i 的二进制 1 为 i-1 的二进制 1 个数+1 ,如果是偶数则是 i/2 的二进制数
    main1234
        15
    main1234  
       80 天前
    对于奇数,二进制表示中奇数一定比前面的偶数多一个 1 ,多的就是最低位的 1
    如 0 = 0 ,1 = 1 ,2=10 ,3=11
    对于偶数,二进制表示中偶数一定和除以 2 之后的那个数一样多,因为最低位是 0 ,除以 2 就是右移一位
    2 = 10 ,4=100 ,8=1000
    zzblack
        16
    zzblack  
       80 天前
    这个“没必要啊”属实绷不住了,面试官是想通过这个题考查你的算法能力,你直接暴力了,那他面试评价咋写?面试是一个候选人展示自己的过程,面试官的题目难度其实是决定了你能展示出来的能力的上限。你这句没必要啊。。是我面你我也直接结束了
    zhuxuanyu0720
        17
    zhuxuanyu0720  
       80 天前
    动态规划解法:


    def countBits(n):
    result = [0] * (n+1)
    offset = 1
    for i in range(1, n+1):
    if offset * 2 == i:
    offset *= 2
    result[i] = result[i - offset] + 1
    return result[:n]

    offset 代表的是该区间内最小数字(即起始数字)的二进制位数。offset 变量代表当前位置所属的那个长度为 offset 的区间的起始点。举例来说,当 offset=1 时,表示区间[0,1];当 offset=2 时,表示区间[2,3];当 offset=4 时,表示区间[4,7].

    有一个数学规律
    对于任意一个数字 x,如果 x 和 x+1 的二进制位数相同,那么 x 和 x+1 对应的 1 的个数,最多只相差 1 ,这个特性就被用来推导 result 数组中相邻两个数字对应的 1 的个数

    所以通过区间分治的方式,算法可以高效地确定每一个区间的起点,并利用相邻区间的结果推导出当前区间每个数字对应的 1 的个数,从而达到 O(n)的时间复杂度。
    xiaozhaoz
        18
    xiaozhaoz  
       80 天前
    根据前一个数 的三种情况:
    - 最后一位 0 ,1 的个数 + 1
    - 前一个数全 1 ,1 的个数回到 1 ,实现方法:记住前一个数二进制长度,“~前一个数 & ( 0x1<<位数)- 1” == 0
    - 其他情况,1 的个数不变
    xiaozhaoz
        19
    xiaozhaoz  
       80 天前
    @xiaozhaoz 错了,最后一种情况 1 的个数会变。
    看到过一个算法,可以算一个 32bits 的 1 个数。
    int count(unsigned x) {
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
    }
    Orlion
        20
    Orlion  
       79 天前
    leetcode 338 原题,动态规划的转移方程:bits[i] = bits[i >> 1] + (i & 1)。
    GrayXu
        21
    GrayXu  
       79 天前
    算法题只是智力题
    majula
        22
    majula  
       79 天前
    去看了下 leetcode 338 ,果然是不让用 popcnt intrinsic 的,不然就是一个非常 trivial 的 O(n)

    其实就算不让用 intrinsic ,popcnt 也有 branchless 且 lut-less 的 trivial 实现。参考 Bit Twiddling Hacks:

    v = v - ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

    不过既然题干都那么说了,还是别投机取巧了,老老实实动态规划吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1113 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 18:26 · PVG 02:26 · LAX 11:26 · JFK 14:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.