Maximal Rectangle

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

Largest Rectangle in Histogram 升级版。对于矩阵每行，可以看成是这个问题。height array对于相邻的行，假如当前的matrix[i][j] = 0，则无视上一行且当前height[j] = 0，如果matrix[i][j] = 1，则加上之前的height[j] += 1。

public class Solution {
    //Time: O(m*n)  Space: O(n)
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int max = 0;
        int[] height = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
            }
            int cur = largestRectangleArea(height);
            max = Math.max(max, cur);
        }
        return max;
    }
    
    public int largestRectangleArea(int[] height) {
        int max = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i <= height.length; i++) {
            int h = i == height.length ? -1 : height[i];
            while (!stack.isEmpty() && h < height[stack.peek()]) {
                int index = stack.pop();
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, w * height[index]);
            }
            stack.push(i);
        }
        return max;
    }
}

Largest Rectangle in Histogram

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

我们需要维护一个递增的stack。

举例现在在stack里是1，3，5，7。现在来了4，说明以7为高度生成矩阵已经不可能在增长了。把7pop出来，算出以7为高的矩阵和全局比较。在继续这么比较。在数组最后push -1进去，使stack里剩余的高度都能被计算。实际在stack里是高度对应的Index，不是高度本身。宽度：当stack已经为空了则为当前要push的i，否则为i - stack.peek() - 1。

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

Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

KMP和RK会在以后补上。暴力方法：

public class Solution {
    //Time: O(m*n)  Space: O(1)
    public String strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return null;
        }
        if (needle.length() == 0) {
            return haystack;
        }
        
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            int length = 0;
            for (int j = i; j < needle.length() + i; j++) {
                if (haystack.charAt(j) == needle.charAt(j - i)) {
                    length++;
                } else {
                    break;
                }
                if (length == needle.length()) {
                    return haystack.substring(i);
                }
            }
        }
        return null;
    }
}

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        Queue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), ListCom);
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                queue.offer(lists.get(i));   
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (!queue.isEmpty()) {
            ListNode cur = queue.poll();
            head.next = cur;
            if (cur.next != null) {
                queue.offer(cur.next);
            }
            head = head.next;
        }
        return dummy.next;
    }
    
    private Comparator<ListNode> ListCom = new Comparator<ListNode>() {
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }  
    };
}

Longest Substring Without Repeating Characters

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

用左右两个指针，右指针往右移同时把char加进hashset里面，当hashset出现重复时，计算当前长度，移动左指针，一直到左指针指向重复的元素，把经过的元素移除hashset。重复以上过程。

public class Solution {
    //Time: O(n)  Space: O(n)
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) {
            return s.length();
        }
        
        HashSet<Character> set = new HashSet<Character>();
        int left = 0;
        int i = 0;
        int max = 0;
        for (; i < s.length(); i++) {
            if (!set.contains(s.charAt(i))) {
                set.add(s.charAt(i));
            } else {
                max = Math.max(max, i - left);
                while (left < i && s.charAt(left) != s.charAt(i)) {
                    set.remove(s.charAt(left));
                    left++;
                }
                left++;
            }
        }
        max = Math.max(max, i - left);
        return max;
    }
}

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

二分法，但是用除法来检测，避免溢出。

public class Solution {
    //Time: O(logn)  Space: O(1)
    public int sqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        
        int left = 1;
        int right = x;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (x / mid == mid) {
                return mid;
            } else if (x / mid > mid) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (x / right > right) {
            return right;
        } else {
            return left;
        }
    }
}

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

BFS: 用一个HashMap存储已经生成过的点，避免重复生成相同的点。

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = 
        new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        queue.offer(node);
        map.put(node, new UndirectedGraphNode(node.label));
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();
            UndirectedGraphNode newcur = map.get(cur);
            for (UndirectedGraphNode neig : cur.neighbors) {
                //if contains, this node has already been searched
                if (!map.containsKey(neig)) {
                    map.put(neig, new UndirectedGraphNode(neig.label));
                    queue.offer(neig);
                }
                newcur.neighbors.add(map.get(neig));
            }
        }
        return map.get(node);
    }
}

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

bucket sort

public class Solution {
    public int firstMissingPositive(int[] A) {
        //Time: O(n)  Space: O(1)
        if (A == null || A.length == 0) {
            return 1;
        }
        
        for (int i = 0; i < A.length; i++) {
            while (A[i] > 0 && A[i] <= A.length && A[i] != i + 1) {
                int temp = A[i];
                //if same, don't need swap
                if (A[temp - 1] == A[i]) {
                    break;
                }
                A[i] = A[temp - 1];
                A[temp - 1] = temp;
            }
        }
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i + 1) {
                return i + 1;
            }
        }
        return A.length + 1;
    }
}

