Find the row with Max 1s

From http://www.careercup.com/question?id=5700588635422720

 A 2-D array of 1's and 0's is given. Find the row with max 1's. The array is sorted row wise (all 0's in a row are followed by all 1's).





Naive Thinking: A first I just came up with all kinds of O(nm) solutions. For example scan column by column to find the first 1, or scan row by row and note down the earliest 1. Pretty bad, though, because O(n+m) solution did exists and there exists solution better than that.

An O(m+n) algorithm is kinda greedy. Keep two pointers, one for row(i), one for column(j). Start from the very end of first row, each time encounter a 1, step forward(j--), each time encounter a 0, it means current row will have no chance have more 1 than m-j, thus go to next row, starting from j. That saves us the time from repeatedly scanning rows that are denied.

 public class Solution{   
   public static void main(String args[]){   
    Solution s = new Solution();   
    int[][] matrix = {{0,0,0,1,1},   
        {0,0,1,1,1},   
        {0,0,0,0,1},   
        {0,0,0,1,1}};   
    System.out.println(s.findRowWithMaxOnes(matrix));   
   }   
   public int findRowWithMaxOnes(int[][] array){   
    int n = array.length;   
    int m = n==0?0:array[0].length;   
    int i = 0, j = m-1;   
    int row = 0;   
    while(i < n && j >= 0){   
     if(array[i][j]==1){   
      row = i;   
      j--;   
     }else{   
      i++;   
     }   
    }   
    return row;   
   }   
  }    

Improved Way: As you see, since the question gives the condition each row is sorted. That leads to binary search thinking. We can do a binary search to find the first 1 of current row instead of stepping forward once. That brings the run time to O(m+log n)

 public int findRowWithMaxOnes(int[][] array){  
           int n = array.length;  
           int m = n==0?0:array[0].length;  
           int i = 0, j = m-1;  
           int row = 0;  
           while(i < n && j >= 0){  
                j = binarySearch(array[i], 0, j);  
                row = i;  
                i++;  
                while(i < n && array[i][j]==0) i++;  
           }  
           return row;  
      }  
      private int binarySearch(int[] arr, int begin, int end){  
           while(begin < end){  
                int middle = (begin+end)/2;  
                if(arr[middle] == 0 && arr[middle+1] == 1) return middle+1;  
                if(arr[middle] == 0) begin = middle+1;  
                else end = middle;  
           }  
           return begin;  
      }  

Finding all palindromes in String

Finding all palindromes in String.

Naive Thinking: Use the method described in  longest-palindromic-substring . There are covered ranges for each character. That's the result we want.

