151. Max Points on a Line

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) {
            return 0;
        }

        HashMap<Double, Integer> map=new HashMap<Double, Integer>();
        int max = 1;

        for(int i = 0 ; i < points.length; i++) {
            // shared point changed, map should be cleared and server the new point
            map.clear();

            // maybe all points contained in the list are same points,and same points' k is
            // represented by Integer.MIN_VALUE
            map.put((double)Integer.MIN_VALUE, 1);

            int dup = 0;
            for(int j = i + 1; j < points.length; j++) {
                if (points[j].x == points[i].x && points[j].y == points[i].y) {
                    dup++;
                    continue;
                }

                // look 0.0+(double)(points[j].y-points[i].y)/(double)(points[j].x-points[i].x)
                // because (double)0/-1 is -0.0, so we should use 0.0+-0.0=0.0 to solve 0.0 !=-0.0
                // problem

                // if the line through two points are parallel to y coordinator, then K(slop) is
                // Integer.MAX_VALUE
                double key=points[j].x - points[i].x == 0 ?
                    Integer.MAX_VALUE :
                    0.0 + (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);

                if (map.containsKey(key)) {
                    map.put(key, map.get(key) + 1);
                } else {
                    map.put(key, 2);
                }
            }

            for (int temp: map.values()) {
                // duplicate may exist
                if (temp + dup > max) {
                    max = temp + dup;
                }
            }

        }
        return max;
    }
}

150. Word Ladder II

public class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end, Set<String> dict) {

dict.add(end);

// Key: the dictionary string; Value: HashSet<ArrayList<String>>
Map<String, HashSet<ArrayList<String>>> map = new HashMap<String, HashSet<ArrayList<String>>>();
Queue<String> queue = new LinkedList<String>();

ArrayList<String> startPath = new ArrayList<String>();
startPath.add(start);
HashSet<ArrayList<String>> startSet = new HashSet<ArrayList<String>>();
startSet.add(startPath);
queue.offer(start);
map.put(start, startSet);

ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();

while (!queue.isEmpty()) {
String str = queue.poll();

if (str.equals(end)) {
ret.addAll(map.get(end));
return ret;
}

for (int i = 0; i < str.length(); i++) {
for (int j = 0; j <= 25; j++) {
// transform it into another word
String newStr = replace(str, i, (char) ('a' + j));

// if a new word is explored
if (dict.contains(newStr)) {
if (!map.containsKey(newStr)) {
// construct a new path set
HashSet<ArrayList<String>> prevSet = map.get(str);
HashSet<ArrayList<String>> newSet = new HashSet<ArrayList<String>>();
for (ArrayList<String> path : prevSet) {
ArrayList<String> newPath = new ArrayList<String>(path);
newPath.add(newStr);
newSet.add(newPath);
}

map.put(newStr, newSet);
queue.offer(newStr);
} else {
HashSet<ArrayList<String>> prevSet = map.get(str);
HashSet<ArrayList<String>> newSet = map.get(newStr);

Iterator<ArrayList<String>> prevIt = prevSet
.iterator();
Iterator<ArrayList<String>> newIt = newSet
.iterator();

// increase the path set
if (prevIt.next().size() + 1 == newIt.next().size()) {
for (ArrayList<String> path : prevSet) {
ArrayList<String> newPath = new ArrayList<String>(path);
newPath.add(newStr);
newSet.add(newPath);
// queue.offer(newStr); // will cause TLE!!!
}
}
}
}
}
}
}

return ret; // return an empty set
}

// replace the index of the given string with the given char
private String replace(String str, int index, char c) {
StringBuilder sb = new StringBuilder(str);
sb.setCharAt(index, c);
return sb.toString();
}
}

149. Valid Number

public class Solution {
    public boolean isNumber(String s) {
        int len = s.length();
     
        int i = 0, e = len - 1;
        while (i <= e && Character.isWhitespace(s.charAt(i))) i++;
        if (i > len - 1) return false;
        while (e >= i && Character.isWhitespace(s.charAt(e))) e--;
     
        // skip leading +/-
        if (s.charAt(i) == '+' || s.charAt(i) == '-') i++;
        boolean num = false; // is a digit
        boolean dot = false; // is a '.'
        boolean exp = false; // is a 'e'
     
        while (i <= e) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = true;
            }
            else if (c == '.') {
                if(exp || dot) return false;
                dot = true;
            }
            else if (c == 'e') {
                if(exp || num == false) return false;
                exp = true;
                num = false;
            }
            else if (c == '+' || c == '-') {
                if (s.charAt(i - 1) != 'e') return false;
            }
            else {
                return false;
            }
            i++;
        }
        return num;
    }
}

148. Wildcard Matching

public class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0;
        int j = 0;
        int star = -1;
        int mark = -1;
        while (i < s.length()) {
            if (j < p.length()
                    && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
                i++;
                j++;
            } else if (j < p.length() && p.charAt(j) == '*') {
                star = j++;
                mark = i;
            } else if (star != -1) {
                j = star + 1;
                i = ++mark;
            } else {
                return false;
            }
        }
        while (j < p.length() && p.charAt(j) == '*') {
            j++;
        }
        return j == p.length();
    }
}

