leetcode bug free

---不包含jiuzhang ladders中出现过的题。如出现多个方法，则最后一个方法是最优解。

 目录：

1 String

2 Two pointers

3 Array

4 DFS && BFS

5 Math

6 Dynamic Programming

7 Data Structure

8 Binary Search

9 Tree

10 Bit Manipulation

11 Linked List

12 graph

1 String

1.1  Longest Palindromic Substring --- bug free

求一个字符串中的最长回文子串

求一个字符串中的最长回文子串。

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

分析1:中心扩展，以每个字符为中心向外扩展，找到最长回文串。时间复杂度O(n^2)，空间复杂度O(1)。外层循环次数为2 * slen - 2，使代码更简洁。

public class Solution {
    public String longestPalindrome(String s) {
        int length = 0;
        String res = "";
        
        //要考虑回文串是abba和aba两种情况
        for (int i = 0; i < 2 * s.length() - 1; i++) {
            int p1 = i % 2 == 0 ? i / 2 - 1 : i / 2;
            int p2 = i % 2 == 0 ? i / 2 + 1 : i / 2 + 1;
            int len = i % 2 == 0 ? 1 : 0;
            while (p1 >= 0 && p2 < s.length() && s.charAt(p1) == s.charAt(p2)) {
                len += 2;
                p1--;
                p2++;
            }
            if (len > length) {
                length = len;
                res = s.substring(p1 + 1, p2);
            }
        }
        return res;
    }
}

分析2:Manacher算法。时间复杂度O(n)，空间复杂度O(1)。

1.2  ZigZag Conversion --- not bug free

按Z字形来重新打印一个字符串

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P    A   H    N
A P L S I  I G
Y    I    R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

分析：画图找规律。第一行和最后一行的字符索引的间隔是2*(nRows - 1)，其它行的间隔则是2*(nRow - i - 1)与2 * i交替的，i表示当前的行号。注意numRows为1时要单独讨论，不然会死循环。时间O(n)，额外空间O(1)。

public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < numRows; i++) {
            int step1 = 2 * (numRows - i - 1);
            int step2 = 2 * i;

            if (i == 0) {
                for (int j = i; j < s.length(); j += step1) {
                    sb.append(String.valueOf(s.charAt(j)));
                }
            } else if (i == numRows - 1) {
                for (int j = i; j < s.length(); j += step2) {
                    sb.append(String.valueOf(s.charAt(j)));
                }
            } else {
                int count = 0;
                for (int j = i; j < s.length(); count++) {
                    sb.append(String.valueOf(s.charAt(j)));
                    if (count % 2 == 0) {
                        j += step1;
                    } else {
                        j += step2;
                    }
                }
            }
        }
        return sb.toString();
    }
}

1.3 Longest Common Prefix ---not bug free

给n个字符串，求它们的最长公共前缀

Write a function to find the longest common prefix string amongst an array of strings.

分析：时间O(n*len)，其中len是答案的长度，n是字符串的个数。额外空间O(1)。

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (String str : strs) {
                if (i >= str.length() || str.charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

1.4 Count and Say --- bug free

1读作“1个1”或11，11读作“2个1”或21，21读作“1个2，1个1”或1211......以此类推，求第n个字符串。("1"是第一个)。

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
is read off as "one 1" or 11.
is read off as "two 1s" or 21.
is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

分析：通过数第n-1个字符串来产生第n个字符串，可用for循环代替递归。注意stringbuider可以直接append数字和字符，之前一直以为只能append字符串。

class Solution {
    public String countAndSay(int n) {
        String last = "1";
        for (int i = 1; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            char number = last.charAt(0);
            int count = 0;
            for (int j = 0; j <= last.length(); j++) {
                char cur = j == last.length() ? '*' : last.charAt(j);
                if (cur == number) {
                    count++;
                } else {
                    sb.append(count);
                    sb.append(number);
                    count = 1;
                    number = cur;
                }
            }
            last = sb.toString();
        }   
        return last;
    }   
}

1.5 Reverse Words in a String ---not bug free

给一个字符串，要求把词的顺序反转。

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

分析：使用java的内置函数很容易做。但是我们要思考的是，对于C程序员来说，如何inplace地来做这道题。方法就是，先把整个字符串反转，然后用两个指针控制，i指针指向当前复制到的位置，j指针往后扫描，这一步相当于把一个单词往前挪动到与前一个单词只间隔一个空格。每挪动完一个单词，就把该单词再进行反转。使用C语言实现该方法，时间复杂度O(n)，空间O(1)。表达了该方法的java代码如下。

version1:

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        char[] sa = s.toCharArray();
        reverse(sa, 0, sa.length - 1);
        int i = 0;
        for (int j = 0; j < sa.length; j++) {
            if (sa[j] != ' ') {
                if (i != 0) {
                    sa[i++] = ' ';
                }
                int start = i;
                while (j < sa.length && sa[j] != ' ') {
                    sa[i++] = sa[j++];
                }
                reverse(sa, start, i - 1);
            }
        }
        
        return new String(sa).substring(0, i);
    }
    
    public void reverse(char[] sa, int start, int end) {
        int p1 = start;
        int p2 = end;
        while (p1 < p2) {
            char tmp = sa[p1];
            sa[p1] = sa[p2];
            sa[p2] = tmp;
            p1++;
            p2--;
        }
    }
}

version2:

public class Solution {
    public String reverseWords(String s) {
        if (s.length() == 0) {
            return "";
        }
        char[] sa = s.toCharArray();
        reverse(sa, 0, sa.length - 1);
        int p1 = 0;
        int p2 = 0;
        int wordStart = 0;
        boolean flag = false;
        for (; p2 < sa.length; p2++) {
            if (sa[p2] == ' ' && flag) {
                reverse(sa, wordStart, p1 - 1);
                sa[p1++] = ' ';
                flag = false;
                wordStart = p1;
            } else if (sa[p2] != ' ') {
                flag = true;
                sa[p1++] = sa[p2];
            }
        }
        if (flag) {
            reverse(sa, wordStart, p1 - 1);
        } else if (p1 != 0) {
            p1--;
        }
        return new String(sa).substring(0, p1);
    }
    public void reverse(char[] A, int start, int end) {
        while (start < end) {
            char tmp = A[start];
            A[start] = A[end];
            A[end] = tmp;
            start++;
            end--;
        }
    }
}

1.6  Compare Version Numbers ---bug free

比较两个字符串表示的版本号哪个大。

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

分析：对于两个长度不一样的版本号，把长度小的后面用0来补齐。例如：1.8.9和2.21，将2.21补齐为2.21.0。然后从高到低比较即可。

public int compareVersion(String version1, String version2) {
    String[] levels1 = version1.split("\.");
    String[] levels2 = version2.split("\.");
    
    int length = Math.max(levels1.length, levels2.length);
    for (int i=0; i<length; i++) {
        Integer v1 = i < levels1.length ? Integer.parseInt(levels1[i]) : 0;
        Integer v2 = i < levels2.length ? Integer.parseInt(levels2[i]) : 0;
        int compare = v1.compareTo(v2);
        if (compare != 0) {
            return compare;
        }
    }
    
    return 0;
}

1.7 Largest Number ---bug free

给一堆非负整数，把它们按照一定的顺序排列，组成最大的数字。

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

分析：判断s1和s2哪个应该排在前面的依据是：比较s1+s2和s2+s1的字典序。

public class Solution {
    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        
        Comparator<String> c = new Comparator<String>() {
            public int compare(String s1, String s2) {
                String str1 = s1 + s2;
                String str2 = s2 + s1;
                return str1.compareTo(str2);
            }
        };
        Arrays.sort(strs, c);
        if (strs[strs.length - 1].equals("0")) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = strs.length - 1; i >= 0; i--) {
            sb.append(strs[i]);
        }
        return sb.toString();
    }
}

1.8  Isomorphic Strings ---bug free

判断两个字符串结构是否相同。

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

分析：用两个hash表记录历史的字符映射关系，这里用数组代替hash表更快。时间O(n)。

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] sa = s.toCharArray();
        char[] ta = t.toCharArray();
        int[] map1 = new int[256];
        int[] map2 = new int[256];
        for (int i = 0; i < s.length(); i++) {
            char sc = sa[i];
            char tc = ta[i];
            
            if (map1[sc] == 0 && map2[tc] == 0) {
                map1[sc] = tc + 1;
                map2[tc] = sc + 1;
            } else if (map1[sc] - 1 != tc || map2[tc] - 1 != sc) {
                return false;
            }
        }
        return true;
    }
}

1.9 Split Concatenated Strings

给一个字符串列表，允许对每个字符串反转或不反转，将所有字符串连接起来，并做循环位移，找到字典序最大的连接字符串。

给定一个字符串列表，你可以将这些字符串连接成一个循环字符串，对于每个字符串，你可以选择是否翻转它。在所有可能的循环字符串中，你需要分割循环字符串（这将使循环字符串变成一个常规的字符串），然后找到字典序最大的字符串。

具体来说，要找到字典序最大的字符串，你需要经历两个阶段：

将所有字符串连接成一个循环字符串，你可以选择是否翻转某些字符串，并按照给定的顺序连接它们。
在循环字符串的某个位置分割它，这将使循环字符串从分割点变成一个常规的字符串。
你的工作是在所有可能的常规字符串中找到字典序最大的一个。

示例:

输入: "abc", "xyz"
输出: "zyxcba"
解释: 你可以得到循环字符串 "-abcxyz-", "-abczyx-", "-cbaxyz-", "-cbazyx-"，
其中 '-' 代表循环状态。 
答案字符串来自第四个循环字符串， 
你可以从中间字符 'a' 分割开然后得到 "zyxcba"。
 

注意:

输入字符串只包含小写字母。
所有字符串的总长度不会超过 1,000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-concatenated-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析：

