Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.

Naive Way: My first thought was to use "&" operation going though all numbers between m and n inclusively. That gets a TLE. I later wrote some test cases and find out that "&" operation is hard to keep even one bit when there is a gap between n and m.
For example: 4-8: 0100, 0101, 0110, 0111, 1000. result is 0000.
It turns out that m and n need to have same highest bit, otherwise the result will be 0.

I tried many times and finally find out that a method use only bit shift operation will do the trick. Any ">" or "<" compare condition will possibly ruin he algorithm because 0x80000000 is a negative number.

My method is a recursive one. The idea is keep finding highest bit of m, check if n has a higher bit. And let the recursive call do the rest bits.

 public class Solution {  
   public int rangeBitwiseAnd(int m, int n) {  
     return rangeBitwiseAnd(m,n,0x80000000);  
   }  
     
   private int rangeBitwiseAnd(int m, int n, int shift){  
       
     // edge case  
     if(m==0) return 0;  
       
     // find highest bit of m  
     while((shift & m) == 0){  
       if((shift & n) != 0) return 0;  
       shift >>>= 1;  
     }  
       
     return shift + rangeBitwiseAnd(m - shift, n - shift, shift);  
   }  
 }  

Improved Way: After viewing the Discuss, I find there are tons of lot better solutions.

One is from applewolf, who find out that keep comparing from lower bits to higher bits can do the trick.

 int rangeBitwiseAnd(int m, int n) {  
   return (n > m) ? (rangeBitwiseAnd(m/2, n/2) << 1) : m;  
 }  

Another is from haw64, who find out that the result of AND operation is just left most consecutive common part of n and m (just two numbers, no need of numbers in between).

 public int rangeBitwiseAnd(int m, int n) {  
     int count = 0;  
     while(m != n){  
       m >>= 1;  
       n >>= 1;  
       count++;  
     }  
     return m<<=count;  
   }  

Number of 1 Bits

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.

Naive Way: To go through each bit using a mask will take 32 unit time. However, there is a way that runs faster, x & (x-1), which removes the right most 1 from x. For reference, see low-level-bit-hacks

 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;  
   }  
 }  

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).
Follow up:
If this function is called many times, how would you optimize it?

Naive Way:Need to use another integer to store the reversed bits. Traversal target from low to high,  construct result from high to low.
The key here is to use ">>>" instead of ">>"
1000 >> 1 becomes 1100
1000 >>>1 becomes 0100

 public class Solution {  
   // you need treat n as an unsigned value  
   public int reverseBits(int n) {  
     int m = 0;  
     for(int i = 0;i < 32;i++)  
       if((n & (0x00000001 << i)) != 0) m |= (0x80000000 >>> i);  
     return m;  
   }  
 }  

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

Naive Way:通常不让用这些数学运算符都是在指向比特运算符。除以2，4，8就好办了，可以通过移位实现，除以3怎么办呢。可不可以从结果开始想，除以3相当于先把结果左移1位(2)，再加上他自己(1)。那么除以7就相当于找到一个数左移2位，左移1位，左移0位之和为除数。如果不能整除，就是除数在（左移2位，左移1位，左移0位之和）和（左移2位，左移1位，左移1位之和）之间。好像可以用一个recursive的方法，每次都找都最高位的商，剩下的交给下一级recursive call。

还有负数，真是烦。因为Integer.MIN_VALUE没有对应的正数，写的时候特别麻烦。不能先全转成正数，于是我就打算全用负数做。

最后的最后，终于是全通过了，并且迫于无奈只能将dividend = Integer.MIN_VALUE, divisor = -1这个case单独列出了，因为它使唯一一个会超出表示范围的数。

