( 位运算 ) 338. 比特位计数 ——【Leetcode每日一题】

这篇具有很好参考价值的文章主要介绍了( 位运算 ) 338. 比特位计数 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

❓338. 比特位计数

难度:简单

给你一个整数 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 < = 1 0 5 0 <= n <= 10^5 0<=n<=105

进阶:

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

💡思路:位运算

基础知识必知:一篇文章搞懂位运算 !

对于数字 6(110),它可以看成是 4(100) 再加一个 2(10),因此 dp[i] = dp[i&(i-1)] + 1;

即,使用位运算 去除最低的那一位 1,此时的 dp[i&(i-1)]已经计算过,然后再加上最低为的这个 1

🍁代码:(Java、C++)

Java

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

C++

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1);
        for(int i = 1; i <= n; i++){
            ans[i] = ans[i & (i - 1)] + 1;
        }
        return ans;
    }
};
🚀 运行结果:

( 位运算 ) 338. 比特位计数 ——【Leetcode每日一题】

🕔 复杂度分析:
  • 时间复杂度 O ( n ) O(n) O(n),对于每个整数,只需要 O ( 1 ) O(1) O(1) 的时间计算「一比特数」。
  • 空间复杂度 O ( n ) O(n) O(n),除了返回的数组以外,空间复杂度为常数。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-447040.html

注: 如有不足,欢迎指正!

到了这里,关于( 位运算 ) 338. 比特位计数 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每日一题:leetcode 57 插入区间

    给你一个  无重叠的  , 按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 0 = intervals.length = 104 intervals[i].length == 2 0 = int

    2024年02月11日
    浏览(46)
  • 【每日一题】Leetcode - 283. 移动零

    Leetcode - 283. 移动零 从右向左遍历,遇到0,就将后面所有元素前移,同时更新长度,使其减1,因为移动n次,倒数n位就被0占据,后续操作可忽略 前面的操作,从右向左,每次遇到0移动都要跑半个数组,慢在整体前移; 换个思路,从左向右,记录首个0的位置,将后面的第一

    2024年02月11日
    浏览(45)
  • 【LeetCode每日一题】——566.重塑矩阵

    矩阵 简单 566.重塑矩阵 在 MATLAB 中,有一个非常有用的函数 reshape ,它可以将一个 m x n 矩阵重塑为另一个大小不同(r x c)的新矩阵,但保留其原始数据。 给你一个由二维数组 mat 表示的 m x n 矩阵,以及两个正整数 r 和 c ,分别表示想要的重构的矩阵的行数和列数。 重构后

    2024年02月14日
    浏览(47)
  • 【LeetCode每日一题】——575.分糖果

    哈希表 简单 575.分糖果 Alice 有 n 枚糖,其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长,所以前去拜访了一位医生。 医生建议 Alice 要少摄入糖分,只吃掉她所有糖的 n / 2 即可(n 是一个偶数)。Alice 非常喜欢这些糖,她想要在遵循医生建议的情况下,尽可

    2024年02月13日
    浏览(76)
  • 【LeetCode每日一题】——85.最大矩形

    矩阵 困难 85.最大矩形 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例 1: 输入:matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“

    2024年02月13日
    浏览(41)
  • 【LeetCode】每日一题:移除元素

    目录  题目: 思想1:暴力解法 思想2:创建一个temp数组  思想3:双指针 👻内容专栏:《LeetCode刷题专栏》 🐨本文概括: 27.移除元素 🐼本文作者:花 碟 🐸发布时间:2023.4.15 https://leetcode.cn/problems/remove-element/   点击跳转到LeetCode平台OJ页面(27.移除元素)  👉 示例1: 解

    2023年04月19日
    浏览(73)
  • LeetCode每日一题之 复写0

    目录 题目介绍: 算法原理: 特殊位置处理: 代码实现: 题目链接:. - 力扣(LeetCode) 这种对数组元素进行修改,移动的题目我们仍然可以使用双指针法,不过我们按照常规思路从左到右处理数组,不难发现如下这种问题: 当cur指向1时,让dest下一个元素复写cur指向的元素

    2024年04月23日
    浏览(58)
  • leetcode每日一题:62. 不同路径

    系列:动态规划 语言:java 难度:中等 题目来源:Leetcode62. 不同路径 开启动态规划章节了!!欢迎您在留言和我一起完成每日打卡,以后每天8点半前发布每日一题。 原题链接:Leetcode62. 不同路径 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )

    2023年04月22日
    浏览(45)
  • Leetcode每日一题——“移除元素”

    各位CSDN的uu们你们好呀,小雅兰又来啦,今天,小雅兰的内容是移除元素,下面,让我们进入Leetcode的世界吧   说明: 为什么返回数值是整数,但输出的答案是数组呢? 请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。 你可以

    2023年04月23日
    浏览(54)
  • 每日一题(LeetCode)----二分查找(一)

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 104 -104 = nums[i] = 104 nums 为 无重复元素 的 升序 排列数

    2024年02月08日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包