second round leetcode
57,
Insert Interval (Done)

/**
 * 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 List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> ret = new ArrayList<Interval>();
        int i = 0;
        for (; i < intervals.size(); i++) {
            if (intervals.get(i).end < newInterval.start) {
                ret.add(intervals.get(i));
            }
            else {
                break;
            }
        }
        
        for (; i < intervals.size(); i++) {
            if (intervals.get(i).start > newInterval.end) {
                break;
            }
            else {
                newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
                newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
            }
        }
        
        ret.add(newInterval);
        for (; i < intervals.size(); i++) {
            ret.add(intervals.get(i));
        }
        
        return ret;
    }
}

381,
Insert Delete GetRandom O(1) - Duplicates allowed (Done)

public class RandomizedCollection {
    Map<Integer, Set<Integer>> map;
    List<Integer> list;
    Random r;
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        map = new HashMap<Integer, Set<Integer>>();
        list = new ArrayList<Integer>();
        r = new Random();
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        if (!map.containsKey(val)) {
            map.put(val, new HashSet<Integer>());
            map.get(val).add(list.size());
            list.add(val);
            return true;
        }
        else {
            map.get(val).add(list.size());
            list.add(val);
            return false;
        }
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        else {
            int index = map.get(val).iterator().next();
            map.get(val).remove(index);
            if (map.get(val).size() == 0) {
                map.remove(val);
            }
            if (index < list.size() - 1) {
                list.set(index, list.get(list.size() - 1));
                map.get(list.get(list.size() - 1)).remove(list.size() - 1);
                map.get(list.get(list.size() - 1)).add(index);
            }
            list.remove(list.size() - 1);
            return true;
        }
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        return list.get(r.nextInt(list.size()));
    }
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

4,
Median of Two Sorted Arrays (Done)

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.length;
        int n = nums2.length;
        int half = (m + n + 1) / 2;
        int begin = 0;
        int end = m;
        while (begin <= end) {
            int i = begin + (end - begin) / 2;
            int j = half - i;
            // nums1[i - 1] and nums2[j]
            if (i > 0 && j < n && nums1[i - 1] > nums2[j]) {
                end = i - 1;
            }
            // nums2[j - 1] and nums1[i]
            else if (j > 0 && i < m && nums2[j - 1] > nums1[i]) {
                begin = i + 1;
            }
            else {
                int left = 0;
                if (i == 0) {
                    left = nums2[j - 1];
                }
                else if (j == 0) {
                    left = nums1[i - 1];
                }
                else {
                    left = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return left * 1.0;
                }
                
                int right = 0;
                if (i == m) {
                    right = nums2[j];
                }
                else if (j == n) {
                    right = nums1[i];
                }
                else {
                    right = Math.min(nums1[i], nums2[j]);
                }
                return (left + right) / 2.0;
            }
        }
        return -1;
    }
}

死記住

45
Jump Game II (Done)

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        
        int step = 0;
        int edge = 0;
        int maxReach = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            if (i > edge) {
                edge = maxReach;
                step++;
                if (edge >= nums.length - 1) {
                    return step;
                }
            }
            maxReach = Math.max(maxReach, nums[i] + i);
        }
        
        return step;
    }
}

63, 在矩形四邊處趾浅，處理上有點(diǎn)小問題 (Done)
Unique Paths II
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int[][] nums = obstacleGrid;
if (nums == null || nums.length == 0 || nums[0].length == 0) {
return 0;
}

    int row = nums.length;
    int col = nums[0].length;
    int temp = nums[0][0];
    int i = 0;
    for (; i < col; i++) {
        if (nums[0][i] == 0) {
            nums[0][i] = 1;
        }
        else {
            break;
        }
    }
    for (; i < col; i++) {
        nums[0][i] = 0;
    }
    
    nums[0][0] = temp;
    i = 0;
    for (; i < row; i++) {
        if (nums[i][0] == 0) {
            nums[i][0] = 1;
        }
        else {
            break;
        }
    }
    for (; i < row; i++) {
        nums[i][0] = 0;
    }
    
    for (i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            if (nums[i][j] == 1) {
                nums[i][j] = 0;
            }
            else {
                nums[i][j] = nums[i - 1][j] + nums[i][j - 1];
            }
        }
    }
    
    return nums[row - 1][col - 1];
}

}

31,
Next Permutation (Done)
有點(diǎn)不順 注意术徊，我們需要找的一定是 > nums[i] 的最小數(shù)
** 注意：nums[] 可能會有重復(fù)荔棉。所以一開始找區(qū)域時，是 >= 時凳鬓，i--
然后找最接近的最大值時秀又，不能特殊考慮相等的情況 **
public class Solution {
public void nextPermutation(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}

    int i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i < 0) {
        reverse(nums, 0, nums.length - 1);
        return;
    }
    
    int begin = i + 1;
    int end = nums.length - 1;
    while (begin <= end) {
        int mid = begin + (end - begin) / 2;
        if (nums[mid] > nums[i]) {
            begin = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
    
    int temp = nums[end];
    nums[end] = nums[i];
    nums[i] = temp;
    reverse(nums, i + 1, nums.length - 1);
}

private void reverse(int[] nums, int i, int j) {
    int begin = i;
    int end = j;
    while (begin < end) {
        int temp = nums[begin];
        nums[begin] = nums[end];
        nums[end] = temp;
        begin++;
        end--;
    }
}

}

277,
Find the Celebrity (Done)
沒做出來
/* The knows API is defined in the parent class Relation.
boolean knows(int a, int b); */

