Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.

Naive Way: Return the square root of an integer as an integer. I use binary search. First I need to find maximum possible square root, which is (int)Math.sqrt(Integer.MAX_VALUE). And when it happens sqrt(x) is this value, can't use i^2 <= x <(i+1)^2 to end the loop since (i+1)^2 will overflow. List this case separately.

 public class Solution {  
   static final int MAX_SQRT = (int)Math.sqrt(Integer.MAX_VALUE);  
   public int sqrt(int x) {  
     int high = MAX_SQRT, low = 0;  
     while(low <= high){  
       int middle = (high+low)/2;  
       if(middle*middle <= x && middle == MAX_SQRT) return middle;  
       if(middle*middle <= x && (middle+1)*(middle+1) > x) return middle;  
       if(middle*middle > x)  
         high = middle-1;  
       else  
         low = middle+1;  
     }  
     return low;  
   }  
 }  

Improved Way: There is a mathematical method Newton's Method. I can't understand what is stated in the link. There are too mathematical. I understand from other one's algorithm newtons-iterative-method-in-c . In the answer of that question. Newton's method was explained.

Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.

Naive Way: I think a sorted array is highly related to a binary search approach, especially finding an element. Use the picture I draw in search-in-rotated-sorted-array-ii . There are two situations when doing a binary search approach. It the first scene, when b2 > b1 and e1 > e2, the minimum lies in the second half. It the second scene, whose condition is the opposite, minimum lies in the first half. And what we are looking for is the position where num[i-1] > num[i]. If such position doesn't found, we can return the first element.

 public class Solution {  
   public int findMin(int[] num) {  
     return binarySearch(num, 0, num.length-1);  
   }  
   private int binarySearch(int[] num, int begin, int end){  
     while(begin < end){  
       int middle = (begin+end)/2;  
       if(num[middle] > num[middle+1]) return num[middle+1];  
       if(num[middle] > num[end]) begin = middle+1;  
       else end = middle;  
     }  
     return num[begin];  
   }  
 }  

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Naive Way:时间复杂度的要求决定了只能是merge sort, quick sort 或者用 heap。空间复杂度先排除heap。Quick sort不熟，先试merge sort。merge sort能否只用O(1) space？好像是可以的。

