leetcode 338. Counting Bits

柔光的暖阳◎ 2022-07-28 10:51 94阅读 0赞

# 分析 #

打算用动态规划，所以先找x和x-1的规律：  
0  
1  
10  
11  
100  
101  
110  
111  
1000  
1001  
1010  
1010010100101  
1010010100110  
111  
1000

f(x) 表示x二进制表示中1的个数， m表示从右往左第一个0的位置（从0开始计数）。

找数字x-1 从右往左第一个0的位置m；

f(x) = f（x-1） - m + 1；

我们认为7这样的数字的二进制表示中没有0，如果x-1的二进制表示中没有找到0，则：

f（x） = 1；

# 代码 #

public class Solution { 
        public int findZeroFromRight(int n){
            int ans = 0;
            while(n % 2 == 1){
                n = n >> 1;
                ans++;
            }
            if(n == 0)
                return -1;//表示n的二进制表示中没有0
            else
                return ans;
        }
    
        public int[] countBits(int num) {
            int ans[] = new int[num+1];
            ans[0] = 0;
            for(int i = 1; i <= num; i++){
                int m = findZeroFromRight(i-1);
                if(m == -1){
                    ans[i] = 1;
                }
                else{
                    ans[i] = ans[i-1] - m + 1;
                }
            }
            return ans;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，94人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 338. Counting Bits

分析打算用动态规划，所以先找x和x-1的规律： 0 1 10 11 100 101 110 111 1000 1001 10

柔光的暖阳◎/ 2022年07月28日 10:51/ 0 赞/ 95 阅读

相关 LeetCode-338. Counting Bits

Problem: Given a non negative integer number num. For every numbers i in the range

梦里梦外;/ 2022年07月26日 00:07/ 0 赞/ 114 阅读

相关 338. Counting Bits（计算整数二进制表示中1的位数）

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num ca

偏执的太偏执、/ 2022年07月15日 07:00/ 0 赞/ 148 阅读

相关 [leetcode]--338. Counting Bits

Question 338. Counting Bits > Question: Given a non negative integer number num. For ev

一时失言乱红尘/ 2022年07月11日 23:00/ 0 赞/ 114 阅读

相关 [leetcode]: 338. Counting Bits

1.题目 Given a non negative integer number num. For every numbers i in the range 0 ≤ i

╰半橙微兮°/ 2022年06月13日 00:13/ 0 赞/ 141 阅读

相关 leetcode 338. Counting Bits 位计算 + 统计二进制1的数量

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num ca

迈不过友情╰/ 2022年06月07日 01:13/ 0 赞/ 146 阅读

相关 338. Counting Bits

/\ 338. Counting Bits Given a non negative integer number num. For every numbers i i

冷不防/ 2022年05月23日 06:25/ 0 赞/ 118 阅读

相关 338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num ca

迷南。/ 2022年03月25日 00:46/ 0 赞/ 152 阅读

相关 338. Counting Bits

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] ![c5a2642370c2ca3440abed1546dc0893e51.jpg][

￡神魔★判官ぃ/ 2022年01月15日 06:51/ 0 赞/ 150 阅读

相关 LeetCode : 338. Counting Bits 统计二进制

试题 Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ n

落日映苍穹つ/ 2021年06月24日 16:11/ 0 赞/ 241 阅读