复杂度上并没有使用binary search 找当前位，尝试过，很难，尤其是负数。 边界由
divisor << cur < 0 && cur < 31 控制，第一个是要保持负数形式，唯一一个例外就是Integer.MIN_VALUE除以1的时候，因为没有上限，-1移位成Integer.MIN_VALUE时下一个就只会移0位，因为java不让左移33位，会变回左移1位，所以有了第二个条件 cur <31。

 public class Solution {  
   public int divide(int dividend, int divisor) {  
     if(dividend==Integer.MIN_VALUE && divisor==-1) return Integer.MAX_VALUE;  
     if(dividend > 0 && divisor > 0) return divideHelper(-dividend, -divisor);  
     else if(dividend > 0) return -divideHelper(-dividend,divisor);  
     else if(divisor > 0) return -divideHelper(dividend,-divisor);  
     else return divideHelper(dividend, divisor);  
   }  
   private int divideHelper(int dividend, int divisor){  
     // base case  
     if(divisor < dividend) return 0;  
     // get highest digit of divisor  
     int cur = 0, res = 0;  
     while((divisor << cur) >= dividend && divisor << cur < 0 && cur < 31) cur++;  
     res = dividend - (divisor << cur-1);  
     if(res > divisor) return 1 << cur-1;  
     return (1 << cur-1)+divide(res, divisor);  
   }  
 }   

Improved Way:看到Discuss里大部分人都是用long做的，有人就问，如果让你divide的是两个long呢。long的做法完全可以用正数做了。我觉得应该能使用Binary search提高效率。记住要补上！

Single Number II

Single Number II

 

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?

Naive Way:根据Single Number 中的做法，有没有一种运算x 能使得
1 x 1 x 1 = 0;
0 x 0 x 0 = 0;
1 x 0 = 1;
0 x 0 = 0;

要是有也不是一种好办法，因为如果k=4,5,6...就还要想新的运算。所以必须有一种运算能够满足k个的情况。

以上推断给了一个实例，如果k个数，在同一个 bit 位上就可能会有 k 个 1，如果用一个 int 表示每一位上 1 的个数，有k个数的就会有k个1，最后除以k就会被除尽，而多出的那个1就是多出的那个 single one 的对应 bit 位上的 1。

算法复杂度 O(n), space O(1)

 public class Solution {  
   public int singleNumber(int[] A) {  
     int k = 3;  
     int x = 0;  
     int num[] = new int[32];  
     for(int i = 0;i < A.length;i++)  
       for(int j = 0;j < num.length;j++)  
         num[j] += ((A[i] & (1 << j)) != 0)?1:0;  
     for(int j = 0;j < num.length;j++) x |= ((num[j]%k) << j);  
     return x;  
   }  
 }  

Improved Way:此题在Discuss里的方法还真不少。

  public class Solution {  
   public int singleNumber(int[] A) {  
     int ones = 0, twos = 0;  
     for(int i = 0; i < A.length; i++){  
       ones = (ones ^ A[i]) & ~twos;  
       twos = (twos ^ A[i]) & ~ones;  
     }  
     return ones;  
   }  
 }  

这里有一个方法找到了一种 x 运算满足之前说的条件。

来自leetcode 用户  againest1 。理解这个算法首先要认识到数字出现的顺序对于比特运算是无关的，根据比特运算的交换律。那么我们可以把这个序列看成是连续三个一样的不停出现，直到那一个落单的。
第一个 x 出现，ones = x & ~0 = x, twos = x & ~x = 0;
第二个 x 出现，ones = x ^ x & ~0 = 0 & ~0 = 0; twos = 0 ^ x & ~0 = x;
第三个 x 出现，ones = 0 ^ x & ~x = x & ~x = 0; twos = x ^ x & ~0 = 0;
只出现一次会被ones记录，只出现两次会被twos记录，出现3次两者都不记录。


 这里还有一个解释超长的，做法是一样的 https://oj.leetcode.com/discuss/9763/accepted-proper-explaination-does-anyone-have-better-idea

 

Single Number

Single Number

 

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?

Naive Way:好有纪念意义的一道题啊，这是我做leetcode的第一道题，对我有启蒙之恩。当时竟不知道Map为何物，更惶论HashTable了。