Time complexity O(n^2) (because to generate output, Hoops, that seems not great benefit using longest-palindrome's algorithm) 
Space O(n^2) (Also because of the output).

 import java.util.List;  
 import java.util.ArrayList;  
 import java.util.Set;  
 import java.util.HashSet;  
 public class Solution{  
   public static void main(String args[]){  
     Solution s = new Solution();  
     List<String> list = s.findAllPalindrome("abbbbabaaabab");  
     System.out.println(list);  
   }  
   public List<String> findAllPalindrome(String s){  
     List<String> list = new ArrayList<String>();  
     Set<String> set = new HashSet<String>();  
     String str = preProcess(s);  
     int f[] = new int[str.length()]; // coverage  
     int p = 0; // pivot  
     for(int i = 1;i < str.length();i++){  
       // check if position i is in pivot's coverage  
       if(p + f[p] > i){  
         if(2*p-i - f[2*p-i] > p-f[p])  
           f[i] = f[2*p-i];  
         else  
           f[i] = f[p] - (i-p);  
       }else{  
         f[i] = 0;  
       }  
       // extend if necessary  
       int j = 1;  
       while(i-f[i]-j >= 0 && i+f[i]+j < str.length() && str.charAt(i+f[i]+j)==str.charAt(i-f[i]-j)) j++;  
       f[i] += j-1;  
       // check if need to replace pivot  
       if(i+f[i] > p+f[p]) p = i;  
     }  
     // generate result  
     for(int i = 0;i < f.length;i++)  
       for(int j = 2;j <= f[i];j++)  
         set.add(s.substring((i-j)/2,(i+j+1)/2));  
     list.addAll(set);  
     return list;  
   }  
   private String preProcess(String s){  
     StringBuilder str = new StringBuilder();  
     for(int i = 0;i < s.length();i++){  
       str.append("#");  
       str.append(s.charAt(i));  
     }  
     str.append("#");  
     return str.toString();  
   }  
 }  

Arithmetic Slice

From http://codesays.com/2014/solution-to-count-arithmetic-sequence/
There is another question related to Arithmetic Sequence Longest Arithmetic Sequenece

Arithmetic Slice, is a slice of an array num[i..j] with at least size 3 and has num[i], num[i+1]...num[j-1],num[j] forming an arithmetic sequence.

For example:

Input:

[-1, 1, 3, 3, 3, 2, 1, 0]

Output:

5

Explanation:

There are five arithmetic sequences in the input:

[-1, 1, 3], [3, 3, 3], [3, 2, 1], [2, 1, 0], and [3, 2, 1, 0]

O(n) time complexity is required. Once the number of Arithmetic Slice is greater than 1000000000, return -1.

Naive Thinking:这道题一开始的例子给的好烦人，最好自己写一两个例子。
[1 2 3] has 1 arithmetic slice
[1 2 3 4] has 3 arithmetic slice since [1 2 3], [2 3 4] and [1 2 3 4].

 这样就很清楚了，如果再来个[1 2 3 4 5]， 那就有6个了，就是连续的差等数列会使得count 要算上每一个子集。遍历的时候追溯直到不能形成等差数列为止。

 算法复杂度是O(n)， space O(1)。

 public static final int limit = 1000000000;  
   public int getLAS(int[] A){  
     int count = 0;  
     // edge case  
     if(A.length <= 2) return count;  
     // main process  
     int i = 1;  
     while(i+1 < A.length){  
       int k = i+1;  
       // if its neighbor and itself form an AS, count++  
       if(2*A[i] == A[i-1]+A[k]){  
         count++;  
         if(count > limit) return -1;  
         // if two neighbors match, go through all the way until not match  
         while(k+1 < A.length && 2*A[k] == A[k-1]+A[k+1]){  
           k++;  
           count += (k-i);  
           if(count > limit) return -1;  
         }  
       }  
       // increment  
       i = k;  
     }  
     return count;  
   }  

Amplitude of Tree

From http://codesays.com/2014/solution-to-tree-amplitude/

In a binary tree T, a path P is a non-empty sequence of nodes of tree such that, each consecutive node in the sequence is a subtree of its preceding node. In the example tree, the sequences [9, 8, 2] and [5, 8, 12] are two paths, while [12, 8, 2] is not. The amplitude of path P is the maximum difference among values of nodes on path P. The amplitude of tree T is the maximum amplitude of all paths in T. When the tree is empty, it contains no path, and its amplitude is treated as 0.
For exmaple.

Input:

         5

       /   \

    8        9

   /  \     /  \ 

12   2  8   4

          /    /

        2    5

Output:

7

Explanation:

The paths [5, 8, 12] and [9, 8, 2] have the maximum amplitude 7.

Naive Thinking: 关键句是The amplitude of path P is the maximum difference among values of nodes on path P. 可以采用DFS，记录一条路径上的最大值和最小值，求差值，最后再总的求一个最大值。

算法复杂度是 O(n), space O(n)。 

也可以用一个全局变量去记录max, 那样就不需要最后再总的求一次最大值。 

 class TreeNode{  
   int val;  
   TreeNode left, right;  
   TreeNode(int x){  
     val = x;  
     left = null;  
     right = null;  
   }  
 }  
 public int amplitudeOfTree(TreeNode root){  
     if(root==null) return 0;  
     int max = 0;  
     List<Integer> maxs = new ArrayList<Integer>();  
     // use a List<Integer> to record min and max along a path  
     List<Integer> list = new ArrayList<Integer>();  
     list.add(root.val);  
     list.add(root.val);  
     dfs(root,list,maxs);  
     for(int i = 0;i < maxs.size();i++)  
       max = Math.max(maxs.get(i),max);  
     return max;  
   }  
   private void dfs(TreeNode root, List<Integer> cur, List<Integer> maxs){  
     if(root.left==null && root.right==null) maxs.add(cur.get(1)-cur.get(0));  
     if(root.left != null){  
       List<Integer> list = new ArrayList<Integer>(cur);  
       if(root.left.val < list.get(0)) list.set(0,root.left.val);  
       if(root.left.val > list.get(1)) list.set(1,root.left.val);  
       dfs(root.left, list, maxs);  
     }  
     if(root.right != null){  
       List<Integer> list = new ArrayList<Integer>(cur);  
       if(root.right.val < list.get(0)) list.set(0,root.right.val);  
       if(root.right.val > list.get(1)) list.set(1,root.right.val);  
       dfs(root.right, list, maxs);  
     }  
     return;  
   }   

Longest Arithmetic Sequenece

There is another question related to Arithmetic Sequence Arithmetic Slice

Given an array, return the number of longest possible arithmetic sequence
For example, [-1, 1, 3, 3, 3, 2, 1, 0}  return 5 because {-1, 0, 1, 2, 3} forms a arithmetic sequence. 

Naive Thinking: 先排序会给找等差序列带来极大的便利。还有就是重复的是差为0的等差数列。
假设从第一个数开始，之后每一个数都会与之形成一个差值，以该差值为步长，看之后的数是否出现在数组中，遍历过的数字对可以放入一个Set中防止重复遍历，并将时间复杂度降低至O(n^2)。

算法复杂度是O(n^2), space O(n^2)

 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.Map;  
 import java.util.HashMap;  
 import java.util.Set;  
 import java.util.HashSet;  
 import java.util.Arrays;  
 public class Solution{  
   public static void main(String args[]){  
     Solution s = new Solution();  
     int num[] = {1,1,1,3,4,5,6,7,9,11};  
     System.out.println(s.longestArithmeticSeq(num));  
   }  
   // O(n^2)  
   public int longestArithmeticSeq(int num[]){  
     int longest = 0;  
     Map<Integer,Integer> map = new HashMap<Integer, Integer>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     // sort the array  
     Arrays.sort(num);  
     // put num->freq into a map  
     for(int i = 0;i < num.length;i++){  
       if(!map.containsKey(num[i]))  
         map.put(num[i],1);  
       else  
         map.put(num[i],map.get(num[i])+1);  
       longest = Math.max(longest,map.get(num[i]));  
     }  
     // go through the array  
     for(int i = 0;i < num.length-longest+1;i++){  
       for(int j = i+1;j < num.length;j++){  
         int gap = num[j]-num[i];  
         if(gap==0) continue;  
         int cur = num[i];  
         while(map.containsKey(cur+gap)){  
           // use set to record the path  
           List<Integer> list = new ArrayList<Integer>();  
           list.add(cur);  
           cur += gap;  
           list.add(cur);  
           if(set.contains(list)) break;  
           set.add(list);  
         }  
         longest = Math.max(longest, (cur-num[i])/gap+1);  
       }  
       // early break  
       if(longest > num.length/2) break;  
     }  
     return longest;  
   }  
 }   

Improved Way: 上面的方法感觉是比较麻烦而且容易出错，答案是一个DP。想都没想过这道题用DP。
而且这个DP很非常规。在http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/有详细解释。基本逻辑为：
opt[i][j] //  the length of arithmetic sequence by setting num[i] and num[j] as first two elements
// base case
opt[i][j] = 2  for all i and j
// iteration
opt[i][j] = 
if(num[i] + num[k|k>j] = 2*num[j]) opt[j][k]+1

算法复杂度为O(n^2), space O(n^2), 因为定义的是以num[i] 和 num[j] 开头的数列，所以在找的时候要从后往前扫，后面的部分先更新，前面的部分才能囊括后面的信息。

 public int longestArithmeticSeq(int num[]){  
     int longest = 0;  
     int opt[][] = new int[num.length][num.length];  
     Arrays.sort(num);  
     // base case  
     for(int i = 0;i < num.length-1;i++)  
       for(int j = i;j < num.length;j++)  
          opt[i][j] = 2;  
     // iteration  
     for(int j = num.length;j >= 0;j--){  
       int i = j-1, k = j+1;  
       while(i >= 0 && k < num.length){  
         if(num[i] + num[k] < 2*num[j])  
           k++;  
         else if (num[i] + num[k] > 2*num[j])  
           i--;  
         else{  
           opt[i][j] = opt[j][k] + 1;  
           longest = Math.max(longest, opt[i][j]);  
           i--;  
           k++;  
         }  
       }  
     }    
     return longest;  
   }  

还有人在Discuss里提出一个以最大差距为一个参数的DP。基本逻辑为
opt[i][j] // 从num[0..i]的以 j 为步长的等差数列的长度。
// base case
opt[0][j] = 1
// iteration
opt[i][j] = if(num[i]-num[t] == j) opt[t][j] + 1

实际写得时候不用在Iteration部分遍历所有j，因为只需要求出num[i]-num[t]能产生的所有j就行了。

算法复杂度是 O(max(n^2, num[max]-num[min])), space 是 O(n * num[max]-num[min]))。
由于整数最大差值达到2^32，有可能空间不足以创建这个二维数组。所以这个算法有很大的漏洞。但是这个想法是对的。如果空间不足创建二维数组，可以将步长用map来记录，只记录num中可以产生的步长，将步长map到一个list上，list里存所有以该步长为间隔的两个数的集合。这样还是可以使算法复杂度达到O(n^2)， space O(n^2)的。

 public int longestArithmeticSeq(int num[]){  
     if(num.length < 2) return num.length;  
     Arrays.sort(num);  
     int longest = 2;  
     int m = num[num.length-1] - num[0];  
     // opt is defined "the length of longest arithmetix seq in num[0..i] using j as step"  
     int opt[][] = new int[num.length][m+1];  
     // base case  
     for(int i = 0;i <= m;i++) opt[0][i] = 1;  
     // iteration  
     for(int i = 0;i < num.length-1;i++){  
       for(int j = i+1;j < num.length;j++){  
         opt[j][num[j]-num[i]] = opt[i][num[j]-num[i]]+1;  
         longest = Math.max(longest, opt[j][num[j]-num[i]]);  
       }  
     }  
     return longest;  
   }   

