Recover Binary Search Tree

对于一个Binary Search Tree来说, 按照inOrder的顺序visit各个节点就会是从小到大的排列.
因为有两个节点放错了,所以会出现两次前面的点的值大于后面的点.
用三个指针, 第一个指针pre, 用来遍历整个Tree; 第二个指针first, 用来标记第一个错误的点; 第三个指针second, 用来标记第二个错误的点.

Note:在递归的时候, 何时给pre赋值, 何时给first赋值都是容易bug的地方. 说白了pre就是一个带头的, 发现一个不对的点就标记一下. (第一个点: 它的值比该层递归的root值大, 这个点不对; 第二个点, 当它作为root的时候, 位于前面的点比他大, 就是这个root有问题, 标记为second)

 public class Solution {  
   TreeNode pre;  
   TreeNode first;  
   TreeNode second;  
   public void recoverTree(TreeNode root) {  
     if (root == null)  
       return;  
     inOrder(root);  
     int tmp = first.val;  
     first.val = second.val;  
     second.val = tmp;  
   }  
   public void inOrder(TreeNode root) {  
     if (root == null)  
       return;  
     inOrder(root.left);  
     if (pre == null) {  
       pre = root;  
     }else {  
       if (pre.val > root.val) {  
         if (first == null) {  
           first = pre;  
         }
         second = root;  // 这里会发现, 如果出现了异常, second会一直跟着root走.直到不再出现异常为止,
                         // 这个时候second也就指向了第二个异常的点了.注意: second不是等于pre!!!!
       }  
       pre = root;  
     }  
     inOrder(root.right);  
   }  
 }  

上面是优解,下面这个方法虽然不是最优解, 但是容易上手. 将BST按照inorder顺序把节点和节点的数值存到两个list中, 将节点值list sort一下, 重新赋值给各个节点.

 public class Solution {  
   public void recoverTree(TreeNode root) {  
          if (root == null)  
            return;  
          ArrayList<TreeNode> visit = new ArrayList<TreeNode>();  
          ArrayList<Integer> values = new ArrayList<Integer>();  
          inOrder(visit, values, root);  
          Collections.sort(values);  
          for (int i=0; i<values.size(); i++) {  
            TreeNode curr = visit.get(i);  
            curr.val = values.get(i);  
          }  
        }  
   public void inOrder(ArrayList<TreeNode> visit, ArrayList<Integer> values, TreeNode node) {  
     if (node == null)  
       return;  
     inOrder(visit, values, node.left);  
     visit.add(node);  
     values.add(node.val);  
     inOrder(visit, values, node.right);  
   }  
 }  

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

The key of this problem, is to calculate k-1 times each time you do "in place" operation!

The way of "in place" is very smart!!!

 public class Solution {  
   public ListNode reverseKGroup(ListNode head, int k) {  
     if (head == null || head.next == null || k < 2)  
       return head;  
     ListNode newHead = new ListNode(0);  
     newHead.next = head;  
     ListNode pre = newHead;  
     ListNode curr = head;  
     while (curr != null) {  
       // make sure the rest of the List is enough   
       int counter = k;         // calculate k-1 times
         curr = curr.next;  
         counter--;  
       }  
       if (curr != null) {  
         curr = pre.next;  
         counter = k;  
         while (counter > 1) {  // calculate k-1 times
ListNode tmp = curr.next;  
           curr.next = tmp.next;  
           tmp.next = pre.next;  
           pre.next = tmp;  
           counter--;  
         }  
         pre = curr;  
         curr = pre.next;  
       }  
     }  
     return newHead.next;  
   }  
 }  

Insertion Sort List

Sort a linked list using insertion sort.
This is insertion sort

Algorithm: 

-1-Create a new head has the same value with the value of original list.
-2-Create two pointers: pointer initialized to point to the second node in the original list, and and innerPointer used to do insertion operation in the new sorted list. InnerPointer is initialized to point to the new head;
-3-There are three parts need you to take care of: update head of the new list; effectively insert node into the new list; update tail the new list.
Note:small bug on dealing with the new head every. Consider if the value of the node waiting to insert has the same value with new head!

 public class Solution {  
   public ListNode insertionSortList(ListNode head) {  
     if (head == null || head.next == null)  
       return head;  
     ListNode newHead = new ListNode(head.val);  
     ListNode pointer = head.next;  
     while(pointer!=null){  
       ListNode innerPointer=newHead;  
       ListNode next=pointer.next;  
       if(newHead.val>=pointer.val){  // "=" is a source of bug!
         ListNode oldHead=newHead;  
         newHead=pointer;  
         newHead.next=oldHead;  
       }else{  
         while(innerPointer.next!=null){  
           if(innerPointer.val<pointer.val&&innerPointer.next.val>=pointer.val){  
             pointer.next=innerPointer.next;  
             innerPointer.next=pointer;  
             break;  
           }  
           innerPointer=innerPointer.next;  
         }  
         if(innerPointer.next==null){  
           innerPointer.next=pointer;  
           pointer.next=null;  
         }  
       }  
       pointer=next;  
     }  
     return newHead;  
   }  
 }  

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Find next larger number which consists of all the digits of current number.
You had better to remember this algorithm:

