Single Number III leetcode

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

与single number1 类似 每个重复的数都出现两次, 假设不重复的数字为a, b. 用^遍历所有数组就会得到一个a^b的结果c. 我们知道在c中, 每一位1说明在这一位上a与b是不同的. 
      3 (0011) xor 
      5 (0101)= 
     6 (0110) 
我们只需要找到这1位, 然后把数组按照这一位是1还是这一位是0分为两个数组 然后分别做^遍历 就会在每个组中找到一个独立的单身狗了.

public class Solution {
    public int[] singleNumber(int[] nums) {
        int[] res = new int[2];
        if (nums == null || nums.length == 0) {
            return res;
        }
        int tem = 0;
        for (int c : nums) {
            tem ^= c;
        }
        int pre = 0;
        while (tem!= 0) {
            pre = tem;
            tem &= tem - 1;
        }
        for (int n : nums) {
            if ((n & pre) == 0) {
                res[0] ^= n;
            } else {
                res[1] ^= n;
            }
        }
        return res;
    }
}

Reverse Bits leetcode

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++, n >>= 1) {
            res = res << 1 | (n & 1);//给res的最后一位置为(n最右一位)
        }
        return res;
    }
}

//方法2
public int reverseBits(int n) {
        int res = 0;
        int[] tem = new int[32];
        for (int i = 0; i < 32; i++) {
            tem[i] = n >> i & 1;
        }
        for (int i = 31; i >= 0; i--) {
            res += tem[i] << (31 - i);
        }
        return res;
    }

Power of Two leetcode

Given an integer, write a function to determine if it is a power of two.

public class Solution {
    public boolean isPowerOfTwo(int n) {
         if (n <= 0) {
             return false;
         }
         return (n & (n - 1)) == 0;
        
    }
}

Number of 1 Bits leetcode

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

解法1: 把每一位都 & 1, 计算所有1的个数
解法2: 因为n & (n - 1)就可以消除掉最右边的一个1, 比如110，减去1得101，相与得100，消去了最右边的1。这样一直消除到没有, 可以计算出1得个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >> i) & 1) == 1) {
                count++;
            }
        }
        return count;
    }
}

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

Repeated DNA Sequences leetcode

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

一开始暴力解法超时了, 看了答案发现要用位运算 就是把A看为00 C 01, G 10, T 11. 用一个hash来存这20位数字 然后拿数字比较

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<String>();
        if (s.length() < 10) {
            return res;
        }
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        HashSet<Integer> set = new HashSet<Integer>();
        HashSet<Integer> resset = new HashSet<Integer>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);
        int hash = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i < 9) {
                hash = (hash << 2) + map.get(s.charAt(i));
            } else {
                hash = (hash << 2) + map.get(s.charAt(i));
                hash = hash &  ((1 << 20) - 1); // 取20位1与hash 进行&运算, 这样可以保留hash的后20位
                if (set.contains(hash) && ! resset.contains(hash)) {
                    resset.add(hash);
                    res.add(s.substring(i - 9, i + 1));
                } else {
                    set.add(hash);
                }
            }
        }
        return res;
        
    }
}

Single Number II leetcode

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

这回数组内相同的数出现三次

reference: http://www.cnblogs.com/springfor/p/3870863.html

          解题思想是：

把每一位数都想成二进制的数，用一个32位的数组来记录每一位上面的1的count值。这里注意数组计数是从左往右走，而二进制数数是从右往左的。。所以数组第0位的count就是二进制最低位上的count的。例如：4的二进制是100（当然作为32位就是前面还一堆了000...000100这样子），3个4的话按照每位相加的话，按照二进制表示法考虑就是300，当然存在数组里面就是003（A[0]=0;A[1]=0;A[2]=3，然后后面到A[31]都得0）。

然后对所有数按照二进制表示按位加好后，就要把他还原成所求的值。这里面的想法是，如果一个数字出现了3次，那么这个数字的每一位上面，如果有1那么累加肯定是得3的，如果是0，自然还是0。所以对每一位取余数，得的余数再拼接起来就是我们要找的那个single one。

这里还原的方法是，对32位数组从0开始，对3取余数，因为数组0位置其实是二进制的最低位，所以每次要向左移。用OR（|）和 + 都可以拼接回来。。

public class Solution {
    public int singleNumber(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return -1;
        }
        int result = 0;
        int[] bits = new int[32];
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < nums.length; j++) {
                bits[i] += nums[j] >> i & 1;// 把数值又移是第i位变为最后一位, 然后数值与0000....1 取and, 这样只有最后一位是1的话保存 其余位数均为0
                bits[i] %= 3;
            }
            result |= bits[i] << i;//bits[i]只有第i位为1 其余位都为0 所以result只要把第i为变为1其他不变 所以取或运算 这里也可以是+=
        }
        return result;
    }
}

Single Number leetcode

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

1. a ^ a = 0

2. a ^ b = b ^ a

3. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c

----> a ^ b ^ a = b

所以把全部数字异或一遍就能找到只出现一次的数 时间O(n)

public class Solution {
    public int singleNumber(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return -1;
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res = res ^ nums[i];
        }
        return res;
    }
}

Bit Manipulation 位运算

位操作符：

OR (|)	AND (&)	XOR (^)	Left Shift (<<)	Right Shift (>>)	Not (~)
1|0=1	1&0=0	1^0=1	0010<<2=1000	1100>>2=0011	~1=0

1. a ^ a = 0

2. a ^ b = b ^ a

按位或（OR）

按位或处理两个长度相同的二进制数，两个相应的二进位中只要有一个为1，该位的结果值为1。例如

        0101（十进制5）
     OR 0011（十进制3）
      = 0111（十进制7）

按位异或（XOR）

按位异或运算，对等长二进制模式按位或二进制数的每一位执行逻辑异按位或操作。操作的结果是如果某位不同则该位为1，否则该位为0。例如

         0101
     XOR 0011
       = 0110

按位与（AND）[编辑]

按位与处理两个长度相同的二进制数，两个相应的二进位都为1，该位的结果值才为1，否则为0。例如：

         0101
     AND 0011
       = 0001

常用方法:

• 1. n & （n-1）能够消 除n中最右侧的一个1。
• 2. 左移 << 右移>>
• 3. (a >> x) & 1 或者 a & (1 << x) 判断a的x位是否为0
• 4. num | (1 << i) 把num的第i位置为1