Leetcode 95 Unique Binary Search Trees 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

Solution 1: Divide and conquer. In order to generate 1...n, we can choose any of them to be root, let us say i, root.left is from list of 0...i-1 and root.right is from list of i+1...n. Code as below:

 public class Solution {  
   public List<TreeNode> generateTrees(int n) {  
     return generate(1,n);  
   }  
   private List<TreeNode> generate(int lo, int hi) {  
     List<TreeNode> res=new ArrayList<>();  
     if (lo>hi) res.add(null);  
     else {  
       for (int i=lo; i<=hi; i++) {  
         for (TreeNode l: generate(lo,i-1)) {  
           for (TreeNode r: generate(i+1,hi)) {  
             TreeNode x=new TreeNode(i);  
             x.left=l;  
             x.right=r;  
             res.add(x);  
           }  
         }  
       }  
     }  
     return res;  
   }  
 }  

Leetcode 94 Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1: recursive

 public class Solution {  
   public List<Integer> inorderTraversal(TreeNode root) {  
     List<Integer> res=new ArrayList<>();  
     travel(root, res);  
     return res;  
   }  
   private void travel(TreeNode x, List<Integer> res){  
     if (x==null) return;  
     travel(x.left,res);  
     res.add(x.val);  
     travel(x.right,res);  
   }  
 }  

Solution 2: iterative

 public class Solution {  
   public List<Integer> inorderTraversal(TreeNode root) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     List<Integer> res=new ArrayList<>();  
     TreeNode x=root;  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         x=stack.pop();  
         res.add(x.val);  
         x=x.right;  
       }  
     }  
     return res;  
   }  
 }  

Leetcode 93 Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Solution 1: iterative

 public class Solution {  
   public List<String> restoreIpAddresses(String s) {  
     int n=s.length();  
     List<String> res=new ArrayList<>();  
     for (int i=1; i<=3 ; i++) {  
       if (i<n-9) continue;  
       for (int j=i+1; j<=i+3; j++) {  
         if (j<n-6) continue;  
         for (int k=j+1; k<=j+3 && k<n; k++) {  
           if (k<n-3) continue;  
           int a=Integer.valueOf(s.substring(0,i));  
           int b=Integer.valueOf(s.substring(i,j));  
           int c=Integer.valueOf(s.substring(j,k));  
           int d=Integer.valueOf(s.substring(k,n));  
           if (a>255 || b>255 || c>255 || d>255) continue;  
           String one=String.valueOf(a)+'.'+String.valueOf(b)+'.'+String.valueOf(c)+'.'+String.valueOf(d);  
           if (one.length()<n+3) continue;  
           res.add(one);  
         }  
       }  
     }  
     return res;  
   }  
 }  

Solution 2: recursive

 public class Solution {  
   public List<String> restoreIpAddresses(String s) {  
     List<String> res=new ArrayList<>();  
     dfs(0,s,"",res);  
     return res;  
   }  
   private void dfs(int d, String s, String one, List<String> res) {  
     int n=s.length();  
     if (d==4) {  
       if (n==0) res.add(one.substring(0,one.length()-1));  
     }  
     else {  
       if (n>=1) dfs(d+1,s.substring(1),one+s.charAt(0)+'.',res);  
       if (n>=2 && s.charAt(0)!='0') dfs(d+1,s.substring(2),one+s.substring(0,2)+'.',res);  
       if (n>=3 && s.charAt(0)!='0') {  
         String t=s.substring(0,3);  
         if (Integer.valueOf(t)<=255) dfs(d+1,s.substring(3),one+t+'.',res);  
       }  
     }  
   }  
 }  

Leetcode 92 Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Solution 1: simple two pointer problem.

 public class Solution {  
   public ListNode reverseBetween(ListNode head, int m, int n) {  
     ListNode dummy=new ListNode(0);  
     dummy.next=head;  
     ListNode x=dummy, p=dummy, t=dummy;  
     for (int k=0; k<=n; k++) {  
       if (k==m-1) p=x;  
       if (k==n) t=x;  
       x=x.next;  
     }  
     ListNode i=p.next, j=t.next;  
     t.next=null;  
     while (i!=null) {  
       t=i.next;  
       i.next=j;  
       j=i;  
       i=t;  
     }  
     p.next=j;  
     return dummy.next;  
   }  
 }  