假设字符串列表长度为n，所有字符串长度和为N。
（1）暴力方法是枚举所有情况，每个字符串有反转和不反转两种情况，所以暴力的时间复杂度为O(2^n * N)，显然太慢。
（2）试想下，循环位移时，除了从中间断开的那个字符串，其他字符串一定要是反转和不反转两种情况中字典序最大的那一种。所以枚举应该从哪个字符串断开以及断开的位置，其他字符串取反转和不反转中字典序最大的连接上即可。时间复杂度降为O(N^2)。

code：

class Solution {
    public String splitLoopedString(String[] strs) {
        String[] maxStrs = new String[strs.length];
        for (int i = 0; i < strs.length; i++) {
            String s = strs[i];
            StringBuilder sb = new StringBuilder(strs[i]);
            String rs = sb.reverse().toString();
            if (s.compareTo(rs) > 0) {
                maxStrs[i] = s;
            } else {
                maxStrs[i] = rs; 
            }   
        }   

        StringBuilder res = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            res.append(maxStrs[i]);
        }   
        for (int i = 0; i < strs.length; i++) {
            StringBuilder other = new StringBuilder();
            for (int k = i + 1; k < strs.length; k++) {
                other.append(maxStrs[k]);
            }   
            for (int k = 0; k < i; k++) {
                other.append(maxStrs[k]);
            }   
            for (int m = 1; m <= 2; m++) {
                String s = m % 2 == 0 ? strs[i] : new StringBuilder(strs[i]).reverse().toString();
                for (int j = 0; j < s.length(); j++) {
                    StringBuilder head = new StringBuilder();
                    head.append(s.substring(j, s.length()));
                    head.append(other.toString());
                    head.append(s.substring(0, j));
                    if (head.toString().compareTo(res.toString()) > 0) {
                        res = head;
                    }
                }
            }
        }
        return res.toString();
    }
}

2 Two pointers

2.1 Longest Substring Without Repeating Characters --- bug free

给一个字符串，求出其中最长的不包含重复字符的子串

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

分析：hash表记录每个字符最近出现的索引，p1指针表示以当前字符为末尾的最长不重复子串的左端点。时间复杂度O(n)，空间O(1)（因为字符种类是有限的，所以哈希表可以当作O(1)的空间）。这里用256大小的数组代替哈希表更快（ascll码范围是0～255）。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] map = new int[256];
        int p1 = 0;
        int p2 = 0;
        int res = 0;
        for (; p2 < s.length(); p2++) {
            char c = s.charAt(p2);
            if (map[c] - 1 >= p1) {
                p1 = map[c];
            } 
            map[c] = p2 + 1;
            res = Math.max(res, p2 - p1 + 1);
        }
        return res;
    }
}

2.2 Container With Most Water ---bug free

给一堆垂直与X轴的线，找出其中两条线，能装最多的水

平面上有一堆垂直于x轴的线段，它们之间间隔相等，找出其中两条线段，使得它们与x轴围成的容器能装最多的水。

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

分析：两个指针，通过比较p1和p2的线段长度来决定移哪个。时间O(n)，空间O(1)。

public class Solution {
    public int maxArea(int[] height) {
        int res = 0;
        int p1 = 0;
        int p2 = height.length - 1;
        while (p1 < p2) {
            int cur = Math.min(height[p1], height[p2]) * (p2 - p1);
            res = Math.max(res, cur);
            if (height[p1] < height[p2]) {
                p1++;
            } else {
                p2--;
            }
        }
        return res;
    }
}

2.3 Remove Duplicates from Sorted Array ---bug free

给一个排序数组例如[1,1,1,2,2,3,3,4]，in-place删除其中的重复元素，变为[1,2,3,4,.....]，省略号是什么不重要。

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

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

分析：两个指针，p1指向待填充位置，p2直接pass的条件是p2!=0 && A[p2-1]==A[p2]。时间O(n)，空间O(1)。

public class Solution {
    public int removeDuplicates(int[] nums) {
        int p1 = 0;
        int p2 = 0;
        for (; p2 < nums.length; p2++) {
            if (p2 != 0 && nums[p2 - 1] == nums[p2]) {
                continue;
            }
            nums[p1++] = nums[p2];
        }
        return p1;
    }
}

2.4 Remove Element ---bug free

给一个数组，一个目标数，in-place删除目标数。例如，[1,3,3,2]，3。删除后变为[1,2,...]，省略号是什么不重要。

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

分析：用两个指针，p1指向待填充位置，p2遇到val就pass，否则就复制到前面。时间O(n)，空间O(1)。

public class Solution {
    public int removeElement(int[] nums, int val) {
        int p1 = 0, p2 = 0;
        for (p2 = 0; p2 < nums.length; p2++) {
            if (nums[p2] == val) {
                continue;
            }
            nums[p1++] = nums[p2];
        }
        return p1;
    }
}

2.5 Substring with Concatenation of All Words

2.6 Trapping Rain Water --- bug free

有一堆高高低低的柱形，问下完雨后所能接的雨水的量

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

分析：两边的柱子决定了灌水的基调，它们之间灌完水的高度一定是大于等于两边柱子的最小值的，哪边低就从哪边开始灌。时间O(n)，空间O(1)。

public class Solution {
    public int trapRainWater(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int p1 = 0;
        int p2 = heights.length - 1;
        int left = heights[p1];
        int right = heights[p2];
        int res = 0;
        while (p1 < p2) {
            if (left < right) {
            //从左边灌
                p1++;
                if (left > heights[p1]) {
                    res += left - heights[p1];
                } else {
                    left = heights[p1];
                }
            } else {
            //从右边灌
                p2--;
                if (right > heights[p2]) {
                    res += right - heights[p2];
                } else {
                    right = heights[p2];
                }
            }
        }
        return res;
    }
}

2.7 Remove Duplicates from Sorted Array II ---bug free

给一个排序数组例如[1,1,1,2,2,3,3,4]，in-place删除其中的重复元素，至多保留两个重复项，变为[1,1,2,2,3,3,4,.....]，省略号是什么不重要。,

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

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

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

分析：p1指针指向待插入的位置，p2往后扫描，用一个count变量来记录重复元素的个数。时间O(n),空间O(1)。

public class Solution {
    public int removeDuplicates(int[] nums) {
        int p1 = 0;
        int p2 = 0;
        int count = 0;
        while (p2 < nums.length) {
            if (p2 != 0 && nums[p2 - 1] == nums[p2]) {
                count++;
            } else {
                count = 0;
            }
            if (count <= 1) {
                nums[p1++] = nums[p2];
            }
            p2++;
        }
        return p1;
    }
}

2.8 Valid Palindrome ---bug free

给一个字符串，只考虑其中的字母和数字，并且不区分大小写，判断它是否为回文串。

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

分析：两个指针。时间O(n)，空间O(1)。

public class Solution {
    public boolean isPalindrome(String s) {
        int p1 = 0;
        int p2 = s.length() - 1;
        while (p1 < p2) {
            while (p1 < p2 && !isAlp(s.charAt(p1))) {
                p1++;
            }
            while (p1 < p2 && !isAlp(s.charAt(p2))) {
                p2--;
            }
            if (p1 < p2 && !isSame(s.charAt(p1), s.charAt(p2))) {
                return false;
            }
            p1++;
            p2--;
        }
        return true;
    }
    public boolean isAlp(char c) {
        return (c - '0' >= 0 && c - '0' <= 9) || (c - 'a' >= 0 && c - 'a' <= 25) || (c - 'A' >= 0 && c - 'A' <= 25);
    }
    public boolean isSame(char c1, char c2) {
        if (c1 == c2) {
            return true;
        }
        if (Character.isLowerCase(c1) && c2 - 'A' == c1 - 'a') {
            return true;
        }
        if (Character.isLowerCase(c2) && c1 - 'A' == c2 - 'a') {
            return true;
        }
        return false;
    }
}

3 Arrays

3.1 Next Permutation ---bug free

给出一个全排列，求按字典序的下一个全排列

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

分析：生成下一个全排列的方法：1先找到当前数组的最长递减后缀，范围是p~nums.length-1；2 将该后缀反转；3找到第一个大于nums[p-1]的元素，与nums[p-1]交换。时间复杂度O(n)，空间O(1)。

public class Solution {
    public void nextPermutation(int[] nums) {
        int p = nums.length - 1;
        while (p >= 1 && nums[p - 1] >= nums[p]) {
            p--;
        }
      
        reverse(nums, p, nums.length - 1);
        if (p != 0) {
            for (int i = p; i <= nums.length - 1; i++) {
                if (nums[i] > nums[p - 1]) {
                    int tmp = nums[i];
                    nums[i] = nums[p - 1];
                    nums[p - 1] = tmp;
                    break;
                }
            }
        }
    }
    
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }
}

3.2 First Missing Positive --- bug free 

给一个整数数组，找出其中丢失的第一个正整数（从1开始）。

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.

分析：把每个正整数放到正确的位置（1放到A[0]，2放到A[1]....），最后遍历数组，第一个位置和数不对应的就是丢失的数。使用swap操作代码简单。时间O(n)，空间O(1)。

public class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] >= 1 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
    
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

3.3 Rotate Image --- not bug free

顺时针90度翻转一个n*n的二维数组，要求inplace。

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

分析：先转第一层，然后转第二层......。位置(i,j)翻转后位置为(j,n-1-i)。时间O(n^2)，空间O(1)。

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        
        for (int lev = 1; lev <= n / 2; lev++) {
            int i = lev - 1;
            for (int j = i; j < n - lev; j++) {
                int n1 = matrix[i][j];
                int n2 = matrix[j][n - 1 - i];
                int n3 = matrix[n - 1 - i][n - 1 - j];
                int n4 = matrix[n - 1 - j][i];
                matrix[i][j] = n4;
                matrix[j][n - 1 - i] = n1;
                matrix[n - 1 - i][n - 1 - j] = n2;
                matrix[n - 1 - j][i] = n3;
            }
        }
    }
}

