Rotate List LeetCode

Recursion is very simple.

 public ListNode rotateRight(ListNode head, int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
     
       if (head==null || head.next == null) return head;
       if (n==0) return head;
     
       ListNode curr = head;
       ListNode prev = head;
     
       while (curr.next != null) {
           prev = curr;
           curr = curr.next;
       }
     
       curr.next = head;
       prev.next = null;
     
       return rotateRight(curr, n-1);
    }

1. n may be larger than the length of list.
2. Non-recursion

public ListNode rotateRight(ListNode head, int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
       if (head==null || head.next ==null) return head;
       ListNode dummy = new ListNode(0);
       dummy.next = head;
       int len = listLen(head);
       n%=len;
       ListNode p = dummy, q = dummy;
       int i=0;
       while (q.next != null) {
           if (i>=n) {
               p=p.next;
           }
           q=q.next;
           i++;
       }
       q.next = dummy.next;
       dummy.next = p.next;
       p.next = null;
       return dummy.next;
    }
   
    private int listLen(ListNode p) {
        int len = 0;
        while (p != null) {
            len++;
            p = p.next;
        }
        return len;
    }

Spiral Matrix II LeetCode

public int[][] generateMatrix(int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       
        int start = 0;
        int end = n-1;
        int[][] res = new int[n][n];
        int num = 1;
        //This is the special case of n=1
        if (start == end) {
            res[start][start] = num;
            return res;
        }
        //Regular case
        while (start < end) {
            //from Left to Right
            for (int i=start; i<end; i++) {
                res[start][i] = num;
                num++;
            }
           
            //from Up to Bottom
            for (int i=start; i<end; i++) {
                res[i][end] = num;
                num++;
            }
           
            //from Right to Left
            for (int i=end; i>start; i--) {
                res[end][i] = num;
                num++;
            }
           
            //from Bottom to Up
            for (int i=end; i>start; i--) {
                res[i][start]=num;
                num++;
            }
           
            start++;
            end--;
            if (start==end) res[start][start] = num;
        }
        return res;
    }

Insert Interval LeetCode

Check the comments

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new ArrayList<Interval>();
       
        int i=0;
        //Add all the interval before the overlapping
        for (; i<intervals.size() && newInterval.start > intervals.get(i).end; i++) {
            res.add(intervals.get(i));
        }
       
        //Add the overlapping interval (Find the last overlapping interval)
        for (; i<intervals.size() && intervals.get(i).start<= newInterval.end; i++) {
            newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
            newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
        }
        res.add(newInterval);
        //Add all the interval after the overlapping
        for (; i<intervals.size(); i++) {
            res.add(intervals.get(i));
        }
        return res;
    }

Spiral Matrix LeetCode

Pay attention to the index and the break condition.

public List<Integer> spiralOrder(int[][] matrix) {

        List<Integer> res = new ArrayList<Integer>();

        if (matrix== null || matrix.length==0 || matrix[0].length==0) return res;

        

        int width = matrix[0].length;

        int height = matrix.length;

        

        for (int i=0; i<(Math.min(width, height) + 1)/2; i++) {

            for (int j=i; j<width-i; j++) {

                res.add(matrix[i][j]);

            }

            for (int j=i+1; j<height-i; j++) {

                res.add(matrix[j][width-i-1]);

            }

            

            if (height - i - 1 == i) break;

            for (int j=width-i-2; j>=i; j--) {

                res.add(matrix[height-i-1][j]);

            }

            

            if (width - i - 1 == i) break;

            for (int j = height-i-2; j>=i+1; j--) {

                res.add(matrix[j][i]);

            }

        }

        return res;

    }

N-Queens II LeetCode

Here is the solution for the N-Queens II

It is easier than N-Queens.

int total;
    public int totalNQueens(int n) {
        total = 0;
        int[] loc = new int[n];
        dfs(loc, 0, n);
        return total;
    }
   
    private void dfs(int[] loc, int curr, int n) {
        if (curr == n) {
            total++;
            return;
        }
        for (int i=0; i<n; i++) {
            loc[curr] = i;
            if (isValid(loc, curr)) {
                dfs(loc, curr+1, n);
            }
        }
    }
   
    private boolean isValid(int[] loc, int curr) {
        for (int i=0; i<curr; i++) {
            if (loc[curr]==loc[i] || Math.abs(loc[curr] - loc[i]) == (curr-i)) {
                return false;
            }
        }
        return true;
    }

N-Queens Leetcode

Here is the reference:
http://blog.csdn.net/u011095253/article/details/9158473

I like the idea of chopping the problems into several pieces.

首先我们弄清楚一下输出，最终输出是ArrayList<String[]>，每一个解是String[], 每一个解的每一行是String

我们当然可以采用上一题，Word Search里更新board内容的方法，不过更新来更新去比较麻烦，这一题我们换个思路

我们把这一题分成几个小问题

1. 传统的dfs递归

