算法打卡Day24_leetcode _338. 比特位数

简介: 算法打卡Day24_leetcode _338. 比特位数

Leetcode原题

338.比特位数

20200401134307494.png

思路

方法一 动态规划

a[i]表示i的二进制中1的个数,那么bits[i-1]就是bits[i]拿掉一个1之后的值,i & (i - 1)就是去掉最低位的一个1。,因此 i & (i - 1)是比 i 小的,而且i & (i - 1)的1的个数已经在前面算过了,所以i的1的个数就是 i & (i - 1)的1的个数加上1

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

方法二 奇偶法

对于所有的数字,只有两类:

奇数:二进制表示中,奇数一定比前面那个偶数多一个 1,因为多的就是最低位的 1。

  举例: 
         0 = 0       1 = 1
         2 = 10      3 = 11

偶数:二进制表示中,偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0,除以 2 就是右移一位,也就是把那个 0 抹掉而已,所以 1 的个数是不变的。

 举例:
         2 = 10       4 = 100       8 = 1000
         3 = 11       6 = 110       12 = 1100

另外,0 的 1 个数为 0,于是就可以根据奇偶性开始遍历计算了。

 //方法2: 奇偶法
    public int[]  countBits2(int n) {
        int a[]=new int[n+1];
        a[0] =0;
        for (int i = 1; i <=n ; i++) {
            if ((i&1) ==1){ //使用位运算判断奇偶数,等于1是奇数
                a[i] = a[i-1]+1;
                //二进制表示中,奇数一定比前面那个偶数多一个 1,因为多的就是最低位的 1
            }else {
                a[i] =a[i>>1];
                //二进制表示中,偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0,除以 2 就是右移一位,也就是把那个 0 抹掉而已,所以 1 的个数是不变的。
            }
        }
        return  a;
    }

有兴趣的老爷,还可以关注我的公众号【一起收破烂】,回复【006】获取 最新java面试资料以及简历模型120套哦~

相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
39 0
|
17天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
1月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
27 2
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
52 6
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
50 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
61 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
80 0
|
3月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
43 0
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
55 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
39 0
下一篇
无影云桌面