Sliding Window Sum

Given a list of integers and a window size, return a new list of integers where each integer is the sum of all integers in the kth window of the input list. The kth window of the input list is the integers from index k to index k + window size - 1(inclusive).

For example, [1, 2, 3, 4] and window size 3 should return [6,9].

Naive Thinking: 用一个var标记当前和，每次前进一步都减头部加尾部。

算法复杂度是O(n)。

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int num[] = {1,2,4,6};
        int sums[] = s.slidingWindowSum(num,4);
        for(int i = 0;i < sums.length;i++)
            System.out.print(sums[i] + " ");
        System.out.println();
    }

    public int[] slidingWindowSum(int num[], int window_size){
        // initialize result
        int sums[] = new int[Math.max(num.length-window_size+1,1)];
        // check if window_size is greater than num[] size, return -1
        if(window_size > num.length) sums[0] = -1;
        // current sum, function as a window
        int cur_sum = 0;
        // go through num[]
        for(int i = 0, j = 0;i < num.length;i++){
            // each time a new number come, add to window
            cur_sum += num[i];
            if(i >= window_size-1){
                // if not the start window, delete the first one from window
                if(i-window_size >= 0) cur_sum -= num[i-window_size];
                // set window(cur_sum) to output
                sums[j++] = cur_sum;
            }
        }
        return sums;
    }
}

Four Integers

有4个正数，A,B,C,D。改变他们的位置使得他们两两之间的距离之和最大。

Naive Way ：先写一个例子，1 3 4 6。如果采用一种greedy 的方法，第一个固定，第二个挑距离最大的6，第三个挑4，最后是3。这样下来 5 + 3 + 1 = 8。很明显，3和4放在一起距离太小了，把他们分开放最好。于是有了3 1 6 4，这样还是不如 4 1 6 3大。因为最大的和最小的会创造最大距离，而且他们离中间的两个都可以再差一个数，这样将一头一尾放在中间，然后中间两个分立两边，可造成最大距离和。

 import java.util.Arrays;

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int num[] = s.solution(1,3,4,6);
        for(int i = 0;i < num.length;i++)
            System.out.println(num[i]);
    }

    public int[] solution(int A, int B, int C, int D){
        int num[] = {A,B,C,D};
        Arrays.sort(num);
        swap(num, 0, 2);
        swap(num, 1, 3);
        swap(num, 0, 3);
        return num;
    }

    private void swap(int[] num, int x, int y){
        int temp = num[x];
        num[x] = num[y];
        num[y] = temp;
    }
}

Find Loops In Linkedlist

Find loops in LinkedList

Naive Thinking:用一快一慢两个指针找出是否有loop。着相当于是找圈的起点的简化版。 加强版的见Intersection of Two Linked Lists


算法复杂度O(n)。

class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
        next = null;
    }
}

public class Solution{

    public static void main(String args[]){
        ListNode l1 = new ListNode(0);
        ListNode l2 = new ListNode(1);
        ListNode l3 = new ListNode(2);
        l1.next = l2;
        l2.next = l3;
        l3.next = l2;
        Solution s = new Solution();
        System.out.println(s.hasLoop(l1));
    }

    public boolean hasLoop(ListNode head){
        ListNode slow = head, fast = slow;
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
            if(fast==null) break;
            fast = fast.next;
            if(slow==fast) return true;
        }
        return false;
    }
}
 

Check Rotation Using one isSubstring Call

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 suing only one call to isSubstring (e.g, "waterbottle" is a rotation of "erbottlewat"). All Strings are assumed lowercase.

Naive Thinking:限制条件是只能用一次 isSubstring()。假设没有这个条件，先考虑这道题怎么做。假设单词A 和单词B，单词A从某个字母开始将和单词B完全匹配，知道单词A结尾，剩下的部分正好可以用 isSubstring来判断是否 单词B的后面的部分，这里同时还引出了一个漏洞就是必须确保单词A和单词B具有同样的词频。

算法复杂度是O(n^2)

public boolean isRotation(String s1, String s2){
        // check same character set
        int freq[] = new int[26];
        for(int i = 0;i < s1.length();i++)
            freq[(int)(s1.charAt(i)-'a')]++;
        for(int i = 0;i < s2.length();i++)
            freq[(int)(s2.charAt(i)-'a')]--;
        for(int i = 0;i < freq.length;i++)
            if(freq[i]!=0) return false;
        // check rotation
        for(int i = 0;i < s1.length();i++)
            if(s1.charAt(i)==s2.charAt(0))
                if(isEnd(s1, i, s2)) return isSubstring(s1.substring(0,i),s2);
        return false;
    }

    private boolean isEnd(String s1, int index, String s2){
        for(int i = index,j = 0;i < s1.length();i++,j++)
            if(s1.charAt(i)!=s2.charAt(j)) return false;
        return true;
    }

    public boolean isSubstring(String s1, String s2){
        return s2.indexOf(s1) >= 0;
    }

Improved Way: 这道题是Cracking the Coding Interview 里String/Array那一章的最后一道题。它的做法我想都没想过，特别巧妙。

这里直接照搬它的解释：
s1 = waterbottle; Let x = wat, y = erbottle
s1 = xy;
s2 = erbottlewat;
s2 = yx;

s1s1 = xyxy;
s2 = yx;
s2 will always be a substring of s1s1.

算法复杂度是O(n)。