2. 验证放置Queen的地方是否合法

3. 输出Board结果

这么做的好处就是，一开始，我们不用建立一个庞大的Board，我们选用一个数组对应Board里面的每一行，数组每一个值对应这一行放置Queen的列号

比如： int[ ] {3,1,4,2} 代表放置的地点分别为[1,3], [2,1], [3,4], [2,4] 这么一来，我们用很简单的用数组表示了整个Board，而且在isValid函数里判断的时候会非常简洁，而且把输出Board单独隔离了出来

public List<String[]> solveNQueens(int n) {
        List<String[]> res = new ArrayList<>();
        int[] loc = new int[n];
        dfs(res, loc, 0, n);
        return res;
    }
   
    private void dfs(List<String[]> res, int[] loc, int curr, int n) {
        if (curr==n) {
            printBoard(res, loc, n);
        } else {
            for (int i=0; i<n; i++) {
                loc[curr] = i;
                if (isValid(loc, curr)) {
                    dfs(res, loc, curr+1, n);
                }
            }
        }
    }
   
    private boolean isValid(int[] loc, int curr) {
        for (int i=0; i<curr; i++) {
            //first condition for column and second condition for diagnal (no need check the row)
            if (loc[i]== loc[curr] || Math.abs(loc[curr]-loc[i]) == (curr-i)) {
                return false;
            }
        }
        return true;
    }
   
    private void printBoard(List<String[]> res, int[] loc, int n) {
        String[] ans = new String[n];
        for (int i=0; i<n; i++) {
            String row = new String();
            for (int j=0; j<n; j++) {
                if (j==loc[i]) {
                    row += "Q";
                } else {
                    row += ".";
                }
            }
            ans[i] = row;
        }
        res.add(ans);
    }

Jump Game I LeetCode

public boolean canJump(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int coverage = 0;
        for (int i=0; i<=coverage && i<A.length; i++) {
            coverage = Math.max(coverage, A[i] + i);
        }
        return coverage >= A.length - 1;
    }

Jump Game II LeetCode

Greedy

4 2 3 5 1 2 3 2 1 2

When we searching 4, the next step for us is calculating the largest coverage for "2 3 5 1".
Although the code is easy, it is not easy to get the clear solution for this kind of question.

The code is as follows:

public int jump(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       
        int steps = 0;
        int last = 0;
        int coverage = 0;
       
        for (int i=0; i<A.length; i++) {
            if (i > last) {
                steps++;
                last = coverage;
            }
            coverage = Math.max(coverage, A[i] + i);
        }
        return steps;
    }

Wildcard Match

http://decomplexify.blogspot.com/2014/04/wildcard-match-star-and-qmark-asymmetric.html

Here is the solution for it.

I cannot find any explanation is better than this.

  public boolean isMatch(String s, String p) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        String[] T = p.split("\\*+", -1);
        //special case: p has no star
        if (T.length == 1) {
            return matchedWithQMark(s, p, 0) && s.length()==p.length();
        }
       
        String head = T[0];
        String tail = T[T.length - 1];
       
        //Special case can't match first and last without overlapping
        if (head.length()+tail.length() > s.length() || !matchedWithQMark(s, head, 0) ||
            !matchedWithQMark(s, tail, s.length()-tail.length())) {
                return false;
            }
           
        int n = T.length;
       
        if (n==2) { return true; }
       
        //Do not match the first piece
        int start = head.length();
        int sLen = s.length() - tail.length();
       
        //index for the next piece
        int i=1;
        for (; i<T.length - 1; i++) {
            int tLen = T[i].length();
            boolean found = false;
            while (start <= sLen -tLen) {
                if (matchedWithQMark(s, T[i], start)) {
                    found = true;
                    break;
                }
                start++;
            }
            if (!found) {return false;}
           
            //updating the start index
            start += tLen;
        }
        return i>=T.length-1;
    }
   
    private boolean matchedWithQMark(String s, String t, int start) {
        if (start + t.length() > s.length()) return false;
       
        for (int j=0; start+j < s.length()&& j<t.length();++j) {
            if (s.charAt(start+j)!=t.charAt(j) && t.charAt(j)!='?') {
                return false;
            }
        }
        return true;
    }

Trapping Rain Water LeetCode

DP O(n) time O(n) space

public int trap(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       
       int[] leftMax = new int[A.length];
       int[] rightMax = new int[A.length];
     
       for (int i=0; i<A.length; i++) {
           if (i==0) {
               leftMax[i] = 0;
               rightMax[A.length-1-i] = 0;
           } else {
               leftMax[i] = Math.max(leftMax[i-1], A[i-1]);
               rightMax[A.length-i-1] = Math.max(rightMax[A.length-i], A[A.length-i]);
           }
       }
     
       int sum = 0;
       for (int i=0; i<A.length; i++) {
           int height = Math.min(leftMax[i], rightMax[i]);
           if (height>A[i]) {
               sum+=height-A[i];
           }
       }
       return sum;
    }