public class Solution extends Relation {
public int findCelebrity(int n) {
if (n <= 0) {
return -1;
}

    int candidate = 0;
    for (int i = 1; i < n; i++) {
        if (knows(candidate, i)) {
            candidate = i;
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (i == candidate) {
            continue;
        }
        else if (knows(i, candidate) && !knows(candidate, i)) {
            continue;
        }
        else {
            return -1;
        }
    }
    
    return candidate;
}

}

280
Wiggle Sort (Done)
public class Solution {
public void wiggleSort(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}

    for (int i = 0; i + 1 < nums.length; i += 2) {
        if (nums[i + 1] < nums[i]) {
            swap(nums, i, i + 1);
        }
    }
    for (int i = 1; i + 1 < nums.length; i += 2) {
        if (nums[i] < nums[i + 1]) {
            swap(nums, i, i + 1);
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

}

34
Search for a Range (Done)
public class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[]{-1, -1};
}

    int begin = 0;
    int end = nums.length - 1;
    int index = -1;
    while (begin <= end) {
        int mid = begin + (end - begin) / 2;
        if (nums[mid] < target) {
            begin = mid + 1;
        }
        else if (nums[mid] > target) {
            end = mid - 1;
        }
        else {
            index = mid;
            break;
        }
    }
    if (index == -1) {
        return new int[]{-1, -1};
    }
    
    begin = 0;
    end = index - 1;
    while (begin <= end) {
        int mid = begin + (end - begin) / 2;
        if (nums[mid] == target) {
            end = mid - 1;
        }
        else {
            begin = mid + 1;
        }
    }
    int left = end + 1;
    
    begin = index + 1;
    end = nums.length - 1;
    while (begin <= end) {
        int mid = begin + (end - begin) / 2;
        if (nums[mid] == target) {
            begin = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
    int right = begin - 1;
    
    return new int[]{left, right};
}

}

163
Missing Ranges (Not Done)
** 注意可能越界恋昼，所有的 nums[i] + 1 or - 1 都得將 nums[i] 先轉(zhuǎn)換成long **

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

public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> ret = new ArrayList<String>();
        long min = lower;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > min) {
                String s = getRange(min, (long) nums[i] - 1);
                ret.add(s);
            }
            min = (long) nums[i] + 1;
        }
        if (min <= upper) {
            String s = getRange(min, upper);
            ret.add(s);
        }
        
        return ret;
    }
    
    private String getRange(long begin, long end) {
        if (begin == end) {
            return "" + begin;
        }
        else {
            return begin + "->" + end;
        }
    }
}