即使不知道这些也是可以做的，这是我第一次的做法。

 public int singleNumber(int[] A) {  
     int map[] = new int[(A.length+1)/2];  
     int len = map.length;  
     int temp;  
     // 0 case && 1 case  
     int count0 = 0;  
     int count1 = 0;  
     for(int i = 0;i < A.length;i++){  
       if(A[i] == 0){  
         count0++;  
       }  
       if(A[i] == 1){  
         count1++;  
       }  
     }  
     if(count0 == 1){  
       return 0;  
     }  
     if(count1 == 1){  
       return 1;  
     }  
     // general case  
     for(int i = 0;i < A.length;i++){  
       temp = Math.abs(A[i]%len);  
       while(map[temp] != 0 && map[temp] != A[i]){  
         temp++;  
         temp = temp%len;  
       }  
       if(map[temp] == 0){  
         map[temp] = A[i];  
       }else if(map[temp] == A[i]){  
         map[temp] = 1;  
       }  
     }  
     for(int i = 0;i < len;i++){  
       if(map[i] != 0 && map[i] != 1){  
         return map[i];  
       }  
     }  
     return 0;  
   }  

Improved Way: 现在我知道 a^a = 0这回事了。

 

  public class Solution {  
   public int singleNumber(int[] A) {  
     int x = 0;  
     for(int i = 0;i < A.length;i++) x ^= A[i];  
     return x;  
   }  
 }  

Gray Code

Gray Code

 

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Naive Way: 有这样一个想法，从0000开始，先做镜像（倒着取），得到0000，然后第一位与mask=1或运算，就是0001，然后加入list中。不断从list中倒着取，然后和新的mask取或，每次把mask进一位。

算法复杂度O(2^n)

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> list = new ArrayList<Integer>();
        int mask = 1, i = 1;
        list.add(0);
        while(i <= n){
            int k = list.size();
            for(int j = k-1;j >=0;j--){
                int t = list.get(j) | mask;
                list.add(t);
            }
            mask <<= 1;
            i++;
        }
        return list;
    }
}


还有一个方法，是我第一次做的方法，相当于用数学运算求镜像。

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> lst= new ArrayList<Integer>();
        // base case
        lst.add(0);
        
        // iteration
        for(int i = 1;i < Math.pow(2,n);i++){
            int level = (int)Math.floor(Math.log(i)/Math.log(2));
            int cur_index = (int)Math.pow(2,level)+lst.get((int)Math.pow(2,level+1)-1-i);
            lst.add(cur_index);
        }
        return lst;
    }
}

 

Improved Way: 最厉害的方法，G(i) = i^(i/2)。来自leetcode 用户 jinrf 

wiki上的说法是G(i) = i ^ (i >> 1)



public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new LinkedList<>();
        for(int i=0;i<1<<n;i++) result.add(i^i>>1);
        return result;
    }
}

Repeated DNA Sequences

Repeated DNA Sequences

 

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"]. 

Naive Way: 一开始试了两种方法都不行。一种是用一个set去存

已经遍历过的substring，然后每取得一个新的就看set是否contain。 

这样的做法的算法复杂度是O(n)，但是需要O(n)的space,

会出现内存不够。第二种方法是不用set，每次取得一个substring

都和之前开头到当前位置的每一个substring比较，

这样的算法复杂度是O(n^2),space O(1)，会出现超时。

然后我想到了这个在time complexity 和 

memory之间折中的办法。Map存的是对应前m个字符一致时，

各个(m字符串)出现的位置，1<m<=10，这样m越大，space 

需求越大，time complexity越小。 但是还是不行，