147. LRU Cache

import java.util.LinkedHashMap;

public class LRUCache {
   
    LinkedHashMap<Integer, Integer> map;
int capacity;
   
    public LRUCache(int capacity) {
        map = new LinkedHashMap<Integer, Integer> (capacity);
   this.capacity = capacity;
    }
   
    public int get(int key) {
        if(map.containsKey(key)){
            int val = map.get(key);
       map.remove(key);
       map.put(key, val);
       return val;
        }
        return -1;
    }
   
    public void set(int key, int value) {
        if(map.containsKey(key)){
            map.remove(key);
            map.put(key, value);
        }else{
            if(map.size() == capacity){
                int firstKey = map.keySet().iterator().next();
                map.remove(firstKey);
            }
            map.put(key, value);
        }
    }
}

146. Surrounded Regions

public class Solution {
    private Queue<Integer> queue = new LinkedList<Integer>();
   
    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) return;
       
        int row = board.length;
        int col = board[0].length;

        for (int j = 0; j < col; j++) {
            if (board[0][j] == 'O') bfs(board, 0, j);
        }

        for (int j = 0; j < col; j++) {
            if (board[row - 1][j] == 'O') bfs(board, row - 1, j);
        }

        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') bfs(board, i, 0);
        }

        for (int i = 0; i < row; i++) {
            if (board[i][col - 1] == 'O') bfs(board, i, col - 1);
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'P') board[i][j] = 'O';
            }
        }
    }
   
    public void bfs(char[][] board, int i, int j) {
        int col = board[0].length;

        fill(board, i, j);
       
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int x = cur / col;
            int y = cur % col;

            fill(board, x - 1, y);
            fill(board, x + 1, y);
            fill(board, x, y - 1);
            fill(board, x, y + 1);
        }
    }
   
    public void fill(char[][] board, int i, int j) {
        int row = board.length;
        int col = board[0].length;
       
        if (i < 0 || i >= row || j < 0 || j >= col || board[i][j] != 'O') return;

        queue.offer(i * col + j);
        board[i][j] = 'P';
    }
}

145. Reverse Words in a String

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        String[] array = s.split(" ");
        StringBuilder sb = new StringBuilder();

        for (int i = array.length - 1; i >= 0; i--) {
            if (!array[i].equals("")) {
                sb.append(array[i]).append(" ");
            }
        }

        //remove the last " "
        return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
    }
}

144. Text Justification

public class Solution {
    public ArrayList<String> fullJustify(String[] words, int L) {
        ArrayList<String> ret = new ArrayList<String>();
        int wordsLen = words.length;    // 单词数组的长度
        int curWordIdx = 0;     // 处理第i个单词
        while(curWordIdx < wordsLen){        // 处理完所有单词后退出
            int charLen = 0;  // 当前行累积的字符数量
            int probeWordIdx = curWordIdx;
            while(probeWordIdx<wordsLen && charLen+words[probeWordIdx].length()<=L){  // 贪婪加入尽可能多的单词
                charLen += ((words[probeWordIdx++]).length()+1);        // 累积单词长度和至少要有一个空格
            }
            if(probeWordIdx-curWordIdx == 1){       // tmpWordIdx-curWordIdx: 该行放入单词的数目，如果只有一个单词要特殊处理
                String tmp = words[curWordIdx]; // 唯一的那个单词
                tmp = addSpace(tmp, L-words[curWordIdx].length());  // 那个单词后面都接上空格
                ret.add(tmp);
                curWordIdx = probeWordIdx;      // 更新curWordIdx，因为已经处理好当前行了
                continue;
            }
           
            // tmpWordIdx-curWordIdx: 该行放入单词的数目，也就是紧接的空格的数量（因为每个单词后接一个空格）
            // wordCharLen：当前行所有由单词组成的字符数量（不包括空格）
            int wordCharLen = charLen - (probeWordIdx-curWordIdx);      
            //meanSpace: 平均每个单词后的空格,tmpWordIdx<wordsLen 表示不是最后一行
            int meanSpace = probeWordIdx<wordsLen ? (L-wordCharLen)/(probeWordIdx-curWordIdx-1) : 1;
            //leftSpace: 多余的空格
            int leftSpace = probeWordIdx<wordsLen ? (L-wordCharLen)%(probeWordIdx-curWordIdx-1) : L-wordCharLen-(probeWordIdx-curWordIdx-1);
            String tmp = new String();
            for(int k=curWordIdx; k<probeWordIdx-1; k++){    // 对当前行最后一个单词特殊处理
                tmp += words[k];
                tmp = addSpace(tmp, meanSpace);
                if(probeWordIdx<wordsLen && leftSpace>0){ // 因为居中对齐
                    tmp += " ";
                    leftSpace--;
                }
            }
            tmp += words[probeWordIdx-1];       // 处理当前行的最后一个单词
            if(leftSpace > 0){       // 因为左对齐，所以在最后补上剩下的空格
                tmp = addSpace(tmp, leftSpace);
            }
            ret.add(tmp);
            curWordIdx = probeWordIdx;      // 处理下一行的要处理的单词
        }
        return ret;
    }
   
