Leetcode hot100 比特位计数【简单】

法一模拟二进制加一主要想借这个题讲明白做题的思路第一步为什么是先看透了这个题用自己的话讲明白。这个题不是让你数1的个数嘛如果你上来就直接数会发现什么规律也找不到。0 1 -- 0个 1个10 11 -- 1个 2个100 101 110 111 -- 1个 2个 2个 3个1000 1001 1010 1011 1100 1101 1110 1111 -- 1个 2个 2个 3个 2个 3个 3个 4个就应该先看透了题不止求数字n的1个数n前面的也要给出来。直觉告诉你应该是能用到前面的不然只求数字n的不就好了。所以其实只是让你模拟二进制的加一操作而已。。。观察规律来一个1只有两种情况一种是末尾是0那么直接把1放上去就好了一种是末尾是1那么就往前一直找到第一个0把0的位置改为1后面的1都改为0。怎么找第1个0呢其实就是10进制转2进制。不断对2取模拿余数。那其实可以合并成同一种情况也就是从低位往前找第一个0.本质上考的是①找到进制的加一操作的规律 ②考你10进制转2进制。class Solution { public int[] countBits(int n) { //结果集 int[] result new int[n1]; //用数字0去初始化 int size1; int oneNum 0; result[0]oneNum; for(int i1;in;i){ //1-特殊情况提前做处理而不是混到后面去考虑——如果1的个数等于位数那么位数11的个数变为1 if(oneNumsize){ size; oneNum1; //2-普通情况——如果1的个数小于位数 }else{ int lastOneNum 0; //从后往前数1的个数 int beforeI i-1; //i前面那个数 while(beforeI%21){ lastOneNum; beforeIbeforeI/2; } oneNum oneNum-lastOneNum1; } result[i]oneNum; } return result; } }法二更简单的规律对于所有的数字只有两类奇数二进制表示中奇数一定比前面那个偶数多一个 1因为多的就是最低位的 1。偶数偶数的最低位是0也就是对于偶数来说二进制表示里1的个数和去掉最低位的二进制表示里1的个数同样多。例如“1010”中1的个数和“101”中1的个数同样多。去掉最低位也就是右移一位Java里右移一位的运算和除以2的运算等价。所以两种运算方式都可以class Solution { public int[] countBits(int n) { //结果集 int[] result new int[n1]; //用数字0去初始化 result[0]0; for(int i1;in; i){ //1-奇数 if(i%21){ result[i]result[i-1]1; //2-偶数 }else{ result[i]result[i/2]; //除以2 //result[i]result[i1]; //右移一位 } } return result; } }