[Swift]LeetCode338. 比特位计数 | Counting Bits_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: 2Outpu

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,2,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]

示例 2:

输入: 5输出: [0,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..<loopCount {13                 if index > 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 }