3.4 Spiral Matrix ---not bug free

螺旋形遍历一个m*n的二维数组。

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

分析：按层遍历，两个指针控制。每层的左上角p1是(start_x,start_y)，右下角p2是(end_x,end_y)。遍历完一层后，start_x++,start_y++,end_x--,enx_y--。注意单独讨论p1和p2在一条线上的情况。时间O(m*n),空间O(1)。

version1:

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0] == null) {
            return res;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int start_x = 0;
        int start_y = 0;
        int end_x = m - 1;
        int end_y = n - 1;
        while (end_x > start_x && end_y > start_y) {
            for (int j = start_y; j < end_y; j++) {
                res.add(matrix[start_x][j]);
            }
            for (int i = start_x; i < end_x; i++) {
                res.add(matrix[i][end_y]);
            }
            for (int j = end_y; j > start_y; j--) {
                res.add(matrix[end_x][j]);
            }
            for (int i = end_x; i > start_x; i--) {
                res.add(matrix[i][start_y]);
            }
            start_x++;
            start_y++;
            end_x--;
            end_y--;
        }
        if (end_x == start_x && end_y >= start_y) {
            for (int j = start_y; j <= end_y; j++) {
                res.add(matrix[start_x][j]);
            }
        } else if (end_y == start_y && end_x >= start_x) {
            for (int i = start_x; i <= end_x; i++) {
                res.add(matrix[i][start_y]);
            }
        }
        
        return res;
    }
}

version2:为避免连写四个for循环，使用了两个方向数组Di Dj。

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0] == null) {
            return res;
        }
        int m = matrix.length, n = matrix[0].length;
        int[] Di = {0, 1, 0, -1};
        int[] Dj = {1, 0, -1, 0};
        int starti = 0, startj = 0;
        int endi = m - 1, endj = n - 1;
        while (starti < endi && startj < endj) {
            int cur_i = starti;
            int cur_j = startj;
            for (int k = 0; k < 4; k++) {
                int count = k % 2 == 0 ? endj - startj : endi - starti;
                for (int c = 1; c <= count; c++) {
                    res.add(matrix[cur_i][cur_j]);
                    cur_i += Di[k];
                    cur_j += Dj[k];
                }
            }
            starti++;
            startj++;
            endi--;
            endj--;
        }
        if (starti < endi && startj == endj) {
            for (; starti <= endi; starti++) {
                res.add(matrix[starti][startj]);
            }
        } else if (startj <= endj && starti == endi) {
            for (; startj <= endj; startj++) {
                res.add(matrix[starti][startj]);
            }
        }
        return res;
    }
}

3.5 Spiral Matrix II ---bug free

螺旋形地给一个n*n矩阵赋1～n^2的值。

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

分析：与上一题一样。边遍历边赋值。

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] mat = new int[n][n];
        int count = 1;
        int start_x = 0;
        int start_y = 0;
        int end_x = n - 1;
        int end_y = n - 1;
        while (start_x < end_x && start_y < end_y) {
            for (int j = start_y; j < end_y; j++) {
                mat[start_x][j] = count++;
            }
            for (int i = start_x; i < end_x; i++) {
                mat[i][end_y] = count++;
            }
            for (int j = end_y; j > start_y; j--) {
                mat[end_x][j] = count++;
            }
            for (int i = end_x; i > start_x; i--) {
                mat[i][start_y] = count++;
            }
            start_x++;
            start_y++;
            end_y--;
            end_x--;
        }
        if (start_x == end_x && start_y <= end_y) {
            for (int j = start_y; j <= end_y; j++) {
                mat[start_x][j] = count++;
            }
        } else if (start_x <= end_x && start_y == end_y) {
            for (int i = start_x; i <= end_x; i++) {
                mat[i][start_y] = count++;
            }
        }
        return mat;
    }
}

3.6 Set Matrix Zeroes ---not bug free

将矩阵中所有0元素所在列和行都置0。

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

click to show follow up.

Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

分析：(1)先确定第0行和第0列要不要置0;(2)第一次遍历，把每个0元素的状态投射到第0行第0列;(3)第二次遍历，根据第0行第0列的状态进行矩阵置0;(4)对第0行第0列进行置0。

void setZeroes(vector<vector<int> > &matrix) {
    int col0 = 1, rows = matrix.size(), cols = matrix[0].size();

    for (int i = 0; i < rows; i++) {
        if (matrix[i][0] == 0) col0 = 0;
        for (int j = 1; j < cols; j++)
            if (matrix[i][j] == 0)
                matrix[i][0] = matrix[0][j] = 0;
    }

    for (int i = rows - 1; i >= 0; i--) {
        for (int j = cols - 1; j >= 1; j--)
            if (matrix[i][0] == 0 || matrix[0][j] == 0)
                matrix[i][j] = 0;
        if (col0 == 0) matrix[i][0] = 0;
    }
}

3.7 Gas Station ---not bug free

环形加油站，给出gas数组和cost数组，求能绕一圈的位置。

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.

分析：时间O(n)，空间O(1)。

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int start = 0;
        int past = -1;
        while (start < n && start > past) {
            past = start;
            int i = start;
            int tank = 0;
            while (tank + gas[i] - cost[i] >= 0) {
                tank = tank + gas[i] - cost[i];
                i = (i + 1) % n;
                if (i == start) {
                    return start;
                }
            }
            start = i + 1;
        }
        return -1;
    }
}

3.8 Majority Element ---not bug free

找出一个数组中出现次数超过一半的数。

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

分析：Moore voting algorithm：先选取第一个元素作为多数元素，记一个count作为它的得票数，如果后面的元素与它相等则count++，如果不相等则count--，当count为0时，说明前面的数中不存在重复次数超过一半的数，原问题可以转化为从剩下的数组中找出多数元素。时间复杂度O(n)，空间复杂度O(1)。

public class Solution {
    public int majorityElement(int[] nums) {
        int res = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                res = num;
                count = 1;
            } else {
                if (res == num) {
                    count++;
                } else {
                    count--;
                }
            }
        }
        return res;
    }
}

3.9  Majority Element II 

3.10 Rotate Array ---not bug free

把一个数组往右循环移动k位。

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

分析：使用三步翻转法。时间O(n)，空间O(1)。

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }
}

3.11 Contains Duplicate II ---bug free

判断数组中是否存在相同的两个数，使得它们的索引之差小于等于k。

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

分析：使用hash表。时间O(n)，空间O(n)。

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }
}

3.12 Contains Duplicate III ---not bug free

判断数组中是否存在两个数nums[i]和nums[j]，它们的差值的绝对值小于等于t，且i和j的差值的绝对值小于等于k。

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

分析1:滑动窗口+TreeSet，即Treeset中只存k + 1个数，保证了set中的两两数之间都满足索引差的条件。时间O(nlgk)。

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < nums.length; i++) {
            long cur = nums[i];
            if (i > k) {
                set.remove((long) nums[i - k - 1]);
            }

            if ((set.floor(cur) != null && cur - set.floor(cur) <= t) || 
                    (set.ceiling(cur) != null && set.ceiling(cur) - cur <= t)) {
                return true;
            }
            set.add(cur);
        }
        return false;
    }
}

分析2:buckets。

3.13 Summary Ranges ---bug free

给一个排序的整数数组，不包含重复元素，把连续的范围合并起来。

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

分析：遍历一遍数组即可。时间O(n)。

public class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<String>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int past = nums[0];
        int start = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == past + 1) {
                past = nums[i]; 
            } else {
                if (start == past) {
                    res.add(String.valueOf(start));
                } else {
                    res.add(String.valueOf(start) + "->" + String.valueOf(past));
                }
                start = nums[i];
                past = nums[i];
            }
        }
        if (start == past) {
            res.add(String.valueOf(start));
        } else {
            res.add(String.valueOf(start) + "->" + String.valueOf(past));
        }
        return res;
    }
}

3.14 Product of Array Except Self ---not bug free

给一个数组nums，要求求出数组output，其中output[i]是nums中除去nums[i]所有元素的乘积，要求不能用除法，时间O(n)，空间O(1)。

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

分析：要求不能用除法。不能有额外空间消耗（除了输出的output数组外），要在O(n)的时间完成。首先发现每个output值可以分解为左半边的乘积乘以右半边的乘积，因此第一遍扫描先在output记录左边的前缀积，第二遍从后往前扫描，用右边乘积乘以左边记录好的乘积即可。

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] output = new int[nums.length];
        output[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            output[i] = output[i - 1] * nums[i];
        }
        
        int rightPrefix = 1;
        for (int i = nums.length - 1; i > 0; i--) {
            output[i] = output[i - 1] * rightPrefix;
            rightPrefix *= nums[i];
        }
        output[0] = rightPrefix;
        return output;
    }
}

4 DFS && BFS

4.1 Generate Parentheses  ---bug free

给n对括号，求出所有合法的括号字符串

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