    public static String addSpace(String s, int count){
        for(int i=1; i<=count; i++){
            s += " ";
        }
        return s;
    }
}

143. String to Integer (atoi)

public class Solution {
    public int atoi(String str) {
   if (str == null || str.length() < 1)
   return 0;

   // trim white spaces
   str = str.trim();

   char flag = '+';

   // check negative or positive
   int i = 0;
   if (str.charAt(0) == '-') {
   flag = '-';
   i++;
   } else if (str.charAt(0) == '+') {
   i++;
   }
 
   // use double to store result
   double result = 0;

   // calculate value
   while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
   result = result * 10 + (str.charAt(i) - '0');
   i++;
   }

   if (flag == '-') result = -result;

   // handle max and min
   if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE;

   return (int) result;
    }
}

142. Word Break II

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> result = new ArrayList<String>();
         if (s == null || dict.size() <= 0) {
             return result;
         }
         int length = s.length();

         boolean[][] seg = new boolean[length][length + 1];
         for (int len = 1; len <= length; len++) {
             for (int i = 0; i < length - len + 1; i++) {
                 String t = s.substring(i, i + len);
                 if (dict.contains(t)) {
                     seg[i][len] = true;
                     continue;
                 }
                 for (int k = 1; k < len; k++) {
                     if (seg[i][k] && seg[i + k][len - k]) {
                         seg[i][len] = true;
                         break;
                     }
                 }
             }
         }
         if (!seg[0][length]) {
             return result;
         }

         int depth = 0;
         dfs(s, seg, 0, length, depth, result, new StringBuffer(), dict);

         return result;
     }

     private static void dfs(String s, boolean[][] seg, int start, int length,
             int depth, ArrayList<String> result, StringBuffer sb, Set<String> dict) {
         if (depth == length) {
             String t = sb.toString();
             result.add(t.substring(0, t.length() - 1));
             return;
         }

         for (int len = 1; len <= length; len++) {
             if (seg[start][len]) {
                 String t = s.substring(start, start + len);
                 if(!dict.contains(t)){
                     continue;
                 }
                 int beforeAddLen = sb.length();
                 sb.append(t).append(" ");
                 dfs(s, seg, start + len, length, start + len, result, sb, dict);
                 sb.delete(beforeAddLen, sb.length());
             }
         }
    }
}

141. Decode Ways

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
       
        if (n==0) return 0;
       
        int[] dp = new int[n+1];
       
        dp[0] = 1;
        if (isValid(s.substring(0,1))) dp[1] = 1;
        else dp[1] = 0;
       
        for (int i=2; i<=n; i++) {
            if (isValid(s.substring(i-1,i))) dp[i] = dp[i-1];
            if (isValid(s.substring(i-2,i))) dp[i] += dp[i-2];
        }
       
        return dp[s.length()];
    }
   
    public boolean isValid(String s) {
        if (s.charAt(0)=='0') return false;
        int code = Integer.parseInt(s);
        return code>=1 && code<=26;
    }
}

140. Divide Two Integers

public class Solution {

    public int divide(int dividend, int divisor) {
        boolean negative = (dividend > 0 && divisor < 0) ||
            (dividend < 0 && divisor > 0);

        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);
        int ans = 0;

        while (a >= b) {
            int shift = 0;
            while ((b << shift) <= a) {
                shift++;
            }
            ans += 1 << (shift-1);
            a = a - (b << (shift-1));
        }

        return negative ? -ans : ans;
    }
}

139. Median of Two Sorted Arrays

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int m = A.length;
        int n = B.length;
       
        if ((m+n)%2==1) return kthEle(A, B, (m+n)/2+1, 0, m-1);
        else return (kthEle(A, B, (m+n)/2, 0, m-1)+kthEle(A, B, (m+n)/2+1, 0, m-1))/2.0;
    }
   
    public int kthEle(int A[], int B[], int k, int low, int high) {
        int m = A.length;
        int n = B.length;
       
        if (low>high) return kthEle(B, A, k, 0, n-1);
       
        int i = (low+high)/2;
        int j = k-1-i-1;
       
        if ((j<0 || (j<n && A[i]>=B[j])) && (j+1>=n || j+1>=0 && (A[i]<=B[j+1]))) return A[i];
        else if (j<0 || (j+1<n && A[i]>B[j+1])) return kthEle(A, B, k, low, i-1);
        else return kthEle(A, B, k, i+1, high);
    }
}

138. Minimum Window Substring

