标签：cnt return 338 比特 -- res 计数 int diff

问题描述

https://leetcode.cn/problems/counting-bits/description/

解题思路

这个题目，看上去是一个动态规划问题。

用dp[i]代表i中1的个数。但我没想明白怎么写状态转移方程。

多写了几组数据，发现有如下规律：

2-->0 3-->1 4-->0 5-->1 6-->2 7-->3 8-->0 即：我们认为，10和11 分别为在0和1之前都添加了1. 100、101、110、111分别为在00、01、10、11前面都添加了1. 所以，我们用一个diff记录该去找哪个dp[i]，用一个cnt记录是否应该更新diff即可。在这个题目中，diff是不断变化的。

代码

class Solution:
    def countBits(self, n: int) -> List[int]:
        if n == 0:
            return [0]
        if n == 1:
            return [0, 1]
        res = [0, 1]
        diff, cnt = 2, 0
        for i in range(2, n+1):
            tmp = res[i-diff]+1
            res.append(tmp)
            cnt += 1
            if cnt == diff:
                diff *= 2
                cnt = 0
        return res

 

标签：cnt,return,338,比特,--,res,计数,int,diff
From： https://www.cnblogs.com/bjfu-vth/p/17057483.html