分析：对于找出所有的方案的题，99%是DFS。

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        
        helper(res, n, n, 0, new StringBuilder());
        return res;
    }
    public void helper(List<String> res, int left, int right, int leftWait, StringBuilder sb) {
        if (left == 0 && right == 0) {
            StringBuilder tmp = new StringBuilder(sb.toString());
            res.add(tmp.toString());
            return;
        }
        if (leftWait != 0) {
            sb.append(")");
            helper(res, left, right - 1, leftWait - 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (left != 0) {
            sb.append("(");
            helper(res, left - 1, right, leftWait + 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

4.2 Sudoku Solver ---not bug free

解数独

解一个填了一部分的数独。

分析：先把已知的坑填满，再来搜索。

public class Solution {
    public void solveSudoku(char[][] board) {
        boolean[][] rowUsed = new boolean[10][9];
        boolean[][] colUsed = new boolean[10][9];
        boolean[][][] geUsed = new boolean[10][3][3];
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    rowUsed[c - '0'][i] = true;
                    colUsed[c - '0'][j] = true;
                    geUsed[c - '0'][i / 3][j / 3] = true;
                }
            }
        }
        helper(board, 0, 0, rowUsed, colUsed, geUsed);
    }
    public boolean helper(char[][] board, int i, int j, boolean[][] rowUsed, boolean[][] colUsed, boolean[][][] geUsed) {
        if (i >= 9 || j >= 9) {
            return true;
        }
        
        int next_i = j == 8 ? i + 1 : i;
        int next_j = j == 8 ? 0 : j + 1;
        if (board[i][j] != '.') {
            return helper(board, next_i, next_j, rowUsed, colUsed, geUsed);
        } else {
            for (int num = 1; num <= 9; num++) {
                if (!rowUsed[num][i] && !colUsed[num][j] && !geUsed[num][i / 3][j / 3]) {
                    rowUsed[num][i] = true;
                    colUsed[num][j] = true;
                    geUsed[num][i / 3][j / 3] = true;
                    board[i][j] = (char) ('0' + num);
                    if (helper(board, next_i, next_j, rowUsed, colUsed, geUsed)) {
                        return true;
                    }
                    rowUsed[num][i] = false;
                    colUsed[num][j] = false;
                    geUsed[num][i / 3][j / 3] = false;
                    board[i][j] = '.';
                }
            }
        }
        return false;
    }
}

4.3 Combinations ---bug free

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

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

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

分析：注意剪枝，避免搜索不可能的情况。

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        helper(res, new ArrayList<Integer>(), 1, n, k);
        return res;
    }
    
    public void helper(List<List<Integer>> res, List<Integer> cur, int start, int n, int k) {
        if (cur.size() == k) {
            res.add(new ArrayList<Integer>(cur));
            return;
        }
        for (int i = start; i <= n; i++) {
            if (n - i + 1 + cur.size() < k) {
                break;
            }
            cur.add(i);
            helper(res, cur, i + 1, n, k);
            cur.remove(cur.size() - 1);
        }
    }
}

4.4 Word Search ---bug free

给一个二维字符矩阵和一个单词，问矩阵中是否存在一条路径，刚好能够组成这个单词。(路径方向只有上下左右，走过的地方不能重复走)

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

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

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

分析：这种搜索固定几个方向的题，可以用两个方向数组，使代码重复性大大降低。

public class Solution {
    public boolean exist(char[][] board, String word) {
        char[] s = word.toCharArray();
        boolean[][] used = new boolean[board.length][board[0].length];
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                
                if (board[i][j] == s[0]) {
                    used[i][j] = true;
                    if (helper(board, used, s, 1, i, j, dx, dy)) {
                        return true;
                    }
                    used[i][j] = false;
                }
            }
        }
        return false;
    }
    
    public boolean helper(char[][] board, boolean[][] used, char[] s, int index, int i, int j, int[] dx, int[] dy) {
        //i,j has used, you should search surround, search for index
        if (index == s.length) {
            return true;
        }
        for (int k = 0; k < 4; k++) {
            int nexti = i + dx[k], nextj = j + dy[k];
            if (nexti < 0 || nexti >= board.length || nextj < 0 || nextj >= board[0].length 
                    || used[nexti][nextj] || board[nexti][nextj] != s[index]) {
                continue;
            }
            used[nexti][nextj] = true;
            if (helper(board, used, s, index + 1, nexti, nextj, dx, dy)) {
                return true;
            }
            used[nexti][nextj] = false;
        }
        return false;
    }
}

4.5 Restore IP Addresses ---not bug free

给一个只包含数字的字符串，返回所能构成的所有可能的ip地址。

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

For example:
Given "25525511135",

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

分析：

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();
        helper(res, new StringBuilder(), s, 0, 0);
        return res;
    }
    
    public void helper(List<String> res, StringBuilder sb, String s, int start, int count) {
        if (count == 4 && start >= s.length()) {
            res.add(sb.substring(0, sb.length() - 1));
            return;
        }
        if (count == 4 || start >= s.length()) {
            return;
        }
        
        sb.append(s.substring(start, start + 1));
        sb.append('.');
        helper(res, sb, s, start + 1, count + 1);
        sb.delete(sb.length() - 2, sb.length());
        
        if (s.charAt(start) != '0' && start + 1 < s.length()) {
            sb.append(s.substring(start, start + 2));
            sb.append('.');
            helper(res, sb, s, start + 2, count + 1);
            sb.delete(sb.length() - 3, sb.length());
        }
        if (s.charAt(start) != '0' && start + 2 < s.length() && Integer.parseInt(s.substring(start, start + 3)) <= 255) {
            sb.append(s.substring(start, start + 3));
            sb.append('.');
            helper(res, sb, s, start + 3, count + 1);
            sb.delete(sb.length() - 4, sb.length());
        }
    }
}

4.6 Surrounded Regions ---not bug free

给一个矩阵，包含元素X和元素O。将X包围的O区域全部置为X。

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

分析1：从边缘的O开始搜索，将边缘O连着所有O置为“1”。然后遍历整个矩阵，把"1"改为“O”，不是“1”的全都置为“X”。这里的搜索如果用递归的DFS，可能会导致栈溢出，所以最好用非递归的BFS。

public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                BFS(board, i, 0, m, n);
            }
            if (board[i][n - 1] == 'O') {
                BFS(board, i, n - 1, m, n);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                BFS(board, 0, j, m, n);
            }
            if (board[m - 1][j] == 'O') {
                BFS(board, m - 1, j, m, n);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '1') {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }
    
    public void BFS(char[][] board, int i, int j, int m, int n) {
        Queue<Element> q = new LinkedList<Element>();
        q.offer(new Element(i, j));
        board[i][j] = '1';
        while (!q.isEmpty()) {
            Element e = q.poll();
            if (e.x - 1 >= 0 && board[e.x - 1][e.y] == 'O') {
                q.offer(new Element(e.x - 1, e.y));
                board[e.x - 1][e.y] = '1';
            }
            if (e.y - 1 >= 0 && board[e.x][e.y - 1] == 'O') {
                q.offer(new Element(e.x, e.y - 1));
                board[e.x][e.y - 1] = '1';
            }
            if (e.x + 1 < m && board[e.x + 1][e.y] == 'O') {
                q.offer(new Element(e.x + 1, e.y));
                board[e.x + 1][e.y] = '1';
            }
            if (e.y + 1 < n && board[e.x][e.y + 1] == 'O') {
                q.offer(new Element(e.x, e.y + 1));
                board[e.x][e.y + 1] = '1';
            }
        }
    }
}

class Element {
    int x;
    int y;
    Element(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

分析2: 并查集。第一次扫描矩阵，把连成一片的O合并成一个集合。然后把所有边上的O合并为一个集合，记为-1。第二次扫描，把所有不属于集合-1的O都置为X。

4.7 Palindrome Partitioning ---not bug free

给一个字符串，求出它所有的回文串划分方式。

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"]
]

 分析：先用动态规划求出isPalindrome数组，并用palindrome数组保存好所有回文串。然后再使用DFS搜索。

public class Solution {
    public List<List<String>> partition(String s) {
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];
        String[][] palindrome = new String[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            isPalindrome[i][i] = true;
            palindrome[i][i] = s.substring(i, i + 1);
            if (i > 0) {
                isPalindrome[i][i - 1] = true;
            }
        }
        for (int len = 2; len <= s.length(); len++) {
            for (int i = 0; i + len <= s.length(); i++) {
                if (s.charAt(i) == s.charAt(i + len - 1) && isPalindrome[i + 1][i + len - 2]) {
                    isPalindrome[i][i + len - 1] = true;
                    palindrome[i][i + len - 1] = s.substring(i, i + len);
                }
            }
        }
        
        List<List<String>> res = new ArrayList<List<String>>();
        
        helper(s, res, new ArrayList<String>(), 0, isPalindrome, palindrome);
        return res;
    }
    public void helper(String s, List<List<String>> res, List<String> cur, int start, boolean[][] isPalindrome, String[][] palindrome) {
        if (start >= s.length()) {
            res.add(new ArrayList<String>(cur));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome[start][i]) {
                cur.add(palindrome[start][i]);
                helper(s, res, cur, i + 1, isPalindrome, palindrome);
                cur.remove(cur.size() - 1);
            }
        }
    }
}

4.8 Number of Islands ---bug free

给01矩阵，相邻的1构成一个岛屿，求岛屿的数量。

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3

分析：DFS。并查集也可以做。记得用方向数组使代码更好看。

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] marked = new boolean[m][n];
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !marked[i][j]) {
                    count++;
                    helper(grid, marked, i, j, m, n);
                }
            }
        }
        return count;
    }
    public void helper(char[][] grid, boolean[][] marked, int x, int y, int m, int n) {
        marked[x][y] = true;
        if (x - 1 >= 0 && grid[x - 1][y] == '1' && !marked[x - 1][y]) {
            helper(grid, marked, x - 1, y, m, n);
        }
        if (y - 1 >= 0 && grid[x][y - 1] == '1' && !marked[x][y - 1]) {
            helper(grid, marked, x, y - 1, m, n);
        }
        if (x + 1 < m && grid[x + 1][y] == '1' && !marked[x + 1][y]) {
            helper(grid, marked, x + 1, y, m, n);
        }
        if (y + 1 < n && grid[x][y + 1] == '1' && !marked[x][y + 1]) {
            helper(grid, marked, x, y + 1, m, n);
        }
    }
}

 

  

5 Math 

5.1 Reverse Integer -- not bug free

将一个整数反转

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

分析：注意先转为正long类型。最后判断，如果溢出应该返回0。时间O(lgx)，空间O(1)。