229,
Majority Element II (Done)
注意順序谒兄，先判斷i1, i2 非空時的情況，再判斷空情況

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ret = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return ret;
        }
        
        Integer i1 = null;
        Integer i2 = null;
        int c1 = 0;
        int c2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i1 != null && i1 == nums[i]) {
                c1++;
            }
            else if (i2 != null && i2 == nums[i]) {
                c2++;
            }
            else if (i1 == null) {
                i1 = new Integer(nums[i]);
                c1 = 1;
            }
            else if (i2 == null) {
                i2 = new Integer(nums[i]);
                c2 = 1;
            }
            else {
                c1--;
                if (c1 == 0) {
                    i1 = null;
                }
                c2--;
                if (c2 == 0) {
                    i2 = null;
                }
            }
        }
        
        c1 = 0;
        c2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i1 != null && i1 == nums[i]) {
                c1++;
            }
            else if (i2 != null && i2 == nums[i]) {
                c2++;
            }
        }
        
        if (c1 > nums.length / 3) {
            ret.add(i1);
        }
        if (c2 > nums.length / 3) {
            ret.add(i2);
        }
        return ret;
    }
}

370,
Range Addition (Done)
沒做出來

public class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] ret = new int[length];
        for (int i = 0; i < updates.length; i++) {
            int start = updates[i][0];
            int end = updates[i][1];
            int step = updates[i][2];
            ret[start] += step;
            if (end + 1 < length) {
                ret[end + 1] -= step;
            }
        }
        
        for (int i = 1; i < length; i++) {
            ret[i] += ret[i - 1];
        }
        
        return ret;
    }
}

209,
Minimum Size Subarray Sum (Done)
有點(diǎn)不順暢

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int begin = 0;
        int end = 0;
        int minLength = Integer.MAX_VALUE;
        int sum = 0;
        while (end < nums.length) {
            sum += nums[end];
            if (sum >= s) {
                minLength = Math.min(minLength, end - begin + 1);
                sum -= nums[begin];
                begin++;
                if (begin > end) {
                    end = begin;
                }
                else {
                    sum -= nums[end];
                }
            }
            else {
                end++;
            }
        }
        
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

396,
Rotate Function (Done)
沒做出來

public class Solution {
    public int maxRotateFunction(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int iteration = 0;
        int base = 0;
        for (int i = 0; i < A.length; i++) {
            base += i * A[i];
            iteration += A[i];
        }
        
        int max = base;
        for (int i = 1; i < A.length; i++) {
            base -= iteration;
            base += A.length * A[i - 1];
            max = Math.max(max, base);
        }
        
        return max;
    }
}

407
Trapping Rain Water II (Done)
忘記了還需要用 priority queue

public class Solution {
    private class Node {
        int x;
        int y;
        int height;
        Node (int x, int y, int height) {
            this.x = x;
            this.y = y;
            this.height = height;
        }
    }
    int row = 0;
    int col = 0;
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) {
            return 0;
        }
        
        this.row = heightMap.length;
        this.col = heightMap[0].length;
        PriorityQueue<Node> pq = new PriorityQueue<Node>(10, new Comparator<Node>() {
            public int compare(Node n1, Node n2) {
                return n1.height - n2.height;
            }    
        });
        boolean[][] mark = new boolean[row][col];
        for (int i = 0; i < col; i++) {
            pq.offer(new Node(0, i, heightMap[0][i]));
            mark[0][i] = true;
            if (row - 1 > 0) {
                pq.offer(new Node(row - 1, i, heightMap[row - 1][i]));
                mark[row - 1][i] = true;
            }
        }
        
        for (int i = 0; i < row; i++) {
            pq.offer(new Node(i, 0, heightMap[i][0]));
            mark[i][0] = true;
            if (col - 1 > 0) {
                pq.offer(new Node(i, col - 1, heightMap[i][col - 1]));
                mark[i][col - 1] = true;
            }
        }
        
        int sum = 0;
        int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            for (int i = 0; i < 4; i++) {
                int next_x = curr.x + dir[i][0];
                int next_y = curr.y + dir[i][1];
                if (check(next_x, next_y) && !mark[next_x][next_y]) {
                    sum += Math.max(0, curr.height - heightMap[next_x][next_y]);
                    mark[next_x][next_y] = true;
                    pq.offer(new Node(next_x, next_y, Math.max(curr.height, heightMap[next_x][next_y])));
                }
            }
        }
        
        return sum;
    }
    
    private boolean check(int i, int j) {
        if (i < 0 || i >= row || j < 0 || j >= col) {
            return false;
        }
        return true;
    }
}

