位运算

137. 只出现一次的数字 II

class Solution {
    public int singleNumber(int[] nums) {
        int once=0,twice=0;
        for(int num:nums){
            once=(once^num)&~twice;
            twice=(twice^num)&~once;
        }
        return once;
    }
}

260. 只出现一次的数字 III

只有两个数字a、b出现了一次，其他数字都出现了两次。全部数字异或的结果就等于a^b。
假设a异或b的结果xor，最右第五位1。
说明a、b的第五位一个是0一个是1，把数组中最右第五位是0的数全部异或一遍，就可以找到那个单独的第五位是0的数字。
同样，把数组中最右第五位是1的数全部异或一遍，就可以找到那个单独的第五位是1的数字。

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor=0;
        for(int num:nums){
            xor=xor^num;
        }
        int flag=1;
        while((xor&1)==0){
            xor=xor>>1;
            flag=flag<<1;
        }
        int a=0,b=0;
        for(int num:nums){
            if((flag&num)==0){
                a=a^num;
            }else{
                b=b^num;
            }
        }
        return new int[]{a,b};
    }
}

89. 格雷编码

class Solution {
    public List<Integer> grayCode(int n) {
        /**
        关键是搞清楚格雷编码的生成过程, G(i) = i ^ (i/2);
        如 n = 3: 
        G(0) = 000, 
        G(1) = 1 ^ 0 = 001 ^ 000 = 001
        G(2) = 2 ^ 1 = 010 ^ 001 = 011 
        G(3) = 3 ^ 1 = 011 ^ 001 = 010
        G(4) = 4 ^ 2 = 100 ^ 010 = 110
        G(5) = 5 ^ 2 = 101 ^ 010 = 111
        G(6) = 6 ^ 3 = 110 ^ 011 = 101
        G(7) = 7 ^ 3 = 111 ^ 011 = 100
        **/
        List<Integer> res = new ArrayList<>();
        for(int i=0;i<(1<<n);i++){
            res.add(i^(i>>1));
        }
        return res;
    }
}

也可以用dfs，但是应该不是题目的本意？
因为这样才打败了10%

class Solution {
    List<Integer> res = new ArrayList();
    boolean[] visited;
    public List<Integer> grayCode(int n) {
        visited = new boolean[1<<n];
        dfs(0,n);
        return res;
    }
    void dfs(int cur,int n){ 
        if(res.size()==(1<<n))
            return;
        res.add(cur);
        visited[cur]=true;
        for(int i=0;i<n;i++){
            int next = cur^(1<<i); //这里改变cur的某一位，用异或
            if(!visited[next]) dfs(next,n);
        }
    }
}

338. 比特位计数

要多写几位找规律。
比如：
9 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
16 10000
如果i是奇数，就只比上一个数多了一个末尾的1
如果i是偶数，就是把（从右往左数）1-n位的连续1变成n+1位的1

class Solution {
    public int[] countBits(int num) {
      int[] dp=new int[num+1];
      if(num==0) return dp;
      for(int i=1;i<=num;i++){
        if(((i-1)&1)==0){
          dp[i]=dp[i-1]+1;
        }
        else{
          dp[i]=dp[i-1]-countOne(i-1)+1;
        }
      }
      return dp;
    }
    private int countOne(int n){
      int count=0;
      while((n&1)==1){
        n=n>>1;
        count++;
      }
      return count;
    }
}