Leetcode 91 Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Solution 1: from end to start will be easier. The key is that '0' can not be used independently. 

 public class Solution {  
   public int numDecodings(String s) {  
     int n=s.length();  
     if (n==0) return 0;  
     int pre=1, res=1;  
     for (int i=n-1; i>=0; i--) {  
       int temp=res;  
       if (s.charAt(i)=='0') res=0;  
       else if (i<n-1 && Integer.valueOf(s.substring(i,i+2))<=26) res+=pre;  
       pre=temp;  
     }  
     return res;  
   }  
 }  

Leetcode 90 Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution 1: back tracking or DFS

 public class Solution {  
   public List<List<Integer>> subsetsWithDup(int[] nums) {  
     Arrays.sort(nums);  
     List<List<Integer>> res=new ArrayList<>();  
     List<Integer> one=new ArrayList<>();  
     dfs(0,nums,one,res);  
     return res;  
   }  
   private void dfs(int d, int[] nums, List<Integer> one, List<List<Integer>> res) {  
     if (d==nums.length) res.add(new ArrayList<Integer>(one));  
     else {  
       int i=d+1;  
       while (i<nums.length && nums[i]==nums[d]) i++;  
       dfs(i,nums,one,res);//select none  
       one.add(nums[d]);//select 1+  
       dfs(d+1,nums,one,res);  
       one.remove(one.size()-1);  
     }  
   }  
 }  

Leetcode 89 Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

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

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Solution 1: simple iterative solution as below

 public class Solution {  
   public List<Integer> grayCode(int n) {  
     List<Integer> res=new ArrayList<>();  
     int size=1;  
     res.add(0);  
     for (int i=1; i<=n; i++) {  
       for (int j=size-1; j>=0; j--) {  
         res.add(1<<i-1|res.get(j));  
       }  
       size*=2;  
     }  
     return res;  
   }  
 }  

Leetcode 88 Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

Solution 1: use merge sort in place from end to start is the key.

 public class Solution {  
   public void merge(int[] nums1, int m, int[] nums2, int n) {  
     int i=m-1, j=n-1, k=m+n-1;  
     while (i>=0 || j>=0) {  
       if (i<0) nums1[k--]=nums2[j--];  
       else if (j<0) nums1[k--]=nums1[i--];  
       else if (nums1[i]<nums2[j]) nums1[k--]=nums2[j--];  
       else nums1[k--]=nums1[i--];  
     }  
   }  
 }  

Leetcode 87 Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Solution 1: Use DP, dp[i][j][k] means s1[i...i+k] & s2[j...j+k] is scramble string or not. It need 3 loop to iterate the dp array and another loop to calculate the dp[i][j][k], so complexity is O(n^4).

 public class Solution {  
   public boolean isScramble(String s1, String s2) {  
     int n=s1.length();  
     if (n!=s2.length()) return false;  
     boolean[][][] dp=new boolean[n][n][n];  
     for (int i=n-1; i>=0; i--) {  
       for (int j=n-1; j>=0; j--) {  
         for (int k=0; i+k<n && j+k<n; k++) {  
           if (k==0) dp[i][j][k]=s1.charAt(i)==s2.charAt(j);  
           else {  
             dp[i][j][k]=false;  
             for (int t=0; t<k; t++) {  
               if ((dp[i][j][t] && dp[i+t+1][j+t+1][k-t-1]) || (dp[i][j+k-t][t] && dp[i+t+1][j][k-t-1])) {  
                 dp[i][j][k]=true;  
                 break;  
               }  
             }  
           }  
         }  
       }  
     }  
     return dp[0][0][n-1];  
   }  
 }  

Leetcode 86 Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Solution 1:  Create 2 dummy list, put <x node to first list and rest to 2nd list. combine them together and then return.

 public class Solution {  
   public ListNode partition(ListNode head, int x) {  
     ListNode d1=new ListNode(0);  
     ListNode d2=new ListNode(0);  
     ListNode i=d1, j=d2, k=head;  
     while (k!=null) {  
       if (k.val<x) {  
         i.next=k;  
         i=i.next;  
         k=k.next;  
       }  
       else {  
         j.next=k;  
         j=j.next;  
         k=k.next;  
       }  
     }  
     i.next=d2.next;  
     j.next=null; //make sure end with null, no loop.  
     return d1.next;  
   }  
 }  