public boolean isRotation(String s1, String s2){
        if(s1.length() == s2.length() && s1.length() > 0){
            String s1s1 = s1 + s1;
            return isSubstring(s2, s1s1);
        }
        return false;
    }

Find First Non Repeating Character in String

From http://www.geeksforgeeks.org/given-a-string-find-its-first-non-repeating-character/
Given a string, find the first non-repeating character in it. For example, if the input string is “GeeksforGeeks”, then output should be ‘f’ and if input string is “GeeksQuiz”, then output should be ‘G’.

Naive Thinking: 用一个map去映射字母和出现次数？最后再遍历一遍，第一个出现次数为1的就是输出。可不可以一次遍历？好像可以，用一个指针指向目前最前出现的次数为1的位置。

public char firstNonRepeatingChar(String s){
        int index = 0;
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i = 0;i < s.length();i++){
            if(!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i), 1);
            }else{
                map.put(s.charAt(i), map.get(s.charAt(i))+1);
                while(index < s.length() && map.containsKey(s.charAt(index)) && map.get(s.charAt(index)) > 1) index++;
            }
        }
        return index<s.length()?s.charAt(index):'0';
    }

Lowest Common Ancestor in a Binary Search Tree

From  http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/
Given values of two nodes in a Binary Search Tree,  find the Lowest Common Ancestor (LCA). You may assume that both the values exist in the tree.

The function prototype should be as follows:

 struct node *lca(node* root, int n1, int n2)
 n1 and n2 are two given values in the tree with given root.

For example, consider the BST in diagram, LCA of 10 and 14 is 12 and LCA of 8 and 14 is 8.


Naive Thinking: Binary Search Tree 的题目一定要用上 左 < 中 < 右 这个性质。可以发现如果当前点是同时大于n1, n2 的，他们的LCA一定在当前节点的左子树，反之则在右子树。如果当前点在二者之间呢，说明这就是他们的LCA！



这是recursive的做法。

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
        left = null;
        right = null;
    }
}

public TreeNode LCAinBinarySearchTree(TreeNode root, int n1, int n2){
        return traversal(root, n1, n2);
    }

    private TreeNode traversal(TreeNode root, int n1, int n2){
        if(root==null) return root;
        if(root.val >= n1 && root.val <= n2) return root;
        if(root.val > n1 && root.val > n2) return traversal(root.left,n1,n2);
        else return traversal(root.right,n1,n2);
    }


这是iterative的做法，用queue也可以，应该直接使用root作指针。这里好傻。

public TreeNode LCAinBinarySearchTree(TreeNode root, int n1, int n2){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root==null) return root;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.val >= n1 && node.val <= n2) return node;
            if(node.val > n1 && node.val > n2 && node.left!=null) stack.push(node.left);
            else if(node.right!=null) stack.push(node.right);
        }
        return null;
    }

这是正确的做法。

public TreeNode LCAinBinarySearchTree(TreeNode root, int n1, int n2){
        if(root==null) return root;
        while(root!=null){
            if(root.val >= n1 && root.val <= n2) return root;
            if(root.val > n1 && root.val > n2) root = root.left;
            else root = root.right;
        }
        return null;
    }


Improved Way: 如果这两个值有可能不在BST里呢？应当在找到LCA的时候继续遍历下去找到两个值。

public TreeNode LCAinBinarySearchTree(TreeNode root, int n1, int n2){
        if(root==null) return root;
        while(root!=null){
            if(root.val >= n1 && root.val <= n2 && findNode(root,n1) && findNode(root, n2)) return root;
            if(root.val > n1 && root.val > n2) root = root.left;
            else root = root.right;
        }
        return root;
    }

    // improved version: make sure existence of n1 and n2
    private boolean findNode(TreeNode root, int n){
        while(root!=null){
            if(root.val == n) return true;
            if(root.val > n) root = root.left;
            else root = root.right;
        }
        return false;
    }

Remove Duplicates from an Unsorted Array

remove duplicates from an unsorted array, return its new length. It doesn't matter what's left beyond the length.

Naive Thinking: 因为是unsorted， 重复的数可能是分开的，不能用两个指针一快一慢进行了。需要用一个set去存已遍历过的。这样是O(n) run time, O(n) space。

 import java.util.Set;
import java.util.HashSet;

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int num[] = {1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3};
        for(int i = 0;i < s.removeDuplicates(num);i++)
            System.out.print(num[i] + " ");
        System.out.println();
    }

    public int removeDuplicates(int num[]){
        Set<Integer> set = new HashSet<Integer>();
        int j = 0;
        for(int i = 0;i < num.length;i++)
            if(!set.contains(num[i])){
                set.add(num[i]);
                num[j++] = num[i];
            }
        return j;
    }
}

Swap Two Numbers Without Temp

How to swap two numbers without a third variable?

I just collected two ways:

1. use bit operation:

a = a ^ b;
b = a ^ b;
a = a ^ b;

to illustrate:
b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a
a = a ^ b ^ (a ^ b ^ b) = a ^ b ^ a = a ^ a ^ b = 0 ^ b = b;

2. use -/+

a = a + b;
b = a - b;
a = a - b;

To illustrate:
b = a+b-b = a;
a = a+b-(a+b-b)=b;

Job Schedule

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum

Naive Thinking:  怎么看怎么像DP，还是经典的那种。
基本逻辑为：
opt[i] // maximum within time [0,i] without overlapping jobs
// base case
opt[0] = 0
// iteration
opt[i] = max(opt[t] + cost of job[k] | where 0<=t<i , job[k]has start time >t, end time<=i)

但是实际做才发现，每次更新opt[i]都要遍历一遍所有job，这很不好，因为即使将job排序也不能有效减少算法复杂度O(n^3)，所以想到了这题跟 maximum non-overlapping intervals 很像。可能可以用Greedy。用Greedy先写一个例子

[  1  ]  [   3     ]
    [    5    ]

如果greedy是优先选start time 小的，这个例子就会通不过。

如果是优先选cost高的，以下这个例子又会不通过。

[  3  ]  [   3     ]
    [    5    ]


那么看来greedy是不可行的，还是老老实写DP。但还是有必要重新讨论一下如何减少一个Loop的。

可不可以先把用什么方法把任意[i,j]时间段对应的job先求出来，如果能在O(n^2)时间内求出来就算是成功的。可以，先将job按start time->end time排序，然后用一个二维数组或者map存每一个时间段对应的job编号，需要用O(n^2)的space。


import java.util.Arrays;
import java.util.Comparator;

class Job{
        int start,end,cost;
        Job(int s, int e, int c){
            start = s;
            end = e;
            cost = c;
        }
    }
public class Solution{

