解法一：利用哈希set存储

优点：由题意只有一个数字出现一次，容易想到hashset不能重复出现相同元素特性

缺点：耗时长，由于每次删除需要遍历hashset，并且使用了额外空间

public int singleNumber(int[] nums) {
       //由于题目中已经说明只有一个元素会出现一次，因此我们可以利用hashset的特性
        HashSet<Integer> hashSet=new HashSet();
        for (int num:nums){
            if (!hashSet.add(num)){//如果这个元素已经添加过了
                hashSet.remove(num);
            }else {
                hashSet.add(num);
            }
        }
        //添加完所有的元素，所有出现两次的元素已经被删除
        return hashSet.iterator().next();
    }

 

 解法二：位运算之异或

优点：没有使用额外空间，时间复杂度是O(n)

缺点：不容易想到

public int singleNumber(int[] nums) {
        int res=0;
       for (int num:nums){
           res=res^num;
       }
       return res;
    }

 

 

解法一：利用位运算中 n&（n-1）可以消去最后一位1的特性 

public int[] countBits(int n) {
        int[] res=new int[n+1];//因为是0~n,所以新数组的长度是n+1
        for (int i=1;i<n+1;i++){//数组的默认值是0，而0的二进制恰好是0个1
            res[i]=res[i&(i-1)]+1;//因为此操作可以消去最后一位1,我们逆向思维加上一个1
        }
        return res;
    }

 

 解法二：利用奇数的含1是他-1的偶然的含1量+1，偶数的含1量就是他除以2的含1量

                当然我们同样可以利用位运算来判断是奇数偶数

 

 public int[] countBits(int n) {
       //同样的，先new一个返回数组
        int[] res=new int[n+1];
        for (int i=1;i<n+1;i++){
            res[i]=(i&1)==1?res[i-1]+1:res[i>>1];
        }
        return res;
    }

 

利用异或运算，把不同的地方都变为1 ，在计算1的个数

public int hammingDistance(int x, int y) {
       //我们将两个数进行异或运算，那么不同的地方都将是一，我们只需要统计1的个数
        int num=0;
        for ( int i=x^y;i!=0;i=i&(i-1)){
            num++;
        }
        return num;
    }