public class Solution {
    public int reverse(int x) {
        long xL = Math.abs((long) x);
        long res = 0;
        while (xL != 0) {
            res = res * 10 + xL % 10;
            xL = xL / 10;
        }
        
        if (x < 0) {
            res = -res;
        }
        if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) {
            return 0;
        }
        return (int) res;
    }
}

5.2 Palindrome Number --- not bug free

判断一个整数是不是回文

Determine whether an integer is a palindrome. Do this without extra space.

分析1：先reverse这个整数，如果溢出则返回0，然后比较reverse之后是否与原来相等。时间O(lgx)，O(1)额外空间。

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int rx = reverse(x);
        return rx == x;
    }
    public int reverse(int x) {
        long xL = Math.abs((long) x);
        long res = 0;
        while (xL != 0) {
            res = res * 10 + xL % 10;
            xL = xL / 10;
        }
        
        if (x < 0) {
            res = -res;
        }
        if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) {
            return 0;
        }
        return (int) res;
    }
}

分析2: 只需要reverse一半即可。这样做可以直接避免溢出，且代码简洁。时间O(lgx / 2)，空间O(1)。

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int rev = 0;
        while (x > rev){
            rev = rev * 10 + x % 10;
            x = x / 10;
        }
        return (x == rev || x == rev / 10);
    }
}

5.3 String to Integer (atoi) 

 实现atoi字符串转数字

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: "42"
输出: 42
示例 2:

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。
示例 5:

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-integer-atoi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

analyse：

定义三个变量：
res为最终结果
inNum 为是否进入数字
pos为结果的正负号。

code：

class Solution {
    public int myAtoi(String str) {
        long res = 0;
        boolean inNum = false;
        int pos = 1;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == ' ' && !inNum) {
                continue;
            } else if ((c == '+' || c == '-') && !inNum) {
                pos = c == '+' ? 1 : -1;
                inNum = true;
            } else if (c - '0' >= 0 && c - '0' <= 9) {
                res = res * 10 + c - '0';
                inNum = true;
                if (res * pos > Integer.MAX_VALUE) {
                    return Integer.MAX_VALUE;
                } else if (res * pos < Integer.MIN_VALUE) {
                    return Integer.MIN_VALUE;
                } 
            } else {
                break;
            }
        }   
        res *= pos;
        return (int)res;
    }   
}

5.4 Roman to Integer

 将罗马数字转换为阿拉伯数字

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "III"
输出: 3
示例 2:

输入: "IV"
输出: 4
示例 3:

输入: "IX"
输出: 9
示例 4:

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/roman-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

analyse:

遍历罗马数字每个字符，将结果累加到res上。特殊情况：如果当前字符的后一个字符比当前字符数字大, 则要累加到res上的数是：后一个字符对应的数字减去当前字符对应的数字，同时跳过后一个字符。

code：

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        initialMap(map);
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            char nc = i < s.length() - 1 ? s.charAt(i + 1) : c;
            if (map.get(nc) > map.get(c)) {
                res += map.get(nc) - map.get(c);
                i++;
            } else {
                res += map.get(c);
            }   
        }   
        return res;
    }   

    public void initialMap(Map<Character, Integer> map) {
        map.put('I', 1); 
        map.put('V', 5); 
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
    }   
}

5.5 Integer to Roman

将阿拉伯数字转换为罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

输入: 3
输出: "III"
示例 2:

输入: 4
输出: "IV"
示例 3:

输入: 9
输出: "IX"
示例 4:

输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:

输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-to-roman
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

analyse:

将罗马数字符号排序为：1000,500,100,50,10,5,1
对于数字num，找到第一个小于num的首1罗马数字e（1000，100, 10, 1），
设fac为num / e.number，分四种情况讨论：
(1) fac < 4
(2) fac ==4
(3) fac > 4 && fac < 9
(4) fac == 9

为了方便实现，定义一个list ： [(1000, M), (500, D), (100, C), (50, L), (10, X), (5, V), (1, I)]

code：

class Solution {
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        List<Element> list = new ArrayList<Element>();
        initialList(list);
        while (num != 0) {
            for (int i = list.size() - 1; i >= 0; i -= 2) {
                Element e = list.get(i);
                if (e.number > num) {
                    continue;
                }
                int fac = num / e.number;

                if (fac < 4) {
                    fac = fac;
                } else if (fac == 4) {
                    sb.append(e.roman);
                    sb.append(list.get(i + 1).roman);
                    fac = 0;
                } else if (fac > 4 && fac < 9) {
                    sb.append(list.get(i + 1).roman);
                    fac = fac - 5;
                } else {
                    sb.append(e.roman);
                    sb.append(list.get(i + 2).roman);
                    fac = 0;
                }
                for (int k = 1; k <= fac; k++) {
                    sb.append(e.roman);
                }
                num = num % e.number;
                break;
            }
        }
        return sb.toString();
    }
    public void initialList(List<Element> list) {
        list.add(new Element('I', 1));
        list.add(new Element('V', 5));
        list.add(new Element('X', 10));
        list.add(new Element('L', 50));
        list.add(new Element('C', 100));
        list.add(new Element('D', 500));
        list.add(new Element('M', 1000));
    }

}
class Element {
    char roman;
    int number;
    Element(char roman, int number) {
        this.roman = roman;
        this.number = number;
    }
}

5.6 Multiply Strings

5.7  Merge Intervals ---not bug free

给一堆区间，把重叠的进行合并。

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

分析：先把所有区间按照start排好序，把第一个区间加到合并集中。然后遍历之后的每个区间，只需要与合并集中最后一个区间进行比较合并。时间O(nlgn)。

