• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode125.验证回文串|ValidPalindrome发布时间:2022-07-13
下一篇:
swiftNSUserDefaults的基本使用发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap