首页 > 其他分享 >力扣---338. 比特位计数

力扣---338. 比特位计数

时间:2023-06-24 10:11:15浏览次数:33  
标签:--- 338 10 int res 左移 力扣 -- 数量

给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。

 

示例 1:

输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
示例 2:

输入:n = 5
输出:[0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
 

提示:

0 <= n <= 105
 

进阶:

很容易就能实现时间复杂度为 O(n log n) 的解决方案,你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗?
你能不使用任何内置函数解决此问题吗?(如,C++ 中的 __builtin_popcount )

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/counting-bits
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


 

虽然简单题,但它是动规加位运算。。。

第一种方法是直接数出每一个位置的数有多少个 1 。

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i ++) {
            res[i] = getNum(i);
        }
        return res;
    }
    private int getNum (int n) {
        int count = 0;
        while (n > 0) {
            n &= (n - 1);
            count ++;
        }
        return count;
    }
}

 可以想到,10 的二进制表示是 1010,而 2 的二进制表示是:10;

去除 10 二进制表示的最后一位 1 后,为:8 (1000),而 10 中,1 的数量就是 8 的数量加已经去掉的 1。

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 1; i <= n; i ++) {
            res[i] = res[i & (i - 1)] + 1;
        }
        return res;
    }
}

还可以想到:

对于 10 (1010) 来说,左移一位后的值为:5(101),两者 1 的数量相同。

对于 9 (1001) 来说,左移一位后的值为 4(100),9 中 1 的数量等于 4 的数量加一。

即:某个数字中 1 的数量,等于其左移一位后中 1 的数量加上左移丢失的那一位。

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 1; i <= n; i ++) {
            res[i] = res[i >> 1] + (1 & i);
        }
        return res;
    }
}

 

标签:---,338,10,int,res,左移,力扣,--,数量
From: https://www.cnblogs.com/allWu/p/17500746.html

相关文章

  • HTTP-响应数据格式
        ......
  • leetcode 16 最接近的三数之和 3sum-closest【ct】
    ===思路:在遍历中去计算,每一轮循环中都去计算,如果distance更小就去更新distance。如果sum>target,end--,如果sum<target,start++,如果等于,就可以直接返回target  ......
  • leetcode 113 路径总和2 path-sum-ii【ct】
    ===思路:很简单,记得递归的时候传入path.slice ......
  • Xcode 15 beta 2 (15A5161b) 发布下载 - Apple 平台 IDE (visonOS 1 beta 已发布)
    Xcode15beta2(15A5161b)发布下载-Apple平台IDE(visonOS1beta已发布)IDEforiOS/iPadOS/macOS/watchOS/tvOS/visonOS此版本已加入visonOS支持。请访问原文链接:https://sysin.org/blog/apple-xcode-15/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org......
  • 堡垒机模块-(jumperserver部署完成)
    堡垒机模块原创 希里安 希里安 2023-05-3018:00 发表于四川收录于合集#堡垒机1个#webshell1个#开源4个关注“希里安”,get更多有用干货 前两天在项目里加了个webshell,还没开发完成,有读者朋友说费那劲干嘛,直接引入类似jumpserver开源堡垒机就完事了。说的不......
  • delphi写的小工具---快速隐藏任务
    这个工具应该不用过多介绍吧~软件界面:软件下载:点击下载>>> ......
  • TensorFlow10.2 卷积神经网络-CIFAR100 实战
    ▪Loaddatasets▪BuildNetwork▪Train▪Test这里先是进行卷积然后再进行全连接Loaddatasetsdefpreprocess(x,y):#[0~1]x=tf.cast(x,dtype=tf.float32)/255.y=tf.cast(y,dtype=tf.int32)returnx,y(x,y),(x_test,y_test)=dat......
  • WPF 入门笔记 - 06 - 命令
    我们把世界看错,反说它欺骗了我们。--飞鸟集前言相较而言,命令对我来说是一个新概念,因为在Winform中压根没有所谓的命令这个概念......
  • tmux后台终端程序启动工具-替代nohup后台程序启动工具
    还在用nohup后台执行任务吗?快来用tmux原创 艺说IT 艺说IT 2023-05-2810:09 发表于广东收录于合集#linux3个#linux命令1个文章目录一、前言1.1tmux介绍1.2之前后台运行查看日志的方式二、各系统安装tmux方法2.1CentOS2.2UbuntuAnd......
  • 牛客题解-mixup2混乱的奶牛(状压dp)
    题解-mixup2混乱的奶牛[原题连接](1026-mixup2混乱的奶牛_2021秋季算法入门班第八章习题:动态规划2(nowcoder.com))题目描述混乱的奶牛[DonPiele,2007]FarmerJohn的N(4<=N<=16)头奶牛中的每一头都有一个唯一的编号S_i(1<=S_i<=25,000).奶牛为她们的编号感到骄傲......