Leetcode 85 Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

Solution 1: translate this problem to max rectangular in histogram. Calculate max histogram in each row. Details below:

 public class Solution {  
   public int maximalRectangle(char[][] matrix) {  
     int m=matrix.length;  
     if (m==0) return 0;  
     int n=matrix[0].length;  
     int[][] his=new int[m][n];  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         if (i==0) his[i][j]=matrix[i][j]=='0'?0:1;  
         else his[i][j]=matrix[i][j]=='0'?0:1+his[i-1][j];  
       }  
     }  
     int res=0;  
     for (int i=0; i<m; i++) res=Math.max(res,calHis(his[i]));  
     return res;  
   }  
   private int calHis(int[] nums) {  
     int n=nums.length, res=0;  
     Deque<Integer> stack=new LinkedList<>();  
     for (int i=0; i<n; i++) {  
       while (!stack.isEmpty() && nums[stack.peek()]>nums[i]) {  
         int j=stack.pop();  
         int left=stack.isEmpty()?0:stack.peek()+1;  
         res=Math.max(res,nums[j]*(i-left));  
       }  
       stack.push(i);  
     }  
     while (!stack.isEmpty()) {  
       int j=stack.pop();  
       int left=stack.isEmpty()?0:stack.peek()+1;  
       res=Math.max(res,nums[j]*(n-left));  
     }  
     return res;  
   }  
 }  

Leetcode 84 Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Solution 1: The best solution use O(n) time and stack. The idea is for given index i, let us see the max rectangle use height[i] as the height. Then the length should be determined but [left,right], left-1 will lower than heigh[i] and right+1 will be lower than height[i]. With this in mind, then use a stack store increasing element to solve it in O(n), details as below:

 public class Solution {  
   public int largestRectangleArea(int[] height) {  
     int n=height.length, res=0;  
     Deque<Integer> stack=new LinkedList<>();  
     for (int i=0; i<n; i++) {  
       while (!stack.isEmpty() && height[stack.peek()]>height[i]) {  
         int j=stack.pop();  
         int left=stack.isEmpty()?0:stack.peek()+1;  
         res=Math.max(res,height[j]*(i-left));  
       }  
       stack.push(i);  
     }  
     while (!stack.isEmpty()) {  
       int j=stack.pop();  
       int left=stack.isEmpty()?0:stack.peek()+1;  
       res=Math.max(res,height[j]*(n-left));  
     }  
     return res;  
   }  
 }  

Leetcode 83 Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Solution 1: simple LinkedList

 public class Solution {  
   public ListNode deleteDuplicates(ListNode head) {  
     if (head==null) return null;  
     ListNode x=head;  
     while (x.next!=null) {  
       if (x.val==x.next.val) x.next=x.next.next;  
       else x=x.next;  
     }  
     return head;  
   }  
 }  

Leetcode 82 Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution 1:  Use dummy node for deleting.

 public class Solution {  
   public ListNode deleteDuplicates(ListNode head) {  
     ListNode dummy=new ListNode(0);  
     dummy.next=head;  
     ListNode i=dummy;  
     while (i.next!=null && i.next.next!=null) {  
       if (i.next.val!=i.next.next.val) i=i.next;  
       else {  
         ListNode j=i.next;  
         while (j.next!=null && j.val==j.next.val) j=j.next;  
         i.next=j.next;  
       }  
     }  
     return dummy.next;  
   }  
 }  

Leetcode 81 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.

Solution 1: if nums[lo]=nums[hi], treat special, other part is same as problem I.

 public class Solution {  
   public boolean search(int[] nums, int target) {  
     int lo=0, hi=nums.length-1;  
     while (lo<=hi) {  
       int mid=lo+(hi-lo)/2;  
       if (nums[mid]==target) return true;  
       if (nums[lo]<nums[hi]) {  
         if (target>nums[mid]) lo=mid+1;  
         else hi=mid-1;  
       }  
       else if (nums[lo]>nums[hi]) {  
         if (nums[mid]>=nums[lo]) {  
           if (target<nums[mid] && target>nums[hi]) hi=mid-1;  
           else lo=mid+1;  
         }  
         else {  
           if (target>nums[mid] && target<nums[lo]) lo=mid+1;  
           else hi=mid-1;  
         }  
       }  
       else if (target==nums[lo]) return true;  
       else {  
         lo++;  
         hi--;  
       }  
     }  
     return false;  
   }  
 }  