• From right to left, find the first index1 that num[index1] > num[index1-1]; if it does not exist, it means the current number is the largest one, just reverse it
• From right to left, find the first index2 that num[index2] > num[index1-1];
• Swap num[index1-1] and num[index2];
• Reverse the array from index1 to the end of this array.

 public class Solution {  
   public void nextPermutation(int[] num) {  
     if (num == null || num.length == 0)  
       return ;  
     int index1 = 0, index2 = 0;  
     for (int i=num.length-1; i>=1; i--) {  
          if (num[i]>num[i-1]) {  
               index1=i;  
               for (int j=num.length-1; j>=index1; j--){  
                    if (num[j]>num[leftPos]) {  
                         index2 = j;  
                         int t = num[index2];  
                         num[index2] = num[index1-1];  
                         num[index1-1] = t;  
                         break;  
                    }  
               }  
               reverseArray(num, index1, num.length-1);  
               return;  
          }  
     }  
     reverseArray(num, 0, num.length-1);  
   }  
   public int[] reverseArray(int[] array, int begin, int end) {  
     if (begin >= end)  
       return array;  
     for (int i=begin, j=end; i<j; i++, j--) {  
       int t = array[i];  
       array[i] = array[j];  
       array[j] = t;  
     }  
     return array;  
   }  
 }  

Unique Binary Search Tree ii

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Algorithm:
This problem is solved using recursion. We should know that every number between 1 and n can be a root value. Thus, going from 1 to n, each time get a number i as the root, the numbers smaller than i form the left child tree and the numbers larger than i form the right child tree. Recursively do this.

Code:

 public class Solution {  
   public List<TreeNode> generateTrees(int n) {  
     return helper(1, n);  
   }  
   public List<TreeNode> helper(int begin, int end) {  
     List<TreeNode> list = new ArrayList<TreeNode>();  
     if (begin > end) {  
       list.add(null);  
       return list;  
     }  
     for (int i=begin; i<=end; i++) {  
       List<TreeNode> left = helper(begin, i-1);  
       List<TreeNode> right = helper(i+1, end);  
       for (int j=0; j<left.size(); j++) {  
         for (int k=0; k<right.size(); k++) {  
           TreeNode root = new TreeNode(i);  
           root.left = left.get(j);  
           root.right = right.get(k);  
           list.add(root);  
         }  
       }  
     }  
     return list;  
   }  
 }  

NOTE: for one value, there is probably several structurally unique binary trees, like 3 as root in the example

Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

这个题目有两种思路: 第一种就是新建一个链表;第二种就是直接修改链表1或者是链表2.

可以看到, 第一种思路要相对多用一些空间. 第二种思路,比较省空间(但是实际上也可以忽略不计了).两个方法的的复杂度都是O(n).

这里只写第一种方法: 代码十分简单!

 public class Solution {  
   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
     if (l1 == null) return l2;  
     if (l2 == null) return l1;  
     ListNode p1=l1, p2=l2;  
     ListNode newHead = new ListNode(0);  
     ListNode p3 = newHead;  
     int carry = 0;  
     while (p1 != null || p2 != null) {  
       if (p1 != null) {  
         carry += p1.val;    
         p1 = p1.next;  
       }  
       if (p2 != null) {  
         carry += p2.val;  
         p2 = p2.next;  
       }  
       ListNode next = new ListNode(carry % 10);  
       p3.next = next;  
       p3 = p3.next;  
       carry = carry / 10;  
     }  
     if (carry != 0) {  
       p3.next = new ListNode(carry);  
     }  
     return newHead.next;  
   }  
 }  

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

 public class Solution {  
   public int lengthOfLongestSubstring(String s) {  
     if (s == null || s.isEmpty())  
       return 0;  
     int len = s.length();  
     boolean[] table = new boolean[256];  
     int start = 0;  
     int maxLength = 1;  
     int i = 0;  
     while (i < s.length()) {  
       char curr = s.charAt(i);  
       if (!table[curr])  
         table[curr] = true;  
       else {  
         int currLen = i - start;  
         maxLength = Math.max(maxLength, currLen);  
         for (int j=start; j<i; j++) {  
           if (s.charAt(j) == s.charAt(i)) {  
             start = j+1;  
             break;  
           }  
           else  
             table[s.charAt(j)] = false;  
         }  
       }  
       i++;  
     }  
     maxLength = Math.max(maxLength, len-start);  
     return maxLength;  
   }  
 }  