public class Solution {
    public String minWindow(String S, String T) {
        int[] needToFind = new int[256];
        int[] hasFound = new int[256];
       
        for (int i=0; i<T.length(); i++) {
            needToFind[T.charAt(i)]++;
        }
       
        int count = 0;
        int minWindowSize = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        String minWindow = "";
       
        for (end=0; end<S.length(); end++) {
            if (needToFind[S.charAt(end)]==0) continue;
           
            char c = S.charAt(end);
            hasFound[c]++;
           
            if (hasFound[c]<=needToFind[c]) count++;
           
            if (count==T.length()) {
                while (needToFind[S.charAt(start)]==0 || hasFound[S.charAt(start)]>needToFind[S.charAt(start)]) {
                    if (hasFound[S.charAt(start)]>needToFind[S.charAt(start)]) hasFound[S.charAt(start)]--;
                    start++;
                }
               
                if (end-start+1<minWindowSize) {
                    minWindowSize = end-start+1;
                    minWindow = S.substring(start, end+1);
                }
            }
        }
       
        return minWindow;
    }
}

136. Palindrome Partitioning II

public class Solution {
    public int minCut(String s) {
        int len = s.length();
        int[] cut = new int[len+1];
        cut[len] = 0;
        boolean[][] table = createTable(s);
       
        for (int i=len-1; i>=0; i--) {
            cut[i] = len-i;
            for (int j=i; j<len; j++) {
                if (table[i][j]) cut[i] = Math.min(cut[i], cut[j+1]+1);
            }
        }
       
        return cut[0]-1;
    }
   
    public boolean[][] createTable(String s) {
        boolean[][] table = new boolean[s.length()][s.length()];
        for (int i=0; i<s.length(); i++) {
            table[i][i] = true;
        }
       
        for (int i=0; i<s.length(); i++) {
            int l = i-1;
            int r = i;
            while (l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)) {
                table[l--][r++] = true;
            }
           
            l = i-1;
            r = i+1;
            while (l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)) {
                table[l--][r++] = true;
            }
        }
       
        return table;
    }
}

136. Substring with Concatenation of All Words

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> res = new ArrayList<Integer> ();
        HashMap<String, Integer> toFind = new HashMap<String, Integer> ();
        HashMap<String, Integer> found = new HashMap<String, Integer> ();
       
        int m = L.length;
        int n = L[0].length();
       
        for (int i=0; i<m; i++) {
            if (!toFind.containsKey(L[i])) {
                toFind.put(L[i], 1);
            } else {
                toFind.put(L[i], toFind.get(L[i])+1);
            }
        }
       
        for (int i=0; i<=S.length()-m*n; i++) {
            found.clear();
            int j;
            for (j=0; j<m; j++) {
                int k = i+j*n;
                String substr = S.substring(k, k+n);
                if (!toFind.containsKey(substr)) break;
                if (!found.containsKey(substr)) {
                    found.put(substr, 1);
                } else {
                    found.put(substr, found.get(substr)+1);
                }
                if (found.get(substr)>toFind.get(substr)) break;
            }
            if (j==m) res.add(i);
        }
       
        return res;
    }
}

135. Word Ladder

public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
        if (dict.size()==0) return 0;
       
        LinkedList<String> wordQueue = new LinkedList<String> ();
        LinkedList<Integer> stepQueue = new LinkedList<Integer> ();
       
        wordQueue.add(start);
        stepQueue.add(1);
       
        while (!wordQueue.isEmpty()) {
            String curWord = wordQueue.pop();
            Integer curStep = stepQueue.pop();
           
            if (curWord.equals(end)) return curStep;
           
            for (int i=0; i<curWord.length(); i++) {
                char[] curCharArr = curWord.toCharArray();
                for (char c='a'; c<='z'; c++) {
                    curCharArr[i] = c;
                    String newWord = new String(curCharArr);
                    if (dict.contains(newWord)) {
                        wordQueue.add(newWord);
                        stepQueue.add(curStep+1);
                        dict.remove(newWord);
                    }
                }
            }
        }
       
        return 0;
    }
}

134. Candy

public class Solution {
    public int candy(int[] ratings) {
        if (ratings.length==0 || ratings==null) return 0;
       
        int[] count = new int[ratings.length];
        Arrays.fill(count, 1);
        int sum = 0;
       
        for (int i=1; i<count.length; i++) {
            if (ratings[i]>ratings[i-1]) {
                count[i] = count[i-1] +1;
            }
        }
       
        for (int i=count.length-1; i>=1; i--) {
            sum += count[i];
            if (ratings[i-1]>ratings[i] && count[i-1]<=count[i]) {
                count[i-1] = count[i]+1;
            }
        }
       
        sum += count[0];
       
        return sum;
    }
}

133. Two Sum

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> hash = new HashMap<Integer, Integer> ();
        int[] res = new int[2];
       
        for (int i=0; i<numbers.length; i++) {
            if (hash.containsKey(numbers[i])) {
                res[0] = hash.get(numbers[i])+1;
                res[1] = i+1;
                return res;
            } else if (!hash.containsKey(target-numbers[i])) {
                hash.put(target-numbers[i], i);
            }
        }
       
        return res;
    }
}

