【Leetcode】:Counting Bits问题 in Go语言

u013564276 · · 2069 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).

  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
题目大意是,给定一个非负整数num,返回0到num之间所有数的二进制表示中1的个数
下面是我的实现,提交到leetcode上显示运行时间超时
思路是这样的:
数  字:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1个数:0 1 1 2 1 2 2 3 1 2   2  3   2   3   3   4   1   2   2   3 
这里可以看到规律,数字4 5 6 7的1的个数一定是数字 0 1 2 3的1的个数加上1,同样数字8 9 10 11 12 13 14 15的1的个数一定是数字0 1 2 3 4 5
6 7 的1的个数加上1,那么看起来按照这个方法可以实现线性的时间复杂度
func countBits(num int) []int {
    if num == 0 {
        return []int{0}
    }
    if num == 1 {
        return []int{0, 1}
    }
    arr := make([]int, num + 1)
    arr[0] = 0
    arr[1] = 1
    j := 0
    lastTurn := 2;    
    for i := 2; i <= num; i++ {            
        arr[i] = arr [j] + 1
        j++        
        if j == lastTurn {
            j = 0
            lastTurn = i + 1
        }
    }
    return arr
}

采用网上推荐的快速算法,仍然超时,快速算法的原理在于n&(n-1),每执行一次该操作,就能将n的最低位的1去掉,那么需要执行多少次该操作来将n变为全0,就是n中1的个数,这个算法在单次运算中具有优势,但是在本次中看起来不行
func countBits(num int) []int {
    arr := make([]int, num + 1)
    for i := 0; i <= num; i++ {
        sum := 0
        n := i
        for ; n != 0; sum++ {
            n = n & (n - 1)            
        }
        arr[i] = sum
    }
    return arr
}

还有就是另一个算法,但是仍然不能通过,不科学啊,我看别人用其他语言也是这样写的就能通过
func countBits(num int) []int {
    arr := make([]int, num+1)    
    for i := 1; i <= num; i++ {
        half := i >> 1
        if i % 2 == 0 {
            arr[i] = arr[half]
        } else {
            arr[i] = arr[half] + 1
        }
    }
    return arr
}




有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:u013564276

查看原文:【Leetcode】:Counting Bits问题 in Go语言

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2069 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传