Add Two Numbers

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

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

只要最后检查下进位是不是1。

public class Solution {
    //Time: O(n)
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        
        int carry = 0;
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                carry += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                carry += l2.val;
                l2 = l2.next;
            }
            node.next = new ListNode(carry % 10);
            carry /= 10;
            node = node.next;
        }
        if (carry == 1) {
            node.next = new ListNode(1);
        }
        return dummy.next;
    }
}

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

两个node互换。举个例子，tree inorder：1，2，3，4，5，6，7

有可能会有1对降序：1，2，4，3，5，6，7。也有可能会有两对降序：1，6，3，4，5，2，7

但是无论如何，第一次降序的大的和最后一次降序小的就是对调的两个。

public class Solution {
    //Time: O(n)
    private TreeNode first = null;
    private TreeNode second = null;
    private TreeNode last = null;
    private void find(TreeNode root) {
        if (root == null) {
            return;
        }
        
        find(root.left);
        if (last != null && first == null && last.val > root.val) {
            first = last;
        }
        if (last != null && first != null && last.val > root.val) {
            second = root;
        }
        last = root;
        find(root.right);
    }
    
    public void recoverTree(TreeNode root) {
        find(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
}

Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Anagrams 指对于不同string，他们不同char的出现次数一样。我们可以用一个26size的array来记录每个string各种char出现的次数，用它来计算对应每个string的hash value，如果是anagrams，value也会相同。把结果放进HashMap，对于每个value，如果对应的string个数大于1，就加进结果里。

public class Solution {
    //Time: O(n * m) m is average length of each string
    public ArrayList<String> anagrams(String[] strs) {
        ArrayList<String> res = new ArrayList<String>();
        if (strs == null || strs.length == 0) {
            return res;
        }
        
        HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();
        for (int i = 0; i < strs.length; i++) {
            int[] count = new int[26];
            String s = strs[i];
            for (int j = 0; j < s.length(); j++) {
                count[s.charAt(j) - 'a']++;
            }
            int val = getValue(count);
            if (!map.containsKey(val)) {
                ArrayList<String> tmp = new ArrayList<String>();
                tmp.add(s);
                map.put(val, tmp);
            } else {
                ArrayList<String> tmp = map.get(val);
                tmp.add(s);
                map.put(val, tmp);
            }
        }
        
        for (int i : map.keySet()) {
            if (map.get(i).size() > 1) {
                res.addAll(map.get(i));
            }
        }
        return res;
    }
    
    private int getValue(int[] count) {
        int val = 0;
        for (int i = 0; i < count.length; i++) {
            val = val * 31 + count[i];
        }
        return val;
    }
}

Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

用一个二维数组进行DP，map[i][j] 表示T在长度前j位在S长度前i位合法的个数。当第i位和第j位char不同，我们只能考虑删掉第i位，相同时还能考虑保留第i为。

public class Solution {
    //Time: O(m * n)  Space: O(m * n)
    public int numDistinct(String S, String T) {
        if (S.length() < T.length()) {
            return 0;
        }
        
        int m = S.length();
        int n = T.length();
        int[][] map = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            map[i][0] = 1;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                map[i][j] += map[i - 1][j];
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    map[i][j] += map[i - 1][j - 1];
                }
            }
        }
        return map[m][n];
    }
}

Reverse Nodes in k-Group

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

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

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

Only constant memory is allowed.

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

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

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

计算一共要反转多少个group，对每个gruop在反转k-1次。

public class Solution {
    //Time: O(n)  Space: O(1)
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        
        int length = getLength(head);
        int num = length / k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        int i = 0;
        while (i < num) {
            int j = 0;
            while (j < k - 1) {
                ListNode tmp = head.next;
                head.next = tmp.next;
                tmp.next = pre.next;
                pre.next = tmp;
                j++;
            }
            pre = head;
            head = pre.next;
            i++;
        }
        return dummy.next;
    }
    
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
}

Remove Duplicates from Sorted List II

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

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

当发现相邻node值一样，记录这个值，把下面和这个值相等的Node都删除。注意Null check。

public class Solution {
    //Time: O(n)  Space: O(1)
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while (head.next != null) {
            if (head.next.next != null && head.next.val == head.next.next.val) {
                int val = head.next.val;
                while (head.next != null && head.next.val == val) {
                    head.next = head.next.next;
                }
            } else {
                head = head.next;
            }
        }
        return dummy.next;
    }
}

Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