132. Interleaving String

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int l1 = s1.length();
        int l2 = s2.length();
        int l3 = s3.length();
       
        if (l1+l2!=l3) return false;
       
        boolean[][] table = new boolean[l1+1][l2+1];
       
        for (int i=0; i<=l1; i++) {
            for (int j=0; j<=l2; j++) {
                if (i==0 && j==0) {
                    table[i][j] = true;
                } else if (i==0 && s3.charAt(j-1)==s2.charAt(j-1)) {
                    table[i][j]=table[i][j-1];
                } else if (j==0 && s3.charAt(i-1)==s1.charAt(i-1)) {
                    table[i][j]=table[i-1][j];
                }
               
                if (i!=0 && j!=0) {
                    if (s3.charAt(i+j-1)==s1.charAt(i-1) && s3.charAt(i+j-1)!=s2.charAt(j-1)) {
                        table[i][j]=table[i-1][j];
                    } else if (s3.charAt(i+j-1)==s2.charAt(j-1) && s3.charAt(i+j-1)!=s1.charAt(i-1)) {
                        table[i][j]=table[i][j-1];
                    } else if (s3.charAt(i+j-1)==s2.charAt(j-1) && s3.charAt(i+j-1)==s1.charAt(i-1)) {
                        table[i][j]=table[i][j-1] || table[i-1][j];
                    }
                }
            }
        }
       
        return table[l1][l2];
    }
}

131. Longest Valid Parentheses

public class Solution {
    public int longestValidParentheses(String s) {
        if (s.length()<2) return 0;
       
        Stack<Integer> stack = new Stack<Integer> ();
       
        int max = 0;
        int last = -1;
       
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i)=='(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    last = i;
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        max = Math.max(max, i-last);
                    } else {
                        max = Math.max(max, i-stack.peek());
                    }
                }
            }
        }
       
        return max;
    }
}

130. Simplify Path

public class Solution {
    public String simplifyPath(String path) {
        if (path.length()==0) return path;
       
        String[] split = path.split("/");
        LinkedList<String> stack = new LinkedList<String> ();
       
        for (String s:split) {
            if (s.length()==0 || s.equals(".")) {
                continue;
            } else if (s.equals("..")) {
                if (!stack.isEmpty()) stack.pop();
            } else stack.push(s);
        }
       
        if (stack.isEmpty()) stack.push("");
       
        String res = "";
       
        while (!stack.isEmpty()) res += "/"+stack.removeLast();
       
        return res;
    }
}

129. Word Search

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (word==null || word.length()==0) return true;
       
        int row = board.length;
        int col = board[0].length;
        char c = word.charAt(0);
       
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (board[i][j]==c) {
                    board[i][j] = ' ';
                    if (dfs(board, word.substring(1), i, j)) return true;
                    board[i][j] = c;
                }
            }
        }
       
        return false;
    }
   
    public boolean dfs(char[][] board, String word, int x, int y) {
        if (word.length()==0) return true;
        int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
        char c = word.charAt(0);
       
        for (int[] d: dir) {
            int i = x+d[0];
            int j = y+d[1];
            if (i>=0 && i<board.length && j>=0 && j<board[0].length && board[i][j]==c) {
                board[i][j] = ' ';
                if (dfs(board, word.substring(1), i, j)) return true;
                board[i][j] = c;
            }
        }
       
        return false;
    }
}

128. Binary Tree Maximum Path Sum

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int max;
   
    public int maxPathSum(TreeNode root) {
        max = Integer.MIN_VALUE;
        dfs(root);
        return max;
    }
   
    public int dfs(TreeNode root) {
        if (root==null) return 0;
        int l = dfs(root.left);
        int r = dfs(root.right);
        int sum = root.val;
       
        if (l>0) sum+=l;
        if (r>0) sum+=r;
       
        max = Math.max(max, sum);
       
        return Math.max(l, r)>0? Math.max(l, r)+root.val: root.val;
    }
}

127. Regular Expression Matching

public class Solution {
    public boolean isMatch(String s, String p) {
        return isM(s, p, 0, 0);
    }
   
    public boolean isM(String s, String p, int i, int j) {
        if (j>=p.length()) return i>=s.length();
       
        if (j==p.length()-1) return (i==s.length()-1) && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.');
       
        if (j+1<p.length() && p.charAt(j+1) != '*') {
            if (i==s.length()) return false;
            if (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.') return isM(s, p, i+1, j+1);
            else return false;
        }
       
        while (i<s.length() && j<p.length() && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.')) {
            if (isM(s, p, i, j+2)) return true;
            i++;
        }
       
        return isM(s, p, i, j+2);
    }
}

126. Evaluate Reverse Polish Notation

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<String> ();
       
        for (int i=0; i<tokens.length; i++) {
            if (tokens[i].equals("+")) {
                int val = Integer.parseInt(stack.pop()) + Integer.parseInt(stack.pop());
                stack.push(String.valueOf(val));
            } else if (tokens[i].equals("-")) {
                int v1 = Integer.parseInt(stack.pop());
                int v2 = Integer.parseInt(stack.pop());
                int val = v2-v1;
                stack.push(String.valueOf(val));
            } else if (tokens[i].equals("*")) {
                int val = Integer.parseInt(stack.pop()) * Integer.parseInt(stack.pop());
                stack.push(String.valueOf(val));
            } else if (tokens[i].equals("/")) {
                int v1 = Integer.parseInt(stack.pop());
                int v2 = Integer.parseInt(stack.pop());
                int val = v2/v1;
                stack.push(String.valueOf(val));
            } else stack.push(tokens[i]);
        }
       