    public static void main(String args[]){
        int n = 1;
        Job[] jobs = new Job[n];
        jobs[0] = new Job(0,3,1);
        jobs[1] = new Job(3,6,3);
        jobs[2] = new Job(1,5,5);
        jobs[3] = new Job(6,7,1);
        jobs[4] = new Job(7,10,4);
        jobs[5] = new Job(6,8,2);
        jobs[6] = new Job(8,10,2);
        jobs[7] = new Job(1,4,6);
        jobs[8] = new Job(3,7,6);
        jobs[9] = new Job(3,8,8);
        Solution s = new Solution();
        System.out.println(s.maxCostOfJobs(jobs));
    }

    public int maxCostOfJobs(Job[] jobs){
        // edge case
        if(jobs.length==0){return 0;}

        // sort the jobs by start time ->end time
        Comparator<Job> comparator = new Comparator<Job>(){
            @Override
            public int compare(Job a, Job b){
                if(a.start > b.start)
                    return 1;
                else if(a.start < b.start)
                    return -1;
                else{
                    if(a.end > b.end)
                        return 1;
                    else if(a.end < b.end)
                        return -1;
                    else
                        return 0;
                }
            }
        };
        Arrays.sort(jobs,comparator);

        // match time interval to job cost
        int min = jobs[0].start, max = jobs[jobs.length-1].end;
        int[][] match = new int[max-min+1][max-min+1];
        Job pre = jobs[0];
        for(int i = 0;i < jobs.length;i++){
            if(jobs[i].start==pre.start && pre.cost > jobs[i].cost){
                match[jobs[i].start-min][jobs[i].end-min] = pre.cost;
            }else{
                match[jobs[i].start-min][jobs[i].end-min] = jobs[i].cost;
                pre = jobs[i];
            }
        }

        // DP to get maximum cost
        int opt[] = new int[max-min+1];
        for(int i = 1;i < opt.length;i++){
            opt[i] = opt[i-1];
            for(int t = 0;t < i;t++)
                opt[i] = Math.max(opt[i], opt[t] + match[t][i]);
        }

        return opt[opt.length-1];

    }
}

Vertical Level Traversal of Tree

Print arbitrary binary tree by vertical levels / columns from left to right


example tree

      a
     / \
    b   c
   / \   \
  d   g   z.
   \     /
    e   i
       /
      q
     /
    x
   /
  x1
/
x2


sample output

x2
d x1
b e x.
a g q
c i




Naive Way: 第一想法是一个recursive的算法，给每个节点设置一个weight每次要遍历左节点weight-1，每次遍历右节点weight+1。后来发现recursive的无论是preorder traversal还是DFS都有一个致命问题就是顺序有可能打乱，比如左边的子节点的某一孙子是连续往右拐的，就会优先占据list的第一个。所以这里一定要BFS。不太能recursive。


import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Queue;
import java.util.LinkedList;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
        left = null;
        right = null;
    }
}

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int n = 13;
        TreeNode[] tree = new TreeNode[n];
        for(int i = 0;i < n;i++)
            tree[i] = new TreeNode(i);
        for(int i = 0;2*i+2 < n;i++){
            tree[i].left = tree[2*i+1];
            tree[i].right = tree[2*i+2];
        }
          List<List<Integer>> rlst = s.verticalLevelTraversalofTree(tree[0]);
          System.out.println(rlst.size());
          for(int i = 0;i < rlst.size();i++)
              System.out.println(rlst.get(i));
    }

    public List<List<Integer>> verticalLevelTraversalofTree(TreeNode root){
        List<List<Integer>> rlst = new ArrayList<List<Integer>>();
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        Queue<TreeNode> queue= new LinkedList<TreeNode>();
        Map<TreeNode, Integer> weight = new HashMap<TreeNode, Integer>();
        if(root==null){return rlst;}
        // initialize
        queue.add(root);
        weight.put(root,0);
        int min = 0;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            int w = weight.get(node);
            // put into map
            if(!map.containsKey(w)){
                List<Integer> list = new ArrayList<Integer>();
                list.add(node.val);
                map.put(w,list);
            }else{
                List<Integer> list = map.get(w);
                list.add(node.val);
            }
            // enqueue
            if(node.left!=null){
                queue.add(node.left);
                weight.put(node.left,w-1);
            }
            if(node.right!=null){
                queue.add(node.right);
                weight.put(node.right,w+1);
            }
            // update min
            min = Math.min(min,w);
        }
        // generate result
        while(map.containsKey(min)){
            rlst.add(map.get(min++));
        }
        return rlst;
    }

}


Improved Way: 还有一道基于这道题目的问题是
Print the sum of all the numbers at every vertical level in a binary tree
解法一样，可以在得到list后还要求sum，也可以用一个map不断更新同一vertical level的sum。
而且这样一来顺序就不重要了，可以DFS或者preorder traversal什么的， 难度其实降低了。

Product of Array

Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of all nums[j], j != i.

Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
      = [120, 60, 40, 30, 24]

You must do this in O(N) without using division.

Naive Thinking:这道题想了很久之后我居然想出来一个办法。
要用额外两个数组。
num[] =[  1     2    3   4   5 ]
arr1[]  =[  1     1    2   6  24]   从前往后，arr1[0] = 1, arr1[i] = arr1[i-1]*num[i-1];
arr2[]  =[120  60  20  5   1 ]   从后往前，arr2[n] = 1, arr2[i] = arr2[i+1]*num[i+1];
num[] =[120  60  40  30 24]  然后num[i] = arr1[i]*arr2[i]

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int num[] = {1,2,3,4,5,6,7};
        s.productOfArray(num);
        for(int i = 0;i < num.length;i++)
            System.out.print(num[i] + " ");
    }

    public void productOfArray(int[] num){
        if(num.length < 2){return;}
        int arr1[] = new int[num.length];
        int arr2[] = new int[num.length];
        arr1[0] = 1;arr2[num.length-1] = 1;
        for(int i = 1;i < num.length;i++)
            arr1[i] = arr1[i-1]*num[i-1];
        for(int i = num.length-2;i >= 0;i--)
            arr2[i] = arr2[i+1]*num[i+1];
        for(int i = 0;i < num.length;i++)
            num[i] = arr1[i]*arr2[i];
        return;
    }
}

A Bird and Fruit Trees

There are n trees in a circle. Each tree has a fruit value associated with it. A bird can sit on a tree for 0.5 sec and then he has to move to a neighbouring tree. It takes the bird 0.5 seconds to move from one tree to another. The bird gets the fruit value when she sits on a tree. We are given n number of seconds the bird has and, the fruit values val[m] of the trees. We have to maximise the total fruit value that the bird can gather. The bird can start from any tree.