317
Shortest Distance from All Buildings (Done)
沒做出來端朵，今天要再寫一遍

public class Solution {
    private class Node {
        int x;
        int y;
        int step;
        Node (int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
    
    int row = 0;
    int col = 0;
    int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        row = grid.length;
        col = grid[0].length;
        int[][] dist = new int[row][col];
        List<Node> list = new ArrayList<Node>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    list.add(new Node(i, j, 0));
                }
                grid[i][j] = -grid[i][j];
            }
        }
        
        for (int i = 0; i < list.size(); i++) {
            bfs(list.get(i), grid, dist, i);
        }
        
        int max = Integer.MAX_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == list.size()) {
                    max = Math.min(max, dist[i][j]);
                }
            }
        }
        
        return max == Integer.MAX_VALUE ? -1 : max;
    }
    
    private void bfs(Node root, int[][] grid, int[][] dist, int k) {
        Queue<Node> q = new LinkedList<Node>();
        q.offer(root);
        while (!q.isEmpty()) {
            Node curr = q.poll();
            for (int i = 0; i < 4; i++) {
                int nei_x = curr.x + dir[i][0];
                int nei_y = curr.y + dir[i][1];
                if (check(nei_x, nei_y) && grid[nei_x][nei_y] == k) {
                    q.offer(new Node(nei_x, nei_y, curr.step + 1));
                    dist[nei_x][nei_y] += curr.step + 1;
                    grid[nei_x][nei_y] = k + 1;
                }
            }
        }
    }
    
    private boolean check(int i, int j) {
        if (i < 0 || i >= row || j < 0 || j >= col) {
            return false;
        }
        return true;
    }
}

301
Remove Invalid Parentheses (Done)
基本寫了出來好芭，有點(diǎn)磨蹭

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> ret = new ArrayList<String>();
        helper(0, 0, s, new char[]{'(', ')'}, ret);
        return ret;
    }
    
    private void helper(int last_i, int last_j, String s, char[] pair, List<String> ret) {
        int cnt = 0;
        for (int i = last_i; i < s.length(); i++) {
            char curr = s.charAt(i);
            if (curr == pair[0]) {
                cnt++;
            }
            else if (curr == pair[1]) {
                cnt--;
                if (cnt < 0) {
                    for (int j = last_j; j <= i; j++) {
                        if (s.charAt(j) == pair[1] && (j == last_j || s.charAt(j - 1) != pair[1])) {
                            helper(i, j, s.substring(0, j) + s.substring(j + 1), pair, ret);
                        }
                    }
                    return;
                }
            }
        }
        
        String r = new StringBuilder(s).reverse().toString();
        if (pair[0] == '(') {
            helper(0, 0, r, new char[]{')', '('}, ret);
        }
        else {
            ret.add(r);
        }
    }
}

323
Number of Connected Components in an Undirected Graph (Done)
沒想出來，以為還是用入度解

public class Solution {
    Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
    int V;
    public int countComponents(int n, int[][] edges) {
        this.V = n;
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            if (!map.containsKey(u)) {
                map.put(u, new HashSet<Integer>());
            }
            if (!map.containsKey(v)) {
                map.put(v, new HashSet<Integer>());
            }
            map.get(u).add(v);
            map.get(v).add(u);
        }
        
        boolean[] mark = new boolean[n];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (!mark[i]) {
                cnt++;
                bfs(i, mark);
            }
        }
        
        return cnt;
    }
    
    private void bfs(int root, boolean[] mark) {
        mark[root] = true;
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(root);
        while (!q.isEmpty()) {
            int curr = q.poll();
            if (map.containsKey(curr)) {
                Set<Integer> nei = map.get(curr);
                for (Integer temp : nei) {
                    if (!mark[temp]) {
                        mark[temp] = true;
                        q.offer(temp);
                    }
                }
            }
        }
    }
}