        return Integer.parseInt(stack.pop());
    }
}

125. Reorder List

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
       
        while (fast!=null && fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
       
        ListNode preReverse = slow;
        if (preReverse==null) return;
       
        ListNode preHead = preReverse.next;
        if (preHead==null) return;
       
        ListNode preCur = preHead.next;
        ListNode cur = preHead.next;
       
        preHead.next = null;
       
        while (cur!=null) {
            cur = cur.next;
            preCur.next = preHead;
            preHead = preCur;
            preCur = cur;
        }
       
        preReverse.next = preHead;
       
        preReverse.next = null;
       
        cur = head;
       
        while (cur!=null && preHead!=null) {
            ListNode temp = cur.next;
            cur.next = preHead;
            preHead = preHead.next;
            cur.next.next = temp;
            cur = temp;
        }
    }
}

124. Sort List

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head==null || head.next==null) return head;
       
        ListNode fast = head;
        ListNode slow = head;
        ListNode preSlow = head;
       
        while (fast!=null && fast.next!=null) {
            fast = fast.next.next;
            preSlow = slow;
            slow = slow.next;
        }
       
        preSlow.next = null;
       
        ListNode first = sortList(head);
        ListNode second = sortList(slow);
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
       
        while (first!=null && second!=null) {
            if (first.val<=second.val) {
                cur.next = first;
                first = first.next;
            } else if (second.val<first.val) {
                cur.next = second;
                second = second.next;
            }
            cur = cur.next;
        }
       
        while (first!=null) {
            cur.next = first;
            first = first.next;
            cur = cur.next;
        }
       
        while (second!=null) {
            cur.next = second;
            second = second.next;
            cur = cur.next;
        }
       
        return dummy.next;
    }
}

123. Insert Interval

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> res = new ArrayList<Interval> ();
        Interval merge = newInterval;
       
        for (int i=0; i<intervals.size(); i++) {
            Interval cur = intervals.get(i);
           
            if (cur.end<merge.start) res.add(cur);
            else if (cur.start>merge.end) {
                res.add(merge);
                merge = cur;
            } else merge = new Interval(Math.min(cur.start, merge.start), Math.max(cur.end, merge.end));
        }
        res.add(merge);
       
        return res;
    }
}

122. Multiply Strings

public class Solution {
    public String multiply(String num1, String num2) {
        String s1 = new StringBuilder(num1).reverse().toString();
        String s2 = new StringBuilder(num2).reverse().toString();
       
        int[] d = new int[s1.length()+s2.length()];
       
        for (int i=0; i<s1.length(); i++) {
            for (int j=0; j<s2.length(); j++) {
                d[i+j] += (s1.charAt(i)-'0')*(s2.charAt(j)-'0');
            }
        }
       
        StringBuilder sb = new StringBuilder();
       
        for (int i=0; i<d.length; i++) {
            int digit = d[i]%10;
            int carry = d[i]/10;
            if (i+1<d.length) d[i+1] += carry;
            sb.insert(0, digit);
        }
       
        while (sb.charAt(0)=='0' && sb.length()>1) {
            sb.deleteCharAt(0);
        }
       
        return sb.toString();
    }
}

121. Restore IP Addresses

public class Solution {
    public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> res = new ArrayList<String> ();
       
        if (s.length()>12 || s.length()<4) return res;
       
        dfs(s, res, "", 0);
       
        return res;
    }
   
    public void dfs(String s, ArrayList<String> res, String temp, int count) {
        if (count==3 && isValid(s)) {
            res.add(temp+s);
            return;
        }
       
        for (int i=1; i<4&&i<s.length(); i++) {
            String substr = s.substring(0, i);
            if (isValid(substr)) dfs(s.substring(i), res, temp+substr+".", count+1);
        }
    }
   
    public boolean isValid(String s) {
        if (s.charAt(0)=='0') return s.equals("0");
        int num = Integer.parseInt(s);
        return num<=255 && num>=0;
    }
}

120. Merge Intervals

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<Interval> ();
       
        if (intervals.size()==0) return res;
       
        //sort by start
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval o1, Interval o2) {
                return o1.start-o2.start;
            }
        });
       
        Interval ref = intervals.get(0);
       
        for (int i=1; i<intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if (cur.end<ref.start) res.add(cur);
            else if (cur.start>ref.end) {
                res.add(ref);
                ref = cur;
            } else ref = new Interval(Math.min(ref.start, cur.start), Math.max(ref.end, cur.end));
        }
        res.add(ref);
       
        return res;
    }
}

119. Word Break

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        boolean[] canbreak = new boolean[s.length()+1];
        canbreak[0] = true;
       
        for (int i=0; i<s.length(); i++) {
            if (canbreak[i]==false) continue;
           
            for (String s_dict:dict) {
                int len = s_dict.length();
                int end = i+len;
                if (end>s.length()) continue;
                if (s.substring(i,end).equals(s_dict)) canbreak[end] = true;
            }
        }
       
        return canbreak[s.length()];
    }
}