But we have to scan twice and spend O(n) space.


Here is a good solution for scanning only once and spend O(1) space.
public int trap(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       
      int l=0, r=A.length-1, res =0;
      while (l<r) {
          int height = Math.min(A[l], A[r]);
         
          if (height == A[l]) {
              l++;
              while (l<r && A[l]<height) {
                  res+=height-A[l];
                  l++;
              }
          } else {
              r--;
              while (l<r && A[r]<height) {
                  res+=height-A[r];
                  r--;
              }
          }
      }
      return res;
    }

First Missing Positive LeetCode

Counting sort.
Also here we need pay attention to this.

public int firstMissingPositive(int[] A) {
        if (A==null || A.length == 0) return 1;
     
        for (int i=0; i<A.length; i++) {
            if (A[i]!=i+1 && A[i] <=A.length && A[i] > 0 && A[A[i]-1]!=A[i]) {
             
                   /*It wont work
                 int temp = A[i];
                A[i] = A[A[i]-1];
                A[A[i]-1] = temp;
                 */
                 int temp = A[A[i]-1];
                A[A[i]-1] = A[i];
                A[i] = temp;
                i--;
            }
        }
     
        for (int i=0; i<A.length;i++) {
            if (A[i] != i+1) {
                return i+1;
            }
        }
        return A.length+1;
    }

LeetCode Search for a range

Find the first element
Find the second element

Find values from sorted array with duplicate elements;
public int[] searchRange(int[] A, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int[] result = new int[2];
        result[0] = findFirstElement(A, 0, A.length-1, target);
        result[1] = findSecondElement(A, 0, A.length-1, target);
        return result;
}

private int findFirstElement(int[] array, int low, int high, int target) {
   while (low <= high) {
       int mid = (low + high)/2;
       if (mid==low && array[mid] == target || array[mid]== target && array[mid-1] < array[mid]) {
           return mid;
       } else {
           if (array[mid] >= target) {
               high = mid - 1;
           } else {
               low = mid + 1;
           }
       }
   }
   return -1;
}

private int findSecondElement(int[] array, int low, int high, int target) {
   while (low <= high) {
       int mid = (low + high)/2;
       if (mid == high && array[mid] == target || array[mid]==target && array[mid] < array[mid+1]) {
           return mid;
       } else {
           if (array[mid] <= target) {
               low = mid + 1;
           } else {
               high = mid - 1;
           }
       }
   }
   return -1;
}

Unique Path I&II Leetcode

Without DP, trace back

public int uniquePaths(int m, int n) {
        return backtrack(0,0,m,n);
    }
   
    private int backtrack(int r, int c, int m, int n) {
        if (r==m-1 || c== n-1) {
            return 1;
        } else if (r >= m || c >= n) {
            return 0;
        }
        return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n);
    }

With DP.
 public int uniquePaths(int m, int n) {
        int[][] mat = new int[m+1][n+1];
        for (int i=0; i<=m; i++) {
            for (int j=0; j<=n; j++) {
                mat[i][j] = -1;
            }
        }
        return backtrack(0,0,m,n, mat);
    }
   
    private int backtrack(int r, int c, int m, int n, int[][] mat) {
        if (r==m-1 || c== n-1) {
            return 1;
        } else if (r >= m || c >= n) {
            return 0;
        }
        if (mat[r+1][c] == -1) {
            mat[r+1][c] = backtrack(r+1, c, m, n, mat);
        }
        if (mat[r][c+1] == -1) {
            mat[r][c+1] = backtrack(r, c+1, m, n, mat);
        }
        return mat[r+1][c] + mat[r][c+1];
    }

Unique Path II

Bottom-up Dynamic programming

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if (m==0) return 0;
        int n = obstacleGrid[0].length;
        int[][] mat = new int[m+1][n+1];
        mat[m-1][n] = 1;
       
        for (int r=m-1; r>=0; r--) {
            for (int c = n-1; c>=0; c--) {
                mat[r][c] = (obstacleGrid[r][c] == 1) ? 0 : mat[r+1][c] + mat[r][c+1];
            }
        }
        return mat[0][0];
    }

Min Stack LeetCode

Minor Space Optimization:

private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();
    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }

Binary Tree Maximum Path Sum Leetcode

public class Solution {
    int max;
    public int maxPathSum(TreeNode root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
    if(root==null)  return 0;
    max = root.val;
    int currentmax = maxPathHelper(root);
    return (max>currentmax) ? max : currentmax;
}
public int maxPathHelper(TreeNode root)  {
    if(root==null)  return 0;
    int leftmax = maxPathHelper(root.left);
    int rightmax = maxPathHelper(root.right);
    max = Math.max(root.val+leftmax+rightmax,max);
    max = Math.max(root.val+leftmax,max);
    max = Math.max(root.val+rightmax,max);
    return Math.max(Math.max(leftmax,rightmax)+root.val,root.val);
}
}