338. 比特位计数

系统管理员 2022-11-27 00:53 160阅读 0赞

# 题目： #

[338. 比特位计数][338.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解： #

1.  解释一：  
    ![在这里插入图片描述][20200812215850649.png_pic_center]
2.  解释二：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]
3.  解释三：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]
4.  解释四：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]

## 1. 题解一：动态规划 + 最低有效位 ##

![在这里插入图片描述][20200812215029971.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]

## 2. 题解二：动态规划 + 最后设置位 ##

![在这里插入图片描述][20200812215247750.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 5]

# 代码： #

## 1. 代码一：动态规划 + 最低有效位 ##

import java.util.*;
    
    public class code338 { 
    
        // 方法1: 动态规划 + 最低有效位
        public static int[] countBits(int num) { 
            int res[] = new int[num + 1];
            for(int i = 1; i <= num; i++)
            { 
                res[i] = res[i >> 1] + (i & 1); // (x / 2) is (x >> 1) and (x % 2) is (x & 1), 注意 (i & 1) 需要加括号
            }
            return res;
        }
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while(sc.hasNextInt())
            { 
                int num = sc.nextInt();
                int res[] = countBits(num);
                for(int i = 0; i <= num; i++)
                { 
                    System.out.print(res[i] + " ");
                }
                System.out.println();
            }
        }
        
    }

## 2. 代码二：动态规划 + 最后设置位 ##

import java.util.*;
    
    public class code338 { 
    
        // 方法2: 动态规划 + 最后设置位
        public static int[] countBits(int num) { 
            int res[] = new int[num + 1];
            for(int i = 1; i <= num; i++)
            { 
                res[i] = res[i & (i - 1)] + 1; // 注意要从1开始，0不满足
            }
            return res;
        }
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while(sc.hasNextInt())
            { 
                int num = sc.nextInt();
                int res[] = countBits(num);
                for(int i = 0; i <= num; i++)
                { 
                    System.out.print(res[i] + " ");
                }
                System.out.println();
            }
        }
        
    }

# 参考： #

1.  [比特位计数][Link 1]
2.  [清晰的思路][Link 2]
3.  [位运算基础知识][Link 3]
4.  [动态规划（位运算性质） python3][python3]
5.  [最清晰的动态规划解题思路分析][Link 4]

[338.]: https://leetcode-cn.com/problems/counting-bits/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/2d63cf04c915473694012d438fd779e1.png
[20200812215850649.png_pic_center]: /images/20221124/478098aaa60b473fa9984cb40b829945.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/1ceaaabb1b374bf5ad6c05e5e75079d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/9ef2ea9b4ad444e7b1fd6c9db4c9fc03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/ff007939fdee457ebf8ec21b1fe78e1c.png
[20200812215029971.png_pic_center]: /images/20221124/801d526e938c417f82232a66ff5fbca2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221124/dc206418e44a447bb66b7af08920f669.png
[20200812215247750.png_pic_center]: /images/20221124/411abd83b35e4555a6cc6469d065ed04.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221124/2d7b4e21ae8443ad844e564983519dc1.png
[Link 1]: https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode/
[Link 2]: https://leetcode-cn.com/problems/counting-bits/solution/hen-qing-xi-de-si-lu-by-duadua/
[Link 3]: https://leetcode-cn.com/problems/counting-bits/solution/zhe-ying-gai-shi-dao-easyti-ba-wei-yun-suan-ji-chu/
[python3]: https://leetcode-cn.com/problems/counting-bits/solution/dong-tai-gui-hua-wei-yun-suan-xing-zhi-python3-by-/
[Link 4]: https://leetcode-cn.com/problems/counting-bits/solution/zui-qing-xi-de-dong-tai-gui-hua-jie-ti-si-lu-fen-x/