剑指offer 专项突破版 3、前 n 个数字二进制中 1 的个数

题目链接

思路

• 思路一
  最简单的思路就是每一个数字单独算二进制下1的个数
  注意有一种简便算法就是利用 i & i-1 来让i最右侧的1变为0 所以说 i & i-1比i的二进制1的位数少1 利用这个规律可以快速的算出n在二进制下1的个数

  复制代码public class Solution { public int[] countBits(int n) { int[] result = new int[n + 1]; for (int i = 0; i <= n; i++) { int count = 0, j = i; while (0 != j) { result[i] += 1; j &= j - 1; } } return result; } }

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  public class Solution {
  public int[] countBits(int n) {
  int[] result = new int[n + 1];
  for (int i = 0; i <= n; i++) {
  int count = 0, j = i;
  while (0 != j) {
  result[i] += 1;
  j &= j - 1;
  }
  }
  return result;
  }
  }
  

  这种解法注意

  1. 要引入变量j 而不能更新i
  2. while循环的判断条件是 0 ！= j

• 思路二
  既然i & i-1比i的二进制1的位数少1 而我们的result数组保存的就是二进制形式1的位数 那么自然有result[i] = result[i&i-1]+1

  复制代码public class Solution { public int[] countBits(int n) { int[] result = new int[n + 1]; for (int i = 0; i <= n; i++) { result[i] = result[i & i - 1] + 1; } return result; } }

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  public class Solution {
  public int[] countBits(int n) {
  int[] result = new int[n + 1];
  for (int i = 0; i <= n; i++) {
  result[i] = result[i & i - 1] + 1;
  }
  return result;
  }
  }
  

• 思路三
  思路三主要是对于规律的寻找 我们知道在二进制情况下 左移1位等价于乘2，所以对于i，必有result[2*i] = result[i]
  那么对于result[2 * i+1],则可以看成result[i]先左移1位再+1，因为此时刚左移结束，最低为一定是0，所以不会产生进位，所以result[2 * i+1] = result[2 * i]+1

  复制代码public class Solution { public int[] countBits(int n) { int[] result = new int[n + 1]; for (int i = 1; i <= n; i++) { result[i] = result[i >> 1] + (1 & i); } return result; } }

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  public class Solution {
  public int[] countBits(int n) {
  int[] result = new int[n + 1];
  for (int i = 1; i <= n; i++) {
  result[i] = result[i >> 1] + (1 & i);
  }
  return result;
  }
  }
  

最后

以上就是想人陪小蝴蝶最近收集整理的关于剑指offer 专项突破版 3、前 n 个数字二进制中 1 的个数的全部内容，更多相关剑指offer内容请搜索靠谱客的其他文章。