写了N久终于写完了。用一快一慢两个指针引领要被merge的部分，merge函数需要在末尾清零（null），主函数需要用一个指针标记剩下的部分，以便前面部分merge完以后接上。

 /**  
  * Definition for singly-linked list.  
  * class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode sortList(ListNode head) {  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake, fast = fake, slow = fake;  
     fake.next = head;  
     // get the length of list  
     int length = 0;  
     while(cur.next!=null){  
       length++;  
       cur = cur.next;  
     }  
     for(int step = 1;step < length;step*=2){  
       cur = fake;  
       while(cur.next!=null){  
         slow = cur.next;  
         fast = cur.next;  
         int i = 0;  
         // find correct merge starting position  
         while(fast.next!=null && i < step){fast = fast.next; i++;}  
         if(i!=step) break;  
         ListNode temp = fast;  
         i = 0;  
         while(temp!=null && i < step){temp = temp.next; i++;}  
         // merge two lists  
         cur.next = merge(slow, fast, step);  
         // connect with remaining nodes  
         i = 0;  
         while(i < 2*step && cur.next!=null){cur = cur.next;i++;}  
         cur.next = temp;  
       }  
     }  
     return fake.next;  
   }  
   private ListNode merge(ListNode a, ListNode b, int len){  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake;  
     int i = 0,j = 0;  
     while(i < len && j < len && a!=null && b!=null){  
       if(a.val < b.val){  
         cur.next = a;  
         a = a.next;  
         i++;  
       }else{  
         cur.next = b;  
         b = b.next;  
         j++;  
       }  
       cur = cur.next;  
     }  
     while(i < len && a!=null){  
       cur.next = a;  
       a = a.next;  
       i++;  
       cur = cur.next;  
     }  
     while(j < len && b!=null){  
       cur.next = b;  
       b = b.next;  
       j++;  
       cur = cur.next;  
     }  
     cur.next = null;  
     return fake.next;  
   }  
 }  

Improved Way:看到Discuss里很多人都是 大的merge  call 小的merge，那样就会造成一个stack的空间使用，就不是O(1)的了，要实现O(1)，必须从小的往大的写，这样才不会同时进行多个merge。

一些提升的地方：

有一个人用Bit 运算移位来实现step*2，这样挺好的。

有一个人将获取slow, 和fast的位置写成单独的函数，这样主函数就会清晰很多。

最重要的问题：Quick Sort 是否可以写成O(1)的关于链表的。从算法的流程上讲是可以的，先对整个list 进行左右交换，然后对前一半和后一半分别进行左右交换，这样下来应该可以不适用额外空间。

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提高效率。记住要补上！

Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

 

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.


Naive Way: 可以用一个recursive的方法，不断比较sum(root.left), sum(root.right)和root.val，在回溯过程中遇到正数也要和最大值比较。

 

Recursive的方法，算法复杂度O(n), space O(n)。这里因为Integer.MIN_VALUE+负数 =正数,所以不能直接写return max(root.val, root.val+right, root.val+left)，必须确认left.val和right.val都是正数。

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        int rootSum = pSum(root);
        return Math.max(rootSum,max);
    }
    
    private int pSum(TreeNode root) {
        // base case
        if(root==null){return Integer.MIN_VALUE;}
        // recursive
        int left = pSum(root.left);
        int right = pSum(root.right);
        max = Math.max(left,max);
        max = Math.max(right,max);
        if(left < 0 && right < 0)
            return root.val;
        else if(left < 0)
            return root.val+right;
        else if(right < 0)
            return root.val+left;
        else
            max = Math.max(root.val+left+right,max);
        return root.val + Math.max(right,left);
    }
    
}

下面是iterative的方法。使用了level-order traversal，相当于BFS，正着一遍将所有节点放入对应的层中，然后倒着一遍由下往上求一遍。还可以用DFS遍历一遍然后全存入一个堆栈中，遍历完后再逐个推出堆栈，因为其顺序也是倒着的（相当于拓扑排序的顺序）。

public class Solution {
    public int maxPathSum(TreeNode root) {
        // level-order traversal
        List<List<TreeNode>> gross = new ArrayList<List<TreeNode>>();
        int max = Integer.MIN_VALUE;
        // initialize
        List<TreeNode> first_layer = new ArrayList<TreeNode>();
        if(root!=null) first_layer.add(root);
        gross.add(first_layer);
        while(gross.get(gross.size()-1).size() > 0){
            List<TreeNode> new_layer = new ArrayList<TreeNode>();
            List<TreeNode> pre_layer = gross.get(gross.size()-1);
            for(int i = 0;i < pre_layer.size();i++){
                TreeNode node = pre_layer.get(i);
                if(node.left!=null) new_layer.add(node.left);
                if(node.right!=null) new_layer.add(node.right);
            }
            gross.add(new_layer);
        }
        
        // back trace
        int index = gross.size();
        while(--index >= 0){
            List<TreeNode> last_layer = gross.get(index);
            for(int i = 0;i < last_layer.size();i++){
                TreeNode node = last_layer.get(i);
                if(node.right!=null && node.left==null){
                    node.val += node.right.val>0?node.right.val:0;
                }else if(node.left!=null && node.right==null){
                    node.val += node.left.val>0?node.left.val:0;
                }else if(node.left!=null && node.right!=null){
                    max = Math.max(max, node.val+node.left.val+node.right.val);
                    node.val += Math.max(Math.max(node.left.val,node.right.val),0);
                }
                max = Math.max(max,node.val);
            }
        }
        
        return max;
    }
}

Search for a Range

Search for a Range

 

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Naive Way:因为是排好序的，所以只需要通过二分搜索（假如要搜索8) [...7,8...] 和[...8,9...]这样的两个位置。

算法复杂度是O(logn)

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] range = new int[2];
        if(A.length==0){return range;}
        range[0] = A[0]==target?0:binarySearch(A, target, true);
        range[1] = A[A.length-1]==target?A.length-1:binarySearch(A, target, false);
        return range;
    }
    
    private int binarySearch(int[] A, int target, boolean downOrUp){
        int begin = 0, end = A.length-1;
        int middle = 0;
        while(begin < end){
            middle = (begin+end)/2;
            // find lower bound
            if(A[middle] < target && A[middle+1] == target && downOrUp)
                return middle+1;
            if(A[middle+1] < target && downOrUp)
                begin = middle+1;
            if(A[middle+1] >= target && downOrUp)
                end = middle;
            // find upper bound
            if(A[middle] == target && A[middle+1] > target && !downOrUp)
                return middle;
            if(A[middle] <= target && !downOrUp)
                begin = middle+1;
            if(A[middle] > target && !downOrUp)
                end = middle;
        }
        return -1;
    }
}

 

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

Search in Rotated Sorted Array II

Search in Rotated Sorted Array II

 

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.

Naive Way: 在原来的基础上增加了数字可重复的条件。这一条件带来什么影响，会不会影响算法复杂度。这种时候我发现一个比较高明的方法是考虑最坏的情况。

这是是 Search in Rotated Sorted Array I 的代码。算法复杂度是O(logn)。

public class Solution {
    public int search(int[] A, int target) {
        return search(A,0,A.length-1,target);
    }
    
    private int search(int[] A, int begin, int end, int target){
        if(begin > end)
            return -1;
        int middle = (begin+end)/2;
        if(A[middle]==target)
            return middle;
        if(A[middle] > A[end]){
            if(A[middle] > target && A[begin] <= target)
                return search(A, begin, middle-1, target);
            else
                return search(A, middle+1, end, target);
        }else{
            if(A[middle] < target && A[end] >= target)
                return search(A, middle+1, end, target);
            else
                return search(A, begin, middle-1, target);
        }
    }
}

如果有重复，最坏的情况是全是同一个数，比如

[1  1  1  1  1]

这样只有1可以做target，找的时候第一下就返回了，不能说明情况。那么退一步只有一个数是不重复的

[1  1  1  2  1  1]

这时有一个重大发现就是这个2摆在哪里都可以，都是rotated array。如果2摆在最前面

[2  1  1  1  1  1]

经过原来的方法会二分的执行算法直到找到2在Index=0的位置。如果2摆在最后，可想而知也会符合O(logn)的时间的。最后把2摆在中间。

[1  1  1  2  1  1]

问题来了，会出现b1 == e1 == b2 == e2的情况。对于这种情况，是无法正确找出2的半区的，因为2既有可能在前半部分，也有可能在后半部分。

这是否说明第一次的算法在这里不能用了呢。仔细走一遍第一次的算法，到了选择分区时：

if(A[middle] > A[end]){
            if(A[middle] > target && A[begin] <= target)
                // 搜索前半部分
            else
                //搜索后半部分
        }else{
            if(A[middle] < target && A[end] >= target)
                //搜索后半部分
            else
                //搜索前半部分
        }

第一个选择条件A[middle] > A[end]不成立，第二个选择条件A[middle] < target && A[end] >= target也不成立，就会自动进入搜索前半部分。这时会想如果能去除一头一尾的重复部分呢？
这样原数组就会变成[1 2 1]，此时过一遍算法发现是可以正确找到2的。那么一个假设诞生了：每次都先去除一头一尾的重复部分，再运行算法是否就可以了呢? 经过测试是可以的，并且因为去除一头一尾的意义其实是打破b1==e1==b2==e2的平衡性，任意去除尾部或者头部都可以打破这种平衡，使数组重心改变，一旦数组重心改变，原来的算法其实就是正确的找出下一个半区。

此时算法复杂度变为O(n)。

public class Solution {
    public boolean search(int[] A, int target) {
        return search(A,0,A.length-1,target);
    }
    
    private boolean search(int[] A, int begin, int end, int target){
        while(begin+1 < end){
            if(A[begin+1]!=A[begin])
                break;
            begin++;
        }
        if(begin > end)
            return false;
        int middle = (begin+end)/2;
        if(A[middle]==target)
            return true;
        if(A[middle] > A[end]){
            if(A[middle] > target && A[begin] <= target)
                return search(A, begin, middle-1, target);
            else
                return search(A, middle+1, end, target);
        }else{
            if(A[middle] < target && A[end] >= target)
                return search(A, middle+1, end, target);
            else
                return search(A, begin, middle-1, target);
        }
    } 
}

总结一下，就是Binary search这种算法的核心思想是利用O(1)的时间发现左右半区的不平衡性，从而发现决定focus on哪一个半区，所以一旦有可能出现完全平衡的情况，binary search就无法正确运行，此时可能是目标情况，也可能是边缘情况，创造新的不平衡性可使算法运行下去。

类似binary search的题目还有Search-in-rotated-sorted-array, Search-insert-position

Search Insert Position

Search Insert Position

 

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Naive Way: 一次遍历直到大于等于target。好傻的方法，我第一次就是这么写的。

    // O(n)
    public int searchInsert(int[] A, int target) {
        for(int i = 0;i < A.length;i++){
            if(A[i] == target){return i;}
            if(A[i] > target){return i;}
        }
        return A.length;
    }

Improved Way: 作为一个程序员看到这样的题没有想到binary search真是一件很忧伤的事情。第二次做法是改了一下binary search

// O(logn)
    public int searchInsert(int[] A, int target) {
        if(A.length==0){return 0;}
        int begin = 0, end = A.length-1;
        int middle = 0;
        if(target <= A[begin]){return 0;}
        if(target >= A[end]){return end+1;}
        while(begin < end){
            middle = (begin+end)/2;
            if(A[middle]==target)
                return middle;
            if(A[middle] < target && A[middle+1] >= target)
                return middle+1;
            if(A[middle] > target)
                end = middle;
            if(A[middle+1] < target)
                begin = middle+1;
        }
        return 0;
    }

类似要用binary search的思想的还有Remove-duplicates-from-sorted-array。

 

Search in Rotated Sorted Array

Search in Rotated Sorted Array

 

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

Naive Way: 这是我算法课期中考试的一道原题，日，当时我没做出来。在一个sorted array里查找Binary search是O(logn)， 那么它如果rotated了一下还能否O(logn)呢。（关于binary search做法的题目，这章文章最下面有链接。）画一张图就很清楚了，有以下两种情况：

示例图

1.  当处于第一种情况时， target 介于[b1,e1）之间，对前半部分进行search, target <= e2 和 target >= b2 ，对后半分布进行search. 注意到e1, b2是连着的，e2,b1也是连着的。
2. 当处于第二种情况时， target介于（b2, e2]之间， 对后半部分search，否则search 前半部分。

      如何区分这两种情况，可以比较e1和e2，也可以比较b1和b2。


public class Solution {
    public int search(int[] A, int target) {
        return search(A,0,A.length-1,target);
    }
    
    private int search(int[] A, int begin, int end, int target){
        if(begin > end)
            return -1;
        int middle = (begin+end)/2;
        if(A[middle]==target)
            return middle;
        if(A[middle] > A[end]){
            if(A[middle] > target && A[begin] <= target)
                return search(A, begin, middle-1, target);
            else
                return search(A, middle+1, end, target);
        }else{
            if(A[middle] < target && A[end] >= target)
                return search(A, middle+1, end, target);
            else
                return search(A, begin, middle-1, target);
        }
    }
}

关于binary search的题目还有Search-in-rotated-sorted-array-ii, Search-insert-position