[Swift]LeetCode338.比特位计数|CountingBits

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10262072.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 1:

Input: 2
Output: [0,1,1]

Example 2:

Input: 5
Output: [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 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]

示例 2:

输入: 5
输出: [0,1,1,2,1,2]

进阶:

给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

36ms

 1 class Solution {
 2     func countBits(_ num: Int) -> [Int] {
 3         guard num > 0 else {
 4             return [0]
 5         }
 6         
 7         var result = [0]
 8         var i = 0
 9         var total = 1
10         
11         for j in 1...num {
12             result.append(result[i] + 1)
13             i += 1
14             if i == total {
15                 i = 0
16                 total = j + 1
17             }
18         }
19         return result
20     }
21 }

40ms

 1 class Solution {
 2     func countBits(_ num: Int) -> [Int] {
 3         if num == 0 {
 4             return [0]
 5         }
 6         var results = [Int]()
 7         results.append(0)
 8         for n in 1...num {
 9             if n%2 == 1 {
10                 results.append(results[n-1]+1)
11             } else {
12                 results.append(results[n/2])
13             }
14         }
15         return results
16     }
17 }

44ms

 1 class Solution {
 2     func countBits(_ num: Int) -> [Int] {
 3         guard num > 0 else {
 4             return [0]
 5         }
 6 
 7         var result = Array(repeating: 0, count: num + 1)
 8         result[1] = 1
 9         var loopCount = 2
10         var index = 2
11         while index <= num {
12             for j in 0..<loopCount {
13                 if index > num {
14                     break
15                 }
16 
17                 result[index] = 1 + result[j]
18                 index += 1
19             }
20 
21             loopCount *= 2
22         }
23         return result
24     }
25 }

48ms

 1 class Solution {
 2     func countBits(_ num: Int) -> [Int] {
 3         var a = [0]
 4         var b = [Int]()
 5         while (a.count + b.count) != num+1 {
 6             if a.count == b.count{
 7                 a = a + b
 8                 b = [Int]()
 9             }
10             b.append(a[b.count]+1)
11         }
12         return a + b
13     }
14 }

88ms

 1 class Solution {
 2     func countBits(_ num: Int) -> [Int] {
 3         guard num > 0 else { return [0] }
 4         var dp = [Int](repeating: 0, count: num + 1)
 5         
 6         for i in 1...num {
 7             dp[i] = dp[i & (i - 1)] + 1
 8         }
 9         return dp
10     }
11 }

108ms

 1 class Solution {
 2     func countBits(_ num: Int) -> [Int] {
 3         var result = [Int]()
 4         if num < 0 {
 5             return result
 6         }
 7         result.append(0)
 8         if num == 0 {
 9             return result
10         }
11         for i in 1 ... num {
12             print(i & 1)
13             result.append(result[i >> 1] + (i & 1))
14         }
15         return result
16     }
17 }

112ms

 1 class Solution {
 2     func countBits(_ num: Int) -> [Int] {       
 3         if num == 0 { return [0] }
 4         var result = [0]
 5         var count = 1
 6         while true {
 7             for j in 0 ..< count {
 8                 result.append(result[j] + 1)    
 9                 if result.count == num + 1 {
10                     return result
11                 }
12             }
13             count = result.count
14         }
15         return result
16         
17     }
18 }

116ms

 1 class Solution {
 2     func countBits(_ num: Int) -> [Int] {
 3         if num == 0 {
 4             return [0]
 5         }
 6         var res = [Int].init()
 7         res.append(0)
 8         for n in 1...num {
 9             let count = res[n & (n - 1)] + 1
10             res.append(count)
11         }
12         return res
13     }
14 }

164ms

 1 class Solution {
 2     func countBits(_ num: Int) -> [Int] {
 3         var b = [Int](repeating: 0, count: num + 1)
 4         if num == 0 { return [0] }
 5         if num == 1 { return [0,1] }
 6         for i in 1...num {
 7             b[i] = b[i >> 1] + i % 2
 8         }
 9         return b
10     }
11 }

176ms

 1 class Solution {
 2     func countBits(_ num: Int) -> [Int]
 3     {
 4         var res = [Int]()
 5         for i in 0...num
 6         {
 7             var n = i
 8             var count = 0
 9             while n > 0
10             {
11                 if n&1 == 1
12                 {
13                     count += 1
14                 }
15                 n = n >> 1
16             }
17             res.append(count)
18         }
19         return res
20     }
21 }

156ms

 1 class Solution {
 2     func countBits(_ num: Int) -> [Int] {
 3         guard num > 0 else { return [0] }
 4         var dp = [Int](repeating: 0, count: num + 1)
 5         
 6         for i in 1...num {
 7             dp[i] = dp[i / 2]
 8             if i % 2 == 1 {
 9                 dp[i] += 1
10             }
11         }
12         return dp
13     }
14 }