• 这两天面试遇到的一个算法面试题
  • 发布于 2个月前
  • 126 热度
    4 评论
题目是这个:
给定一个输入 n ,输出一个包含 n 个元素数组,数组中每个元素表示其索引的二进制形式中的数字 1 的个数,请给出对应算法并说明复杂度

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

那么动态规划怎么更高效的解这个题呢?还是说我对 32n 的这个解释是有问题的?
用户评论
  • 夕阳追脚尖
  • 我一直搞不懂很多公司面试时搞各种复杂的算法面试题是几个意思?坦白说,很多人写个几年代码可能都不会碰上一个算法问题,大家觉得呢?是不是我肤浅了?
  • 2024/4/25 17:04:00 [ 0 ] [ 0 ] 回复
  • 浅月流歌
  • 这个“没必要啊”属实绷不住了,面试官是想通过这个题考查你的算法能力,你直接暴力了,那他面试评价咋写?面试是一个候选人展示自己的过程,面试官的题目难度其实是决定了你能展示出来的能力的上限。你这句没必要啊。。是我面你我也直接结束了
  • 2024/4/24 17:16:00 [ 0 ] [ 0 ] 回复
  • 沫离伤花
  • 这里不就是奇数和偶数判断一下么,如果元素为 i ,i 如果是奇数则 i 的二进制 1 为 i-1 的二进制 1 个数+1 ,如果是偶数则是 i/2 的二进制数
  • 2024/4/24 17:04:00 [ 0 ] [ 0 ] 回复