在m=3的时候会报超时，m=4的时候会报空间不足。

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> rlst = new ArrayList<String>();
        Map<String, List<Integer>> map = new HashMap<String, List<Integer>>();
        int k = 10;
        int offset = 4;
        for(int i = 0;i < s.length()-k+1;i++){
            String ss = s.substring(i,i+offset);
            if(!map.containsKey(ss)){
                List<Integer> list = new ArrayList<Integer>();
                list.add(i);
                map.put(ss, list);
            }else{
                List<Integer> list = map.get(ss);
                boolean found = false;
                for(int j = 0;j < list.size();j++){
                    int t = offset;
                    for(;t < k;t++){
                        if(s.charAt(i+t)!=s.charAt(list.get(j)+t))
                            break;
                    }
                    if(t==k){
                        rlst.add(s.substring(i,i+k));
                        found = true;
                        break;
                    }
                }
                if(!found)
                    list.add(i);
            }
        }
        return rlst;
    }
}

然后还试了一种树形的存贮方式，也是memory limit exceed。看了tag标记为bit manipulate,似乎有点头绪了。四种字符可以用两位二进制完全表示。10个连续字符是20位二进制，一个int型是32位。是否可以用一个Set<Integer>来存遍历过的字符串，这样每一次存贮可以节省16*10-32=128bit 空间。这种方法还是会内存不足。

 最后的最后！

  Improved Way:

终于让这道题Accepted了，已经是第五天了，这回我也算是竭尽所能的减少空间使用率。首先使用了一个byte array来存10个连续单位中A,C,G,T出现次数 ，又因为正好4个byte是一个int，就可以用一个int来表示出现次数，使用一个Map<Integer, Set<String>>的map来将出现次数和同一种出现次数下的对应String Set做映射。然后由于10个单位的两比特数是20比特，又可以用一个int表示，就将所有String换成int来存，这样最后的map就变成了Map<Intger, Set<Integer>>。每次只要看该String对应的Integer是否在Set中就可以判断是否出现过了。

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> list = new ArrayList<String>();
        Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
        Set<String> visited = new HashSet<String>();
        int k = 10;
        byte[] appear = new byte[4];
        Arrays.fill(appear, (byte)0);
        for(int i = 0;i < s.length();i++){
            appear[dna2int(s.charAt(i))]++;
            if(i >= k-1){
                String sample = s.substring(i-k+1,i+1);
                int key = byte2int(appear);
                int intSample = seq2int(sample);
                if(!map.containsKey(key)){
                    Set<Integer> set = new HashSet<Integer>();
                    set.add(intSample);
                    map.put(key,set);
                }else{
                    Set<Integer> set = map.get(key);
                    if(set.contains(intSample)){
                        if(!visited.contains(sample))
                            visited.add(sample);
                    }else{
                        set.add(intSample);
                        //map.put(key,set);
                    }
                }
                appear[dna2int(s.charAt(i-k+1))]--;
            }
        }
        list.addAll(visited);
        return list;
    }
    
    private int dna2int(char a){
        switch(a){
            case 'A':return 0;
            case 'C':return 1;
            case 'G':return 2;
            case 'T':return 3;
            default: return 0;
        }
    }
    
    private int byte2int(byte[] b){
        int x = b[0] << 24 | b[1] << 16 | b[2] << 8 | b[3];
        return x;
    }
    
    private int seq2int(String s){
        int x = 0;
        for(int i = 0;i < s.length();i++){
            x <<= 2;
            switch(s.charAt(i)){
                case 'A':
                    x |= 0;
                    break;
                case 'C':
                    x |= 1;
                    break;
                case 'G':
                    x |= 2;
                    break;
                case 'T':
                    x |= 3;
                    break;
                default:
                    break;
            }
        }
        return x;
    }
    
}

 

 

最后在discuss里看到了一个最厉害的方法，叫做Rabin-Karp，可用来解strStr()。它采用Rolling Hash的方法，每次固定大小的窗移动一位时，只需减去对应的hash量和加上新的hash量就可以形成新的hash码，它的理论基础大概是这样的。

 

对于这道题，一共有ACGT四个变量，为他们赋值0123，那么以4为底的话，就能让连续k个组合的序列具有唯一的hash码。比如k=3时，

