Leetcode/F家 --67.Add Binary (String)

67.Add Binary(String)

• Difficulty: Easy

https://leetcode.com/problems/add-binary/

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

思路: String相加的解法，如进位（inc =1），不然s设回0，sb加的值要%2, i j condition
注意点： numA = charA -'0' （char转成int）
关键字： char to int, StringBuilder, mod

public String addBinary(String a, String b) {
        int i = a.length() - 1, j = b.length() - 1;
        StringBuilder res = new StringBuilder();
        int inc = 0;
        while(i >= 0 || j >= 0){
            int sum = inc;
            inc = 0;//set back inc
            if(i >= 0)sum += a.charAt(i--) - '0';
            if(j >= 0)sum += b.charAt(j--) - '0';
            if(sum >= 2)inc = 1;
            res.append(sum%2);//only have 3 2 1 0
        }
        if(inc == 1)res.append(inc);
        return res.reverse().toString();
    }

Leetcode/F家/G家 -- Power of Two

Power of Two
https://leetcode.com/problems/power-of-two/

解法1. bit manipulation 
8 (1000)           
7 (0111)     =>  8 & 7 = 0
6 (0110)           7 & 6 = (0110)=6
所以如果是2的n次方，一定会是1000....的格式，和n-1 &操作，应得0

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

解法2： 数学做法

public class Solution {
    public boolean isPowerOfTwo(int n) {
       long val = 1;
       while(val<n){
           val *=2;
       }
       if(val ==(long)n){
           return true;
       }else{
           return false;
       }
    }
}

算法小结--Bit Manipulation解法

0. 常用代码
1.Integer.bitCount(n)
2.String运算 ： sum%2（得到不是0就是1）carry = sum/2 来加新的bit 例子
3.2^h ==> (int)Math.pow(2,h) or (2>>(h-1))or(1>>h)//shift is after '-','+'

1. 基本操作
http://stackoverflow.com/questions/6385792/what-does-a-bitwise-shift-left-or-right-do-and-what-is-it-used-for
不和++一样，需要assign c = c>>1
1&0 =0
1 | 0 = 1
XOR // find the different bit
1^0 = 1; 1^1 = 0; 0^0= 0; x^x = 0; x^0=x
shift (for signed)
2>>1 = 1 ; 1>>2 =0
(0010)
 2<<2 = 8
//preserve the first bit

1100 1100 >> 1
1110 0110 

 unsigned operation >>>(convert non number to number)
//not perserve the first bit

1100 1100 >>> 1
0110 0110 

negative number 2's compliement

1111 is -1, in two's complement

1110 is -2, which is ~2 + 1, ~0010 => 1101, 1101 + 1 = 1110 => 2

1101 is -3, which is ~3 + 1

so if you want to get a negative number, you can simply do ~x + 1

~Not
~2(0010) is  -3(1101)

---

Ex：
» 461. Hamming Distance F家
# of different bits in x,y
 return Integer.bitCount(x^y);

1.number of 1 bits
https://leetcode.com/problems/number-of-1-bits/

     while(n>0){
            ones += (n&1);
            n = n>>1;
        }

2.Find the difference
https://leetcode.com/problems/find-the-difference/

方法1： 顺序打乱，但是char的ascill总和不变 ，相减得到新加的letter
方法2： 建一个char c=0；两次loop 不停xor当前letter of string,return c

3. Add sum
https://leetcode.com/problems/sum-of-two-integers/
https://discuss.leetcode.com/topic/49771/java-simple-easy-understand-solution-with-explanation/2

while(b!=0) {
    int carry = a &b; //1.find the carry要进位
    a = a^b; //2. find different bit
    b  = carry<<1; // 3. left shift
}

//get subtract a-b
while( b ! = 0){
    int borrow =  (~a)&b;
    a = a^b;
    b = borrow<<1;
}

4.power of two （F，G家）
详解

http://rainykat.blogspot.com/2016/12/leetcodefg-power-of-two.html

Leetcode/F家,LinkedIn-69.sqrt(x) 和 367.valid perfect square(Binary Search)

69.Sqrt(x) - Binary Search

• Difficulty: Medium

https://leetcode.com/problems/sqrtx/
Implement int sqrt(int x).

Compute and return the square root of x.

sqrt(9)=3

Company： Bloomberg Apple Facebook
思路：用binary search找中间满足条件的数，满足条件的情况特别注意 ，总会在loop里return
            - always use x/mid to compare
            - return case: x/mid >= mid && x/(mid+1) < (mid+1)//eg: 5/2 >2; 5/3<3
Complexity: Time O(logN) Space O(1)

public class Solution {
    public int mySqrt(int x) {
        if(x==0){ return 0;}
        if(x==1){ return 1;}
        int start = 1,end = x;
        while(start<=end){
            int mid = start + (end-start)/2;
            if (mid <= x / mid && (mid + 1) > x / (mid + 1))// 特别注意满足条件，不止是等于
       return mid; 
      else if (x / mid < mid)//mid太大
       end = mid-1;
      else
       start = mid + 1;
        }
        return start;//什么都行。。。。
    }

}

延展题
367.Valid Perfect Square LinkedIn

• Difficulty: Medium

 https://leetcode.com/problems/valid-perfect-square/ 
1.做法1： 1+3+5+7+...
2.bitwise
3.double cast

public class Solution {
    public boolean isPerfectSquare(int num) {
        if(num==0||num==1){ return true;}
        int start = 1, end =num;
        while(start<=end){
            int mid = start+(end-start)/2;
            if(mid<=num/mid&&(mid+1)>num/(mid+1)){
                if((double)num/mid - mid==0.0 ){//和上题一样，加多一个判定条件
                    return true;
                }
                return false;
            }else if(mid>num/mid){
                end = mid - 1;
            }else{
                start = mid+1;
            }
        }
        return false;
    }
}