279
Perfect Squares (Done)
沒做出來

public class Solution {
    public int numSquares(int n) {
        if (n <= 0) {
            return 0;
        }
        
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            int j = 1;
            while (j * j <= i) {
                min = Math.min(min, 1 + dp[i - j * j]);
                j++;
            }
            dp[i] = min;
        }
        
        return dp[n];
    }
}

261
Graph Valid Tree
沒做出來

public class Solution {
    Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
    public boolean validTree(int n, int[][] edges) {
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            if (!map.containsKey(u)) {
                map.put(u, new HashSet<Integer>());
            }
            if (!map.containsKey(v)) {
                map.put(v, new HashSet<Integer>());
            }
            map.get(u).add(v);
            map.get(v).add(u);
        }
        
        int cnt = 0;
        boolean[] mark = new boolean[n];
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(0);
        mark[0] = true;
        while (!q.isEmpty()) {
            int curr = q.poll();
            cnt++;
            if (map.containsKey(curr)) {
                Set<Integer> nei = map.get(curr);
                for (Integer temp : nei) {
                    if (mark[temp]) {
                        return false;
                    }
                    mark[temp] = true;
                    map.get(temp).remove(curr);
                    q.offer(temp);
                }
            }
        }
        
        return cnt == n;
    }
}

269
Alien Dictionary (Not finished)
test case 更新了冲呢，沒寫對
** 記咨岚堋！圖中，利用入度解決問題時邻薯，一定要判斷裙戏，
if (!map.get(u).contains(v)) {// 再去更新入度}
刪去入度時，也得先判斷厕诡，當(dāng)前的 u累榜， 是否存在于 map 中 **

public class Solution {
    Map<Character, Set<Character>> map = new HashMap<Character, Set<Character>>();
    Map<Character, Integer> indegree = new HashMap<Character, Integer>();
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }
        for (String word : words) {
            for (char c : word.toCharArray()) {
                indegree.put(c, 0);
            }
        }
        
        for (int i = 0; i < words.length - 1; i++) {
            String s1 = words[i];
            String s2 = words[i + 1];
            int k = 0;
            while (k < Math.min(s1.length(), s2.length())) {
                if (s1.charAt(k) == s2.charAt(k)) {
                    k++;
                }
                else {
                    break;
                }
            }
            if (k == Math.min(s1.length(), s2.length())) {
                if (s1.length() > s2.length()) {
                    return "";
                }
                else {
                    continue;
                }
            }
            else {
                char c1 = s1.charAt(k);
                char c2 = s2.charAt(k);
                if (!map.containsKey(c1)) {
                    map.put(c1, new HashSet<Character>());
                }
                if (!map.get(c1).contains(c2)) {
                    map.get(c1).add(c2);
                    indegree.put(c2, indegree.get(c2) + 1);
                }
            }
        }
        
        Queue<Character> q = new LinkedList<Character>();
        for (Character c : indegree.keySet()) {
            if (indegree.get(c) == 0) {
                q.offer(c);
            }
        }
        
        String ret = "";
        while (!q.isEmpty()) {
            char c = q.poll();
            ret += c;
            if (map.containsKey(c)) {
                Set<Character> nei = map.get(c);
                for (Character temp : nei) {
                    indegree.put(temp, indegree.get(temp) - 1);
                    if (indegree.get(temp) == 0) {
                        q.offer(temp);
                    }
                }
            }
        }
        
        if (ret.length() == indegree.size()) {
            return ret;
        }
        else {
            return "";
        }
    }
}

