Java 整数 数组 位运算 二进制和十进制 动态规划 2021-10-12

题目：给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

• 二进制和十进制转换

首先想到的是把十进制数转换成二进制数去查1的数量

//数学除法思想
 public void binaryToDecimal(int n){
       int t = 0;  //用来记录位数
      int bin = 0; //用来记录最后的二进制数
      int r = 0;  //用来存储余数
      while(n != 0){
          r = n % 2;
          n = n / 2;
          bin += r * Math().pow(10,t);
          t++; 
      }
          System.out.println(bin);
  }
//移位思想
 public void binaryToDecimal(int n){
      for(int i = 31;i >= 0; i--)
          System.out.print(n >>> i & 1);
 }

后来发现我并不需要输出二进制字符串，只需要返回1的个数就行，那好在其中可以加一个if语句判断是不是1，返回当前值的1的数量就可以作为最后数组的一个值。

class Solution {
	public static int  numOne(int n) {
		int i =0;
		int sum = 0;
		while(n!=0) {
			i = n %2;
			n = n/2;
			if (i==1)
				sum++;
		}
		return sum;
	}
	public int[] countBits(int n) {
		int[] arr = new int[n+1];
		for(int i =0;i<=n;i++) {
			arr[i]=numOne(i);
		}
		return arr;
	}		
}

成功通过了 不过我们可以发现它的时间复杂度是n^2 所以我们继续整！

现在我想到那我们就合并到一个for循环中全部运算完呢
但是数一个值的1的个数要遍历它自身；而输出数组是遍历从0到n的每个数，所以简单的整合思路是不行的

• 那么动态规划去分解子问题呢？
  总1数等于二进制中最后一位的1数加前面剩余位的1数即
• // 当前数x 1的个数 是 x/2 1的个数 + 第0位是否是1
  // res[5] = res[5/2] + (5&1);

class Solution {
    public int[] countBits(int n) {
        int res[] = new int[n + 1];
        for (int i = 0; i < n + 1; i++){
            // 当前数x 1的个数  是 x/2 1的个数 +  第0位是否是1
            // res[5] = res[5/2] + (5&1);
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}