★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★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: 2Output: [0,1,1]
Example 2:
Input: 5Output: [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 = 110 11 for j in 1...num {12 result.append(result[i] + 1)13 i += 114 if i == total {15 i = 016 total = j + 117 }18 }19 return result20 }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 results16 }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 = 210 var index = 211 while index <= num {12 for j in 0.. num {14 break15 }16 17 result[index] = 1 + result[j]18 index += 119 }20 21 loopCount *= 222 }23 return result24 }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 + b13 }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 dp10 }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 result10 }11 for i in 1 ... num {12 print(i & 1)13 result.append(result[i >> 1] + (i & 1))14 }15 return result16 }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 result11 }12 }13 count = result.count14 }15 return result16 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)] + 110 res.append(count)11 }12 return res13 }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 b10 }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 > 010 {11 if n&1 == 112 {13 count += 114 }15 n = n >> 116 }17 res.append(count)18 }19 return res20 }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] += 110 }11 }12 return dp13 }14 }