332
Reconstruct Itinerary (Done)
基本寫對了，還有小Bug

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        List<String> ret = new ArrayList<String>();
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (int i = 0; i < tickets.length; i++) {
            String src = tickets[i][0];
            String dest = tickets[i][1];
            if (!map.containsKey(src)) {
                map.put(src, new ArrayList<String>());
            }
            insert(dest, map.get(src));
        }
        
        ret.add("JFK");
        int total = tickets.length;
        helper("JFK", total, map, ret);
        return ret;
    }
    
    private boolean helper(String src, int total, Map<String, List<String>> map, List<String> ret) {
        if (total == 0) {
            return true;
        }
        else {
            List<String> dests = map.get(src);
            if (dests == null || dests.size() == 0) {
                return false;
            }
            for (int i = 0; i < dests.size(); i++) {
                String dest = dests.get(i);
                ret.add(dest);
                dests.remove(i);
                boolean flag = helper(dest, total - 1, map, ret);
                if (flag) {
                    return true;
                }
                ret.remove(ret.size() - 1);
                dests.add(i, dest);
            }
            return false;
        }
    }
    
    private void insert(String s, List<String> list) {
        int i = 0;
        for (; i < list.size(); i++) {
            if (s.compareTo(list.get(i)) <= 0) {
                break;
            }
        }
        if (i >= list.size()) {
            list.add(s);
        }
        else {
            list.add(i, s);
        }
    }
}

99
Recover Binary Search Tree (Done)
沒做出來

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void recoverTree(TreeNode root) {
        if (root == null) {
            return;
        }
        
        TreeNode small = null;
        TreeNode big = null;
        Stack<TreeNode> st = new Stack<TreeNode>();
        TreeNode p = root;
        while (p != null) {
            st.push(p);
            p = p.left;
        }
        TreeNode pre = null;
        int cnt = 0;
        while (!st.isEmpty()) {
            TreeNode curr = st.pop();
            if (pre == null || pre.val < curr.val) {
                pre = curr;
            }
            else {
                if (cnt == 0) {
                    big = pre;
                    small = curr;
                    cnt++;
                }
                else {
                    small = curr;
                }
            }
            
            if (curr.right != null) {
                curr = curr.right;
                while (curr != null) {
                    st.push(curr);
                    curr = curr.left;
                }
            }
        }
        
        int temp = big.val;
        big.val = small.val;
        small.val = temp;
    }
}

394
Decode String (Not finished)
沒做出來灵嫌，和 basic calculator很像

public class Solution {
    public String decodeString(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        
        Stack<String> st = new Stack<String>();
        Stack<Integer> cnt = new Stack<Integer>();
        int num = 0;
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            if (Character.isDigit(curr)) {
                num = 10 * num + (curr - '0');
            }
            else if (curr == '[') {
                st.push(result);
                cnt.push(num);
                result = "";
                num = 0;
            }
            else if (curr == ']') {
                int counter = cnt.pop();
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < counter; j++) {
                    sb.append(result);
                }
                result = st.pop() + sb.toString();
            }
            else {
                result += curr;
            }
        }
        
        return result;
    }
}

227
Basic Calculator II
沒做出來,因?yàn)橛谐顺挤＃糜幸粋€ char 來保存前一個運(yùn)算符

224
Basic Calculator
沒做出來

366. Find Leaves of Binary Tree
     沒能拿最優(yōu)解來做

367. Nested List Weight Sum II
     沒做出來

368. House Robber III
     沒做出來

369. Interleaving String
     沒做出來

370. Word Break II
     有點(diǎn)生疏，一開始忘記加cache了

371. Distinct Subsequences
     沒做出來

188.Best Time to Buy and Sell Stock IV
沒做出來

87. Scramble String
    基本思路有了寿羞，有幾個東西忘了
    1 . isSame, 用老判斷字母組成是否一致
    2 . cache, 三維dp,
    dp[len][len][len + 1]

88. Palindrome Partitioning II
    沒做出來

89. Create Maximum Number
    沒做出來

90. Remove K Digits
    自己寫了出來猖凛，但有些corner case 沒考慮到
    比如，最后的結(jié)果稠曼，可能有l(wèi)eading zero, 要去了
    比如形病， 最后的結(jié)果，可能長度為0霞幅，這個時候不能返回空字符串，得返回 “0”

91. Max Sum of Rectangle No Larger Than K
    getMaxWithK()
    寫的有些問題
    set.add(0)
    還有temp, 要在判斷之后再加入set中

Paint House II
沒做出來,
min1, min2
lastMin1, lastMin2

264. Ugly Number II
     總是記不琢抗稀司恳！
     int[] dp
     i2, i3, i5 三個指針指向dp

