当前播放: 41 | 面试题:2的幂次方问题&比特位计数问题
00:00 / 00:00
高清
  • 高清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看
课程目录
第一章:课程综述 (4讲)
01 | 合格程序员的第一步:算法与数据结构
免费
02 | 如何事半功倍地学习算法与数据结构
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算法题目练习
免费
第二章:理论讲解+面试题实战 (53讲)
05 | 理论讲解:数组&链表
免费
06 | 面试题:反转一个单链表&判断链表是否有环
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是否有效
09 | 面试题:用队列实现栈&用栈实现队列
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第K大元素
12 | 面试题:返回滑动窗口中的最大值
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二叉搜索树
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索树的最近公共祖先
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时机
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最小深度
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方根的函数
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词搜索问题
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&比特位计数问题
42 | 面试题:N皇后问题的另一种解法
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径和
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友圈(上)
54 | 面试题:岛屿的个数&朋友圈(下)
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LRU Cache缓存机制
57 | 理论讲解:布隆过滤器
第三章:课程总结 (5讲)
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件套
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契数列
62 | 结课测试&最后的一些经验分享
41 | 面试题:2的幂次方问题&比特位计数问题

41 | 面试题:2的幂次方问题&比特位计数问题

覃超
Sophon Tech创始人,前Facebook工程师,卡内基梅隆大学计算机硕士
全集23002
新人首单 ¥29.9 原价 ¥129
12
登录 后留言

精选留言(16)

  • 二驴
    bits[i] += bits[i&(i-1)] + 1;
    应该修改为:bits[i] = bits[i&(i-1)] + 1;
    +=没有意义
    2018-11-21
    6
  • Sean
    @Spiderspiders 你提到的这个问题老师在代码讲解的时候特别说明过了
    2018-11-20
    2
  • Geek_54323c
    感觉231应该判断n>0 输入有可能为负数
    2020-02-06
    1
  • Aliliin
    338 题 PHP DP 方法解法

     /**
         * DP 方程
         * F(0) = 0 , N = 0
         * F(N) = F(N/2) + N%2 , N > 0
         */
        function countBits($num)
        {
            $res[] = 0;
            for ($i = 1; $i <= $num; $i++) {
                $res[$i] = $res[(int)$i / 2] + $i % 2;
            }
            return $res;
        }
    2019-11-22
    1
  • Aliliin
    338题 PHP 的解法:

    function countBits($num) {
           $res = [$num+1=>0];
           for($i=1;$i<=$num;$i++) {
               $res[$i] +=$res[$i&($i-1)] +1;
           }
           return $res;
        }
    声明一下,本地 环境每次会有 Notice 的错误提示,也有出现结果不同的时候。但是可以通过 leetcode 的题。
    2019-11-22
    1
  • 张磊
    i & i - 1,一定是小于i的,这个方法巧妙!
    2020-03-28
  • mickey
    public boolean isPowerOfTwo(int n) {
      return n <= 0 || (n & (n - 1)) != 0 ? false : true;
    }
    2020-03-12
  • lzh
    338题,C++,动态规划思想,打败99%:
    class Solution {
    public:
    vector<int> countBits(int num) {
    vector<int> result = { 0 };
    int highLevelNum;

    for (int i = 1; i <= num; i++)
    {
    if (result[i - 1] & 1 == 0)
    {
    result.push_back(result[i - 1] + 1);
    }
    else
    {
    //从右到左,首个0往右的低位1过滤掉,留下highLevelNum
    highLevelNum = i - 1 & i;
    //若highLevelNum是0,即i-1==(2^n)-1,则由于进位result[i]=1
    //若highLevelNum非0,则结果是highLevelNum中1的个数+1,hightLevelNum小于i,其result已知
    result.push_back(highLevelNum == 0 ? 1 : result[highLevelNum] + 1);
    }
    }

    return result;
    }
    };
    2020-01-20
  • 言十年
    338.php版 动态规划。
    递推公式,自己找个例子[0,1,1,2,1,2,2,3, 1,2, 2, 3, 2, 3, 3, 4],然后找找规律
        function countBits($num) {
            // 使用动态规划
            $dp[0] = 0;
            if(empty($num)) {
                return $dp;
            }
            $dp[1] = 1;
            for($i = 2; $i <= $num; $i++) {
                // $a = $a / 2 + $a % 2;
                $dp[$i] = $dp[$i / 2] + $dp[$i % 2];
            }
            return $dp;
        }
    2019-12-30
  • Aliliin
    231 题两种 PHP 解法:

    A:
    // 循环的笨办法
    function isPowerOfTwo($n)
    {
        if ($n == 1) return true;
        if ($n == 0) return false;
        if ($n / 2 === 0) {
            return true;
        } else {
            if ($n / 2 > 0) {
                if (isPowerOfTwo($n / 2) == true) {
                    return true;
                }
            }
            return false;
        }
    }
    B:
    // 位运算的方法。
    function isPowerOfTwo1($n)
    {
        return $n > 0 && ($n & ($n - 1)) == 0;
    }
    2019-11-22
  • czh
    二进制 x&x-1 ,反人类思维
    2019-09-27
  • 唯夜
    封面老师笑得真开心,老感觉上课的时候有人在逗你笑啊
    2019-06-01
  • 海边的卡夫卡
    还有一种比较容易顺着思考的,就是干掉最高位的1,
    好比两个power_2之间的 是符合递推的,如2和4之间只有一个3,4和8之间有5,6,7
    3=2+1
    5=4+1
    6=4+2
    7=4+3

    因为1,2,3已经在前面计算过了,所以bits_cnt[7]=bits_cnt[4]+bits_cnt[3] 这样。
    2019-04-07
  • yao
    Java的返回是boolean
    2018-12-18
  • Spiderspiders
    白板上for 循环 i从0开始,代码里面从1开始,实际上i是从1开始的,望更正白板上的错误

    作者回复: 好的。

    2018-11-16
  • achenbj
    感觉有点死记硬背了,原理说出来能听懂原来大学就能听懂的
    2018-11-15
收起评论
看过的人还看
数据结构与算法之美

王争  前Google工程师

80讲 | 85872 人已学习

新人首单 ¥29.9 原价 ¥129
趣谈网络协议

刘超  网易研究院云计算技术部首席架构师

51讲 | 44817 人已学习

新人首单 ¥19.9 原价 ¥99
左耳听风

陈皓  网名“左耳朵耗子”,资深技术专家,骨灰级程序员

109讲 | 45576 人已学习

新人首单 ¥69.9 原价 ¥299
Java核心技术面试精讲

杨晓峰  前Oracle首席工程师

44讲 | 46475 人已学习

新人首单 ¥19.9 原价 ¥99