118. Longest Palindromic Substring

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length()==0) return "";

int maxdiff = 0;
int maxindex = 0;
boolean odd = true;
int length = s.length();

for (int i=0; i<length; i++) {
int diff = 0;

if (i+1<length && s.charAt(i)==s.charAt(i+1)) {
diff = 0;
while (i-diff>=0 && i+1+diff<length && s.charAt(i-diff)==s.charAt(i+1+diff)) {
diff++;
}
if (diff-1>=maxdiff) {
maxdiff = diff-1;
maxindex = i;
odd = false;
}
}

diff = 0;
while (i-diff>=0 && i+diff<length && s.charAt(i-diff)==s.charAt(i+diff)) {
diff++;
}
if (diff-1>maxdiff) {
maxdiff = diff-1;
maxindex = i;
odd = true;
}
}

if (odd) return s.substring(maxindex-maxdiff, maxindex+maxdiff+1);
else return s.substring(maxindex-maxdiff, maxindex+maxdiff+2);
    }
}

117. Sudoku Solver

public class Solution {
    public void solveSudoku(char[][] board) {
        ArrayList<Integer> empty = new ArrayList<Integer> ();

for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
if (board[i][j]=='.') empty.add(i*9+j);
}
}

int length = empty.size();

dfs(empty, board, 0, length);
}

public boolean dfs(ArrayList<Integer> empty, char[][] board, int cur, int length) {
if (cur==length) return true;

int index = empty.get(cur);
int row = index/9;
int col = index%9;

for (int v=1; v<=9; v++) {
if (isvalid(v, row, col, board)) {
board[row][col] = (char) (v+'0');
if (dfs(empty, board, cur+1, length)) return true;
board[row][col] = '.';
}
}
return false;
}

public boolean isvalid(int v, int row, int col, char[][] board) {
for (int i=0; i<9; i++) {
if (board[row][i]-'0'==v) return false;
if (board[i][col]-'0'==v) return false;
int row_s = 3*(row/3)+i/3;
int col_s = 3*(col/3)+i%3;
if (board[row_s][col_s]-'0'==v) return false;
}
return true;
}
}

116. Largest Rectangle in Histogram

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height==null || height.length==0) return 0;
       
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
       
        for (int i=0; i<=height.length; i++) {
            int curt = (i==height.length)?-1:height[i];
            while (!stack.isEmpty() && curt<=height[stack.peek()]) {
                int h = height[stack.pop()];
                int w = stack.isEmpty()?i:i-stack.peek()-1;
                max = Math.max(max, h*w);
            }
            stack.push(i);
        }
       
        return max;
    }
}

115. Implement strStr()

public class Solution {
    public String strStr(String haystack, String needle) {
        int index = haystack.indexOf(needle);
        if (index<0) return null;
        else return haystack.substring(index);
    }
}

114. Permutation Sequence

public class Solution {
    public String getPermutation(int n, int k) {
        int[] num = new int[n];
        int percount = 1;
       
        for (int i=0; i<n; i++) {
            num[i] = i+1;
            percount *= (i+1);
        }
       
        k--; //index is 0 based.
        StringBuilder sb = new StringBuilder();
       
        for (int i=0; i<n; i++) {
            percount /= (n-i);
            int index = k/percount;
            sb.append(num[index]);
           
            for (int j=index; j<n-i-1; j++) {
                num[j] = num[j+1];
            }
           
            k %= percount;
        }
       
        return sb.toString();
    }
}

113. Maximal Rectangle

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if (row==0) return 0;
       
        int col = matrix[0].length;
       
        int[][] ones = new int[row][col];
        int max = 0;
       
        for (int i=0; i<row; i++) {
            for(int j=0; j<col; j++) {
                if (matrix[i][j]=='1') {
                    if (j==0) ones[i][j] = 1;
                    else ones[i][j] = ones[i][j-1]+1;
                }
            }
        }
       
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (ones[i][j]!=0) {
                    int minI = i;
                    int minWidth = ones[i][j];
                    while (minI>=0) {
                        minWidth = Math.min(minWidth, ones[minI][j]);
                        int area = minWidth*(i-minI+1);
                        max = Math.max(max, area);
                        minI--;
                    }
                }
            }
        }
       
        return max;
    }
}

112. Sqrt(x)

public class Solution {
    public int sqrt(int x) {
        if (x<=0) return 0;
        if (x==1) return 1;
       
        int mid = x/2;
       
        while (mid*mid>x || mid>46340) mid = (mid+x/mid)/2;
       
        return mid;
    }
}

111. Rotate List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if (head==null) return null;
       
        ListNode front = head;
        ListNode back = head;
        ListNode end = head;
       
        while (front.next!=null) front = front.next;
       
        end = front;
        front.next = head;
        front = head;
       
        for (int i=0; i<n; i++) {
            front = front.next;
        }
       
        while (front!=end) {
            front = front.next;
            back = back.next;
        }
       
        ListNode rotateHead = back.next;
        back.next = null;
       
        return rotateHead;
    }
}