Naive Thinking: 第一眼觉得是DP，但是写了写发现只要找到连续的相加之和最大的树群就行了，每棵树用的时间是固定的。

算法复杂度是O(n)。

 public class Solution{

    public static void main(String args[]){
        int val[] = {1,1,1,1,1,1,1,2,1,1,2,4};
        Solution s = new Solution();
        System.out.println(s.maxFruitValue(4,val));
    }

    public int maxFruitValue(int n, int val[]){
        int sum = 0;
        int max = 0;
        int begin = 0;
        int end = n;
        for(int i = 0;i < end && i < val.length;i++)
            sum += val[i];
        max = sum;
        if(n >= val.length){return max;}
        while(begin < val.length){
            sum -= val[begin++];
            sum += val[end];
            max = Math.max(max,sum);
            end = (end+1)%val.length;
        }
        return max;
    }
}

Path for Binary Tree

Print all the paths from root to every leaf in a binary tree


Naive Thinking: 可以用stack进行DFS，同时还要回溯，也可以用recursive的DFS，避免些回溯的麻烦。

算法复杂度是O(n), space是O(n)。

import java.util.List;
import java.util.ArrayList;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
        left = null;
        right = null;
    }
}

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int n = 10;
        TreeNode[] tree = new TreeNode[n];
        for(int i = 0;i < n;i++)
            tree[i] = new TreeNode(i);
        for(int i = 0;2*i+2 < n;i++){
            tree[i].left = tree[2*i+1];
            tree[i].right = tree[2*i+2];
        }
        List<List<Integer>> list = s.pathsForBinaryTree(tree[0]);
        for(int i = 0;i < list.size();i++)
            System.out.println(list.get(i));

    }

    public List<List<Integer>> pathsForBinaryTree(TreeNode root){
        // recursive DFS
        List<List<Integer>> rlst = new ArrayList<List<Integer>>();
        if(root==null){return rlst;}
        search(new ArrayList<Integer>(), rlst, root);
        return rlst;
    }

    private void search(List<Integer> list, List<List<Integer>> rlst, TreeNode root){
        List<Integer> newList = new ArrayList<Integer>(list);
        newList.add(root.val);
        if(root.left==null && root.right==null)
            rlst.add(newList);
        else{
            if(root.left!=null)
                search(newList, rlst, root.left);
            if(root.right!=null)
                search(newList, rlst, root.right);
        }
    }

}

Maximum overlapping interval

Maximum overlapping interval

Given n intervals [si, fi], find the maximum number of overlapping intervals.

 Naive Thinking: 好像是讲greedy时候的题目。从对所有interval排序，如果si相同就按fi排序。然后用greedy的思想取第一个，接着取最接近却又不和第一个重合的，依次类推，直到不能取，这算是一层，然后同样的方法取第二层、第三层，直到所有的都被取了一遍，看有多少层。

如果用一个doubly linked list去存排好序的interval,就可以实现O(nlogn)的算法复杂度，否则，用数组遍历就是O(n^2)的算法复杂度。

import java.util.Set;
import java.util.HashSet;
import java.util.Comparator;
import java.util.Arrays;
import java.util.Iterator;

class Interval{
        int b;
        int e;
        Interval(int begin, int end){
            b = begin;
            e = end;
        }
    }
public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        Interval[] intervals = new Interval[10];
        intervals[0] = new Interval(0, 3);
        intervals[1] = new Interval(2, 4);
        intervals[2] = new Interval(3, 6);
        intervals[3] = new Interval(4, 5);
        intervals[4] = new Interval(5, 9);
        intervals[5] = new Interval(7, 8);
        intervals[6] = new Interval(6, 7);
        intervals[7] = new Interval(9, 11);
        intervals[8] = new Interval(7, 13);
        intervals[9] = new Interval(3, 8);
        System.out.println(s.maxOverlapInterval(intervals));
    }

   

    public int maxOverlapInterval(Interval[] intervals){
        Set<Interval> set = new HashSet<Interval>();
        int layers = -1;
        int end = -1;
        Comparator<Interval> c = new Comparator<Interval>(){
            @Override
            public int compare(Interval x, Interval y){
                if(x.b < y.b){
                    return -1;
                }else if(x.b > y.b){
                    return 1;
                }else{
                    if(x.e < y.e){
                        return -1;
                    }else if(x.e > y.e){
                        return 1;
                    }
                }
                return 0;
            }
        };
        Arrays.sort(intervals, c);
        for(int i = 0;i < intervals.length;i++)
            set.add(intervals[i]);
        while(!set.isEmpty()){
            // Iterator<Interval> iter = set.iterator();
            // while(iter.hasNext()){
            //     Interval i = iter.next();
            //     if(i.b > end){
            //         set.remove(i);
            //         end = i.e;
            //     }
            // }
            for(int i = 0;i < intervals.length;i++){
                if(set.contains(intervals[i])){
                    if(intervals[i].b > end){
                        set.remove(intervals[i]);
                        end = intervals[i].e;
                    }
                }
            }
            end = -1;
            layers++;
        }
        return Math.max(layers,0);
    }
}

Add two number using bit operation

I saw some articles telling about how to use bit-wise operation to achieve add operation.

Here the explanation for the function.


int add(int x, int y){
    int a,b;
    do{
        a = x & y;// a holds the carry (a承接进位)
        b = x ^ y;// b holds the sum without carry （b承接无进位的和）
        x = a<<1; // perform carry, x becomes carry （进位，并用x承接进位）
        y = b;
    }while（x) // until carry = 0 (直到无进位)
    return y;
}

Implement Queue using Stacks

Implement Queue using Stacks

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2

Naive Way: 我自己试着写了一个。

这个dequeue和enqueue都不能做到O(1)，只有当连续进行单个dequeue或者单个enqueue的指令时，才会实现O(1)的效率。

/*
* I figure out a way to implement queue by two stacks
* However, only when consecutive pop() or consecutive push()
* are conducted, there is efficiency.
*/
import java.util.Stack;
public class StackQueue<Item>{

    public static void main(String args[]){
        StackQueue<Integer> sq = new StackQueue<Integer>();
        sq.enqueue(1);
        sq.enqueue(2);
        sq.enqueue(5);
        System.out.println(sq.dequeue());
    }

    private Stack<Item>stack1;
    private Stack<Item> stack2;

    public StackQueue(){
        stack1 = new Stack<Item>();
        stack2 = new Stack<Item>();
    }