比较直观的是从每个地点开始，但是这题可以只遍历一遍，假设从1开始到4，发现不能走了，说明2，3，4开始也不行。最后检查下，总油量是否大于总消耗。

public class Solution {
    //Time: O(n)  Space: O(1);
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0;
        int cur = 0;
        int index = 0;
        for (int i = 0; i < gas.length; i++) {
            cur += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if (cur < 0) {
                cur = 0;
                index = i + 1;
            }
        }
        return sum < 0 ? -1 : index;
    }
}

Insertion Sort List

Sort a linked list using insertion sort.

public class Solution {

    //Time: O(n^2)
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        while (head != null) {
            ListNode node = dummy;
            while (node.next != null && node.next.val < head.val) {
                node = node.next;
            }
            
            ListNode temp = head.next;
            head.next = node.next;
            node.next = head;
            head = temp;
        }
        return dummy.next;
    }
}

Edit Distance

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

You have the following 3 operations permitted on a word:

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

用一个二维数组，map[i][j]  代表从word1(0,i)变化到word2(0,j)需要的次数。

public class Solution {
    //Time: O(m*n)  Space: O(m*n)
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0) {
            return word2.length();
        }
        
        if (word2.length() == 0) {
            return word1.length();
        }
        
        int m = word1.length() + 1;
        int n = word2.length() + 1;
        int[][] map = new int[m][n];
        for (int i = 1; i < m; i++) {
            map[i][0] = i;
        }
        for (int i = 1; i < n; i++) {
            map[0][i] = i;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    map[i][j] = map[i - 1][j - 1];
                } else {
                    int delete = map[i - 1][j] + 1;
                    int insert = map[i][j - 1] + 1;
                    int replace = map[i - 1][j - 1] + 1;
                    map[i][j] = Math.min(delete, Math.min(insert, replace));
                }
            }
        }
        return map[m - 1][n - 1];
    }
}

Next Permutation

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

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

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

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

从末尾开始找到第一个降序的地方，记录降序地方小的那个值，继续从末尾开始找到第一个比那个值大的数，两者交换，然后把从末尾到降序的部分反转。

注意有可能整个数组从末尾都是升序的情况。

public class Solution {
    //Time: O(n)  Space: O(1)
    public void nextPermutation(int[] num) {
        if (num == null || num.length == 0) {
            return;
        }
        
        int i = num.length - 1;
        for (; i > 0; i--) {
            if (num[i] > num[i - 1]) {
                break;
            }
        }
        if(i == 0) {
            reverse(num, 0);
            return;
        }
        
        int j = num.length - 1;
        for (; j >= 0; j--) {
            if (num[j] > num[i - 1]) {
                break;
            }
        }
        
        int temp = num[i - 1];
        num[i - 1] = num[j];
        num[j] = temp;
        reverse(num, i);
    }
    
    private void reverse(int[] num, int index) {
        int left = index;
        int right = num.length - 1;
        while (left < right) {
            int temp = num[left];
            num[left] = num[right];
            num[right] = temp;
            left++;
            right--;
        }
    } 
}

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

设置一个最大和最小值，同时更新。

 public class Solution {
    //Time: O(n)
    public boolean isValidBST(TreeNode root) {
        return isValid(root, Integer.MAX_VALUE, Integer.MIN_VALUE);
    }
    
    private boolean isValid(TreeNode root, int max, int min) {
        if (root == null) {
            return true;
        }
        
        if (root.val >= max || root.val <= min) {
            return false;
        }
        return isValid(root.left, root.val, min) && isValid(root.right, max, root.val);
    }
}

用类似一个inorder的方法，灵感来自recover BST。

public class Solution {
    private TreeNode last = null;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        boolean left = isValidBST(root.left);
        if (last != null && last.val >= root.val) {
            return false;
        }
        last = root;
        boolean right = isValidBST(root.right);
        return left && right;
    }
}

Palindrome Partitioning

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

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [

    ["aa","b"],

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

  ]

DFS，时间分析，一个有n-1的地方可以断开，所以有断和不断两种情况，所有情况就是2^n。 

public class Solution {
    //Time: O(2^n)
    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        ArrayList<String> tmp = new ArrayList<String>();
        help(res, tmp, s, 0);
        return res;
    }
    
    private void help(ArrayList<ArrayList<String>> res, ArrayList<String> tmp, 
                      String s, int index) {
        if (index == s.length()) {
            res.add(new ArrayList<String>(tmp));
            return;
        }
        
        for (int i = index + 1; i <= s.length(); i++) {
            String cur = s.substring(index, i);
            if (valid(cur)) {
                tmp.add(cur);
                help(res, tmp, s, i);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
    
    private boolean valid(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}