110. Clone Graph

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */

import java.util.Hashtable;

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node==null) return null;
       
        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode> ();
        Hashtable<UndirectedGraphNode, UndirectedGraphNode> hashtable = new Hashtable<UndirectedGraphNode, UndirectedGraphNode> ();
       
        UndirectedGraphNode res = new UndirectedGraphNode(node.label);
        hashtable.put(node, res);
        queue.add(node);
       
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.remove();
            UndirectedGraphNode curclone = hashtable.get(cur);
           
            ArrayList<UndirectedGraphNode> neighbors = (ArrayList<UndirectedGraphNode>) cur.neighbors;
           
            for (int i=0; i<neighbors.size(); i++) {
                UndirectedGraphNode neighbor = neighbors.get(i);
                if (hashtable.containsKey(neighbor)) {
                    UndirectedGraphNode neighborclone = hashtable.get(neighbor);
                    curclone.neighbors.add(neighborclone);
                } else {
                    UndirectedGraphNode neighborclone = new UndirectedGraphNode(neighbor.label);
                    curclone.neighbors.add(neighborclone);
                    queue.add(neighbor);
                    hashtable.put(neighbor, neighborclone);
                }
            }
        }
       
        return res;
    }
}

109. Scramble String

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length()!=s2.length()) return false;
       
        if (s1.length()==1 && s2.length()==1) return s1.charAt(0)==s2.charAt(0);
       
        char[] s1ch = s1.toCharArray();
        char[] s2ch = s2.toCharArray();
       
        Arrays.sort(s1ch);
        Arrays.sort(s2ch);
       
        if (!new String(s1ch).equals(new String(s2ch))) return false;
       
        for (int i=1; i<s1.length(); i++) {
            String s11 = s1.substring(0, i);
            String s12 = s1.substring(i);
            String s21 = s2.substring(0, i);
            String s22 = s2.substring(i);
           
            if (isScramble(s11,s21) && isScramble(s12,s22)) return true;
           
            s21 = s2.substring(0, s2.length()-i);
            s22 = s2.substring(s2.length()-i);
           
            if (isScramble(s11,s22) && isScramble(s12,s21)) return true;
        }
       
        return false;
    }
}

108. Best Time to Buy and Sell Stock III

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length<2) return 0;
       
        int res = 0;
        int[] before = new int[prices.length];
        int[] after = new int[prices.length];
       
        before[0] = 0;
        after[prices.length-1] = 0;
       
        int min = prices[0];
        int max = prices[prices.length-1];
       
        for (int i=1; i<prices.length; i++) {
            if (prices[i]>=min) before[i] = Math.max(prices[i]-min, before[i-1]);
            else {
                min = prices[i];
                before[i] = before[i-1];
            }
        }
       
        for (int i=prices.length-2; i>=0; i--) {
            if (prices[i]<=max) after[i] = Math.max(max-prices[i], after[i+1]);
            else {
                max = prices[i];
                after[i] = after[i+1];
            }
        }
       
        for (int i=0; i<prices.length; i++) {
            res = Math.max(res, before[i]+after[i]);
        }
       
        return res;
    }
}

107. First Missing Positive

public class Solution {
    public int firstMissingPositive(int[] A) {
        int i = 0;
       
        while (i<A.length) {
            if (A[i]>0 && A[i]<A.length+1 && A[i]!=i+1 && A[i]!=A[A[i]-1]) swap(A, i, A[i]-1);
            else i++;
        }
       
        for (i=0; i<A.length; i++) {
            if (A[i]!=i+1) return i+1;
        }
       
        return A.length+1;
    }
   
    public void swap(int[] A, int a, int b) {
        int temp = A[a];
        A[a] = A[b];
        A[b] = temp;
    }
}

106. Longest Substring Without Repeating Characters

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s==null || s.length()==0) return 0;
       
        int[] visited = new int[256];
        Arrays.fill(visited, -1);
       
        int maxLen=1;
        int curLen=1;
        int preIndex=0;
        visited[s.charAt(0)]=0;
       
        for (int i=1; i<s.length(); i++) {
            preIndex = visited[s.charAt(i)];
           
            if (preIndex==-1 || preIndex+curLen<i) curLen++;
            else {
                maxLen = Math.max(maxLen, curLen);
                curLen = i-preIndex;
            }
           
            visited[s.charAt(i)] = i;
        }
       
        maxLen = Math.max(maxLen, curLen);
        return maxLen;
    }
}

105. Valid Palindrome

public class Solution {
    public boolean isPalindrome(String s) {
        if (s==null || s.length()<=1) return true;
       
        int i=0;
        int j=s.length()-1;
       
        while (i<j) {
            while (i<s.length() && !Character.isLetterOrDigit(s.charAt(i))) i++;
            while (j>=0 && !Character.isLetterOrDigit(s.charAt(j))) j--;
            if (i<s.length() && j>=0 && Character.toLowerCase(s.charAt(i))!=Character.toLowerCase(s.charAt(j))) return false;
            i++;
            j--;
        }
       
        return true;
    }
}