    public Item dequeue(){
        if(!stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.isEmpty()?null:stack2.pop();
    }

    public void enqueue(Item e){
        if(!stack2.isEmpty()){
            while(!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
        }
        stack1.push(e);
    }

    public boolean isEmpty(){
        return stack1.isEmpty() && stack2.isEmpty();
    }

}
Improved Way: 后来看了别人的做法，也是不能使两个operation都是O(1)，而是让其中某个成为O(1)，另一个是O(n)。我觉得跟我的方法思路一样的。总之就是无法让两种operation都变成O(1)。

public Item dequeue(){
        while(!stack1.isEmpty()){stack2.push(stack1.pop());}
        Item e = stack2.isEmpty()?null:stack2.pop();
        while(!stack2.isEmpty()){stack1.push(stack2.pop());}
        return e;
    }

    public void enqueue(Item e){
        stack1.push(e);
    }

Remove Numbers in Array

Remove Numbers in Array

Given an array and a value, how to implement a function to remove all instances of that value in place and return the new length? The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Naive Thinking:要求是in-place，那可以通过指针后移或者替换，替换的话顺序会变，这里正好让变。设置一头一尾的指针，从头遍历一旦遇到该value，就与尾部的数替换，最后头指针停留位置就是有效长度。

算法复杂度是O(n)

public class Solution{
    public static void main(String args[]){
        Solution s = new Solution();
        int num[] = {1,1,2,2,3,0,1,4,2,1,4,5};
        int l = s.removeNumberInArray(num,1);
        for(int i = 0;i < l;i++)
            System.out.println(num[i]);
    }
    public int removeNumberInArray(int[] num, int target){
        int i = 0, j = num.length-1;
        while(i < j){
            if(num[i]==target){
                int temp = num[j];
                num[j] = num[i];
                num[i] = temp;
                j--;
            }else{
                i++;
            }
        }
        if(num.length==0){return 0;}
        return num[i]==target?i:i+1;
    }
}

Improved Way:才发现这题和我面试遇到的那道题一样，可以用两个指针一快一慢的遍历。


算法复杂度也是O(n)，但很明显这样要机智很多。


public int removeNumberInArray(int[] num, int target){
        int i = -1,j = 0;
        while(++i < num.length){
            if(num[i] != target)
                num[j++] = num[i];
        }
        return j;
    }

Derive Order for New Language

Derive Order for New Language

here's a new language which uses the latin alphabet. However, you don't know the order among letters.

It could be:
a b c d ...

as it could also be:

b e z a m i ...

You receive a list of words lexicographically sorted by the rules of this new language. From this list, derive one valid particular ordering of letters in this language.

Naive Thinking: 这道题是我从来没有见过的类型，想了半天还是想不出来，看了答案，原来是拓扑排序。好厉害呀。

算法复杂度是O(nk) k是平均每个单词的长。从index = 0开始，每次都先找到前一个字母一样的[begin, end]区段，然后调用子函数setOrder(Node[] order, String[] strs, int begin, int end, int index)去连接对应节点，这一部分完成后就得到一个DAG，在DAG上运行拓扑排序得到的顺序就是新语言的顺序。

import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class Solution{
    class Node{
        char val;
        int father;
        List<Node> next;
        Node(char c){
            val = c;
            father = 0;
            next = new ArrayList<Node>();
        }
    }

    public static void main(String args[]){
        Solution s = new Solution();
        String[] strs = {"battle", "bare", "barffdfsdf", "apple", "act", "do", "coap", "cool","copf"};
        //String[] strs = {"battle","bare","apple"};
        s.deriveOrder(strs);
      
    }

    public char[] deriveOrder(String[] strs){
        char[] rlst = new char[26];
        Node[] order = new Node[26];
        for(int i = 0;i < 26;i++)
            order[i] = new Node((char)(i+'a'));
        char preParent = '0', curParent;
        int index = 0;
        boolean hasNext= strs.length!=0;
        while(hasNext){
            int begin = 0, end = 0;
            hasNext = false;
            // find begin word
            while(end < strs.length){
                if(index < strs[end].length()){
                    preParent = index==0?'0':strs[end].charAt(index-1);
                    hasNext = true;
                    break;
                }
                end++;
            }
            // find end word
            begin = end;
            while(++end < strs.length){
                if(index < strs[end].length()){
                    curParent = index==0?'0':strs[end].charAt(index-1);
                    if(curParent!=preParent){
                        setOrder(order,strs,begin,end,index);
                        begin = end;
                        preParent = index==0?'0':strs[begin].charAt(index-1);
                    }
                }
            }
            if(strs[Math.min(end-1,strs.length-1)].length() > index)
                setOrder(order,strs,begin,end,index);
            index++;
        }
      
        // for(int i = 0;i < 26;i++){
        //     System.out.println((char)(i+'a') + " has "+order[i].father+ " fathers with children:");
        //     for(int j = 0;j < order[i].next.size();j++)
        //         System.out.print((char)(order[i].next.get(j).val)+" ");
        //     System.out.println();
        // }

        // topological sort
        Queue<Node> queue = new LinkedList<Node>();
        for(int i = 0;i < 26;i++)
            if (order[i].father==0)
                queue.add(order[i]);
        index = 0;
        while(!queue.isEmpty()){
            Node node = queue.poll();
            rlst[index++] = node.val;
            for(int i = 0;i < node.next.size();i++){
                node.next.get(i).father--;
                if(node.next.get(i).father==0)
                    queue.add(node.next.get(i));
            }
        }

        // for(int i = 0;i < 26;i++)
        //     System.out.print(rlst[i] + " ");

        return rlst;
    }

    private void setOrder(Node[] order, String[] strs, int begin, int end, int index){
        char pre = strs[begin].charAt(index), cur;
        boolean newStart = true;
        for(int i = begin;i < end && i < strs.length;i++){
            if(index < strs[i].length()){
                if(newStart){
                    pre = strs[i].charAt(index);
                    newStart = false;
                }else{
                    cur = strs[i].charAt(index);
                    if(pre!=cur){
                        order[toInt(pre)].next.add(order[toInt(cur)]);
                        order[toInt(cur)].father++;
                        pre = cur;
                    }
                }
            }
        }
    }

    private int toInt(char c){
        return (int)(c-'a');
    }

}


这题太好了，很难找到考拓扑排序的题。

Tree to Doubly Linked List

Tree to Doubly Linked List

convert a binary tree to a circular doubly-linked list. (I add these words: use right pointer as next pointer, use left pointer as previous pointer.)


Naive Thinking: 这道题目有点宽泛啊，没说具体怎么映射。但是有一点很合我意的就是，它把指针的概念变成一个广义的，left node和right node就一定要做左右子节点的指针吗，就不能做双向链表的前后指针吗，这一点参见我在Populating Next Right Pointers in Each Node II中最后那个引用的例子。所以我自己加的将right变成next，left变成pre，看了别人的回答也是差不多这样的。嗯，这道题很好。

那么我的基本思路就是利用原树节点的左右子节点指针做前后指针。但是具体怎么映射必须得有章法吧，将树写成线性形式的方法有三种:前序遍历，中序遍历，后序遍历。

那么这道题是考验二叉树的遍历咯？肯定在考，即使不是只考这个。这时赶快在心里默默写下三种遍历。一个直觉就是将树转换成链表，一个recursive的算法，肯定不是三种遍历都可以，应该只有一种遍历可以，这道题应该有在看是否能用出正确的遍历方式。仔细分析

基本框架大概是这样的
void traversal(TreeNode root){
    if(root==null){return;}
    if(root.left!=null){traversal(root.left);}
    if(root.right!=null){traversal(root.right);}
} 

问题一，traversal只有一个参数，无返回值，能否确保在回溯过程中树不断掉。比如一旦连了next(right)，right node 可能就找不回来了。

问题二，同时要连next 和 pre，也就是说同时要可能改变right 和left 节点的链接方式，如何做到连好之后还能找回right node 和left node。

回答一，感觉上一个参数应该足够，无返回值有点不好弄，因为如果把一棵树变成链表，一个对树的recursive函数把链表连成圈的，好难，简直无法想象。感觉先把root当成头，连好后面的得到一个尾巴，将一头一尾在外面手动链接才是一个可行的方案。传进去的值是root，如果能传出来的正好是尾巴就好了。那么想到这里，哪种遍历这个问题也迎刃而解了，root必须是第一个遍历的节点，只有中序遍历才能做到。

回答二，为何要同时连next和pre, 连好任意一个，另外一个不就也算连上了吗？

根据以上推导我写了下面这段代码。算法复杂度是O(n)，O(n) space  （其实是preorder)
后面有个用于测试代码可行与否的main函数。

// public class TreeNode{
//         int val;
//         TreeNode left;
//         TreeNode right;
//         TreeNode(int x){
//             val = x;
//             left = null;
//             right = null;
//         }
//     }

public class Solution{