322. Coin Change
     寫的不順暢
     而且， 內(nèi)循環(huán)绍傲，循環(huán)的是 coins array

323. Maximal Square
     遞推式寫的不對扔傅。
     記住，是左烫饼，上猎塞，左上，三個點(diǎn)

324. Counting Bits
     沒做出來

325. Best Time to Buy and Sell Stock with Cooldown
     沒做出來

326. Combination Sum IV
     沒做出來杠纵，和 coin change 很類似,只不過 coin change 求的是最小值荠耽，這里是累加

327. Guess Number Higher or Lower II
     沒做出來，和 burst baloon 很像

328. Android Unlock Patterns
     沒做出來比藻。
     skip[][] 是關(guān)鍵

329. Largest Divisible Subset
     先找出最長子鏈的長度铝量，以及index，然后再倒退后去復(fù)原

330. Is Subsequence
     原題不難银亲。
     但是對于follow up, 需要構(gòu)造map,然后用 binary search 來做

331. Bomb Enemy
     沒做出來
     updateRow
     updateCol

332. Paint Fence
     沒做出來慢叨。
     分成兩種類型
     diff,
     same

333. Longest Substring with At Most Two Distinct Characters
     沒做來，這么重要的題目务蝠。
     不應(yīng)該拍谐。
     leftMost

Longest Substring Without Repeating Characters
自己寫了出來，但有點(diǎn)磨蹭

340. Longest Substring with At Most K Distinct Characters
     本可以做出來的，犯了低級錯誤轩拨。
     map.remove 是移除 character

341. Read N Characters Given Read4
     忘記怎么做了

342. Read N Characters Given Read4 II - Call multiple times
     知道簡單版怎么做后力穗，這個也很容易做了，加一個全局變量隊(duì)列就行

343. Palindrome Pairs
     自己寫了出來气嫁。
     但是錯了挺多次当窗。
     處理好：
     isPalindrome
     reverse = s, “” contains in map
     if word == “”, continue

344. Shortest Palindrome
     基本思路記得，但寫的還是不順手寸宵，沒寫出來

345. Valid Number
     沒能最后寫出來崖面。
     dot, if (dot || exp)
     exp, if (!num || exp)
     還有 curr == ‘+’ or ‘-‘ after exp

346. Substring with Concatenation of All Words
     和 minimum window substring 很類似，只不過一個是 string, 一個是 character
     這里要注意的是梯影，
     有兩個map
     外層for循環(huán)巫员，i < len

347. Mini Parser
     沒做出來，和 basic calculator很像甲棍。
     關(guān)鍵一步在于简识，一開始判斷[0] 是否為 ‘[‘

271. Encode and Decode Strings
     沒做出來
     length of string + “/“ + string

272. Group Anagrams
     hashcode 沒想到怎么求，
     原來直接有系統(tǒng)函數(shù)：
     Arrays.hashCode(char[] arr)

273. Group Shifted Strings
     基本思路是正確的感猛。注意偏差offset

274. Flip Game II
     忘記怎么做了

275. Generalized Abbreviation
     沒做出來七扰。其實(shí)思路和
     interleave string 很像

276. Valid Word Abbreviation
     沒做出來，看的答案

277. Frog Jump
     沒做出來
     DP陪白， 看的答案

278. Sudoku Solver
     基本寫了出來颈走。
     記住， for 循環(huán)結(jié)束后咱士，
     board[i][j] = ‘.’;
     return false;

279. Meeting Rooms II
     有點(diǎn)疙瘩

280. Min Stack
     粗心錯了立由，還得再寫一遍

281. Sliding Window Maximum
     Deque
     peekFirst(), 左側(cè)
     peekLast(), 右側(cè)
     隊(duì)列內(nèi)部保持一個遞減數(shù)列，
     所以第一個循環(huán)序厉，
     q.peekFirst()
     第二個循環(huán)锐膜，
     q.peekLast()

282. Maximum Size Subarray Sum Equals k
     沒做出來。
     注意三種題：
     minimum size subaray sum <= k, all members are positive
     => sliding window
     maximum size subarray sum equals k
     => sums[], and using two sum
     maximum size subarray sum <= k
     => need to use TreeMap