/**
 * 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> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<Interval>();
        if (intervals == null || intervals.size() == 0) {
            return res;
        }
        Comparator<Interval> c = new Comparator<Interval>() {
            public int compare(Interval l1, Interval l2) {
                return l1.start - l2.start;
            }
        };
        
        Collections.sort(intervals, c);
        res.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            Interval last = res.get(res.size() - 1);
            if (last.end < cur.start) {
                res.add(cur);
            } else {
                last.end = Math.max(cur.end, last.end);
            }
        }
        return res;
    }
}

5.8 Insert Interval ---not bug free

有一堆区间，互不重叠，并且按照起点排好序了，现在往里面加入一个新的区间。

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

分析：先直接插入，然后再按照Merge Intervals的方法进行合并。时间O(n)。

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

5.9 Permutation Sequence --- not bug free

已知n和k，求出数字1,2,3...,n组成的全排列中的第k个排列（按字典序）。

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

分析1:一种思路是用next permutation这道题的方法，求k次next permutation。时间复杂度O(nk)，理论上比下面的方法好，但在leetcode测试集上不如方法2。

public class Solution {
    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        for (int i = 1; i < k; i++) {
            nextPermutation(nums);
        }
        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            sb.append(num);
        }
        return sb.toString();
    }
    public void nextPermutation(int[] nums) {
        int p = nums.length - 2;
        for (; p >= 0; p--) {
            if (nums[p] < nums[p + 1]) {
                break;
            }
        }
        
        reverse(nums, p + 1, nums.length - 1);
        if (p == -1) {
            return;
        }
        for (int i = p + 1; i < nums.length; i++) {
            if (nums[i] > nums[p]) {
                swap(nums, i, p);
                return;
            }
        }
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

分析2：按第一个数字来分，有n组，每组有(n-1)!个，因此用(k - 1) / (n - 1)!就能确定第一个数字，然后令k = (k - 1) % (n - 1)，即下一位是第几个；然后，第二个数字有n - 1组，每组有(n - 2)!个...以此类推。用一个list来存当前剩的数。时间O(n^2)，空间O(n)。

public class Solution {
    public String getPermutation(int n, int k) {
        if (n == 1) {
            return "1";
        }
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        
        int[] mults = new int[n];
        mults[1] = 1;
        for (int i = 2; i < n; i++) {
            mults[i] = mults[i - 1] * i;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n - 1; i++) {
            int j = (k - 1) / mults[n - 1 - i];
            sb.append(list.get(j));
            list.remove(j);
            k = (k - 1) % mults[n - 1 - i] + 1;
        }
        sb.append(list.get(0));
        
        return sb.toString();
    }
}

5.10 Add Binary ---not bug free

给两个字符串表示的二进制数，求他们的和。

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

分析：对应数字相加模2即可。时间O(n)。没有bug free是忘记p1--p2--。

public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int p1 = a.length() - 1;
        int p2 = b.length() - 1;
        int carry = 0;
        while (p1 >= 0 || p2 >= 0) {
            char c1 = p1 >= 0 ? a.charAt(p1--) : '0';
            char c2 = p2 >= 0 ? b.charAt(p2--) : '0';
            int sum = (c1 - '0') + (c2 - '0') + carry;
            carry = sum / 2;
            sb.append(sum % 2);
        }
        if (carry != 0) {
            sb.append(1);
        }
        return sb.reverse().toString();
    }
}

5.11 Gray Code ---bug free

打印n位的格雷码序列。

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

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

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

00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.

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

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

分析：n位格雷码序列，相当于先求出n-1位格雷码序列，做镜像后前面加一个1。非递归版，时间O(2^n)，额外空间O(1)。

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

5.12 Fraction to Recurring Decimal ---not bug free

用循环小数的形式表示两个整数相除的结果。

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".
Hint:

No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

分析：本题是用程序模拟人做除法。出现循环小数的情况是：当前的余数前面出现过。因此用一个hashmap来记住余数与其产生的小数位数的映射。为了考虑负数并避免溢出，要使用long类型。

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        StringBuilder sb = new StringBuilder();
        long n1L = numerator;
        long n2L = denominator;
        
        if ((numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0)) {
            sb.append("-");
            n1L = Math.abs(n1L);
            n2L = Math.abs(n2L);
        }
        Map<Long, Integer> map = new HashMap<Long, Integer>();
        sb.append(n1L / n2L);
        if (n1L % n2L == 0) {
            return sb.toString();
        }
        sb.append('.');
        
        long yushu = n1L % n2L;
        
        while (yushu != 0 && !map.containsKey(yushu)) {
            map.put(yushu, sb.length());
            sb.append(yushu * 10 / n2L);
            yushu = (yushu * 10) % n2L;
        }
        if (yushu == 0) {
            return sb.toString();
        }
        sb.insert(map.get(yushu), "(");
        sb.append(")");
        return sb.toString();
    }
}

5.13 Factorial Trailing Zeroes ---bug free

求n的阶乘的结果中末尾0的个数。

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

分析：末尾的0只可能由2*5产生，考虑乘式可以分解为a个2和b个5相乘，a和b的最小值就是末尾0的个数。又因为2的个数一定比5的个数多，因此只计算5的个数即可。

　　　5的个数 = 所有因子中能被5整除的个数 + 所有因子中能被25整除的个数 + 所有因子中能被125整除的个数······

public class Solution {
    public int trailingZeroes(int n) {
        long fiveCount = 0;
        long fiveBase = 5;
        while (fiveBase <= n) {
            fiveCount += n / fiveBase;
            fiveBase *= 5;
        }
        return (int) fiveCount;
    }
}

5.14 Happy Number ---bug free

判断一个数是否是happy number。

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

分析：用hash表记录历史出现的数。一旦出现重复就退出循环。判断当前数是否是1即可。

public class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<Integer>();
        while (!set.contains(n)) {
            set.add(n);
            int next = 0;
            while (n != 0) {
                next += (n % 10) * (n % 10);
                n = n / 10;
            }
            n = next;
        }
        if (n == 1) {
            return true;
        }
        return false;
    }
}

5.15 Count Primes

5.16 Rectangle Area ---bug free

求两个矩形覆盖的面积。

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

分析：设矩形1的上下左右边分别为u1,d1,l1,r1，矩形2的上下左右边分别为u2,d2,l2,r2。则两矩形不相交的充要条件是：u1在d2下方 或 u2在d1下方 或 l1在r2右边 或 l2在r1右边。其余情况一定相交。相交面积的求法是：相交矩形的左边是l1和l2其中靠右的边，相交矩形的右边是r1和r2其中靠左的边，相交矩形的上边是u1和u2的靠下的边，相交矩形的下边是d1和d2的靠上的边。

 public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int l1 = A, r1 = C, u1 = D, d1 = B, l2 = E, r2 = G, u2 = H, d2 = F;
        int area1 = (r1 - l1) * (u1 - d1);
        int area2 = (r2 - l2) * (u2 - d2);
        if (l1 >= r2 || r1 <= l2 || u1 <= d2 || u2 <= d1) {
            return area1 + area2;
        }
        int l3 = Math.max(l1, l2);
        int r3 = Math.min(r1, r2);
        int d3 = Math.max(d1, d2);
        int u3 = Math.min(u1, u2);
        int area3 = (r3 - l3) * (u3 - d3);
        return area1 + area2 - area3;
    }
}

6 Dynamic Programming

6.1 Regular Expression Matching --- not bug free 

判断字符串s和正则表达式p是否匹配，p可能包含'.'，'*' 和字符。

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

分析1：dp[i][j]表示s的前i个字符和p的前j个字符是否匹配，根据最后一个字符来列不同的状态方程。时间O(m*n)，空间O(m*n)。

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

分析2:滚动数组优化。时间O(m*n),空间O(n)。滚动数组避免出错的方法是，把二维dp表画在纸上，手机上的一张图清晰看出这种情况。

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

6.2 Longest Valid Parentheses --- not bug free

一个字符串，只包含'('和')'，求最长的合法的括号子串。

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

分析：使用栈和动态规划。dp[i]表示以位置i的括号为末尾的最长有效括号的长度。栈的作用是找到与当前右括号配对的左括号的位置。时间复杂度O(n)，空间复杂度O(n)。

public class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        int[] dp = new int[s.length()];
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else if (!stack.isEmpty()) {
                int left = stack.pop();
                dp[i] = i - left + 1;
                if (left > 0) {
                    dp[i] += dp[left - 1];
                }
                res = Math.max(dp[i], res);
            }
        }
        return res;
    }
}

6.3 Unique Binary Search Trees ---bug free

给定n，则数1,2,3,...,n能组成多少不同的二叉查找树。

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
           /     /      /       
     3     2     1      1   3      2
    /     /                        
   2     1         2                 3

分析：时间O(n^2)，空间O(n)。

public class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1; 
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= i - 1; j++) {
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }
        return dp[n];
    }
}

6.4  Unique Binary Search Trees II

6.5  House Robber ---bug free

相邻房子不能抢，求能抢的最大钱数。

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

分析：滚动指针法，时间O(n)，空间O(1)。

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length < 2) {
            return nums[0];
        }
        int[] dp = new int[2];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i % 2] = Math.max(dp[(i - 1) % 2], dp[(i - 2) % 2] + nums[i]);
        }
        return dp[(nums.length - 1) % 2];
    }
}

6.6 House RobberII ---not bug free

环形的街道，相邻房子不能抢，求能抢的最大钱数。

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

分析：由于第一个和最后一个不能同时抢，因此等效于分解为两个House Robber I 的问题，分别是从第二家到最后一家，从第一家到倒数第二家，求这两个解的最大值。时间O(n)，空间O(1)。

public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        
        int[] dp = new int[2];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length - 1; i++) {
            dp[i % 2] = Math.max(nums[i] + dp[(i - 2) % 2], dp[(i - 1) % 2]);
        }
        int tmp = dp[(nums.length - 2) % 2];
        
        dp[0] = nums[1];
        dp[1] = Math.max(nums[1], nums[2]);
        for (int i = 2; i < nums.length - 1; i++) {
            dp[i % 2] = Math.max(nums[i + 1] + dp[(i - 2) % 2], dp[(i - 1) % 2]);
        }
        return Math.max(dp[(nums.length - 2) % 2], tmp);
    }
}

6.7 Maximal Square ---bug free

一个01矩阵，求其中最大的1组成的正方形面积。

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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

分析：动态规划。dp[i][j]表示以当前元素为右下角的最大正方形边长。时间O(m * n)，空间O(n)。

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null) {
            return 0;
        }
        int res = 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[2][n];
        
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == '1') {
                dp[0][j] = 1;
                res = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            dp[i % 2][0] = 0;
            if (matrix[i][0] == '1') {
                dp[i % 2][0] = 1;
                res = Math.max(1, res);
            }
            for (int j = 1; j < n; j++) {
                dp[i % 2][j] = 0;
                if (matrix[i][j] == '1') {
                    dp[i % 2][j] = Math.min(Math.min(dp[(i - 1) % 2][j], dp[i % 2][j - 1]), dp[(i - 1) % 2][j - 1]) + 1;
                }
                res = Math.max(res, dp[i % 2][j] * dp[i % 2][j]);
            }
        }
        return res;
        
    }
}

7 Data Structure

7.1 Valid Parentheses ---bug free

一个字符串，包含了'(', ')', '{', '}', '[' and ']'，判断它是不是合法的。

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

分析：用栈。时间O(n)，空间O(n)。

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }
            } else if (c == ']') {
                if (stack.isEmpty() || stack.pop() != '[') {
                    return false;
                }
            } else {
                if (stack.isEmpty() || stack.pop() != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

7.2 Valid Sudoku --- bug free

判断一个填了部分的数独属否合法。

判断一个填了部分的数独是否有效。（不需要可解）

分析：开两个二维数组，一个三维数组。由于数独是9*9有限的，所以时间O(1)，空间O(1)。

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rowUsed = new boolean[10][9];
        boolean[][] colUsed = new boolean[10][9];
        boolean[][][] geUsed = new boolean[10][3][3];
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    if (rowUsed[c - '0'][i] || colUsed[c - '0'][j] || geUsed[c - '0'][i / 3][j / 3]) {
                        return false;
                    }
                    rowUsed[c - '0'][i] = true;
                    colUsed[c - '0'][j] = true;
                    geUsed[c - '0'][i / 3][j / 3] = true;
                }
            }
        }
        return true;
    }
}

7.3 Group Anagrams ---bug free

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], 
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]
Note: All inputs will be in lower-case.

分析：如果两个字符串是一个组，则它们排序后应该是相等的。用这个排序后的作为key。时间O(N * LlgL)，N是字符串个数，L是字符串平均长度。

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<List<String>>();
        Map<String, Integer> map = new HashMap<String, Integer>();
        
        for (String str : strs) {
            char[] cs = str.toCharArray();
            Arrays.sort(cs);
            String key = String.valueOf(cs);
            if (map.containsKey(key)) {
                res.get(map.get(key)).add(str);
            } else {
                List<String> l = new ArrayList<String>();
                l.add(str);
                res.add(l);
                map.put(key, res.size() - 1);
            }
        }
        return res;
    }
}

7.4 Maximal Rectangle ---not bug free

给一个矩阵，包含元素0和1，求里面最大只包含1的矩形面积。

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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.

分析：使用“最大直方图”这道题的思想，求出以每一行为底的最大直方图面积，时间O(mn)，空间O(n)。

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        Stack<Integer> s = new Stack<Integer>();
        int[] h = new int[n];
        int res = 0;
        
        for (int i = 0; i < m; i++) {
            //s.clear();
            for (int j = 0; j <= n; j++) {
                int key = 0;
                if (j == n) {
                    key = -1;
                } else {
                    h[j] = matrix[i][j] == '0' ? 0 : h[j] + 1;
                    key = h[j];
                }
                while (!s.isEmpty() && h[s.peek()] > key) {
                    int height = h[s.pop()];
                    int left = s.isEmpty() ? -1 : s.peek();
                    int right = j;
                    res = Math.max(res, height * (right - left - 1));
                }
                if (j != n) {
                    s.push(j);
                }
            }
        }
        return res;
    }
}

7.5 Evaluate Reverse Polish Notation ---bug free

计算逆波兰表达式。

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

分析：使用栈。

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> s = new Stack<Integer>();
        for (String str : tokens) {
            if (str.equals("+")) {
                s.push(s.pop() + s.pop());
            } else if (str.equals("-")) {
                int num1 = s.pop();
                int num2 = s.pop();
                s.push(num2 - num1);
            } else if (str.equals("*")) {
                s.push(s.pop() * s.pop());
            } else if (str.equals("/")) {
                int num1 = s.pop();
                int num2 = s.pop();
                s.push(num2 / num1);
            } else {
                s.push(Integer.parseInt(str));
            }
        }
        return s.pop();
    }
}

7.6 Basic Calculator ---not bug free

计算一个字符串表示的算式，可能包含的符号是'('，')'，'+'，'-'。

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

分析：只用使用一个栈。遍历字符串的时候，如果当前字符是数字，则加到当前的数字上；如果是加号，则说明当前数字已经结束，把当前数字乘上sign加到结果上，同时sign更新为1，数字更新为0；如果是减号，则说明当前数字已经结束，把当前数字乘上sign加到结果上，同时sign更新为-1，数字更新为0；如果是左括号，说明开始计算括号内的子表达式，前面的结果和当前符号应该压入栈中，同时结果置0，符号置1；如果是右括号，首先说明当前数字已经结束，把当前数字乘上sign加到结果上，同时当前结果应该乘上之前的sign，并加上之前的结果。bug free的诀窍是，碰到符号，想想做什么，res,num,sign哪些需要更新。

public int calculate(String s) {
    Stack<Integer> stack = new Stack<Integer>();
    int result = 0;
    int number = 0;
    int sign = 1;
    for(int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if(Character.isDigit(c)){
            number = 10 * number + (int)(c - '0');
        }else if(c == '+'){
            result += sign * number;
            number = 0;
            sign = 1;
        }else if(c == '-'){
            result += sign * number;
            number = 0;
            sign = -1;
        }else if(c == '('){
            //we push the result first, then sign;
            stack.push(result);
            stack.push(sign);
            //reset the sign and result for the value in the parenthesis
            sign = 1;   
            result = 0;
        }else if(c == ')'){
            result += sign * number;  
            number = 0;
            result *= stack.pop();    //stack.pop() is the sign before the parenthesis
            result += stack.pop();   //stack.pop() now is the result calculated before the parenthesis
            
        }
    }
    if(number != 0) result += sign * number;
    return result;
}

7.7 Basic Calculator II ---not bug free

计算一个字符串表示的算式，可能包含的符号是'+'，'-'，'*'，'/'。

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

分析：注意有5个变量，num记录当前的数，res存储最终的结果，sign表示每个加数的符号，tmp存储每个加数的值，op表示当前做乘法还是除法。每次遇到运算符号，都要用当前的数来更新tmp的值（tmp = op == '*' ? tmp * num : tmp / num），如果遇到的是加号和减号，tmp就是最终加数的值，将其乘以sign加到res上。

class Solution {
    public int calculate(String s) {
        int res = 0;
        int num = 0;
        int sign = 1;
        int tmp = 1;
        char op = '*';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c - '0' >= 0 && c - '0' <= 9) {
                num = num * 10 + c - '0';
            } else if (c == '+' || c == '-') {
                tmp = op == '*' ? tmp * num : tmp / num;
                res += sign * tmp;
                tmp = 1;
                op = '*';
                sign = c == '+' ? 1 : -1;
                num = 0;
            } else if (c == '*' || c == '/') {
                tmp = op == '*' ? tmp * num : tmp / num;
                op = c;
                num = 0;
            } else {
                continue;
            }
        }
        tmp = op == '*' ? tmp * num : tmp / num;
        res += sign * tmp;
        return res;
    }
}

 7.8 Basic Calculator III

计算一个字符串表示的算式，可能包含的符号是'+', '-', '*', '/', '(', ')'。

实现一个基本的计算器来计算简单的表达式字符串。

表达式字符串可以包含左括号 ( 和右括号 )，加号 + 和减号 -，非负 整数和空格 。

表达式字符串只包含非负整数， +, -, *, / 操作符，左括号 ( ，右括号 )和空格 。整数除法需要向下截断。

你可以假定给定的字符串总是有效的。所有的中间结果的范围为 [-2147483648, 2147483647]。

 

一些例子：

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12
 

注：不要 使用内置库函数 eval。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/basic-calculator-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

analyse:

做这道题前提是理解清楚basic calculator I && II：
（1）涉及五个变量：
res：存储最终的结果
num：记录当前的数
sign：当前加数的符号
tmp：当前加数的值
op：可能值为'*'或'/'，记录应该是tmp *= num 还是 tmp /= num。

（2）两个栈
stack1: 存之前的res, sign, tmp
stack2: 存之前的op

（3）遇到 "("
说明遇到新的子表达式，把当前的除num外的四个变量存入到栈中，然后定义新的四个变量，用于计算这个新的子表达式。

（4）遇到")"
说明当前子表达式结束。首先计算出当前子表达式的res，然后可以认为这个res是一个num，
然后弹出栈内存储的四个变量，分别赋值给res, sign, tmp, op。

code：

class Solution {
    public int calculate(String s) {
        int res = 0;
        int num = 0;
        int sign = 1;
        int tmp = 1;
        char op = '*';
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Character> stack2 = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c - '0' >= 0 && c - '0' <= 9) {
                num = num * 10 + c - '0'; 
            } else if (c == '+' || c == '-') {
                tmp = op == '*' ? tmp * num : tmp / num;
                res += tmp * sign;
                num = 0;
                sign = c == '+' ? 1 : -1; 
                tmp = 1;
                op = '*';
            } else if (c == '*' || c == '/') {
                tmp = op == '*' ? tmp * num : tmp / num;
                num = 0;
                op = c;
            } else if (c == '(') {
                stack1.push(res);
                stack1.push(sign);
                stack1.push(tmp);
                stack2.push(op);
                res = 0;
                sign = 1;
                tmp = 1;
                op = '*';
            } else if (c == ')') {
                tmp = op == '*' ? tmp * num : tmp / num;
                res += tmp * sign;
                num = res;
                tmp = stack1.pop();
                sign = stack1.pop();
                res = stack1.pop();
                op = stack2.pop();
            } else {
                continue;
            }
        }
        tmp = op == '*' ? tmp * num : tmp / num;
        res += tmp * sign;
        return res;
    }
}

8 Binary Search

8.1 Pow(x, n) --- not bug free

实现函数pow(x,n)

Implement pow(x, n).

分析：倍增法。时间O(lgn),空间O(1)。

public class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        while (n != 0) {
            long pow = 2;
            double fac = x;
            while (pow <= n) {
                fac *= fac;
                pow *= 2;
            }
            n = n - (int) (pow / 2);
            res *= fac;
        }
        return res;
    }
}

9 Tree

9.1 Symmetric Tree ---bug free

判断一颗树是不是对称的。

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / 
  2   2
 /  / 
3  4 4  3
But the following [1,2,2,null,3,null,3] is not:
    1
   / 
  2   2
      
   3    3
Note:
Bonus points if you could solve it both recursively and iteratively.

分析1:递归版。太简单代码不列了。主要看跌代版。

分析2:迭代版。对左子树做正常的中序遍历，同时对右子树做“右-根-左”的反向中序遍历（这样我就能保证，每次s1弹出的点与s2弹出的点刚好是关于结构对称的，再验证这两点的值是否相等即可）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        
        while (left != null && right != null) {
            s1.push(left);
            s2.push(right);
            left = left.left;
            right = right.right;
        }
        if (left != null || right != null) {
            return false;
        }
        
        while (!s1.isEmpty() && !s2.isEmpty()) {
            TreeNode cur1 = s1.pop();
            TreeNode cur2 = s2.pop();
            if (cur1.val != cur2.val) {
                return false;
            }
            left = cur1.right;
            right = cur2.left;
            while (left != null && right != null) {
                s1.push(left);
                s2.push(right);
                left = left.left;
                right = right.right;
            }
            if (left != null || right != null) {
                return false;
            }
        }
        return s1.isEmpty() && s2.isEmpty();
    }
}

9.2 Convert Sorted Array to Binary Search Tree --- bug free

把一个排序数组转化成一个平衡二叉查找树。

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

分析：思想很简单，时间O(n)，额外空间O(1)。注意与Convert Sorted List to Binary Search Tree这道题的区别，Convert Sorted List这道题使用的思想很巧妙。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }
    public TreeNode helper(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, start, mid - 1);
        root.right = helper(nums, mid + 1, end);
        return root;
    }
}

9.3 Flatten Binary Tree to Linked List ---bug free

把一颗二叉树拉直。

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / 
       2   5
      /    
     3   4   6
The flattened tree should look like:
   1
    
     2
      
       3
        
         4
          
           5
            
             6

分析：

/**
 * 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 flatten(TreeNode root) {
        falttenHelper(root);
    }
    public TreeNode falttenHelper(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        TreeNode leftEnd = null;
        TreeNode rightEnd = null;
        if (left != null) {
            root.left = null;
            root.right = left;
            leftEnd = falttenHelper(left);
            leftEnd.right = right;
        }
        if (right != null) {
            rightEnd = falttenHelper(right);
        }
        if (rightEnd != null) {
            return rightEnd;
        } else if (leftEnd != null) {
            return leftEnd;
        } else {
            return root;
        }
    }
}

9.4 Populating Next Right Pointers in Each Node ---not bug free

给一颗满二叉树，把同一层的节点连接起来。要求使用O(1)额外空间。

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
         1
       /  
      2    3
     /   / 
    4  5  6  7
After calling your function, the tree should look like:
         1 -> NULL
       /  
      2 -> 3 -> NULL
     /   / 
    4->5->6->7 -> NULL

分析：由于不能使用额外空间，因此不能使用队列做BFS的方法。这里的方法是，遍历第一层的时候，把第二层连接起来，然后再遍历第二层......。时间O(N)，空间O(1)。

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode head = root;
        TreeLinkNode cur = head;
        TreeLinkNode pre = null;
        
        while (head != null && head.left != null) {
            while (cur != null) {
                if (pre != null) {
                    pre.right.next = cur.left;
                }
                cur.left.next = cur.right;
                pre = cur;
                cur = cur.next;
            }
            head = head.left;
            cur = head;
            pre = null;
        } 
    }
}

9.5 Populating Next Right Pointers in Each Node II ---not bug free

给一颗任意的二叉树，把同一层的节点连接起来。要求使用O(1)额外空间。

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.
For example,
Given the following binary tree,
         1
       /  
      2    3
     /     
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  
      2 -> 3 -> NULL
     /     
    4-> 5 -> 7 -> NULL

分析：用一个哨兵节点dummy，遍历当前层链表，把每个节点的左儿子右儿子加到下一个链表上。时间O(N)，空间O(1)。

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode head = root;
        while (head != null) {
            TreeLinkNode dummy = new TreeLinkNode(0);
            TreeLinkNode tail = dummy;
            while (head != null) {
                if (head.left != null) {
                    tail.next = head.left;
                    tail = tail.next;
                }
                if (head.right != null) {
                    tail.next = head.right;
                    tail = tail.next;
                }
                head = head.next;
            }
            head = dummy.next;
        }
    }
}

9.6 Count Complete Tree Nodes ---bug free

求一颗完全二叉树的节点数。

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

分析：分别求出左右子树的高度，如果高度相等，说明左边是满树，可以用公式直接算出，右子树递归算；如果高度不相等，说明右子树是满树，直接算出，左子树递归求解。时间O(lgN * lgN)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int lh = getHeight(root.left);
        int rh = getHeight(root.right);
        if (lh == rh) {
            return (1 << lh) + countNodes(root.right);
        } else {
            return countNodes(root.left) + (1 << rh);
        }
    }
    public int getHeight(TreeNode root) {
        int h = 0;
        while (root != null) {
            root = root.left;
            h++;
        }
        return h;
    }
}

9.7 Invert Binary Tree ---not bug free

反转一颗二叉树。

Invert a binary tree.

     4
   /   
  2     7
 /    / 
1   3 6   9
to
     4
   /   
  7     2
 /    / 
9   6 3   1

分析：递归版很简单，非递归版则是用BFS遍历每个节点，遍历的时候把每个节点的左右子树互换。

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            TreeNode left = cur.left;
            TreeNode right = cur.right;
            cur.left = right;
            cur.right = left;
            if (left != null) {
                q.offer(left);
            }
            if (right != null) {
                q.offer(right);
            }
        }
        return root;
    }
}

9.8 Kth Smallest Element in a BST ---bug free

求二叉查找树的第k个节点。

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

分析：先找到第一个节点，然后用非递归中序遍历的方法往后数到第k个。

Follow up:在节点中存储左子树的大小. 在插入删除时也要同时维护左子树的大小. 再查找时,可以用二分. 时间复杂度为O(lgn)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> s = new Stack<TreeNode>();
        while (root != null) {
            s.push(root);
            root = root.left;
        }
        
        int res = 0;
        for (int i = 1; i <= k; i++) {
            TreeNode cur = s.pop();
            if (i == k) {
                res = cur.val;
            }
            cur = cur.right;
            while (cur != null) {
                s.push(cur);
                cur = cur.left;
            }
        }
        return res;
    }
}

9.9 Lowest Common Ancestor of a Binary Search Tree ---bug free

找二叉查找树中，两个节点的最近公共祖先。

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              
    ___2__          ___8__
   /              /      
   0      _4       7       9
         /  
         3   5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

分析：从根节点开始查找这两个节点，当两个节点分别在左右两边或者有一个等于当前节点时，当前节点就是最近公共祖先。时间复杂度是O(lgn)。这道题如果不用二叉查找树的性质，经典方法的时间是O(n)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null && ((root.val > p.val && root.val > q.val) || (root.val < p.val && root.val < q.val))) {
            if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return root;
    }
}

10 Bit Manipulation

10.1 Single Number  ---bug free

给一个数组，除了一个数之外，其他数都成对出现，求出这个数。

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

分析：把所有数异或起来，最终结果就是这个数。时间O(n),空间O(1)。

public class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }
}

10.2 Single Number II ---not bug free

给一个数组，除了一个数只出现了一次之外，其他数都出现了三次，求出这个数。

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

分析：int 数据共有32位，可以用32变量存储这N个元素中各个二进制位上1出现的次数，最后在进行模三操作，如果为1，那说明要找元素二进制表示中这一位为1。如果把3次改为k次，只需模k就行。时间O(n),空间O(1)。

public class Solution {
    public int singleNumber(int[] nums) {
        int[] count = new int[32];
        for (int num : nums) {
            for (int i = 0; i <= 31; i++) {
                count[i] += (num >> i) & 1;
            }
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res += (1 << i) * (count[i] % 3);
        }
        return res;
    }
}

10.3 Repeated DNA Sequences ---bug free

检测DNA中的重复序列。

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

分析1:最直接的办法，用hash表记录所有长为10的子序列出现的次数。时间O(n)，空间O(n)。

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<String>();
        Map<String, Integer> map = new HashMap<String, Integer>();
        
        int p1 = 0;
        int p2 = 9;
        while (p2 < s.length()) {
            String sub = s.substring(p1, p2 + 1);
            if (map.containsKey(sub)) {
                map.put(sub, map.get(sub) + 1);
            } else {
                map.put(sub, 1);
            }
            p1++;
            p2++;
        }
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 1) {
                res.add(entry.getKey());
            } 
        }
        return res;
    }
}

分析2:由于每个子序列长度是固定的，并且只包含四个字母。所以可以把数字进行编码。但是这种方式在时间上有什么好处呢？不明白。

10.4 Reverse Bits ---bug free

翻转位。

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

分析：每次用n & (n - 1)取出最后一位1，除2^31后加到结果上。

public class Solution {
    public int reverseBits(long n) {
        long m = ((long) Integer.MAX_VALUE) + 1;
        long res = 0;
        while (n != 0) {
            long tmp = n;
            n = n & (n - 1);
            res += m / (n ^ tmp);
        }
        return (int) res;
    }
}

10.5 Number of 1 Bits ---bug free

二进制中1的个数。

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

分析：使用n&(n-1)可以把最后一个1置0，比一位一位地判断是否是1要更优。

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1;
            count++;
        }
        return count;
    }
}

10.6 Bitwise AND of Numbers Range ---not bug free

求[m, n]范围内所有数的与运算结果。

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

分析：最终结果是m和n左边共同的部分。时间复杂度O(1)。

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int i = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            ++i;
        }
        return (m << i);
    }
};

11 Linked List

11.1 Intersection of Two Linked Lists ---bug free

给两条单链表，求它们的交点。

Write a program to find the node at which the intersection of two singly linked lists begins.


For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
begin to intersect at node c1.


Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

分析：先分别求出两条链表的长度。然后把较长链表的头指针往后移动长度的差值，之后两个头指针同时移动，第一个相等的节点就是交点。时间O(n)，空间O(1)。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = getLen(headA);
        int lenB = getLen(headB);
        if (lenA > lenB) {
            for (int i = 1; i <= lenA - lenB; i++) {
                headA = headA.next;
            }
        } else if (lenA < lenB) {
            for (int i = 1; i <= lenB - lenA; i++) {
                headB = headB.next;
            }
        }
        while (headA != headB && headA != null && headB != null) {
            headA = headA.next;
            headB = headB.next;
        }
        if (headA == headB) {
            return headA;
        }
        return null;
    }
    public int getLen(ListNode head) {
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        return len;
    }
}

12 graph

12.1 Course Schedule I && II---not bug free

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

分析：先遍历一遍所有边，求出所有点的入度，以及每个点的邻节点。然后用队列来做拓扑排序。I和II的思路完全一样。

语言细节：使用两个数组来代替hash表，数组inDegree[i]表示课程i的入度，数组neighbors[i]表示课程i的邻节点。由于java数组不支持泛型，因此声明neighbors时使用List[] neighbors = new List[numCourses]，从neighbors中取元素时要使用强制类型转换。

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];
        List[] neighbors = new List[numCourses];
        
        for (int i = 0; i < prerequisites.length; i++) {
            int start = prerequisites[i][0];
            int end = prerequisites[i][1];
            if (neighbors[start] == null) {
                neighbors[start] = new ArrayList<Integer>();
            }
            neighbors[start].add(end);
            inDegree[end]++;
        }
        
        Queue<Integer> q = new LinkedList<Integer>();
        List<Integer> res = new ArrayList<Integer>();
        
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            int cur = q.poll();
            res.add(cur);
            if (neighbors[cur] == null) {
                continue;
            }
            for (int j = 0; j < neighbors[cur].size(); j++) {
                int neighbor = (int) neighbors[cur].get(j);
                if (--inDegree[neighbor] == 0) {
                    q.offer(neighbor);
                }
            }
        }
        return res.size() == numCourses;
    }
}

12.2 判断有向图有没有环

拓扑排序，如果所有的点最后都能排序，说明不存在环。 

12.3 判断无向图有没有环 

 并查集，与“判断图是否是树”类似，只不过不需要最后的集合数为1。

Split Concatenated Strings