LeetCode 题解：338. Counting Bits

本文主要是介绍LeetCode 题解：338. Counting Bits，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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].

解题思路

这题使用动态规划算法求解。

通过仔细观察可以发现：

1. 若数 num 为偶数，那么 num 的二进制形式所包含的数字1的个数和数 num / 2（数 num 的一半）的二进制形式所包含的数字1的个数相同
2. 若数 num 为奇数，那么 num 的二进制形式所包含的数字1的个数比在它前面的偶数（即数 num - 1）的二进制形式所包含的数字1的个数要多1

因此，只需要初始化 num = 0 和 num = 1这两种情况的结果，后面的数字都可以直接求解，时间复杂度为线性时间O(n)。

C++代码

class Solution {
public:vector<int> countBits(int num) {vector<int> res;res.push_back(0);if(num == 0)return res;res.push_back(1);if(num == 1)return res;for(int i = 2; i <= num; i++) {if(i % 2 == 0){res.push_back(res[i/2]);}else{res.push_back(res[i-1]+1);}}return res;}
};

这篇关于LeetCode 题解：338. Counting Bits的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---