    public void tree2DoublyList(TreeNode root){
        TreeNode end = traversal(root);
        TreeNode cur = root;
        if(cur==null){return;}
        root.left = end;
        while(cur.right!=null){
            TreeNode tail = cur.right;
            tail.left = cur;
            cur = tail;
        }
        cur.right = root;
        return;
    }

    private TreeNode traversal(TreeNode root){
        if(root==null){return null;}
        TreeNode temp = root.right;
        TreeNode fromLeft = null, fromRight = null;
        root.right = root.left;
        fromLeft = root.left!=null?traversal(root.left):root;
        fromLeft.right = temp;
        fromRight = temp!=null?traversal(temp):fromLeft;
        return fromRight;
    }
    
   // test correctness
    public static void main(String args[]){
        Solution s = new Solution();
        List<TreeNode> list = new ArrayList<TreeNode>();
        for(int i = 0; i < 10;i++){
            TreeNode node = new TreeNode(i);
            list.add(node);
        }
        for(int i = 0;i < list.size();i++){
            if(2*i+1 < list.size())
                list.get(i).left = list.get(2*i+1);
            if(2*i+2 < list.size())
                list.get(i).right = list.get(2*i+2);
        }
        s.showTree(list.get(0));
        s.tree2DoublyList(list.get(0));
        TreeNode cur = list.get(0);
        for(int i = 0;i < list.size();i++){
            System.out.print(cur.val + "  ");
            cur = cur.right;
        }
        System.out.println();
        for(int i = 0;i < list.size();i++){
            System.out.print(cur.val + "  ");
            cur = cur.left;
        }
        System.out.println();
    }

    private void showTree(TreeNode root){
        if(root==null){return;}
        System.out.println(root.val);
        if(root.left!=null)
            showTree(root.left);
        if(root.right!=null)
            showTree(root.right);
    }

}


Improved Way: 这道题我被面到了，但是条件不一样了，变成将二叉树转化成排好序的doubly-linked-list。

这里知道了一个规律，binary search tree一般就要跟inorder traversal 联系起来了。 我上面的代码相当于是一个preorder 顺序的doubly-linked-list。我下面的代码是对应inorder traversal recursive的方法。

这是我在面试时候写的，算法复杂度是O(n)，space O(n)。将recursive函数改为返回一头一尾两个节点了，质量不高的代码。

public void tree2DoublyList_inorder(TreeNode root){
        List<TreeNode> list = inorder(root);
        TreeNode head = list.get(0);
        TreeNode tail = list.get(1);
        TreeNode pre = head;
        while(pre!=tail){
            TreeNode cur = pre.right;
            cur.left = pre;
            pre = cur;
        }
        head.left= tail;
        tail.right = head;
        return;
    }

    private List<TreeNode> inorder(TreeNode root){
        List<TreeNode> list = new ArrayList<TreeNode>();
        if(root==null){return list;}
        TreeNode head1, head2, tail1, tail2;
        List<TreeNode> fromLeft = inorder(root.left);
        if(fromLeft.size()!=0){
            head1 = fromLeft.get(0);
            tail1 = fromLeft.get(1);
            tail1.right = root;
        }else{
            head1 = root;
            tail1 = root;
        }
        List<TreeNode> fromRight = inorder(root.right);
        if(fromRight.size()!=0){
            head2 = fromRight.get(0);
            tail2 = fromRight.get(1);
            root.right = head2;
        }else{
            head2 = root;
            tail2 = root;
        }
        list.add(head1);
        list.add(tail2);
        return list;
    }


比较好的方法应该是这样的。用一个list<TreeNode>存，任意顺序遍历tree，每次遍历到哪个节点就add哪个节点，这个方法估计才是面试官想要的算法。

这样子做的好处一是清晰简洁，二是如果想要变换顺序(inorder，preorder，postorder)，只需要改变recursive函数中遍历的顺序即可，算法复杂度是O(n)， space也是O(n)。

public void tree2DoublyList(TreeNode root){
        List<TreeNode> list = new ArrayList<TreeNode>();
        traversal(root, list);
        for(int i = 0;i < list.size()-1;i++)
            list.get(i).right = list.get(i+1);
        list.get(list.size()-1).right = list.get(0);
        for(int i = 1;i < list.size();i++)
            list.get(i).left = list.get(i-1);
        list.get(0).left = list.get(list.size()-1);
        return;
    }

    private void traversal(TreeNode root, List<TreeNode> list){
        if(root==null){return;}
        // adjust the order to achieve inorder, preorder, postorder
        traversal(root.left,list);
        list.add(root);
        traversal(root.right,list);
        return;
    }