您现在的位置是:首页 > 正文

比特位计数-LeetCode338

2024-02-01 00:11:12阅读 2

一、题目描述

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

示例一

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

二、解题思路

1)暴力算法:循环1~n,再利用循环计算每个数中包含的1的个数

public int[] countBits(int n) {
        int[] nums = new int[n + 1];
        for (int i = 1; i < n; i++) {
            nums[i] = count(i);
        }
        return nums;
    }

    public int count(int n) {
        int sum = 0;
        //每次与上一次都会消去一个1
        while (n > 0) {
            n = n & (n - 1);
            sum++;
        }
        return sum;
    }

2)利用动态规划。

public int[] countBits02(int n) {
        int[] bits = new int[n + 1];
        bits[0] = 0;
        int hightBits = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                hightBits = i;
            }
            bits[i] = bits[i - hightBits] + 1;
        }
        return bits;
    }

 

 

网站文章

  • 2021-01-08

    Search by pressing enter Hi,欢迎来到RioTianの博客. | 收藏 闪存 小组 博问 RioTian 关注 园龄:1年2个月 粉丝:68 关注:10 ???? langu...

    2024-02-01 00:11:05
  • 误删的文件咋恢复?

    误删的文件咋恢复?

    永久删除文件是很常见的数据恢复故障。在永久删除文件后如何恢复数据就显的尤为重要了,首先我们需要明白,在永久删除文件后不能往要恢复的误删文件所在的分区,存入任何新的文件,否则数据覆盖了就无力回天了。接下来我们还需要了解下具体如何恢复永久删除文件的文件,具体请看正文了解。

    2024-02-01 00:10:59
  • python小技巧

    想知道某类中的所有成员变量和函数 for temp in dir(request): print temp转载于:https://www.cnblogs.com/fanzi2009/archive/2009/11/10/1599881.html

    2024-02-01 00:10:31
  • spring mvc xss html,SpringMvc防御XSS实践

    项目在漏洞扫描时发现xss漏洞, 本以为是常见漏洞,网上有很多解决方案,应该能很快搞定,但实际上文章看了不少,却并未找到十分“顺手”的解决方案。历经波折终于完成了一套自己想要的方案,现将过程分享出来,...

    2024-02-01 00:10:25
  • cad面积计算机,AutoCAD如何测面积 AutoCAD面积计算方法

    cad面积计算机,AutoCAD如何测面积 AutoCAD面积计算方法

    在AutoCAD运用的实例中,我们常常需要测量所画图形的尺寸面积,如果通过手算的方式总会觉得特别麻烦,还容易出错,为此小编特意为大家准备了最全面的CAD面积计算方法,教你如何巧妙的使用AutoCAD完...

    2024-02-01 00:10:17
  • Jest 学习03 - Mock 函数、声明周期钩子

    Mock 函数Mock Functions(模拟函数)也被称为“spies”(间谍),官方文档:Mock Functions介绍Mock Functions 的使用方法是抹除函数的实际实现,捕获对函数...

    2024-02-01 00:09:47
  • 解析网页--BeautifulSoup-bs4-python爬虫知识点6

    BeautifulSoup 一、BeautifulSoup基本信息 定义 主要学bs4.BeautifulSoup,bs4内的一个非常好用的模块,美丽的汤,bs4:Beautiful Soup4 Be...

    2024-02-01 00:09:40
  • Maven传递依赖的原则

    maven引入的传递性依赖机制,一方面大大简化和方便了依赖声明,大部分情况下我们只需要关心项目的直接依赖是什么,而不永哥你考虑这些直接依赖会引入什么传递性依赖。但有时候,当歘地形依赖造成问题时,我们就需要清除知道该传递性依赖是从哪条依赖路径引入的。如下示例:1.依赖同一个jar包,深度不同:A->B->C->X(1.0)   依赖深度为3A->D->X(2.0)   依赖深度为2

    2024-02-01 00:09:34
  • 1951 查询具有最多共同关注者的所有两两结对组

    1951 查询具有最多共同关注者的所有两两结对组

    题目描述:写出一个查询语句,找到具有最多共同关注者的所有两两结对组。换句话说,如果有两个用户的共同关注者是最大的,我们应该返回所有具有此最大值的两两结对组The result table should...

    2024-02-01 00:09:06
  • axios拦截器之重复请求取消上次请求、路由切换取消接口

    在项目中经常会遇到需要主动取消接口的场景,axios提供CancelToken的功能可以主动停止当前请求,从而避免无效请求,优化网络性能场景:远程搜索接口频繁请求,第二个接口先成功导致显示第一个接口返...

    2024-02-01 00:08:58