ACG = 0 * 4^2 + 1 * 4^1 + 2 * 4^0;

TTC  = 3 * 4^2 + 3 * 4^1 + 1 * 4^0;

就像10进制，只要每一位上的数不是完全相同，两个数就不相同。

使用这个的前提是4^(k+1) <= Integer.MAX_VALUE。

k=10的时候 4^11 = 2^22 < 2^31。

维基百科中说，即使变量的个数很大时，也可以用小于变量个数的大质数做底，因为质数幂次方后很少出现两个不同数的hash码一致。

public class Solution {
    private static final int base = 4;
    public List<String> findRepeatedDnaSequences(String s) {
        // Rabin-Karp rolling hash
        List<String> list = new ArrayList<String>();
        Set<Integer> set = new HashSet<Integer>();
        Set<String> rslt = new HashSet<String>();
        int k = 10;
        int head_factor = (int)Math.pow(base,k-1);
        int hash = 0;
        for(int i = 0;i < s.length();i++){
            hash -= i>=k?head_factor*dna2int(s.charAt(i-k)):0;
            hash = hash*base+dna2int(s.charAt(i));
            if(i >= k-1 && !set.add(hash))
                rslt.add(s.substring(i-k+1,i+1));
        }
        list.addAll(rslt);
        return list;
    }
    
    private int dna2int(Character c){
        switch(c){
            case 'A':return 0;
            case 'C':return 1;
            case 'G':return 2;
            case 'T':return 3;
            default:return 0;
        }
    }
}

Pow(x, n)

Pow(x, n)

Implement pow(x, n).

Naive Way: brute force是O(n)。很明显x^5 = x^2 * x^2 * x 是缩小时间复杂度的关键。这里还要记得有负数次幂的情况。经观察和我第一次做时看别人做法的记忆，7=4+2+1 是核心。
x^7 = x^4 + x^2 + x^1。
那么先将[x^1,x^2,x^4...x^(logn)]罗列出来，
第一次n=7， 7/4 = 1...3 说明有一个x^4,
第二次n=3,    3/2 = 1...1 说明有一个x^2,
第三次n=1,    1/1 = 1...0 说明有一个x^1。
要注意如果商是0，说明没有对应项的乘因子，就不乘或者乘1.0。

这样就变成了不断取最高位的算法。算法复杂度是O(logn)，space是O(logn)

public class Solution {
    public double pow(double x, int n) {
        if(n==0 || x==1.0){return 1.0;}
        if(x==-1.0){return n%2==0?1.0:-1.0;}
        if(n < 0){return 1.0/pow(x,-n);}
        int len = (int)Math.floor(Math.log(n)/Math.log(2));
        double rlst = 1.0;
        double[] carry = new double[len+1];
        for(int i = 0;i <= len;i++)
            carry[i] = i==0?x:Math.pow(carry[i-1],2);
        while(n!=0){
            int num = n/(int)Math.pow(2,len);
            rlst *= num==0?1.0:carry[len]*num;
            n %= (int)Math.pow(2,len--);
        }
        return rlst;
    }
}


Improved Way:x^7 = x^4 + x^2 + x^1的这个信息，其实就藏在7这个数的比特位中，7 = 0x0111,
只需要用比特运算就可以提取对应位了。并且，因为这样不需要从高往低乘，可以从低往高乘，那么低位的乘因子乘过以后就不会再用了，不需要一直存着，可以通过与比特位递进同步平方乘因子，达到O(1)space的效果。

这种方法也太牛了，居然只用O(1) run time 和O(1) space。

public class Solution {
    public double pow(double x, int n) {
        if(n < 0){return 1.0/(n==Integer.MIN_VALUE?x*pow(x,-(n+1)):pow(x,-n));}
        double rlst = 1.0;
        while(n!=0){
            if((n & 1) == 1){
                rlst*= x;
            }
            x*=x;
            n = n >> 1;
        }
        return rlst;
    }
}