Leetcode 80 Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

Solution 1: Use p0 and p1 to store the last two numbers in order to make judgement.

 public class Solution {  
   public int removeDuplicates(int[] nums) {  
     int j=0, p0=0, p1=0;  
     for (int i=0; i<nums.length; i++) {  
       if (i<2 || nums[i]!=p0 || nums[i]!=p1) nums[j++]=nums[i];  
       p0=p1;  
       p1=nums[i];  
     }  
     return j;  
   }  
 }  

Leetcode 78 Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution 1, also a combination problem not permutation.

 public class Solution {  
   public List<List<Integer>> subsets(int[] nums) {  
     List<List<Integer>> res=new ArrayList<>();  
     List<Integer> one=new ArrayList<>();  
     Arrays.sort(nums);  
     dfs(0,nums,one,res);  
     return res;  
   }  
   private void dfs(int d, int[]nums, List<Integer> one, List<List<Integer>> res) {  
     res.add(new ArrayList<Integer>(one));  
     for (int i=d; i<nums.length; i++) {  
       one.add(nums[i]);  
       dfs(i+1,nums,one,res);  
       one.remove(one.size()-1);  
     }  
   }  
 }  

Solution 2, another way to wring the code.

 public class Solution {  
   public List<List<Integer>> subsets(int[] nums) {  
     List<List<Integer>> res=new ArrayList<>();  
     List<Integer> one=new ArrayList<>();  
     Arrays.sort(nums);  
     dfs(0,nums,one,res);  
     return res;  
   }  
   private void dfs(int d, int[]nums, List<Integer> one, List<List<Integer>> res) {  
     if (d==nums.length) res.add(new ArrayList<Integer>(one));  
     else {  
       dfs(d+1,nums,one,res);  
       one.add(nums[d]);  
       dfs(d+1,nums,one,res);  
       one.remove(one.size()-1);  
     }  
   }  
 }  

Leetcode 79 Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
Solution 1: dfs on every element of the matrix.

 public class Solution {  
   public boolean exist(char[][] board, String word) {  
     int m=board.length;  
     if (m==0) return false;  
     int n=board[0].length;  
     for (int i=0; i<m; i++)   
       for (int j=0; j<n; j++)   
         if (dfs(board,i,j,0,word)) return true;  
     return false;      
   }  
   private boolean dfs(char[][] board, int i, int j, int d, String word) {  
     if (d==word.length()) return true;  
     int m=board.length, n=board[0].length;  
     if (i>=m || i<0 || j>=n || j<0) return false;  
     if (board[i][j]=='.' || board[i][j]!=word.charAt(d)) return false;  
     boolean res=false;  
     char temp=board[i][j];  
     board[i][j]='.';  
     if (!res && dfs(board,i+1,j,d+1,word)) res=true;  
     if (!res && dfs(board,i-1,j,d+1,word)) res=true;  
     if (!res && dfs(board,i,j+1,d+1,word)) res=true;  
     if (!res && dfs(board,i,j-1,d+1,word)) res=true;  
     board[i][j]=temp;  
     return res;  
   }  
 }  

Leetcode 77 Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution 1: pay attention this is combination(组合) not permutation(排列).

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<Integer> one=new ArrayList<>();  
     List<List<Integer>> res=new ArrayList<>();  
     dfs(1,k,n,one,res);  
     return res;  
   }  
   private void dfs(int i, int k, int n, List<Integer> one, List<List<Integer>> res) {  
     if (k==one.size()) res.add(new ArrayList<Integer>(one));  
     else if (i>n) return;  
     else {  
       for (int j=i; j<=n; j++) {  
         one.add(j);  
         dfs(j+1,k,n,one,res);  
         one.remove(one.size()-1);  
       }  
     }  
   }  
 }  