Note:这里关键是看到如何处理else中update完maxLength之后的部分

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
    ["aa","b"],
    ["a","a","b"]
  ]

 public class Solution {  
   public ArrayList<ArrayList<String>> partition(String s) {  
     ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();  
     if (s == null || s.length() == 0) {  
       list.add(new ArrayList<String>());  
       return list;  
     }  
     helper(s, list, new ArrayList<String>(), 0, s.length());  
     return list;  
   }  
   public void helper(String s, ArrayList<ArrayList<String>> r, ArrayList<String> temp, int pos, int n) {  
     if (pos == n) {  
       ArrayList<String> newTemp = new ArrayList<String>(temp);  
       r.add(newTemp);  
       return;  
     }  
     // here we need an end pointer to extract each substrings  
     for (int end=pos+1; end<=n; end++) {  
       String sub = s.substring(pos, end);  
       if (isPalindrome(sub)) {  
         temp.add(sub);  
         helper(s, r, temp, end, n);  
         temp.remove(temp.size()-1);  
       }  
       // here you do not need to deal with the case that sub is not palindorme  
     }  
   }  
   public boolean isPalindrome(String string) {  
     if (string == null || string.length()==0)  
       return true;  
     boolean b = true;  
     int i=0, j=string.length()-1;  
     while (i <= j) {  
       if (string.charAt(i) != string.charAt(j))  
         b = false;  
       i++;  
       j--;  
     }  
     return b;  
   }  
 }  

Reverse Linked List II

Given positions m and n in a linked list, reverse all the nodes from mth node to nth node.

 public class Solution {  
   public ListNode reverseBetween(ListNode head, int m, int n) {  
     if (head == null || head.next == null || m == n)  
       return head;  
     ListNode newHead = new ListNode(0);  
     newHead.next = head;  
     ListNode pre = newHead;  
     ListNode first = head, second = head;  
     int further = n > m ? n:m, near = n < m?n:m;  
     for (int i=1; i<=further; i++) {  
       if (i < near)   
         pre = pre.next;  
       else if (i == near) {  
         first = pre.next;  
         second = first.next;  
       }else {  
         first.next = second.next;  
         second.next = pre.next;  
         pre.next = second;  
         second = first.next;  
       }  
     }  
     return newHead.next;  
   }  
 }  

Letter Combinations of Phone Number

There are 2 solutions the first one is wrong, the second one is right. Be careful!

 public class Solution {  
   public List<String> letterCombinations(String digits) {  
     List<String> r = new ArrayList<String>();  
     if (digits.length() == 0 || digits == null) return r;  
     String[] table = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     helper(digits, r, table, new StringBuilder(), 0, digits.length());  
     return r;  
   }  
   public void helper(String digits, List<String> r, String[] table, StringBuilder temp, int pos, int n) {  
     if (pos >= n) {  
       String s = temp.toString();  
       r.add(s);  
       return;  
     }  
     for (int i=pos; i<n; i++) {  
       int curr = digits.charAt(i)-'0';  
       if (curr == 0 || curr == 1 || digits.charAt(i) == '*' || digits.charAt(i) == '#')  
         helper(digits, r, table, temp, i+1, n);  
       else {  
         String choice = table[curr];  
         for (int j=0; j<choice.length(); j++) {  
           char choiceCurr = choice.charAt(j);  
           temp.append(choiceCurr);  
           helper(digits, r, table, temp, i+1, n);  
           temp = new StringBuilder(temp.substring(0, temp.length()-1));  
         }  
       }  
     }  
   }  
 }  

 public class Solution {  
   public static List<String> letterCombinations(String digits) {  
     List<String> r = new ArrayList<String>();  
     if (digits == null) return r;  
     String[] table = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     if (digits.isEmpty()) {  
       r.add("");  
       return r;  
     }  
     helper(digits, r, table, new StringBuilder(), 0, digits.length());  
     return r;  
   }  
   public static void helper(String digits, List<String> r, String[] table, StringBuilder temp, int pos, int n) {  
     if (pos >= n) {  
       String s = temp.toString();  
       r.add(s);  
       return;  
     }  
     int curr = digits.charAt(pos)-'0';  
     if (curr == 0 || curr == 1 || digits.charAt(pos) == '*' || digits.charAt(pos) == '#')  
       helper(digits, r, table, temp, pos+1, n);  
     else {  
       String choice = table[curr];  
       for (int j=0; j<choice.length(); j++) {  
         char choiceCurr = choice.charAt(j);  
         temp.append(choiceCurr);  
         helper(digits, r, table, temp, pos+1, n);  
         temp.deleteCharAt(pos);  
       }  
     }  
   }  
 }  

LeetCode: Binary Tree PostOrder Traversal

 /*  
 ** This is problem can be solved in a very smart way.  
 ** The key point here is if you use a stack to do DFS  
 ** (Left-to-right), the order of visiting is preorder.  
 ** But, if you do in the opposite way, it will generate  
 ** the opposite result of postorder traversal.  
 **  
 ** Preorder, stack push right first, then left  
 ** PostOrder, stack push left first, then right, after  
 ** finish the loop, reverse the result.  
 */  
 public class Solution {  
   public List<Integer> postorderTraversal(TreeNode root) {  
     List<Integer> ans = new ArrayList<Integer>();  
     if (root == null) return ans;  
     Stack<TreeNode> stack = new Stack<TreeNode>();  
     stack.push(root);  
     while (!stack.empty()) {  
       TreeNode curr = stack.pop();  
       ans.add(curr.val);  
       if (curr.left != null)   
         stack.push(curr.left);  
       if (curr.right != null)  
         stack.push(curr.right);  
     }  
     Collections.reverse(ans);  
     return ans;  
   }  
 }