Leetcode 76 Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution 1:  Use a counter to store the count number of each character. C1 is for S and C2 is for T, use C1-C2 and maintain a slide window that count is non-negative.

 public class Solution {  
   public String minWindow(String s, String t) {  
     int m=s.length();  
     int n=t.length();  
     if (m==0 || n==0) return "";  
     int[] c1=new int[256];  
     int[] c2=new int[256];  
     for (int i=0; i<m; i++) c1[s.charAt(i)]++;  
     for (int i=0; i<n; i++) c2[t.charAt(i)]++;  
     for (int i=0; i<256; i++) {  
       c1[i]-=c2[i];  
       if (c1[i]<0) return "";  
     }  
     int i=0, j=m-1, min=m;  
     String res=s;  
     while (c1[s.charAt(j)]>0) c1[s.charAt(j--)]--;  
     while (true) {  
       while (c1[s.charAt(i)]>0) c1[s.charAt(i++)]--;  
       if (j-i+1<min) {  
         min=j-i+1;  
         res=s.substring(i,j+1);  
       }  
       if (++j==m) break;  
       c1[s.charAt(j)]++;  
     }  
     return res;  
   }  
 }  

Leetcode 75 Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

Solution 1: use quick sort 3 way partition, time complexity is O(n);

 public class Solution {  
   public void sortColors(int[] nums) {  
     int n=nums.length;  
     int i=0, j=-1, k=n-1;//quick sort 3-way partition  
     while (i<=k) {  
       if (nums[i]==1) i++;  
       else if (nums[i]==0) swap(nums,i++,++j);  
       else swap(nums,i,k--);  
     }  
   }  
   private void swap(int[] nums, int i, int j) {  
     int temp=nums[i];  
     nums[i]=nums[j];  
     nums[j]=temp;  
   }  
 }  

Leetcode 74 Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Solution 1: use binary search column 0 to find the row, then binary search the row to find the target. Time complexity is log(m)+log(n).

 public class Solution {  
   public boolean searchMatrix(int[][] matrix, int target) {  
     int m=matrix.length;  
     if (m==0) return false;  
     int n=matrix[0].length;  
     int lo=0, hi=m-1;  
     while (lo<=hi) {  
       int mid=lo+(hi-lo)/2;  
       if (target==matrix[mid][0]) return true;  
       else if (target<matrix[mid][0]) hi=mid-1;  
       else lo=mid+1;  
     }  
     if (hi<0) return false; //last postion is [hi,lo]=[-1,0]  
     int r=hi;  
     lo=0; hi=n-1;  
     while (lo<=hi) {  
       int mid=lo+(hi-lo)/2;  
       if (target==matrix[r][mid]) return true;  
       else if (target<matrix[r][mid]) hi=mid-1;  
       else lo=mid+1;  
     }  
     return false;  
   }  
 }  

Leetcode 73 Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Solution 1: if matrix[i][j] is 0, mark matrix[i][0] and matrix[0][j] to 0. Then go through entire matrix again, set related matrix[i][j]=0 if either matrix[i][0] or matrix[0][j] is marked.

 public class Solution {  
   public void setZeroes(int[][] matrix) {  
     int m=matrix.length;  
     if (m==0) return;  
     int n=matrix[0].length;  
     boolean row0=false, col0=false;  
     for (int j=0; j<n; j++) if (matrix[0][j]==0) row0=true;  
     for (int i=0; i<m; i++) if (matrix[i][0]==0) col0=true;  
     for (int i=1; i<m; i++) {  
       for (int j=1; j<n; j++) {  
         if (matrix[i][j]==0) {  
           matrix[0][j]=0;  
           matrix[i][0]=0;  
         }  
       }  
     }  
     for (int i=1; i<m; i++)  
       for (int j=1; j<n; j++)  
         if (matrix[0][j]==0 || matrix[i][0]==0) matrix[i][j]=0;  
     if (row0) for (int j=0; j<n; j++) matrix[0][j]=0;  
     if (col0) for (int i=0; i<m; i++) matrix[i][0]=0;  
   }  
 }  

Leetcode 72 Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Solution 1: DP without Space optimization, easy to understand. Time O(mn), space O(mn).

 public class Solution {  
   public int minDistance(String word1, String word2) {  
     int m=word1.length();  
     int n=word2.length();  
     int[][] dp=new int[m+1][n+1];  
     for (int i=0; i<=m; i++) {  
       for (int j=0; j<=n; j++) {  
         if (i==0) dp[i][j]=j;  
         else if (j==0) dp[i][j]=i;  
         else if (word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j]=dp[i-1][j-1];  
         else dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;  
       }  
     }  
     return dp[m][n];  
   }  
 }  

Solution 2: Optimize Space to O(n)

 public class Solution {  
   public int minDistance(String word1, String word2) {  
     int m=word1.length();  
     int n=word2.length();  
     int[] dp=new int[n+1];  
     for (int i=0; i<=m; i++) {  
       int pre=0;  
       for (int j=0; j<=n; j++) {  
         int temp=dp[j];  
         if (i==0) dp[j]=j;  
         else if (j==0) dp[j]=i;  
         else if (word1.charAt(i-1)==word2.charAt(j-1)) dp[j]=pre;  
         else dp[j]=Math.min(pre,Math.min(dp[j],dp[j-1]))+1;  
         pre=temp;  
       }  
     }  
     return dp[n];  
   }  
 }  

Leetcode 71 Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Solution 1: Use stack. One thing to be noticed is that, when use String split function, it may contains blank strings.

 public class Solution {  
   public String simplifyPath(String path) {  
     String[] strs=path.split("/"); //note: may have blank string  
     Deque<String> stack=new LinkedList<>();  
     for (String x:strs) {  
       if (x.equals("..")) {  
         if (!stack.isEmpty()) stack.pop();  
       }  
       else if (x.length()>0 && !x.equals(".")) stack.push(x); //  
     }  
     StringBuilder res=new StringBuilder();  
     while (!stack.isEmpty()) {  
       res.insert(0,stack.pop());  
       res.insert(0,'/');  
     }  
     if (res.length()==0) return "/";  
     return res.toString();  
   }  
 }  

Leetcode 70 Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution 1: simple DP

 public class Solution {  
   public int climbStairs(int n) {  
     if (n<=0) return 0;  
     int pre=0, res=1;  
     for (int i=1; i<=n; i++) {  
       int temp=res;  
       res=res+pre;  
       pre=temp;  
     }  
     return res;  
   }  
 }  

Leetcode 69 Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Solution 1:  Pay attention to 0 and mid*mid may too big (>Integer.MAX_VALUE)

 public class Solution {  
   public int mySqrt(int x) {  
     if (x<=0) return x;  
     int lo=1, hi=x;  
     while (lo<=hi) {  
       int mid=lo+(hi-lo)/2;  
       if (x/mid==mid) return mid;  
       else if (x/mid<mid) hi=mid-1;  
       else lo=mid+1;  
     }  
     return hi;  
   }  
 }  

Leetcode 68 Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactlyL characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Solution 1: Need to be extreme careful with all corner case. 

 public class Solution {  
   public List<String> fullJustify(String[] words, int maxWidth) {  
     List<String> res=new ArrayList<>();  
     int n=words.length, i=0, l=0;  
     for (int j=0; j<n; j++) {  
       l+=words[j].length();  
       if (l+j-i>maxWidth) {  
         l-=words[j].length();  
         if (j-1==i) {  
           char[] blank=new char[maxWidth-l];  
           Arrays.fill(blank,' ');  
           res.add(words[i]+new String(blank));  
         }  
         else {  
           int w=(maxWidth-l)/(j-i-1);  
           int ex=(maxWidth-l)%(j-i-1);  
           char[] blank=new char[w];  
           Arrays.fill(blank,' ');  
           StringBuilder one=new StringBuilder();  
           for (int k=i; k<j; k++) {  
             one.append(words[k]);  
             if (k!=j-1) one.append(blank);  
             if (k-i<ex) one.append(' ');  
           }  
           res.add(one.toString());  
         }  
         i=j;  
         l=words[j].length();  
       }  
     }  
     char[] blank=new char[maxWidth-l-n+i+1];  
     Arrays.fill(blank,' ');  
     StringBuilder one=new StringBuilder();  
     for (int k=i; k<n; k++) {  
       one.append(words[k]);  
       if (k==n-1) one.append(blank);  
       else one.append(' ');  
     }  
     res.add(one.toString());  
     return res;  
   }  
 }