LeetCode 1-100 - MikeYan01

LeetCode Problems 1-100.

1. Two Sum#

我们需要保证nums[i]和target - nums[i]都在数组中，因此使用哈希表存储循环遍历时每个数nums[i]以及下标i的值，并检查target - nums[i]是否也在map中，如果存在，就可以直接提取两个数的位置得到结果。

1
class Solution {
2
    public int[] twoSum(int[] nums, int target) {
3
        if (nums == null || nums.length == 0) {
4
            return new int[] {};
5
        }
6

7
        int[] result = new int[2];
8

9
        // <Element, Index>
10
        Map<Integer, Integer> map = new HashMap<>();
11
        for (int i = 0; i < nums.length; i++) {
12
            if (map.containsKey(target - nums[i])) {
13
                result[0] = i;
14
                result[1] = map.get(target - nums[i]);
15
                return result;
16
            }
17
            map.put(nums[i], i);
18
        }
19

20
        return result;
21
    }
22
}

2. Add Two Numbers#

https://leetcode.com/problems/add-two-numbers/

加法运算是一个从低位到高位的循环过程，只要下列3个条件之一满足，就会一直持续下去：

第一个数某位不为空
第二个数某位不为空
进位不为0

因此我们创建一个新链表，按照上述条件，对l1和l2逐位计算相加，得到结果后创建一个新节点插入到链表中。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
13
        if (l1 == null) {
14
            return l2;
15
        }
16
        if (l2 == null) {
17
            return l1;
18
        }
19

20
        ListNode dummyHead = new ListNode(0); // dummy head of new list
21
        ListNode cur = dummyHead; // traverse new list
22

23
        int carry = 0;
24

25
        // still have digits
26
        while (l1 != null || l2 != null || carry != 0) {
27
            int val = 0;
28

29
            int val1 = l1 != null ? l1.val : 0;
30
            int val2 = l2 != null ? l2.val : 0;
31

32
            val = (val1 + val2 + carry) % 10;
33
            carry = (val1 + val2 + carry) / 10;
34

35
            // insert a new node
36
            cur.next = new ListNode(val);
37
            cur = cur.next;
38

39
            // move pointers forward
40
            if (l1 != null) {
41
                l1 = l1.next;
42
            }
43
            if (l2 != null) {
44
                l2 = l2.next;
45
            }
46
        }
47

48
        return dummyHead.next;
49
    }
50
}

3. Longest Substring Without Repeating Characters#

https://leetcode.com/problems/longest-substring-without-repeating-characters/

我们需要一个map记录每个字符最后一次出现的位置。由于s中的字符已经确定是英文字母或者符号，因此可以使用定长数组模拟map，提高运行效率。

定义两个指针begin和end，begin指向最长不重复子串起点，尾指针用于遍历s，判断当前字符是否于map中。我们的目标就是尾指针完成遍历后，通过两个指针的最大距离差值，得到最长的不重复子串长度。

遍历时需要注意，在遇到重复字符时，begin有两种更新方式：

这个字符上一次出现位置的后面（+1），这是满足不重复的前提下的最小取值
保持不变，因为有可能这个重复字符上一次出现的位置相当靠前，在[map[currentChar] + 1, begin]中间出现了其他的重复字符

具体选择哪种方式更新，只需比较当前begin和上一次出现位置+1的大小。

1
class Solution {
2
    public int lengthOfLongestSubstring(String s) {
3
        if (s.length() == 0) {
4
            return 0;
5
        }
6

7
        char[] array = s.toCharArray();
8

9
        int begin, end = 0; // two pointers to mark the longest substring
10
        int result = 0; // longest substring's length
11

12
        int[] map = new int[128]; // <Character, Index>
13
        Arrays.fill(map, -1);
14

15
        for (begin = 0, end = 0; end < s.length(); end++) {
16
            char currentChar = array[end];
17

18
            // if this is a repeating character, we either reset begin index to last appearance index + 1 to avoid duplicate
19
            // or remains unchanged. It is possible that [map[currentChar] + 1, begin] contains duplicate characters
20
            if (map[currentChar] >= 0) {
21
                begin = Math.max(begin, map[currentChar] + 1);
22
            }
23

24
            // update current character's last position index
25
            map[currentChar] = end;
26

27
            // update result
28
            result = Math.max(result, end - begin + 1);
29
        }
30
        return result;
31
    }
32
}

4. Median of Two Sorted Arrays#

https://leetcode.com/problems/median-of-two-sorted-arrays/

对于一个有序数组，我们做一次分割，将数组分割为两半部分，则数组中位数为下半部分最大值与上半部分最小值的平均值。这种取法的前提是两半部分具有相同的元素值。当数组中有偶数个元素时，分割很容易；而当有奇数个元素时，我们尝试将实际的中位数mid一分为二，这样两部分都有了这个mid，数组的中位数仍然可以用(mid + mid) / 2 = mid得到。

对于一个有N个元素的数组，如果定义分割左侧的数为L，右侧的数为R，则它们可以表示为：

1
L = nums[(N - 1) / 2]
2
R = nums[N/2]
3
mid = (L + R) / 2

现在，假设为元素之间的间隔也增加下标。例如：

1
[6 9 13 18]  ->   [# 6 # 9 # 13 # 18 #]    (N = 4)
2
position index     0 1 2 3 4 5  6 7  8     (N_Position = 9)
3

4
[6 9 11 13 18]->   [# 6 # 9 # 11 # 13 # 18 #]   (N = 5)
5
position index      0 1 2 3 4 5  6 7  8 9 10    (N_Position = 11)

易得知，总共有2N + 1个下标位，并且分割的位置一定在下标为N处。因此仍然有

1
index(L) = (N - 1) / 2
2
index(R) = N / 2

至此，我们完成了单个数组的推导。扩展到两个有序数组时，我们可以总结出：

一共有2M + 2N + 2个下标位
需要2个切割点，下标设定为C1和C2
切割的左侧和右侧总共都有M + N个元素

假设nums2是长度较短的数组，并且切割点的下标为C2 = K，则nums1的切割点下标为C1 = M + N - K。完成这两次切割后，我们可以得到切割点附近的四个下标：

1
L1 = nums1[(C1 - 1) / 2]
2
R1 = nums1[C1/2]
3
L2 = nums2[(C2 - 1) / 2]
4
R2 = nums2[C2/2]

为了保证我们的切割是合理的，我们需要保证：

1
L1 <= R1
2
L1 <= R2
3
L2 <= R1
4
L2 <= R2

显然，第1、4个条件是肯定满足的，因此只有中间两个条件满足时，我们才能得到正确的划分。此时，我们可以引用二分搜索。如果L1 > R2，说明nums1中的切割点取的过大，需要缩小，换言之，我们可以调整nums2中的切割点，使其变大并超过nums1中的切割点；而如果L2 > R1，说明nums2中的切割点取的过大，缩小即可。完成切分点的选取后，选取两个子数组相应的最大最小值取平均，即可得到最终答案。

需要注意的是，切割点的下标有可能会发生数组越界。只需假设数组两端各自存在一个极值，当切割点越界时自动赋极值即可解决。

1
class Solution {
2
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
3
        int m = nums1.length, n = nums2.length;
4

5
        // make sure nums2 is the smaller array
6
        if (m < n) {
7
            return findMedianSortedArrays(nums2, nums1);
8
        }
9

10
        int low = 0, high = n * 2;
11
        while (low <= high) {
12
            int cut2 = (low + high) / 2;
13
            int cut1 = m + n - cut2;
14

15
            // avoid boundary exception
16
            double L1 = (cut1 == 0) ? Integer.MIN_VALUE : nums1[(cut1-1)/2];
17
            double L2 = (cut2 == 0) ? Integer.MIN_VALUE : nums2[(cut2-1)/2];
18
            double R1 = (cut1 == m * 2) ? Integer.MAX_VALUE : nums1[(cut1)/2];
19
            double R2 = (cut2 == n * 2) ? Integer.MAX_VALUE : nums2[(cut2)/2];
20

21
            if (L1 > R2) {
22
                // nums1's lower half is too big; need to move C1 left (C2 right)
23
                low = cut2 + 1;
24
            } else if (L2 > R1) {
25
                // nums2's lower half too big; need to move C2 left.
26
                high = cut2 - 1;
27
            } else {
28
                // Otherwise, that's the right cut.
29
                return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
30
            }
31
        }
32
        return -1;
33
    }
34
}

5. Longest Palindromic Substring#

https://leetcode.com/problems/longest-palindromic-substring/

遍历每一个字符，每一个字符都向两侧延展，如果新延展得到的两个字符仍然相同则继续延展，以此计算能延展的最大长度。

考虑到回文字符串的长度有两种可能，需要按照奇偶性进行两次延展判断。

1
class Solution {
2
    private int startIndex = 0, maxLen = 0;
3

4
    private void checkPalindrome(char[] array, int left, int right) {
5
        while (left >= 0 && right <= array.length - 1 && array[left] == array[right]) {
6
            left--;
7
            right++;
8
        }
9

10
        // update maxLen = (right - 1) - (left + 1) + 1 = right - left - 1
11
        if (maxLen < right - left - 1) {
12
            maxLen = right - left - 1;
13
            startIndex = left + 1;
14
        }
15
    }
16

17
    public String longestPalindrome(String s) {
18
        if (s.length() <= 1) {
19
            return s;
20
        }
21

22
        char[] array = s.toCharArray();
23
        for (int i = 0; i < array.length - 1; i++) {
24
            checkPalindrome(array, i, i); // assume odd length
25
            checkPalindrome(array, i, i+1); // assume even length
26
        }
27

28
        return s.substring(startIndex, startIndex + maxLen);
29
    }
30
}

6. Zigzag Conversion#

https://leetcode.com/problems/zigzag-conversion/

根据numRows的长度建立等长的StringBuilder数组，每一行对应一个StringBuilder。按照“竖直向下——斜向右上”的顺序不断向当前行的StringBuilder添加字符串中的字符即可。输出时，要对StringBuilder进行格式转化。

1
class Solution {
2
    public String convert(String s, int numRows) {
3
        int len = s.length();
4

5
        // every row is a StringBuilder
6
        StringBuilder[] sb = new StringBuilder[numRows];
7
        for (int i = 0; i < numRows; i++) {
8
            sb[i] = new StringBuilder();
9
        }
10

11
        // index to traverse the whole string
12
        int index = 0;
13
        while (index < len) {
14
            // vertically down
15
            for (int i = 0; i < numRows && index < len; i++) {
16
                sb[i].append(s.charAt(index++));
17
            }
18

19
            // obliquely up (not include the first and last row)
20
            for (int i = numRows - 2; i >= 1 && index < len; i--) {
21
                sb[i].append(s.charAt(index++));
22
            }
23
        }
24

25
        // append all rows of result
26
        for (int i = 1; i < numRows; i++) {
27
            sb[0].append(sb[i]);
28
        }
29

30
        return sb[0].toString();
31
    }
32
}

7. Reverse Integer#

https://leetcode.com/problems/reverse-integer/

通过整除反向提取每一位数。为了预防范围溢出，需要在每一次提取后进行一次溢出判断。

1
class Solution {
2
    public int reverse(int x) {
3
        long result = 0;
4

5
        while (x != 0) {
6
            // obtain the last bit
7
            result = result * 10 + x % 10;
8
            x /= 10;
9

10
            // overflow check
11
            if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
12
                return 0;
13
            }
14
        }
15

16
        return (int)result;
17
    }
18
}

8. String to Integer (atoi)#

https://leetcode.com/problems/string-to-integer-atoi/

流程分为三步：

去除字符串开头的空格
判断是否存在正负号
判断是否为数字。如果是数字，更新运算结果，并检查当前结果是否超出整数范围；如果不是数字，则返回当前结果

1
class Solution {
2
    public int myAtoi(String str) {
3
        // trim leading blank space
4
        str = str.trim();
5
        if (str.length() == 0) {
6
            return 0;
7
        }
8

9
        // detect sign
10
        char firstChar = str.charAt(0);
11
        int sign = 1;
12
        int digitStart = 0; // default no sign char, thus digit start from index 0
13
        if (firstChar == '+' || firstChar == '-') {
14
            sign = (firstChar == '+') ? 1 : -1;
15
            digitStart++;
16
        }
17

18
        // add digits
19
        long sum = 0;
20
        for (int i = digitStart; i < str.length(); i++) {
21
            char current = str.charAt(i);
22

23
            // non-digit, return sum immediately
24
            if (current < '0' || current > '9') {
25
                return (int)sum * sign;
26
            }
27

28
            // continue adding current digit
29
            sum = sum * 10 + current - '0';
30

31
            // overflow checking
32
            if (sign == 1 && sum > Integer.MAX_VALUE) {
33
                return Integer.MAX_VALUE;
34
            }
35
            if (sign == -1 && -sum < Integer.MIN_VALUE) {
36
                return Integer.MIN_VALUE;
37
            }
38
        }
39
        return (int)sum * sign;
40
    }
41
}

9. Palindrome Number#

https://leetcode.com/problems/palindrome-number/

将数字反转后与原数字进行比较。注意，不需要完整地将整个数字进行反转，只需要反转一半的数字，并与剩余一半进行比较即可。

1
class Solution {
2
    public boolean isPalindrome(int x) {
3
        // exclude negative number and 10's multiple
4
        if (x < 0 || (x != 0 && x % 10 == 0)) {
5
            return false;
6
        }
7

8
        int result = 0;
9

10
        // only need to reverse half of all digits
11
        while (x > result) {
12
            result = result * 10 + x % 10;
13
            x /= 10;
14
        }
15

16
        // odd or even length
17
        return (x == result || x == result / 10);
18
    }
19
}

10. Regular Expression Matching#

https://leetcode.com/problems/regular-expression-matching/

此题需要使用二维动态规划算法。对于s和p，我们需要从头开始推导出子字符串s[i]和p[j]的匹配情况，进而推出整个s和p是否匹配。

解决时，需要对题设条件进行分类讨论：

最标准的匹配情况，即string[i] = pattern[j]，则dp[i+1][j+1] = dp[i][j]
pattern中出现了'.'，可以匹配string中任意的一个字符，同样有dp[i+1][j+1] = dp[i][j]
pattern中出现了'*'，需要进一步讨论：
- 如果pattern[j-1] != string[i]，说明此时的'a*'只能作为空字符串匹配，因此dp[i+1][j+1] = dp[i+1][j-1]
- 如果pattern[j-1] == string[i], 或是pattern[j-1] == '.'，即在’*‘之前的一个字符也能够匹配上，则：
  - 如果'*'匹配空字符串，则dp[i+1][j+1] = dp[i+1][j-1]
  - 如果'*'匹配一个字符，则dp[i+1][j+1] = dp[i+1][j]
  - 如果'*'匹配多个字符，则dp[i+1][j+1] = dp[i][j+1]

1
class Solution {
2
    public boolean isMatch(String s, String p) {
3
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
4

5
        // s and p are both empty, so they can match
6
        dp[0][0] = true;
7

8
        // pattern cannot start with '*'
9
        if (p.length() > 0 && p.charAt(0) == '*') {
10
            return false;
11
        }
12

13
        // '*' match
14
        for (int j = 0; j < p.length(); j++) {
15
            if (p.charAt(j) == '*' && dp[0][j-1]) {
16
                dp[0][j+1] = true;
17
            }
18
        }
19

20
        for (int i = 0; i < s.length(); i++) {
21
            for (int j = 0; j < p.length(); j++) {
22
                // regular matching, or '.' matching
23
                if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
24
                    dp[i+1][j+1] = dp[i][j];
25
                } else if (p.charAt(j) == '*') {
26
                    // * can only be matched as empty char
27
                    if (s.charAt(i) != p.charAt(j-1)) {
28
                        dp[i+1][j+1] = dp[i+1][j-1];
29
                    }
30

31
                    // * can be matched as 0, 1 or multiple chars
32
                    if (s.charAt(i) == p.charAt(j-1) || p.charAt(j-1) == '.') {
33
                        dp[i+1][j+1] = dp[i+1][j-1] || dp[i+1][j] || dp[i][j+1];
34
                    }
35
                }
36
            }
37
        }
38

39
        return dp[s.length()][p.length()];
40
    }
41
}

11. Container With Most Water#

https://leetcode.com/problems/container-with-most-water/

问题转化为判断两个横坐标之间能够围成的最大面积。定义两个指针，一个指向数组头向尾遍历，另一个指向数组尾向头遍历。在遍历之前不断计算当前能围成的最大面积，并且向着可能进一步增大面积的方向移动指针。

1
class Solution {
2
    public int maxArea(int[] height) {
3
        if (height == null || height.length <= 1) {
4
            return 0;
5
        }
6

7
        int left = 0, right = height.length - 1;
8
        int result = 0, current = 0; // max area, current area
9

10
        while (left < right) {
11
            current = (right - left) * Math.min(height[left], height[right]);
12
            result = Math.max(result, current);
13

14
            // keep the higher edge, and try to increase the other edge
15
            if (height[left] < height[right]) {
16
                left++;
17
            } else {
18
                right--;
19
            }
20
        }
21
        return result;
22
    }
23
}

12. Integer to Roman#

https://leetcode.com/problems/integer-to-roman/

非常无聊的题目，直接穷举nums范围内各个基数单位，不断叠加上当前的最大基数对应的罗马字符。

1
class Solution {
2
    public String intToRoman(int num) {
3
        int[] value = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
4
        String[] roman = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
5
        StringBuilder sb = new StringBuilder();
6

7
        for (int i = 0; i < value.length; i++) {
8
            while (num >= value[i]) {
9
                sb.append(roman[i]);
10
                num = num - value[i];
11
            }
12
        }
13

14
        return sb.toString();
15
    }
16
}

13. Roman to Integer#

https://leetcode.com/problems/roman-to-integer/

遇到可能包含歧义的字母（M, X, V等）时，额外判断后一个字母明确具体数字即可。

1
class Solution {
2
    public int romanToInt(String s) {
3
        if (s.length() == 0) {
4
            return 0;
5
        }
6

7
        int i = 0;
8
        int len = s.length();
9
        int result = 0;
10

11
        while (i < len) {
12
            char c = s.charAt(i); // current character
13
            char nextChar = '.'; // if there is a next character
14
            if (i != len - 1) {
15
                nextChar = s.charAt(i+1);
16
            }
17

18
            // need to check IV and IX
19
            if (c == 'I') {
20
                if (nextChar == 'V') {
21
                    result += 4;
22
                    i += 2;
23
                } else if (nextChar == 'X') {
24
                    result += 9;
25
                    i += 2;
26
                } else {
27
                    result += 1;
28
                    i += 1;
29
                }
30
            }
31

32
            else if (c == 'V') {
33
                result += 5;
34
                i += 1;
35
            }
36

37
            // need to check XL and XC
38
            else if (c == 'X') {
39
                if (nextChar == 'L') {
40
                    result += 40;
41
                    i += 2;
42
                } else if (nextChar == 'C') {
43
                    result += 90;
44
                    i += 2;
45
                } else {
46
                    result += 10;
47
                    i += 1;
48
                }
49
            }
50

51
            else if (c == 'L') {
52
                result += 50;
53
                i += 1;
54
            }
55

56
            // need to check CD and CM
57
            else if (c == 'C') {
58
                if (nextChar == 'D') {
59
                    result += 400;
60
                    i += 2;
61
                } else if (nextChar == 'M') {
62
                    result += 900;
63
                    i += 2;
64
                } else {
65
                    result += 100;
66
                    i += 1;
67
                }
68
            }
69

70
            else if (c == 'D') {
71
                result += 500;
72
                i += 1;
73
            }
74

75
            else if (c == 'M') {
76
                result += 1000;
77
                i += 1;
78
            }
79
        }
80
        return result;
81
    }
82
}

14. Longest Common Prefix#

https://leetcode.com/problems/longest-common-prefix/

初始假定第一个词就是LCS。为了验证假设，我们需要逐个检查所有后续字符串，确定最开始的LCS也是后面字符串的前缀。如果不满足，则删掉LCS的最后一个字符。

1
class Solution {
2
    public String longestCommonPrefix(String[] strs) {
3
        if (strs == null || strs.length == 0) {
4
            return "";
5
        }
6

7
        // initialized as the first word of strs
8
        String result = strs[0];
9

10
        for (int i = 0; i < strs.length; i++) {
11
            // keeps removing the last character until matching the common prefix requirement
12
            while (strs[i].indexOf(result) != 0) {
13
                result = result.substring(0, result.length() - 1);
14
                if (result.length() == 0) {
15
                    break;
16
                }
17
            }
18
        }
19

20
        return result;
21
    }
22
}

15. 3Sum#

https://leetcode.com/problems/3sum/

先对数组进行排序，接着设立三个指针first, second, third。first负责从数组头遍历至数组尾，在每一次循环中固定first，移动头尾指针two和third，对nums[first]、nums[second]、nums[third]求和判断是否为0。

这题需要最大化利用排序带来的优势，缩短运行时间：

检查最小/最大值，跳过一些不必要的检查
跳过相邻的重复元素

1
class Solution {
2
    public List<List<Integer>> threeSum(int[] nums) {
3
        List<List<Integer>> result = new ArrayList<>();
4

5
        int len = nums.length;
6
        if (len < 3) {
7
            return result;
8
        }
9

10
        // sort so we can use pointers to quickly sum
11
        Arrays.sort(nums);
12

13
        // skip impossible cases
14
        if (3 * nums[0] > 0 || 3 * nums[len - 1] < 0) {
15
            return result;
16
        }
17

18
        for (int first = 0; first < len - 2; first++) {
19
            // skip if nums[first] is duplicate
20
            if (first > 0 && nums[first] == nums[first-1]) {
21
                continue;
22
            }
23

24
            // too big, no need to check subsequent combinations
25
            if (3 * nums[first] > 0) {
26
                break;
27
            }
28

29
            // too small, we need to start from a larger nums[first]
30
            if (nums[first] + 2 * nums[len - 1] < 0) {
31
                continue;
32
            }
33

34
            int second = first + 1, third = len - 1;
35
            while (second < third) {
36
                if (nums[first] + nums[second] + nums[third] == 0) {
37
                    result.add(Arrays.asList(nums[first], nums[second], nums[third]));
38

39
                    // skip nums[second] and nums[third] duplicates
40
                    while (second < third && nums[second] == nums[second + 1]) {
41
                        second++;
42
                    }
43
                    while (third > second && nums[third] == nums[third - 1]) {
44
                        third--;
45
                    }
46

47
                    // move pointers
48
                    second++;
49
                    third--;
50
                } else if (nums[first] + nums[second] + nums[third] < 0) {
51
                    second++;
52
                } else {
53
                    third--;
54
                }
55
            }
56
        }
57
        return result;
58
    }
59
}

16. 3Sum Closest#

https://leetcode.com/problems/3sum-closest/

与前一题思路类似，只是将”等于“改成了”最接近于“。额外加一个变量tempSum用于存储当前最接近的和即可。

1
class Solution {
2
    public int threeSumClosest(int[] nums, int target) {
3
        if (nums == null || nums.length == 0) {
4
            return 0;
5
        }
6
        int len = nums.length;
7
        int result = 0;
8

9
        // less than three numbers, directly return all num's sum
10
        if (len <= 3) {
11
            for (int num : nums) {
12
                result += num;
13
            }
14
            return result;
15
        }
16

17
        // initialized as the sum of first three elements
18
        result = nums[0] + nums[1] + nums[2];
19

20
        // sort so we can use pointers to quickly sum
21
        Arrays.sort(nums);
22

23
        for (int first = 0; first < len - 2; first++) {
24
            // skip if nums[first] is duplicate
25
            if (first > 0 && nums[first] == nums[first - 1]) {
26
                continue;
27
            }
28

29
            int second = first + 1, third = len - 1;
30
            while (second < third) {
31
                int tempSum = nums[first] + nums[second] + nums[third];
32

33
                // determine if tempSum is equal to target, or try to get tempSum closer to target
34
                if (tempSum == target) {
35
                    return tempSum;
36
                } else if (tempSum < target) {
37
                    second++;
38
                } else {
39
                    third--;
40
                }
41

42
                // update result
43
                if (Math.abs(target - result) > Math.abs(target - tempSum)) {
44
                    result = tempSum;
45
                }
46
            }
47
        }
48

49
        return result;
50
    }
51
}

17. Letter Combinations of a Phone Number#

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

设立一个字符串数组，数组下标0-9分别对应键盘0-9上的字符串。

遍历digits的每一位数字，得到这个数字可能对应的所有字母。使用回溯算法，尝试添加每一个字符，再通过深度优先思想添加下一个。以此类推，直到当前的string builder长度等于digits长度，表示发掘出了一种组合。

1
class Solution {
2
    private List<String> result = new ArrayList<>();
3
    private final String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
4

5
    public List<String> letterCombinations(String digits) {
6
        if (digits == null || digits.length() == 0) {
7
            return result;
8
        }
9

10
        backtrack(new StringBuilder(), digits, 0);
11

12
        return result;
13
    }
14

15
    private void backtrack(StringBuilder current, String digits, int index) {
16
        // find a combination, add to result
17
        if (current.length() == digits.length()) {
18
            result.add(current.toString());
19
            return;
20
        }
21

22
        // get all possible letters that are matching with current digit
23
        int digit = digits.charAt(index) - '0';
24
        String letters = mapping[digit];
25

26
        for (char letter: letters.toCharArray()) {
27
            current.append(letter);
28
            backtrack(current, digits, index + 1);
29
            current.deleteCharAt(current.length() - 1);
30
        }
31
    }
32
}

18. 4Sum#

https://leetcode.com/problems/4sum/

4Sum与3Sum的思路类似，仍然是使用多个指针的移动解决问题。使用first, second两个指针从头到尾遍历整个数组，而third, fourth两个指针则在second的后面，一前一后。

需要注意，在判断极值的时候可能会产生溢出，因此需要考虑int和long之间的转换。

1
class Solution {
2
    public List<List<Integer>> fourSum(int[] nums, int target) {
3
        List<List<Integer>> result = new ArrayList<>();
4
        int len = nums.length;
5
        if (len < 4) {
6
            return result;
7
        }
8

9
        // sort so we can use pointers to quickly sum
10
        Arrays.sort(nums);
11

12
        // too big or small
13
        Long potentialMin = (long)4 * nums[0];
14
        if (potentialMin > target) {
15
            return result;
16
        }
17

18
        Long potentialMax = (long)4 * nums[len - 1];
19
        if (potentialMax < target) {
20
            return result;
21
        }
22

23
        for (int first = 0; first < len - 3; first++) {
24
            // skip if nums[first] is duplicate
25
            if (first > 0 && nums[first] == nums[first-1]) {
26
                continue;
27
            }
28

29
            // too big, no need to check subsequent combinations
30
            Long potentialRestFourMin = (long)4 * nums[first];
31
            if (potentialRestFourMin > target) {
32
                break;
33
            }
34

35
            // too small, we need to start from a larger nums[first]
36
            Long potentialRestThreeMax = (long)3 * nums[len - 1];
37
            if (nums[first] + potentialRestThreeMax < target) {
38
                continue;
39
            }
40

41
            for (int second = first + 1; second < len - 2; second++) {
42
                // skip if nums[first] is duplicate
43
                if (second > first + 1 && nums[second] == nums[second - 1]) {
44
                    continue;
45
                }
46

47
                // too big, no need to check subsequent combinations
48
                Long potentialRestThreeMin = (long)3 * nums[second];
49
                if (potentialRestThreeMin + nums[first] > target) {
50
                    break;
51
                }
52

53
                // too small, we need to start from a larger nums[second]
54
                if (nums[first] + nums[second] + 2 * nums[len - 1] < target) {
55
                    continue;
56
                }
57

58
                int third = second + 1, fourth = len - 1;
59
                while (third < fourth) {
60
                    if (nums[first] + nums[second] + nums[third] + nums[fourth] == target) {
61
                        result.add(Arrays.asList(nums[first], nums[second], nums[third], nums[fourth]));
62

63
                        // skip duplicates
64
                        while (second < len - 2 && nums[second] == nums[second + 1]) {
65
                            second++;
66
                        }
67
                        while (third < fourth && nums[third] == nums[third + 1]) {
68
                            third++;
69
                        }
70
                        while (third < fourth && nums[fourth] == nums[fourth - 1]) {
71
                            fourth--;
72
                        }
73

74
                        // move pointers
75
                        third++;
76
                        fourth--;
77
                    } else if (nums[first] + nums[second] + nums[third] + nums[fourth] < target) {
78
                        third++;
79
                    } else {
80
                        fourth--;
81
                    }
82
                }
83
            }
84
        }
85
        return result;
86
    }
87
}

19. Remove Nth Node From End of List#

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

引入两个指针，一快一慢，二者之间的下标差为n（即slow指针指向第1个元素，则fast指针指向第n+1个元素）。删除节点则只需要调整节点的next指针即可。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode removeNthFromEnd(ListNode head, int n) {
13
        ListNode dummyHead = new ListNode(0);
14
        dummyHead.next = head;
15

16
        // slow and fast pointers
17
        ListNode slow = dummyHead, fast = dummyHead;
18

19
        // fast moves n steps ahead
20
        for (int i = 0; i < n; i++) {
21
            fast = fast.next;
22
        }
23

24
        // move slow and fast together
25
        while (fast.next != null) {
26
            slow = slow.next;
27
            fast = fast.next;
28
        }
29

30
        // delete nth node
31
        slow.next = slow.next.next;
32

33
        return dummyHead.next;
34
    }
35
}

20. Valid Parentheses#

https://leetcode.com/problems/valid-parentheses/

利用栈的特性，如果遇到左半侧的括号则推入栈中，右半侧的括号则检查是否与当前栈顶元素配对，如果不能配对就返回false，否则配对成功就把栈顶括号弹出。最后确认栈是否为空。

1
class Solution {
2
    public boolean isValid(String s) {
3
        if (s.length() == 0) {
4
            return true;
5
        }
6

7
        Stack<Character> st = new Stack<>();
8
        for (int i = 0; i < s.length(); i++) {
9
            char c = s.charAt(i);
10

11
            // push all left parentheses into stack
12
            if (c == '(' || c == '[' || c == '{') {
13
                st.push(c);
14
            } else if (c == ')' || c == ']' || c == '}') {
15
                // current right parenthesis must match with top parenthesis in the stack
16
                if (st.size() == 0) {
17
                    return false;
18
                }
19

20
                if (c == ')' && st.peek() != '(') {
21
                    return false;
22
                } else if (c == ']' && st.peek() != '[') {
23
                    return false;
24
                } else if (c == '}' && st.peek() != '{') {
25
                    return false;
26
                } else {
27
                    // successfully matched, pop the top parenthesis
28
                    st.pop();
29
                }
30
            }
31
        }
32
        return st.isEmpty();
33
    }
34
}

21. Merge Two Sorted Lists#

https://leetcode.com/problems/merge-two-sorted-lists/

第一种方法，比较l1和l2上的指针当前指向的元素，取较小元素之后的子链表和另一个链表继续进行递归合并。这样能保证每一次比较都优先提取出两个剩余链表的最小值，其余部分的结果也会接在这个最小值之后。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
13
        if (l1 == null) {
14
            return l2;
15
        }
16
        if (l2 == null) {
17
            return l1;
18
        }
19

20
        // merge after smaller node
21
        if (l1.val < l2.val) {
22
            l1.next = mergeTwoLists(l1.next, l2);
23
            return l1;
24
        } else {
25
            l2.next = mergeTwoLists(l1, l2.next);
26
            return l2;
27
        }
28
    }
29
}

第二种方法，也是比较l1和l2上的指针当前指向的元素，但不使用递归，而是直接根据大小关系决定排列顺序。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
13
        if (l1 == null) {
14
            return l2;
15
        }
16
        if (l2 == null) {
17
            return l1;
18
        }
19

20
        ListNode dummyHead = new ListNode(0);
21
        ListNode cur = dummyHead;
22

23
        while (l1 != null && l2 != null) {
24
            // decide which element to be added to the result list
25
            if (l1.val < l2.val) {
26
                cur.next = l1;
27
                l1 = l1.next;
28
            } else {
29
                cur.next = l2;
30
                l2 = l2.next;
31
            }
32
            cur = cur.next;
33
        }
34

35
        // one list reaches the end, add the rest list elements to result
36
        cur.next = (l2 == null) ? l1 : l2;
37

38
        return dummyHead.next;
39
    }
40
}

22. Generate Parentheses#

https://leetcode.com/problems/generate-parentheses/

使用递归策略，优先构造左括号，当左括号个数大于右括号时再构造右括号。

具体代码实现时，可以使用两个变量left，right跟踪当前左、右括号数量，在递归中将它们与n进行比较。

1
class Solution {
2
    List<String> result = new ArrayList<>();
3

4
    public List<String> generateParenthesis(int n) {
5
        generate("", 0, 0, n);
6
        return result;
7
    }
8

9
    // left: left parentheses' count
10
    // right: right parentheses' count
11
    private void generate(String s, int left, int right, int n) {
12
        if (right == n) {
13
            // finish construction
14
            result.add(s);
15
        } else {
16
            // always prefer to generate left parenthesis first
17
            if (left < n) {
18
                generate(s + "(", left + 1, right, n);
19
            }
20

21
            // left is greater than right, then generate a right parenthesis
22
            if (left > right) {
23
                generate(s + ")", left, right + 1, n);
24
            }
25
        }
26
    }
27
}

23. Merge k Sorted Lists#

https://leetcode.com/problems/merge-k-sorted-lists/

第一种解法是使用优先队列。优先队列本质上是一种堆，具体使用时可以自定义comparator指定最小堆或是最大堆。由于此题要求从小到大排序，因此需要定义最小堆。

将每一条链表的头元素加入优先队列中。优先级最高的元素就是这些元素里的最小值。将其排序后进行判断，如果该元素的next指针不指向空，则将剩下的链表头元素重新插入优先队列中。

以一个形象一些的方式描述该场景：一位教师正在向一群排队的学生解答问题，每个学生都有多个问题，并且问题的难度有难有易，教师优先回答简单的问题。为保证公平，当前问问题的学生问完一个问题后需要重新排队，排队顺序取决于他下一个问题的难度。

时间复杂度上，如果链表有N个节点，则堆的插入、删除操作时间复杂度均为O(logN)，总的时间复杂度为O(NlogN)。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode mergeKLists(ListNode[] lists) {
13
        if (lists == null || lists.length == 0) {
14
            return null;
15
        }
16

17
        // override priority queue's comparator in ascending order
18
        Queue<ListNode> pq = new PriorityQueue<>((ListNode l1, ListNode l2) -> {
19
            return l1.val - l2.val;
20
        });
21

22
        // add each list's head (smallest) node into the priority queue
23
        for (ListNode list : lists) {
24
            if (list != null) {
25
                pq.offer(list);
26
            }
27
        }
28

29
        ListNode dummyHead = new ListNode(0);
30
        ListNode cur = dummyHead;
31

32
        while (!pq.isEmpty()) {
33
            // pick out the smallest element from priority queue
34
            ListNode currentHead = pq.poll();
35
            cur.next = currentHead;
36
            cur = cur.next;
37

38
            // add its next element into the queue
39
            if (cur.next != null) {
40
                pq.offer(cur.next);
41
            }
42
        }
43

44
        return dummyHead.next;
45
    }
46
}

第二种解法是使用分治策略，将k条链表对半分为两组，问题转化为了广义版的merge two sorted lists问题。不断从上而下划分，再由小到大不断两两合并，得到完整的链表。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode mergeKLists(ListNode[] lists) {
13
        return merge(lists, 0, lists.length - 1);
14
    }
15

16
    private ListNode merge(ListNode[] lists, int l, int r) {
17
        // invalid interval
18
        if (l > r) {
19
            return null;
20
        }
21

22
        // interval only has one list group
23
        if (l == r) {
24
            return lists[l];
25
        }
26

27
        // divide k lists into two groups
28
        int mid = l + (r - l) / 2;
29
        ListNode left = merge(lists, l, mid);
30
        ListNode right = merge(lists, mid + 1, r);
31

32
        // merge two "big" lists together
33
        ListNode dummyHead = new ListNode(0);
34
        ListNode cur = dummyHead;
35

36
        while (left != null || right != null) {
37
            // right list is null, or the head of left list is smaller than the one of right list
38
            if (right == null || (left != null && left.val < right.val)) {
39
                cur.next = left;
40
                left = left.next;
41
            } else {
42
                cur.next = right;
43
                right = right.next;
44
            }
45
            cur = cur.next;
46
        }
47

48
        return dummyHead.next;
49
    }
50
}

24. Swap Nodes in Pairs#

https://leetcode.com/problems/swap-nodes-in-pairs/

使用递归，只提取前两个节点，将剩余节点视为一个整体。

新的头节点newHead是原来的第二个节点head.next，而原来的头节点head指向剩余节点整体（剩余部分的头节点为head.next.next）。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode swapPairs(ListNode head) {
13
        if (head == null || head.next == null) {
14
            return head;
15
        }
16

17
        // previous second node now bcomes the head node
18
        ListNode newHead = head.next;
19

20
        // regard all other nodes as an entity, and the head of this entity is head.next.next
21
        head.next = swapPairs(head.next.next);
22

23
        // previous head node now becomes the second node
24
        newHead.next = head;
25

26
        return newHead;
27
    }
28
}

25. Reverse Nodes in k-Group#

https://leetcode.com/problems/reverse-nodes-in-k-group/

假设遍历链表的指针为cur，将cur移动k个节点，获取到k个节点就能组成一个节点簇。我们优先递归完成链表后续部分的反转，再来倒转节点簇的k个节点。每个节点簇内，我们的核心思想是把原先的第一个节点指向链表后续部分，这样一来这个节点就可以被归到已经逆序的子链表中；而原先节点簇的第二个节点就成为了剩余未逆序部分的头节点。我们需要不断循环k次，按照上述流程调整顺序。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode reverseKGroup(ListNode head, int k) {
13
        if (head == null) {
14
            return null;
15
        }
16

17
        // move cur k nodes forward
18
        ListNode cur = head;
19
        int count = 0;
20
        while (cur != null && count != k) {
21
            count++;
22
            cur = cur.next;
23
        }
24

25
        // we get k nodes in a group now
26
        if (count == k) {
27
            // recursively complete all other nodes first to get the modified sub-list
28
            cur = reverseKGroup(cur, k);
29

30
            // reverse k nodes
31
            while (count-- > 0) {
32
                // get the second element among k nodes
33
                ListNode second = head.next;
34

35
                // current first element (head) will point to the modified sub-list
36
                head.next = cur;
37

38
                // previous head has become the head of the modified sub-list
39
                cur = head;
40

41
                // previous second element now becomes the new head of the un-reversed part
42
                head = second;
43
            }
44

45
            // after reverse, the head of the modified sub-list is actually the head of the whole list
46
            head = cur;
47
        }
48

49
        return head;
50
    }
51
}

26. Remove Duplicates from Sorted Array#

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

从头开始遍历，只要遇到不重复的数时，就覆盖数组的原始值。最后返回的result值实际上就是不同数字的个数。

1
class Solution {
2
    public int removeDuplicates(int[] nums) {
3
        int len = nums.length;
4
        if (len <= 1) {
5
            return len;
6
        }
7

8
        int result = 1;
9
        for (int i = 1; i < len; i++) {
10
            if (nums[i] != nums[i - 1]) {
11
                nums[result] = nums[i]; // in-place modification
12
                result++;
13
            }
14
        }
15

16
        return result;
17
    }
18
}

27. Remove Element#

https://leetcode.com/problems/remove-element/

与上一题一样的思路，遇到值为val的元素时跳过，其余仍从头到尾开始覆盖。

1
class Solution {
2
    public int removeElement(int[] nums, int val) {
3
        int len = nums.length;
4

5
        int result = 0;
6
        for (int i = 0; i < len; i++) {
7
            if (nums[i] != val) {
8
                nums[result] = nums[i]; // in-place modification
9
                result++;
10
            }
11
        }
12

13
        return result;
14
    }
15
}

28. Implement strStr()#

https://leetcode.com/problems/implement-strstr/

遍历haystack中的每一个字符，如果某个字符与needle的首字符相同，再检查haystack中该字符起的子串是否与needle的值相同。

1
class Solution {
2
    public int strStr(String haystack, String needle) {
3
        int hLen = haystack.length(), nLen = needle.length();
4

5
        // needle is an empty string
6
        if (nLen == 0) {
7
            return 0;
8
        }
9

10
        // haystack is empty and impossible to contain needle
11
        if (hLen == 0) {
12
            return -1;
13
        }
14

15
        for (int i = 0; i <= hLen - nLen; i++) {
16
            // current char is equal to needle's first char & substring is equal to needle
17
            if (haystack.charAt(i) == needle.charAt(0) && haystack.substring(i, i + nLen).equals(needle)) {
18
                return i;
19
            }
20
        }
21

22
        return -1;
23
    }
24
}

29. Divide Two Integers#

https://leetcode.com/problems/divide-two-integers/

此题要求实现除法，并且不能使用乘、除、取模三个符号。大致的思路流程是：

专门处理被除数为Integer.MIN_VALUE，divisor为-1时的情况，这种时候int形式的结果会发生溢出
将dividend和divisor都取绝对值
使用指数倍增思想，快速寻找到dividend中至少包含几个divisor。
决定最终结果的实际符号

为了避免溢出，在第一步处理完特例后，我们最好将dividend和divisor都转为long格式。

1
class Solution {
2
    public int divide(int dividend, int divisor) {
3
        // corner case
4
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
5
            return Integer.MAX_VALUE;
6
        }
7

8
        long dividendCopy = (long)dividend, divisorCopy = (long)divisor;
9

10
        // get rid of sign
11
        long a = Math.abs(dividendCopy), b = Math.abs(divisorCopy);
12
        long result = 0;
13

14
        while (a >= b) {
15
            int x = 0;
16

17
            // count how many divisor does the dividend "has"
18
            while (a >= (b << 1 << x)) {
19
                x++;
20
            }
21

22
            result += 1 << x;
23
            a -= b << x;
24
        }
25

26
        // determine if dividend and divisor have same sign
27
        return (dividend > 0) == (divisor > 0) ? (int)result : (int)-result;
28
    }
29
}

30. Substring with Concatenation of All Words#

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

只要words中的所有单词拼接得到s中的子字符串即可满足题意，单词的顺序并不重要。因此我们只需要关注words中每一个单词出现的次数。

此题可以使用两个HashMap解决，一个HashMap用于记录words数组中的每一个单词出现的次数；另一个HashMap用于记录当前遍历s时的单词已经出现了几次。如果当前遍历的单词是words中没有的，或者出现次数已经超过了“应该”出现的次数，则说明不满足题意。

1
class Solution {
2
    public List<Integer> findSubstring(String s, String[] words) {
3
        List<Integer> result = new ArrayList<>();
4
        if (words.length == 0) {
5
            return result;
6
        }
7

8
        // how many times each word is supposed to occur
9
        Map<String, Integer> expected = new HashMap<>();
10
        for (String word : words) {
11
            expected.put(word, expected.getOrDefault(word, 0) + 1);
12
        }
13

14
        // each word's length and all words' count
15
        int len = words[0].length(), count = words.length;
16
        if (s.length() < count * len) {
17
            return result;
18
        }
19

20
        for (int i = 0; i < len; i++) {
21
            for (int j = i; j <= s.length() - count * len; j += len) {
22
                // how many times every word actually occurs in each substring
23
                Map<String, Integer> actual = new HashMap<>();
24

25
                // iterate from the last
26
                for (int k = count - 1; k >= 0; k--) {
27
                    // extract current word
28
                    String currentWord = s.substring(j + k * len, j + (k + 1) * len);
29

30
                    // current word is not supposed to occur
31
                    if (!expected.containsKey(currentWord)) {
32
                        break;
33
                    } else {
34
                        int occurences = actual.getOrDefault(currentWord, 0) + 1;
35

36
                        // can not exceed expected occurences
37
                        if (occurences > expected.get(currentWord)) {
38
                            // start right after invalid occurence, as previous choices will include invalid.
39
                            j += k * len;
40
                            break;
41
                        }
42

43
                        actual.put(currentWord, occurences);
44

45
                        // all words appear
46
                        if (k == 0) {
47
                            result.add(j);
48
                        }
49
                    }
50
                }
51
            }
52
        }
53
        return result;
54
    }
55
}

31. Next Permutation#

https://leetcode.com/problems/next-permutation/

一个数组向下一置换演变的趋势总体是从升序演变为降序。

找到下一置换，实际上就是从右到左遍历，先找到破坏升序的第一个数nums[i]，再从这个数的右侧（也是从右向左遍历）找到第一个比nums[i]大的数nums[j]，这两个数进行交换。最后，对下标i之后的数需要全部进行反转，因为在经过交换之后，从下标i开始一直到结尾都是降序，我们需要将i + 1到结尾重新调整为升序，确保不遗漏置换的可能。

1
class Solution {
2
    public void nextPermutation(int[] nums) {
3
        if (nums == null || nums.length <= 1) {
4
            return;
5
        }
6

7
        // search from right to left and find the first element to break the ascending order
8
        int i = nums.length - 2;
9
        while (i >= 0 && nums[i] >= nums[i+1]) {
10
            i--;
11
        }
12

13
        // if there is an element that break the ascending order
14
        if (i >= 0) {
15
            int j = nums.length - 1;
16

17
            // find the rightmost element which is larger than nums[i]
18
            while (nums[i] >= nums[j]) {
19
                j--;
20
            }
21

22
            // swap nums[i] and nums[j]
23
            swap(nums, i, j);
24
        }
25
        // reverse all elements after index i
26
        reverseArray(nums, i + 1, nums.length - 1);
27
    }
28

29
    // swap two nums
30
    private void swap(int[] nums, int i, int j) {
31
        int temp = nums[i];
32
        nums[i] = nums[j];
33
        nums[j] = temp;
34
    }
35

36
    // reverse part of the array
37
    private void reverseArray(int[] nums, int i, int j) {
38
        while (i < j) {
39
            swap(nums, i++, j--);
40
        }
41
    }
42
}

32. Longest Valid Parentheses#

https://leetcode.com/problems/longest-valid-parentheses/

使用栈解决。遍历字符串，如果遇到’(‘，则将当前下标推入栈中；遇到’)‘，则将栈顶下标弹出，并讨论。需要注意：

栈里存储的下标，实质上指的是“截止到这个下标时，字符串不能组成valid parentheses”。我们最后更新结果时，也是用当前下标与栈顶下标的差值来更新长度，因为这一段差值之间的字符串一定是有效的
因为上述设定，栈的初始化需要push一个-1；如果空栈的时候，说明截止至目前的字符串一定是无效的，我们要想找有效字符串只能在此之后寻找

1
class Solution {
2
    public int longestValidParentheses(String s) {
3
        int result = 0;
4

5
        ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
6

7
        // the index preceding to potential start of valid parentheses
8
        stack.push(-1);
9

10
        for (int i = 0; i < s.length(); i++) {
11
            char curr = s.charAt(i);
12
            if (curr == '(') {
13
                stack.push(i);
14
            } else {
15
                // no matter we get valid parentheses or not, we need to pop here
16
                // if valid, we need to get last index to calculate diff
17
                // if unvalid, we update with current index
18
                stack.pop();
19

20
                if (stack.isEmpty()) {
21
                    // the stack is empty only if we have an extra ')'. Any further extensions of valid parentheses is impossible
22
                    // push current index, since it is preceding to potential start of valid parentheses
23
                    stack.push(i);
24
                } else {
25
                    // this may be our longest valid parentheses
26
                    result = Math.max(result, i - stack.peek());
27
                }
28
            }
29
        }
30

31
        return result;
32
    }
33
}

33. Search in Rotated Sorted Array#

https://leetcode.com/problems/search-in-rotated-sorted-array/

这一题需要将数组对半划分来看，其中一半一定是有序的，而另一半则在中间某处破坏了升序。因此在使用模型1时，我们无法简单通过比较nums[mid]和target确定下一轮搜索区间，而是应该比较nums[left]、nums[mid]和nums[right]三者的值，先判断哪一半数组是有序的；之后将target放进有序的这一侧进行比较，如果target的值介于其中则把区间定为有序的这一侧，反之定为另一侧。

1
class Solution {
2
    public int search(int[] nums, int target) {
3
        if (nums == null || nums.length == 0) {
4
            return -1;
5
        }
6

7
        int left = 0, right = nums.length - 1;
8
        while (left <= right) {
9
            int mid = left + (right - left) / 2;
10

11
            // nums[mid] matches with target, return
12
            if (nums[mid] == target) {
13
                return mid;
14
            }
15

16
            // left half is ordered
17
            if (nums[left] <= nums[mid]) {
18
                // target is in left half
19
                if (target >= nums[left] && target <= nums[mid]) {
20
                    right = mid - 1;
21
                } else {
22
                    left = mid + 1;
23
                }
24
            }
25

26
            // right half is ordered
27
            if (nums[mid] <= nums[right]) {
28
                // target is in right half
29
                if (target >= nums[mid] && target <= nums[right]) {
30
                    left = mid + 1;
31
                } else {
32
                    right = mid - 1;
33
                }
34
            }
35
        }
36

37
        return -1;
38
    }
39
}

34. Find First and Last Position of Element in Sorted Array#

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

分别进行左边界搜索和右边界搜索即可。

1
class Solution {
2
    public int[] searchRange(int[] nums, int target) {
3
        int[] result = new int[] {-1, -1};
4
        if (nums == null || nums.length == 0) {
5
            return result;
6
        }
7

8
        // left
9
        int left = 0, right = nums.length;
10
        while (left < right) {
11
            int mid = left + (right - left) / 2;
12
            if (nums[mid] < target) {
13
                left = mid + 1;
14
            } else if (nums[mid] >= target) {
15
                right = mid;
16
            }
17
        }
18

19
        if (left != nums.length && nums[left] == target) {
20
            result[0] = left;
21
        }
22

23
        // right
24
        left = 0;
25
        right = nums.length;
26
        while (left < right) {
27
            int mid = left + (right - left) / 2;
28
            if (nums[mid] <= target) {
29
                left = mid + 1;
30
            } else if (nums[mid] > target) {
31
                right = mid;
32
            }
33
        }
34

35
        if (left != 0 && nums[left - 1] == target) {
36
            result[1] = left - 1;
37
        }
38

39
        return result;
40
    }
41
}

35. Search Insert Position#

https://leetcode.com/problems/search-insert-position/

可以假想把target插入到nums数组中，再转化为数组长度+1后的标准二分查找。

1
class Solution {
2
    public int searchInsert(int[] nums, int target) {
3
        if (nums == null || nums.length == 0) {
4
            return 0;
5
        }
6

7
        // num's length +1, therefore right should be 'nums.length' instead of 'nums.length - 1'
8
        int left = 0, right = nums.length;
9

10
        // standard binary search
11
        while (left < right) {
12
            int mid = left + (right - left) / 2;
13
            if (nums[mid] < target) {
14
                left = mid + 1;
15
            } else {
16
                right = mid;
17
            }
18
        }
19

20
        // both left and right are valid
21
        return left;
22
    }
23
}

36. Valid Sudoku#

https://leetcode.com/problems/valid-sudoku/

每一个数字只能在所处的行、列、3*3方格内出现一次。因此，构造三个二维数组检查当前数字num分别在当前行、列、方格内出现的次数，超过1次就是不合法的。

1
class Solution {
2
    public boolean isValidSudoku(char[][] board) {
3
        int[][] row = new int[9][9]; // row[i][num] indicates the count of 'num' in the i-th row
4
        int[][] col = new int[9][9]; // col[j][num] indicates the count of 'num' in the j-th column
5
        int[][] block = new int[9][9]; // block[k][num] indicates the count of 'num' in the k-th 3*3 block
6

7
        for (int i = 0; i < 9; i++) {
8
            for (int j = 0; j < 9; j++) {
9
                // only validate filled cells
10
                if (board[i][j] != '.') {
11
                    int num = board[i][j] - '1';
12
                    int blockIndex = (i/3) * 3 + j/3;
13

14
                    // each num should not duplicate in each row, col, block
15
                    if (row[i][num] > 0 || col[j][num] > 0 || block[blockIndex][num] > 0) {
16
                        return false;
17
                    }
18

19
                    row[i][num] += 1;
20
                    col[j][num] += 1;
21
                    block[blockIndex][num] += 1;
22
                }
23
            }
24
        }
25
        return true;
26
    }
27
}

37. Sudoku Solver#

https://leetcode.com/problems/sudoku-solver/

遇到一个空方格，从0-9循环填入每一个数字，填完后确认没有违规，再以深度优先，尝试后续所有方格都满足要求，才能保证当前方格也满足要求。

遇到列尾时跳下一行，遇到行尾则说明深度优先搜索结束，数独解决完毕；而如果遇到不符合的情况，则要回溯复原当前填入的数字，再继续循环填入下一个数字。

1
class Solution {
2
    public void solveSudoku(char[][] board) {
3
        solve(board, 0, 0);
4
    }
5

6
    // solve based on index
7
    private Boolean solve(char[][] board, int i, int j) {
8
        // finish all 9 row
9
        if (i == 9) {
10
            return true;
11
        }
12

13
        // finish current row, jump to next row
14
        if (j == 9) {
15
            return solve(board, i+1, 0);
16
        }
17

18
        // non-digit, switch to next column
19
        if (board[i][j] != '.') {
20
            return solve(board, i, j+1);
21
        }
22

23
        // backtrack
24
        for (char c = '1'; c <= '9'; c++) {
25
            if (check(board, i, j, c)) {
26
                board[i][j] = c;
27

28
                // all subsequent cells are valid
29
                if (solve(board, i, j+1)) {
30
                    return true;
31
                }
32

33
                board[i][j] = '.';
34
            }
35
        }
36

37
        return false; // no solution
38
    }
39

40
    // check if current character is valid
41
    private Boolean check(char[][] board, int i, int j, char val) {
42
        for (int c = 0; c < 9; c++) {
43

44
            // duplicate in current row, column or 3 * 3 block
45
            if (board[i][c] == val ||
46
                board[c][j] == val ||
47
                board[i - i%3 + c/3][j - j%3 + c%3] == val) {
48
                return false;
49
            }
50
        }
51
        return true;
52
    }
53
}

38. Count and Say#

https://leetcode.com/problems/count-and-say/

直接的想法是使用递归。递归的起点显然是n为1的情况。此后对于任意输入的n，先计算出n-1的结果字符串pre，再遍历pre得到n的结果。遍历pre时，统计当前数字连续出现了几次，把数字和次数直接加到StringBuilder里。

注意使用StringBuilder的目的主要是优化性能，因为String每次追加字符时都会产生新的对象；而StringBuilder与StringBuffer都是直接在同一对象上追加字符，效率很高。另外StringBuffer()适合多线程，而StringBuilder()适合单线程。

1
class Solution {
2
    public String countAndSay(int n) {
3
        if (n == 1) {
4
            return "1";
5
        }
6

7
        // all upper levels' result
8
        StringBuilder pre = new StringBuilder(countAndSay(n - 1));
9

10
        // construct this level
11
        StringBuilder result = new StringBuilder();
12

13
        int i = 0;
14
        while (i < pre.length()) {
15
            int count = 0; // current number's count
16
            int j = i; // start index of current number
17

18
            char say = pre.charAt(j);
19
            while (i < pre.length() && pre.charAt(i) == say) {
20
                count++;
21
                i++;
22
            }
23

24
            result.append(count);
25
            result.append(say);
26
        }
27
        return result.toString();
28
    }
29
}

39. Combination Sum#

https://leetcode.com/problems/combination-sum/

将原始数组排序，并遍历数组，创建一个新的临时数组用于存放当前的组合。每当向临时数组中添加一个数后，更新target，递归进入下一层搜索；由于每一个数可以使用无限次，下一次递归的起点下标index不变。最后当target等于0，说明当前组合满足；否则，则将临时数组中最后一个元素移除，寻找下一个数。

1
class Solution {
2
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
3
        List<List<Integer>> result = new ArrayList<>();
4
        Arrays.sort(candidates);
5
        backtrack(result, new ArrayList<>(), candidates, target, 0);
6
        return result;
7
    }
8

9
    private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] candidates, int target, int index) {
10
        if (target == 0) {
11
            result.add(new ArrayList<>(temp));
12
        } else {
13
            for (int i = index; i < candidates.length && candidates[i] <= target; i++) {
14
                temp.add(candidates[i]);
15
                backtrack(result, temp, candidates, target - candidates[i], i); // allow duplicate, thus starts from i
16
                temp.remove(temp.size() - 1);
17
            }
18
        }
19
    }
20
}

40. Combination Sum II#

https://leetcode.com/problems/combination-sum-ii/

与上一题几乎一样的题设，唯一不同是输入数组中可能有重复的数字，且数组中每个数只能用一次。只需要稍微改变上一题的代码，调整下一层递归的起始下标；此外，完成一次回溯后，需要及时跳过重复的数字。

1
class Solution {
2
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
3
        List<List<Integer>> result = new ArrayList<>();
4
        Arrays.sort(candidates);
5
        backtrack(result, new ArrayList<>(), candidates, target, 0);
6
        return result;
7
    }
8

9
    private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] candidates, int target, int index) {
10
        if (target == 0) {
11
            result.add(new ArrayList<>(temp));
12
        } else {
13
            for (int i = index; i < candidates.length && candidates[i] <= target; i++) {
14
                temp.add(candidates[i]);
15
                backtrack(result, temp, candidates, target - candidates[i], i + 1); // not allow duplicate, thus starts from i + 1
16
                temp.remove(temp.size() - 1);
17

18
                // skip duplicates
19
                while (i + 1 < candidates.length && candidates[i] == candidates[i + 1]) {
20
                    i++;
21
                }
22
            }
23
        }
24
    }
25
}

41. First Missing Positive#

https://leetcode.com/problems/first-missing-positive/

要寻找最小的缺失正整数，可以对数组进行处理：假如遍历发现了1，则将1放在数组第一个位置；发现2，则将2放在数组第二个位置…以此类推。当然，前提是只有遍历的元素值位于0和数组长度之间，才做此处理。

为了达到这一目的，只需要将nums[i]与nums[nums[i] - 1]进行交换即可。最后，重新遍历顺序处理后的数组，第一个元素值和下标不匹配的元素即为答案。

1
class Solution {
2
    public int firstMissingPositive(int[] nums) {
3
        int len = nums.length;
4
        for (int i = 0; i < len; i++) {
5
            // if nums[i] is in the range of (0, len] and not in its place,
6
            // put nums[i] on the (nums[i] - 1)th index of the array
7
            while (nums[i] > 0 && nums[i] <= len && nums[i] != nums[nums[i] - 1]) {
8
                // swap nums[i] and nums[nums[i] - 1]
9
                int temp = nums[nums[i] - 1];
10
                nums[nums[i] - 1] = nums[i];
11
                nums[i] = temp;
12
            }
13
        }
14

15
        // the first number unmatched is the answer
16
        for (int i = 0; i < len; i++) {
17
            if (nums[i] != i + 1) {
18
                return i + 1;
19
            }
20
        }
21

22
        // all matched, the smallest positive integer is last integer + 1
23
        return len + 1;
24
    }
25
}

42. Trapping Rain Water#

https://leetcode.com/problems/trapping-rain-water/

使用左右两个指针跟踪当前的池壁高度。根据木桶效应，高度下界lowerBound取决于池壁高度较低的一边，而当前已有的水槽高度currentLevel则根据较低的池壁高度不断更新。指针移动过程中，新增的水量为currentLevel与lowerBound的差值。

1
class Solution {
2
    public int trap(int[] height) {
3
        if (height == null || height.length <= 1) {
4
            return 0;
5
        }
6

7
        int left = 0, right = height.length - 1;
8
        int currentLevel = 0, result = 0;
9

10
        while (left < right) {
11
            int lowerBound = 0;
12

13
            // smaller of height[left] and height[right], then move left or right accordingly
14
            if (height[left] <= height[right]) {
15
                lowerBound = height[left];
16
                left++;
17
            } else {
18
                lowerBound = height[right];
19
                right--;
20
            }
21

22
            // update current bar's level
23
            currentLevel = Math.max(currentLevel, lowerBound);
24

25
            // new water fills in
26
            result += currentLevel - lowerBound;
27
        }
28

29
        return result;
30
    }
31
}

43. Multiply Strings#

https://leetcode.com/problems/multiply-strings/

此题限定了输入字符串只包含数字，并且不能直接转成整数再调用乘法计算，实际上便是指定了思路：模拟实现大数的乘法运算，类似于小学进行竖式乘法的过程。

对于一个m位整数与一个n位整数，其结果的长度一定为m+n-1或m+n，因此可以提前创建一个长为m+n的数组用于存放最终结果的每一位数。双重循环遍历两个整数，可以发现num1[i] * num2[j]的结果对应的是result[i+j+1]。明确了位数之后，剩余的工作较为简单，只需逐位求值，保留尾数，提取进位向前累加即可。输出结果时，需要去掉起始的0。

1
class Solution {
2
    public String multiply(String num1, String num2) {
3
        int m = num1.length(), n = num2.length();
4

5
        if (m == 0 || n == 0) {
6
            return "0";
7
        }
8
        if (num1.equals("0") || num2.equals("0")) {
9
            return "0";
10
        }
11

12
        // num1[i] * num2[j] reflects on result[i+j+1]
13
        int[] result = new int[m+n];
14
        for (int i = m-1; i >= 0; i--) {
15
            for (int j = n-1; j >= 0; j--) {
16
                result[i+j+1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
17
            }
18
        }
19

20
        // calculate each digit and each carry
21
        int carry = 0;
22
        for (int k = result.length - 1; k >= 0; k--) {
23
            int digit = (result[k] + carry) % 10;
24
            carry = (result[k] + carry) / 10;
25
            result[k] = digit;
26
        }
27

28
        StringBuilder sb = new StringBuilder();
29

30
        // trim all leading 0
31
        for (int each : result) {
32
            if (!(each == 0 && sb.length() == 0)) {
33
                sb.append(each);
34
            }
35
        }
36

37
        return sb.toString();
38
    }
39
}

44. Wildcard Matching#

https://leetcode.com/problems/wildcard-matching/

解法一，参考Regular Expression Matching中的解法，使用二维动态规划：

1
class Solution {
2
    public boolean isMatch(String s, String p) {
3
        boolean[][] dp = new boolean[s.length() + 1][p.length()+1];
4
        dp[0][0] = true;
5

6
        // empty pattern cannot match with any string
7
        for (int i = 1; i <= s.length(); i++) {
8
            dp[i][0] = false;
9
        }
10

11
        // multiple '*' pattern can match with empty string
12
        for (int j = 1; j <= p.length(); j++) {
13
            if (p.charAt(j-1) != '*') {
14
                break;
15
            } else {
16
                dp[0][j] = true;
17
            }
18
        }
19

20
        for (int i = 0; i < s.length(); i++) {
21
            for (int j = 0; j < p.length(); j++) {
22
                if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
23
                    dp[i+1][j+1] = dp[i][j];
24
                } else if (p.charAt(j) == '*') {
25
                    dp[i+1][j+1] = dp[i+1][j] || dp[i][j+1];
26
                } else {
27
                    dp[i][j] = false;
28
                }
29
            }
30
        }
31

32
        return dp[s.length()][p.length()];
33
    }
34
}

解法二，使用指针：

使用两个指针sIdx和pIdx分别跟踪s和p，分类讨论所有情况：

严格的单字对应，或p中出现?，两个指针分别前移
p遇到*，暂不清楚匹配情况，记录s当前的匹配起点和p最近一个*的位置，前移pIdx
前一个pIdx是*，但现在不是，可能对应着匹配多个字符的情况，将pIdx置于最近一个*的右侧，并前移sIdx

其他情况下，直接判定为匹配失败。

1
class Solution {
2
    public boolean isMatch(String s, String p) {
3
        int sIdx = 0, pIdx = 0, match = 0, starIdx = -1;
4

5
        while (sIdx < s.length()) {
6
            if (pIdx < p.length() && (p.charAt(pIdx) == '?' || s.charAt(sIdx) == p.charAt(pIdx))) {
7
                // regular match or match ?, moving both pointers forward
8
                sIdx++;
9
                pIdx++;
10
            } else if (pIdx < p.length() && p.charAt(pIdx) == '*') {
11
                // * found, only moving pattern pointer forward
12
                starIdx = pIdx; // update the latest *'s index
13
                match = sIdx;
14
                pIdx++;
15
            } else if (starIdx != -1) {
16
                // last pattern pointer was * but current is not, moving string pointer forward to match
17
                pIdx = starIdx + 1;
18
                sIdx = ++match;
19
            } else return false;
20
        }
21

22
        // check for remaining characters in pattern
23
        while (pIdx < p.length() && p.charAt(pIdx) == '*') {
24
            pIdx++;
25
        }
26

27
        return pIdx == p.length();
28
    }
29
}

45. Jump Game II#

https://leetcode.com/problems/jump-game-ii/

此题需要使用贪心算法。第i次跳跃中，必然有nums[i]个可选落点，检查每一个可选落点最远可以到达何处，选取最远的一个作为下一次跳跃的最远边界。以此类推，每一步都选择下一步可能最远的落点，直到最终可以到达终点。

1
class Solution {
2
    public int jump(int[] nums) {
3
        if (nums == null || nums.length == 0) {
4
            return 0;
5
        }
6

7
        int steps = 0; // steps taken
8
        int start = 0, end = 0; // in current step, I can reach the interval [start, end]
9
        int maxEnd = 0; // the farthest fall of the jump
10

11
        while (end < nums.length - 1) {
12
            steps++;
13

14
            // find out the maxEnd
15
            for (int i = start; i <= end; i++) {
16
                maxEnd = Math.max(maxEnd, nums[i] + i);
17
            }
18

19
            // generate next [start, end] range
20
            start = end + 1; // next range's start must be larger than current range's end
21
            end = maxEnd;
22
        }
23

24
        return steps;
25
    }
26
}

46. Permutations#

https://leetcode.com/problems/permutations/

使用通用的回溯算法解题模版。使用一个boolean数组跟踪每个下标的数字是否使用过，跳过已经使用过的数；在回溯的时候重新设为未使用。

1
class Solution {
2
    public List<List<Integer>> permute(int[] nums) {
3
        List<List<Integer>> result = new ArrayList<>();
4
        Arrays.sort(nums);
5
        backtrack(result, nums, new ArrayList<>(), new boolean[nums.length]);
6
        return result;
7
    }
8

9
    private void backtrack(List<List<Integer>> result, int[] nums, List<Integer> temp, boolean[] used) {
10
        // match with num's length, add this permutation to result
11
        if (temp.size() == nums.length) {
12
            result.add(new ArrayList<>(temp));
13
            return;
14
        }
15

16
        for (int i = 0; i < nums.length; i++) {
17
            // current number has already been used, skip
18
            if (used[i] == true) {
19
                continue;
20
            }
21

22
            // set current number as used and add it to temp permutation
23
            used[i] = true;
24
            temp.add(nums[i]);
25

26
            backtrack(result, nums, temp, used);
27

28
            // after using, reset current number as unused and remove it from temp permutation
29
            used[i] = false;
30
            temp.remove(temp.size() - 1);
31
        }
32
    }
33
}

47. Permutations II#

https://leetcode.com/problems/permutations-ii/

此题的输入数组可能含有重复的数字，只需要在上一题的基础上，跳过重复的数字即可。

需要注意，判断重复时，used[i - 1]和!used[i - 1]都能让代码成功运行，然而LeetCode运行时间显示，!used[i - 1]快的多，可能是因为LeetCode生成的随机测试数据中，包含重复的情况较多，因此我们发现当前一个相同的数字被使用时，我们也优先加入当前这个相同的数字，这样能更快试出所有permutation。

1
class Solution {
2
    public List<List<Integer>> permuteUnique(int[] nums) {
3
        List<List<Integer>> result = new ArrayList<List<Integer>>();
4
        Arrays.sort(nums);
5
        backtrack(result, nums, new ArrayList<>(), new boolean[nums.length]);
6
        return result;
7
    }
8

9
    private void backtrack(List<List<Integer>> result, int[] nums, List<Integer> temp, boolean[] used) {
10
        // match with num's length, add this permutation to result
11
        if (temp.size() == nums.length) {
12
            result.add( new ArrayList<>(temp) );
13
            return;
14
        }
15

16
        for (int i = 0; i < nums.length; i++) {
17
            // current number is used / if previous identical number is used, use current number
18
            if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) {
19
                continue;
20
            }
21

22
            // mark current number as used and add it to temp permutation
23
            used[i] = true;
24
            temp.add(nums[i]);
25

26
            backtrack(result, nums, temp, used);
27

28
            // after using, unmark current number as unused and remove it from temp permutation
29
            used[i] = false;
30
            temp.remove(temp.size() - 1);
31
        }
32
    }
33
}

48. Rotate Image#

https://leetcode.com/problems/rotate-image/

观察发现，矩阵内的元素旋转实际上是在建构一个旋转矩形，矩形顶点的轮换导致了整个矩阵的变化。

例如对于例子中的两个矩阵，第一个矩阵中2, 4, 6, 8构成了一个旋转矩形，第二个矩阵中1, 10, 12, 13构成了一个旋转矩形。因此，对于任意一个matrix[i][j]，总能找到另外三个矩阵坐标顶点与之构成一个旋转矩形，只需推出其数学表达式即可。

1
class Solution {
2
    public void rotate(int[][] matrix) {
3
        if (matrix == null) {
4
            return;
5
        }
6
        int len = matrix.length;
7

8
        // locate four corner points
9
        for (int i = 0; i < (len + 1) / 2; i++) {
10
            for (int j = 0; j < matrix[0].length / 2; j++) {
11
                int temp = matrix[i][j]; // first
12
                matrix[i][j] = matrix[len - 1 - j][i]; // second
13
                matrix[len - 1 - j][i] = matrix[len - 1 - i][len - 1 - j]; // third
14
                matrix[len - 1 - i][len - 1 - j] = matrix[j][len - 1 - i]; // fourth
15
                matrix[j][len - 1 - i] = temp;
16
            }
17
        }
18
    }
19
}

49. Group Anagrams#

https://leetcode.com/problems/group-anagrams/

统计每个单词中各个字母出现的次数，存到一个长度为26的数组中。利用这个数组生成对应的hash码(Arrays.hashCode())，具有相同hash码的字符串就可以被归类在一起。

如果字符串很短的情况下，也可以每一个字母映射一个质数，质数相乘作为hashcode，提升运行效率。

1
class Solution {
2
    public List<List<String>> groupAnagrams(String[] strs) {
3
        List<List<String>> result = new ArrayList<>();
4

5
        // <hash number, list index in result>
6
        Map<Integer, Integer> map = new HashMap<>();
7

8
        for (String s: strs) {
9
            int key = getKey(s);
10
            int resultIndex = map.getOrDefault(key, -1);
11

12
            List<String> list = null;
13
            if (resultIndex == -1) {
14
                list = new ArrayList<>();
15
                result.add(list);
16
                map.put(key, result.size() - 1);
17
            } else {
18
                list = result.get(resultIndex);
19
            }
20

21
            list.add(s);
22
        }
23
        return result;
24
    }
25

26
    // use count to generate hash number
27
    public int getKey(String s) {
28
        int[] map = new int[26];
29
        for (char c: s.toCharArray()) {
30
            map[c - 'a']++;
31
        }
32
        return Arrays.hashCode(map);
33
    }
34
}

如果字符串很短的情况下，也可以每一个字母映射一个质数，质数相乘作为hashcode，提升运行效率。

1
class Solution {
2
    public List<List<String>> groupAnagrams(String[] strs) {
3
        List<List<String>> result = new ArrayList<>();
4
        if (strs == null || strs.length == 0) {
5
            return result;
6
        }
7

8
        // top 26 positive primes
9
        int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
10

11
        // <product, position in result>
12
        Map<Long, Integer> map = new HashMap<>();
13

14
        for (String str : strs) {
15
            // calculate current string's product
16
            long product = 1;
17
            for (char ch : str.toCharArray()) {
18
                product *= prime[ch - 'a'];
19
            }
20

21
            List<String> temp;
22

23
            // current product is already in the map, add this string to specific list of result
24
            if (map.containsKey(product)) {
25
                result.get(map.get(product)).add(str);
26
            } else {
27
                // create a new list, add current string, then add the list to result
28
                temp = new ArrayList<>();
29
                temp.add(str);
30
                result.add(temp);
31

32
                // record this new list's index
33
                map.put(product, result.size() - 1);
34
            }
35
        }
36

37
        return result;
38
    }
39
}

50. Pow(x, n)#

https://leetcode.com/problems/powx-n/

实现幂函数的构造需要运用递归。然而在开始递归前，需要先排除一些输入的特殊情况。n和x各有若干特殊情况：

输入的x为1，或是n为0，或是x为-1且n为整数下界，返回1
输入的x为0，或是x不为-1且n为整数下界，返回0
输入的n为负数，利用xⁿ = (1/x)^-n这一特点，将n转化成正数。

完成上述处理后，分n的奇偶性进行递归调用。对于奇数，由于整数除法的舍入，需要额外乘一个x。

1
public double myPow(double x, int n) {
2
    if (x == 1 || n == 0 || (n == Integer.MIN_VALUE && x == -1)) {
3
        return 1;
4
    }
5
    if (x == 0 || (n == Integer.MIN_VALUE && x != -1)) {
6
        return 0;
7
    }
8
    if (n < 0) {
9
        n = -n;
10
        x = 1/x;
11
    }
12
    // odd or even
13
    return (n % 2 == 0) ? myPow(x * x, n / 2) : x * myPow(x * x, n / 2);
14
}

51. N-Queens#

https://leetcode.com/problems/n-queens/

运用深度优先搜素，使用一个数组queens记录每一行的皇后位于第几列。每一行放置皇后并递归进入下一行。如果某一列已经摆放了皇后，或对角线上存在皇后，则当前单元格不能放置皇后。

当深度优先搜索结束后，根据queens记录的信息，生成一张棋盘图。

1
class Solution {
2
    public List<List<String>> solveNQueens(int n) {
3
        List<List<String>> result = new ArrayList<>();
4

5
        // queen's position in each row
6
        int[] queens = new int[n];
7
        Arrays.fill(queens, -1);
8

9
        dfs(result, queens, 0);
10
        return result;
11
    }
12

13
    private void dfs(List<List<String>> result, int[] queens, int row) {
14
        int len = queens.length;
15

16
        // finish one solution
17
        if (len == row) {
18
            List<String> temp = new ArrayList<>();
19

20
            // generate an n*n chessboard based on queens' positions
21
            for (int i : queens) {
22
                char[] boardRow = new char[len];
23
                Arrays.fill(boardRow, '.');
24
                boardRow[i] = 'Q';
25

26
                // char[] -> str
27
                temp.add(String.valueOf(boardRow));
28
            }
29

30
            // add this chessboard to result
31
            result.add(temp);
32
            return;
33
        }
34

35
        // look for suitable column to place queen in current row
36
        for (int col = 0; col < len; col++) {
37
            if (isValid(queens, row, col)) {
38
                queens[row] = col; // put queen in current column
39
                dfs(result, queens, row + 1); // move to next row
40
            }
41
        }
42
    }
43

44
    private boolean isValid(int[] queens, int row, int col) {
45
        for (int i = 0; i < row; i++) {
46
            // there should be no queen in this row or diagnosal line
47
            if (queens[i] == col || Math.abs(col - queens[i]) == row - i) {
48
                return false;
49
            }
50
        }
51

52
        return true;
53
    }
54
}

52. N-Queens II#

https://leetcode.com/problems/n-queens-ii/

与上一题完全一致，只是上一题返回整个结果列表，这一题返回结果的个数而已。

1
class Solution {
2
    public int totalNQueens(int n) {
3
        List<List<String>> result = new ArrayList<>();
4

5
        // queen's position in each row
6
        int[] queens = new int[n];
7
        Arrays.fill(queens, -1);
8

9
        dfs(result, queens, 0);
10
        return result.size();
11
    }
12

13
    private void dfs(List<List<String>> result, int[] queens, int row) {
14
        int len = queens.length;
15

16
        // finish one solution
17
        if (len == row) {
18
            List<String> temp = new ArrayList<>();
19

20
            // generate an n*n chessboard based on queens' positions
21
            for (int i : queens) {
22
                char[] boardRow = new char[len];
23
                Arrays.fill(boardRow, '.');
24
                boardRow[i] = 'Q';
25

26
                // char[] -> str
27
                temp.add(String.valueOf(boardRow));
28
            }
29

30
            // add this chessboard to result
31
            result.add(temp);
32
            return;
33
        }
34

35
        // look for suitable column to place queen in current row
36
        for (int col = 0; col < len; col++) {
37
            if (isValid(queens, row, col)) {
38
                queens[row] = col; // put queen in current column
39
                dfs(result, queens, row + 1); // move to next row
40
            }
41
        }
42
    }
43

44
    private boolean isValid(int[] queens, int row, int col) {
45
        for (int i = 0; i < row; i++) {
46
            // there should be no queen in this row or diagnosal line
47
            if (queens[i] == col || Math.abs(col - queens[i]) == row - i) {
48
                return false;
49
            }
50
        }
51

52
        return true;
53
    }
54
}

53. Maximum Subarray#

https://leetcode.com/problems/maximum-subarray/

使用一个临时变量tempSum从首个元素开始跟踪当前的子序列和。只有确保子序列和大于0才继续累积；否则就从当前元素开始重新寻找新的最大子序列。

1
class Solution {
2
    public int maxSubArray(int[] nums) {
3
        if (nums == null || nums.length == 0) {
4
            return 0;
5
        }
6

7
        int len = nums.length;
8
        int result = nums[0], tempSum = nums[0];
9

10
        // if subarray's sum is larger than 0, add nums[i]; or, tempSum should be reset as nums[i]
11
        for (int i = 1; i < len; i++) {
12
            tempSum = Math.max(tempSum, 0) + nums[i];
13
            result = Math.max(result, tempSum);
14
        }
15
        return result;
16
    }
17
}

54. Spiral Matrix#

https://leetcode.com/problems/spiral-matrix/

分别使用四个变量，储存目前输出行、列的两个边界值，保证输出发生在两个边界之内。每一圈输出都按照右、下、左、上的顺序进行，但要注意由于奇偶性关系，左和上的输出可能是不必要的（如果边界值已经重合了）。

1
class Solution {
2
    public List<Integer> spiralOrder(int[][] matrix) {
3
        List<Integer> result = new ArrayList<>();
4
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
5
            return result;
6
        }
7

8
        int left = 0, right = matrix[0].length - 1, up = 0, down = matrix.length - 1;
9
        while (left <= right && up <= down) {
10
            // right
11
            for (int j = left; j <= right; j++) {
12
                result.add(matrix[up][j]);
13
            }
14
            up++;
15

16
            // down
17
            for (int i = up; i <= down; i++) {
18
                result.add(matrix[i][right]);
19
            }
20
            right--;
21

22
            // left, only when up <= down
23
            if (up <= down) {
24
                for (int j = right; j >= left; j--) {
25
                    result.add(matrix[down][j]);
26
                }
27
                down--;
28
            }
29

30
            // up, only when left <= right
31
            if (left <= right) {
32
                for (int i = down; i >= up; i--) {
33
                    result.add(matrix[i][left]);
34
                }
35
                left++;
36
            }
37
        }
38

39
        return result;
40
    }
41
}

55. Jump Game#

https://leetcode.com/problems/jump-game/

此题判断的是能否到达数组终点。仍然使用贪心算法，选取能达到最远位置的落点进行跳跃。

然而，落点可能永远无法落到终点或终点之后，此时下一次备选的落点区域边界start和end都将无法更新，因此需要额外判断这两个落点的关系。

1
class Solution {
2
    public boolean canJump(int[] nums) {
3
        if (nums == null || nums.length == 0) {
4
            return false;
5
        }
6

7
        int start = 0, end = 0; // in current step, I can reach the interval [start, end]
8
        int maxEnd = 0; // the farthest fall of the jump
9

10
        while (end < nums.length - 1) {
11
            // find out the maxEnd
12
            for (int i = start; i <= end; i++) {
13
                maxEnd = Math.max(maxEnd, nums[i] + i);
14
            }
15

16
            // generate next [start, end] range
17
            start = end + 1; // next range's start must be larger than current range's end
18
            end = maxEnd;
19

20
            // this indicates that end does not change, so we cannot go further
21
            if (start == end + 1) {
22
                return false;
23
            }
24
        }
25
        return true;
26
    }
27
}

56. Merge Intervals#

https://leetcode.com/problems/merge-intervals/

将输入的数组元素按区间起始值从小到大排序。

倘若如果出现了重叠，则更新前一个区间的end值。相当于间接合并了区间，把两个区间看作一个整体
没有重叠，将当前区间加入结果集合中。这个区间同时也是当前遍历到的最后一个有效区间

1
class Solution {
2
    public int[][] merge(int[][] intervals) {
3
        if (intervals == null || intervals.length < 2) {
4
            return intervals;
5
        }
6

7
        // sort by interval start
8
        Arrays.sort(intervals, (int[] interval1, int[] interval2) -> {
9
            return interval1[0] - interval2[0];
10
        });
11

12
        List<int[]> result = new ArrayList<>();
13
        int[] prev = intervals[0];
14
        result.add(prev);
15

16
        for (int[] current : intervals) {
17
            if (current[0] <= prev[1]) {
18
                // Overlapping intervals, update previous interval's end
19
                prev[1] = Math.max(prev[1], current[1]);
20
            } else {
21
                // No overlapping, add current to result
22
                prev = current;
23
                result.add(current);
24
            }
25
        }
26

27
        // convert list to array
28
        return result.toArray(new int[result.size()][2]);
29
    }
30
}

57. Insert Interval#

https://leetcode.com/problems/insert-interval/

添加肯定位于newInterval之前的区间
针对所有和newInterval有重叠的区间，计算出最小的起点和最大的终点，直接合并
添加合并后的大区间
添加肯定位于newInterval之后的区间

1
class Solution {
2
    public int[][] insert(int[][] intervals, int[] newInterval) {
3
        if (intervals == null || intervals.length == 0) {
4
            return new int[][] {
5
                { newInterval[0], newInterval[1] }
6
            };
7
        }
8

9
        List<int[]> result = new ArrayList<>();
10
        int i = 0, start = newInterval[0], end = newInterval[1];
11

12
        // intervals prior to newInterval
13
        while (i < intervals.length && intervals[i][1] < start) {
14
            result.add(intervals[i]);
15
            i++;
16
        }
17

18
        // for all overlapping intervals, find the minimum start and maximum end
19
        while (i < intervals.length && intervals[i][0] <= end) {
20
            start = Math.min(start, intervals[i][0]);
21
            end = Math.max(end, intervals[i][1]);
22
            i++;
23
        }
24

25
        // assume all overlapping intervals are merged in one big interval [start, end]
26
        result.add(new int[]{start, end});
27

28
        // add the rest intervals
29
        while (i < intervals.length) {
30
            result.add(intervals[i++]);
31
        }
32

33
        return result.toArray(new int[result.size()][2]);
34
    }
35
}

58. Length of Last Word#

https://leetcode.com/problems/length-of-last-word/

先排除从最右侧开始含有若干空白字符的情况；之后从第一个非空白的字符开始向左遍历，直至遇到下一个空格为止，统计中间经过了多少个字符。

1
class Solution {
2
    public int lengthOfLastWord(String s) {
3
        if (s == null || s.length() == 0) {
4
            return 0;
5
        }
6
        int result = 0, index = s.length() - 1;
7

8
        // trim all trailing 0
9
        while (s.charAt(index) == ' ') {
10
            index--;
11
            if (index < 0) {
12
                return 0;
13
            }
14
        }
15

16
        // calculate last word's length
17
        for (int i = index; i >= 0; i--) {
18
            if (s.charAt(i) == ' ') {
19
                return result;
20
            }
21
            result++;
22
        }
23

24
        return result;
25
    }
26
}

59. Spiral Matrix II#

https://leetcode.com/problems/spiral-matrix-ii/

提前分配好二维数组空间，螺旋遍历逐个将数字塞入即可。由于是n * n矩阵，因此不用考虑矩阵长宽不一致的情况。

1
class Solution {
2
    public int[][] generateMatrix(int n) {
3
        int[][] result = new int[n][n];
4

5
        // current number to be added
6
        int current = 1;
7

8
        int up = 0, down = n - 1, left = 0, right = n - 1;
9

10
        while (left <= right) {
11
            // right
12
            for (int j = left; j <= right; j++) {
13
                result[up][j] = current++;
14
            }
15
            up++;
16

17
            // down
18
            for (int i = up; i <= down; i++) {
19
                result[i][right] = current++;
20
            }
21
            right--;
22

23
            // left
24
            for (int j = right; j >= left; j--) {
25
                result[down][j] = current++;
26
            }
27
            down--;
28

29
            // up
30
            for (int i = down; i >= up; i--) {
31
                result[i][left] = current++;
32
            }
33
            left++;
34
        }
35

36
        return result;
37
    }
38
}

60. Permutation Sequence#

https://leetcode.com/problems/permutation-sequence/

由于题目限定输入的n在1-9之内，因此最快速的方法是提前将1-9的阶乘算好存在数组中。

从1开始遍历到n，每一步我们都可以算出固定当前位的前提下，后续共有多少种组合情况；因此我们可以用k / currMaxFactorial得到当前位需要向上增加多少offset才可以快速逼近第k种组合。

1
class Solution {
2
    public String getPermutation(int n, int k) {
3
        int[] factorials = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
4
        StringBuilder sb = new StringBuilder();
5
        boolean[] used = new boolean[10];
6

7
        // minus starting k by 1 to get correct offset, otherwise we will exactly the (k+1) th permutation
8
        k--;
9

10
        for (int i = 1; i <= n; i++) {
11
            // for current i and n, this is the max factorial threshold
12
            int currMaxFactorial = factorials[n - i];
13

14
            // the diff between current digit (0) and ideal digit
15
            // if we fix current digit, we get currMaxFactorial permutations for subsequent digits
16
            int offset = k / currMaxFactorial;
17

18
            // find the digit to append
19
            int digit = 0;
20
            int count = 0;
21
            while (count <= offset) {
22
                digit++;
23
                if (!used[digit]) {
24
                    count++;
25
                }
26
            }
27

28
            // append current digit and mark as used
29
            sb.append(digit);
30
            used[digit] = true;
31

32
            // we have covered the first currMaxFactorial permutations, so update k and cover the rest
33
            k %= currMaxFactorial;
34
        }
35

36
        return sb.toString();
37
    }
38
}

61. Rotate List#

https://leetcode.com/problems/rotate-list/

获取链表的总长度，并将最后一个元素指向头元素，该过程遍历一次链表可完成
计算出指针实际移动的距离。尽管k的值可能大于链表长度，但是取模后即可解决这个问题
返回新的head，新的结尾将指向NULL

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode rotateRight(ListNode head, int k) {
13
        if (head == null || k == 0) {
14
            return head;
15
        }
16

17
        // get list length and set the last node's next to head
18
        int length = 1;
19
        ListNode cur = head;
20
        while (cur.next != null) {
21
            length++;
22
            cur = cur.next;
23
        }
24
        cur.next = head;
25

26
        // actual move length
27
        k %= length;
28
        k++;
29
        int move = length - k;
30

31
        // find new head
32
        cur = head;
33
        while (move > 0) {
34
            cur = cur.next;
35
            move--;
36
        }
37
        ListNode newHead = cur.next;
38
        cur.next = null;
39

40
        return newHead;
41
    }
42
}

62. Unique Paths#

https://leetcode.com/problems/unique-paths/

使用动态规划，记录到达每一个方格的路径总数，不断递推到出口。

二维空间下，很容易发现动态规划递推式为：

1
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

dp[i][j]依赖的两个值分别是dp[i - 1][j](对应上一行的同一列)和dp[i][j - 1](对应同一行的上一列)。因此我们可以进行空间的压缩：

1
cur[j] = pre[j] + cur[j - 1]
2

3
// pre is last line
4
// cur is current line

在更新cur[j]之前，实际上pre[j]和cur[j]的值就是相等的，因为上一行时的cur自然就是这一行pre。所以可以得到：

1
cur[j] = cur[j] + cur[j - 1]
2

3
// or
4

5
dp[j] += dp[j - 1]

因此最终我们使用一维动态数组降低空间复杂度。

1
class Solution {
2
    public int uniquePaths(int m, int n) {
3
        if (m < 1 || n < 1) {
4
            return 0;
5
        }
6

7
        int[] dp = new int[n];
8
        dp[0] = 1;
9

10
        // row by row and accumulate one by one
11
        for (int i = 0; i < m; i++) {
12
            for (int j = 0; j < n; j++) {
13
                if (j > 0) {
14
                    dp[j] += dp[j-1];
15
                }
16
            }
17
        }
18

19
        return dp[n-1];
20
    }
21
}

63. Unique Paths II#

https://leetcode.com/problems/unique-paths-ii/

仍然使用一维数组动态规划；遇到障碍物时，该列在动态规划中的结果重置为0。

1
class Solution {
2
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
3
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
4
            return 0;
5
        }
6
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
7

8
        int[] dp = new int[n];
9
        dp[0] = 1;
10

11
        // row by row and accumulate one by one
12
        for (int i = 0; i < m; i++) {
13
            for (int j = 0; j < n; j++) {
14
                // when obstacle encountered, this column's result is reset to 0
15
                if (obstacleGrid[i][j] == 1) {
16
                    dp[j] = 0;
17
                } else if (j > 0) {
18
                    dp[j] += dp[j-1];
19
                }
20
            }
21
        }
22

23
        return dp[n-1];
24
    }
25
}

64. Minimum Path Sum#

https://leetcode.com/problems/minimum-path-sum/

对于左边界和右边界上的点，只存在一条道走到黑的情况；对于不在左边界/上边界的点，只需要比较其上方和左方的单元格中哪一格路径更小，即可不断迭代出结果。

1
class Solution {
2
    public int minPathSum(int[][] grid) {
3
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
4
            return 0;
5
        }
6

7
        int m = grid.length, n = grid[0].length;
8

9
        int[][] dp = new int[m][n];
10
        dp[0][0] = grid[0][0];
11

12
        // fill first row and first column
13
        for (int j = 1; j < n; j++) {
14
            dp[0][j] = grid[0][j] + dp[0][j-1];
15
        }
16
        for (int i = 1; i < m; i++) {
17
            dp[i][0] = grid[i][0] + dp[i-1][0];
18
        }
19

20
        // for other grids, choose the smaller value of up or left grid's value
21
        for (int i = 1; i < m; i++) {
22
            for (int j = 1; j < n; j++) {
23
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
24
            }
25
        }
26

27
        return dp[m-1][n-1];
28
    }
29
}

65. Valid Number#

https://leetcode.com/problems/valid-number/

正常情况下，出现数字时默认算作valid number，但考虑一些特殊情况：

出现小数点时，小数点前不能有e（或者E），且小数点不能超过一个
出现e（或者E）时，e不能超过1个，且e前必须有数字
出现正负号时，正负号必须为首字符或紧跟在e之后

1
class Solution {
2
    public boolean isNumber(String s) {
3
        s = s.trim(); // trim all leading blank space
4

5
        boolean pointSeen = false;
6
        boolean eSeen = false;
7
        boolean isNumber = false;
8

9
        for (int i = 0; i < s.length(); i++) {
10
            char ch = s.charAt(i);
11

12
            if (ch >= '0' && ch <= '9') {
13
                // a valid digit
14
                isNumber = true;
15
            } else if (ch == '.') {
16
                // if there is already a 'e', or there is more than one '.'
17
                if (eSeen || pointSeen) {
18
                    return false;
19
                }
20

21
                pointSeen = true;
22
            } else if (ch == 'e' || ch == 'E') {
23
                // if there is more than one 'e', or there is no digit before 'e'
24
                if (eSeen || !isNumber) {
25
                    return false;
26
                }
27

28
                eSeen = true;
29

30
                // need more valid digits
31
                isNumber = false;
32
            } else if (ch == '-' || ch == '+') {
33
                // sign should be first char or part of exponent
34
                if (i != 0 && s.charAt(i - 1) != 'e') {
35
                    return false;
36
                }
37
            } else {
38
                // other characters are invalid
39
                return false;
40
            }
41
        }
42

43
        return isNumber;
44
    }
45
}

66. Plus One#

https://leetcode.com/problems/plus-one/

只有最后一位数为9时，才会有进位可能，其他时候直接+1出结果。如果每一位数都是9，则位数多了一位，直接开辟一个新数组，首位为1即可。

1
class Solution {
2
    public int[] plusOne(int[] digits) {
3
        int len = digits.length;
4

5
        for (int i = len - 1; i >= 0; i--) {
6
            if (digits[i] < 9) {
7
                digits[i]++;
8
                return digits;
9
            }
10

11
            // update current digit as 0
12
            digits[i] = 0;
13
        }
14

15
        // previous number is 999....999, should update to 1000...000
16
        int[] result = new int[len+1];
17
        for (int i = 0; i < result.length; i++) {
18
            result[i] = i == 0 ? 1 : 0;
19
        }
20
        return result;
21
    }
22
}

67. Add Binary#

https://leetcode.com/problems/add-binary/

两个指针分别跟踪a, b，可以避开比较a, b长度的麻烦。

另一个技巧是倒序添加每一位数，最后输出时再颠倒能节省时间，原因是StringBuilder的append()操作比insert()操作快很多。

1
class Solution {
2
    public String addBinary(String a, String b) {
3
        StringBuilder sb = new StringBuilder();
4

5
        // two pointers will traverse a, b from end to begin
6
        int i = a.length() - 1, j = b.length() - 1;
7

8
        // carry and sum
9
        int carry = 0, sum = 0;
10

11
        while (i >= 0 || j >= 0) {
12
            sum = carry;
13

14
            // add from the least significant bit to the most significant bit
15
            if (i >= 0) {
16
                sum += a.charAt(i) - '0';
17
                i--;
18
            }
19
            if (j >= 0) {
20
                sum += b.charAt(j) - '0';
21
                j--;
22
            }
23

24
            sb.append(sum % 2);
25
            carry = sum / 2;
26
        }
27

28
        // add carry to the back
29
        if (carry != 0) {
30
            sb.append(carry);
31
        }
32

33
        // reverse to get final sum
34
        return sb.reverse().toString();
35
    }
36
}

68. Text Justification#

https://leetcode.com/problems/text-justification/

遍历输入的每一个单词，在将一个单词加入到当前行时，需要判断：

当前行未满，可以继续添加单词，即原有单词长度 + 原有单词之间的间隙 + 当前单词长度之和仍然小于maxWidth
当前行已满，则先进行处理。如果只有一个单词，则直接左对齐，在单词右侧加空格；否则，计算出每一个单词之间的间隙。这里使用的是除数取模方法，使得空格前宽后窄。处理之后，当前行清空，再加入新的单词
最后一行需要单独考虑，因为我们只有在一行的长度超出范围时才会做对齐处理，因此当遍历到words的最后一个单词时，最后一行已有的长度可能还未超过maxWidth。我们需要在循环结束后将最后一行提取出来，左对齐处理。

1
class Solution {
2
    public List<String> fullJustify(String[] words, int maxWidth) {
3
        List<String> result = new ArrayList<>();
4
        List<String> line = new ArrayList<>();
5
        if (words.length == 0) {
6
            return result;
7
        }
8

9
        int currentLen = 0;
10
        for (int i = 0; i < words.length; i++) {
11
            // determine if we can add another word to current line
12
            // previous words length + current word length + at least one space between every 2 words
13
            if (currentLen + words[i].length() + line.size() <= maxWidth) {
14
                line.add(words[i]);
15
                currentLen += words[i].length();
16
            } else {
17
                if (line.size() == 1) {
18
                    // current line is full and only has 1 word, left align and add space to the right
19
                    StringBuilder row = new StringBuilder(line.get(0));
20
                    currentLen = row.length();
21
                    for (int j = 1; j <= maxWidth - currentLen; j++) {
22
                        row.append(' ');
23
                    }
24
                    result.add(row.toString());
25
                } else {
26
                    // current line is full and has multiple words
27
                    // first 'mod' words: 'div' + 1 spaces
28
                    // other words: 'div' spaces
29
                    int div = (maxWidth - currentLen) / (line.size() - 1);
30
                    int mod = (maxWidth - currentLen) % (line.size() - 1);
31

32
                    StringBuilder row = new StringBuilder(line.get(0));
33
                    for (int j = 1; j < line.size(); j++) {
34
                        if (j <= mod) {
35
                            for (int k = 0; k < div + 1; k++) {
36
                                row.append(' ');
37
                            }
38
                        } else {
39
                            for (int k = 0; k < div; k++) {
40
                                row.append(' ');
41
                            }
42
                        }
43

44
                        row.append(line.get(j));
45
                    }
46

47
                    result.add(row.toString());
48
                }
49

50
                // clear current line and add new word
51
                line.clear();
52
                line.add(words[i]);
53
                currentLen = words[i].length();
54
            }
55
        }
56

57
        // handle the final row
58
        // left align and separated with blank space
59
        StringBuilder finalRow = new StringBuilder(line.get(0));
60
        for (int i = 1; i < line.size(); i++) {
61
            finalRow.append(" " + line.get(i));
62
        }
63
        currentLen = finalRow.length();
64

65
        // add trailing blanks
66
        for (int i = 1; i <= maxWidth - currentLen; i++) {
67
            finalRow.append(' ');
68
        }
69

70
        result.add(finalRow.toString());
71

72
        return result;
73
    }
74
}

69. Sqrt(x)#

https://leetcode.com/problems/sqrtx/

问题转化为二分查找，即给定0到x的数组，找到sqrt(x)或者是小于sqrt(x)的最大整数。

如果sqrt(x)存在的话，将其找出；如果不存在的话，由于最后left > right，因此right是最接近且小于sqrt(x)的整数。

另外注意，这题需要考虑到整数溢出情况，因此可以在二分查找过程开始前将int转为long。

1
class Solution {
2
    public int mySqrt(int x) {
3
        long left = 0, right = x, target = x;
4

5
        while (left <= right) {
6
            long mid = left + (right - left) / 2;
7
            if (mid * mid == target) {
8
                return (int)mid;
9
            } else if (mid * mid < target) {
10
                left = mid + 1;
11
            } else {
12
                right = mid - 1;
13
            }
14
        }
15

16
        return (int)right;
17
    }
18
}

70. Climbing Stairs#

https://leetcode.com/problems/climbing-stairs/

使用动态规划解决，到达第i层阶梯之前，要么到达第i - 2层阶梯之后爬两层，要么到达第i - 1层阶梯之后爬一层。注意先到i - 2层再到i - 1层的情况是包含在到达第i - 1层的情况里的。

1
class Solution {
2
    public int climbStairs(int n) {
3
        if (n == 1 || n == 2) {
4
            return n;
5
        }
6

7
        // count of distinct ways to climb to the 0 ~ n-th steps
8
        int[] dp = new int[n+1];
9
        dp[1] = 1;
10
        dp[2] = 2;
11

12
        // to reach the i-th step, we could reach the (i - 2)th step, then climb 2 steps
13
        // or reach the (i - 1)th step, then climb 1 step
14
        for (int i = 3; i <= n; i++) {
15
            dp[i] = dp[i-1] + dp[i-2];
16
        }
17

18
        return dp[n];
19
    }
20
}

71. Simplify Path#

https://leetcode.com/problems/simplify-path/

利用String.split()函数，提取出每个实际的文件夹名；利用栈进行判断，只有遇到..且栈不空时需要弹出栈顶元素；其余字符串，如果不是.., .或' '，均直接加入栈中即可。输出时，使用集合遍历，从栈底至栈顶正向输出。

1
class Solution {
2
    public String simplifyPath(String path) {
3
        Stack<String> stack = new Stack<>();
4

5
        for (String dir : path.split("/")) {
6
            // back to upper directory
7
            if (dir.equals("..") && !stack.isEmpty()) {
8
                stack.pop();
9
            } else if (!dir.equals("..") && !dir.equals(".") && !dir.equals("")) {
10
                // lower directory
11
                stack.push(dir);
12
            }
13
        }
14

15
        // format path
16
        String result = "";
17
        for (String dir : stack) {
18
            result += "/" + dir;
19
        }
20

21
        return result.isEmpty() ? "/" : result;
22
    }
23
}

72. Edit Distance#

https://leetcode.com/problems/edit-distance/

使用动态规划，创建一个二维数组result,其中result[i][j]表示将word1的前i个字母转化为word2的前j个字母所需要的最小步数。

比较word1的第i个字母和word2的第j个字母，无非两种情况：

二者相等，不需要变化操作，即result[i+1][j+1] = result[i][j]
二者不相等，则选择插入、删除、替换中的一种，分别对应result[i+1][j], result[i][j+1]和result[i][j]，取最小的值

1
class Solution {
2
    public int minDistance(String word1, String word2) {
3
        int m = word1.length(), n = word2.length();
4
        if (m == 0 || n == 0) {
5
            return m+n;
6
        }
7

8
        int[][] result = new int[m+1][n+1];
9
        for (int i = 0; i <= m; i++) {
10
            result[i][0] = i;
11
        }
12
        for (int j = 0; j <= n; j++) {
13
            result[0][j] = j;
14
        }
15

16
        for (int i = 0; i < m; i++) {
17
            for (int j = 0; j < n; j++) {
18
                // i-th word of word1 is equal to j-th word of word2, no need to change
19
                if (word1.charAt(i) == word2.charAt(j)) {
20
                    result[i+1][j+1] = result[i][j];
21
                } else {
22
                    int insert = result[i+1][j];
23
                    int delete = result[i][j+1];
24
                    int replace = result[i][j];
25
                    // select the operation with minimum cost
26
                    result[i+1][j+1] = 1 + Math.min(insert, Math.min(delete, replace));
27
                }
28
            }
29
        }
30

31
        return result[m][n];
32
    }
33
}

73. Set Matrix Zeroes#

https://leetcode.com/problems/set-matrix-zeroes/

此题的难点在于需要使用O(1)的空间复杂度。一个思路是，先对数组进行一次从上到下的遍历。如果遇到了0，则将当前行、列的首个元素均置为0。完成后，第二次遍历从下到上，如果遇到行首或列首为0，则将当前元素置为0。

一个特殊情况是，数组首个元素既是第一行的行首，又是第一列的列首，产生了冲突。因此，需要将第一列的状态单独标记。

1
class Solution {
2
    public void setZeroes(int[][] matrix) {
3
        if (matrix.length == 0 || matrix[0].length == 0) {
4
            return;
5
        }
6

7
        int row = matrix.length, col = matrix[0].length;
8

9
        // first element of the first column
10
        int col0 = 1;
11

12
        // top-down travel, when encounter 0, set first element of this row & column to 0
13
        for (int i = 0; i < row; i++) {
14
            // the first column should be set as 0 later
15
            if (matrix[i][0] == 0) {
16
                col0 = 0;
17
            }
18

19
            for (int j = 1; j < col; j++) {
20
                if (matrix[i][j] == 0) {
21
                    matrix[i][0] = matrix[0][j] = 0;
22
                }
23
            }
24
        }
25

26
        // bottom-up travel, if first element of this row / column is 0, set current element to 0
27
        for (int i = row - 1; i >= 0; i--) {
28
            for (int j = col - 1; j >= 1; j--) {
29
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
30
                    matrix[i][j] = 0;
31
                }
32
            }
33

34
            if (col0 == 0) {
35
                matrix[i][0] = 0;
36
            }
37
        }
38
    }
39
}

74. Search a 2D Matrix#

https://leetcode.com/problems/search-a-2d-matrix/

将排好序的二维数组看成一个连续的一维数组，就可以应用二分查找。

1
class Solution {
2
    public boolean searchMatrix(int[][] matrix, int target) {
3
        if (matrix.length == 0 || matrix[0].length == 0) {
4
            return false;
5
        }
6
        int m = matrix.length, n = matrix[0].length;
7

8
        // treat the 2D arrays as a big sorted 1D array
9
        int left = 0, right = m * n - 1;
10
        while (left <= right) {
11
            int mid = left + (right - left) / 2;
12

13
            if (matrix[mid / n][mid % n] == target) {
14
                return true;
15
            } else if (matrix[mid / n][mid % n] < target) {
16
                left = mid + 1;
17
            } else {
18
                right = mid - 1;
19
            }
20
        }
21

22
        return false;
23
    }
24
}

75. Sort Colors#

https://leetcode.com/problems/sort-colors/

默认将0放到当前能放到的最左下标，2放到当前能放到的最右下标，并使用两个指针分别跟踪这两个位置。

遍历数组，遇到0或2时，两个指针指向的元素进行交换。需要注意，如果遇到2的时候，下一次仍然是在当前位置继续遍历(因为不知道换过来的元素是什么)，因此i需要递减1退回到当前下标。

1
class Solution {
2
    public void swap(int[] nums, int i, int j) {
3
        int temp = nums[i];
4
        nums[i] = nums[j];
5
        nums[j] = temp;
6
    }
7

8
    public void sortColors(int[] nums) {
9
        if (nums.length == 0) {
10
            return;
11
        }
12
        int index_0 = 0, index_2 = nums.length - 1;
13

14
        for (int i = 0; i <= index_2; i++) {
15
            if (nums[i] == 0) {
16
                swap(nums, i, index_0);
17
                index_0++;
18
            } else if (nums[i] == 2) {
19
                swap(nums, i, index_2);
20
                index_2--;
21

22
                // decrement by 1 as we don't know what we have swapped
23
                i--;
24
            }
25
        }
26
    }
27
}

76. Minimum Window Substring#

https://leetcode.com/problems/minimum-window-substring/

使用两个map：

smap，统计s中每个字符出现的次数
tmap，统计t中每个字符出现的次数

解题步骤：

统计t中每个字符出现的次数到tmap中，并同时统计t中总共有多少个不同的字符
双指针法遍历s，每当遇到一个在t中出现过的字符，就相应更新smap中的字符出现次数
如果某个字符在smap中的出现次数与tmap相等，说明目前的子字符串s[left, right]中已经包含了足够多的该字符。如果全部字符都满足了这个条件，就说明当前的子字符串是一个符合题意的sliding window，看这个window的长度是否是已知最小的
在保证sliding window仍旧合法的前提下，尝试从头开始缩减长度，即：如果当前的字符s[left]在smap中的次数比tmap中多，就删掉一个s[left]，并且向后移动left指针。一直重复这个过程，直到某次完成删除后，sliding window不再合法
完成遍历后，根据此前统计的最小值信息截取子字符串，得到结果；而如果发现最短长度并没有更新过，说明不存在这样的sliding window

1
class Solution {
2
    public String minWindow(String s, String t) {
3
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
4
            return "";
5
        }
6

7
        // count how many times each character appears in t
8
        int[] tmap = new int[256];
9
        for (int i = 0; i < 256; i++) {
10
            tmap[i] = Integer.MIN_VALUE;
11
        }
12

13
        // unique characters count
14
        int unique = 0;
15
        for (char c : t.toCharArray()) {
16
            if (tmap[c] == Integer.MIN_VALUE) {
17
                unique++;
18
                tmap[c] = 1;
19
            } else {
20
                tmap[c]++;
21
            }
22
        }
23

24
        // count how many times each character appears in s
25
        int[] smap = new int[256];
26
        for (int i = 0; i < 256; i++) {
27
            smap[i] = 0;
28
        }
29

30
        // current beginning index of sliding window
31
        int left = 0;
32

33
        // the beginning index & length of the minimum sliding window
34
        int minLeft = 0, minLen = Integer.MAX_VALUE;
35

36
        // how many characters have been completely matched
37
        int count = 0;
38

39
        for (int right = 0; right < s.length(); right++) {
40
            if (tmap[s.charAt(right)] != Integer.MIN_VALUE) {
41
                smap[s.charAt(right)]++;
42

43
                if (smap[s.charAt(right)] == tmap[s.charAt(right)]) {
44
                    count++;
45
                }
46

47
                // contains all characters in t, try to decrease the size of the sliding window
48
                while (count == unique) {
49
                    // record current starting index and minimum length
50
                    if (right - left + 1 < minLen) {
51
                        minLeft = left;
52
                        minLen = right - left + 1;
53
                    }
54

55
                    // delete extra characters
56
                    if (smap[s.charAt(left)] >= tmap[s.charAt(left)]) {
57
                        smap[s.charAt(left)]--;
58

59
                        if (smap[s.charAt(left)] < tmap[s.charAt(left)]) {
60
                            count--;
61
                        }
62
                    }
63

64
                    left++;
65
                }
66
            }
67
        }
68

69
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
70
    }
71
}

77. Combinations#

https://leetcode.com/problems/combinations/

回溯算法，注意每一轮选数之后k值的递减更新，以及起始数startNum的范围。

1
class Solution {
2
    public List<List<Integer>> combine(int n, int k) {
3
        List<List<Integer>> result = new ArrayList<>();
4
        if (n < k) {
5
            return result;
6
        }
7

8
        // the range is 1 ... n, so start from 1
9
        backtrack(result, new ArrayList<>(), n, k, 1);
10
        return result;
11
    }
12

13
    private void backtrack(List<List<Integer>> result, List<Integer> temp, int n, int k, int startNum) {
14
        // deep copy then add to result
15
        if (k == 0) {
16
            result.add(new ArrayList<>(temp));
17
            return;
18
        }
19

20
        // startNum should be no larger than n - k + 1, as [n - k + 1, n] will contain exactly k numbers
21
        for (int i = startNum; i <= n - k + 1; i++) {
22
            temp.add(i);
23

24
            // k - 1 remaining numbers; current index increment by 1
25
            backtrack(result, temp, n, k - 1, i + 1);
26

27
            temp.remove(temp.size() - 1);
28
        }
29
    }
30
}

78. Subsets#

https://leetcode.com/problems/subsets/

深度优先，回溯算法穷举添加每个数到临时list中，每个中间结果都是一个子集。

1
class Solution {
2
    public List<List<Integer>> subsets(int[] nums) {
3
        List<List<Integer>> result = new ArrayList<>();
4
        Arrays.sort(nums);
5
        backtrack(result, new ArrayList<>(), nums, 0);
6
        return result;
7
    }
8

9
    private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] nums, int index) {
10
        // every trial temp list is a subset
11
        result.add(new ArrayList<>(temp));
12

13
        for (int i = index; i < nums.length; i++) {
14
            temp.add(nums[i]);
15

16
            // after trying current number, we should try subsequent numbers, so increment i by 1
17
            backtrack(result, temp, nums, i + 1);
18

19
            temp.remove(temp.size() - 1);
20
        }
21
    }
22
}

79. Word Search#

https://leetcode.com/problems/word-search/

深度优先搜索与回溯算法的结合。对每一单元格，向四个方向的邻近单元格延展，如果超出数组边界或与word当前长度上的字符不匹配就返回false。访问过的单元格用位掩码做标记，避免走回头路，回溯之后复原。

1
class Solution {
2
    public boolean exist(char[][] board, String word) {
3
        if (board.length == 0 || board[0].length == 0 || word.length() == 0) {
4
            return false;
5
        }
6

7
        for (int i = 0; i < board.length; i++) {
8
            for (int j = 0; j < board[0].length; j++) {
9
                if (isMatch(board, i, j, word, 0)) {
10
                    return true;
11
                }
12
            }
13
        }
14

15
        return false;
16
    }
17

18
    private boolean isMatch(char[][] board, int x, int y, String word, int len) {
19
        // the length meets requirement, and the last character is matched in last recursion
20
        if (len == word.length()) {
21
            return true;
22
        }
23

24
        // out of bound
25
        if (x < 0 || x == board.length || y < 0 || y == board[0].length) {
26
            return false;
27
        }
28

29
        // current character is unmatched, fail
30
        if (board[x][y] != word.charAt(len)) {
31
            return false;
32
        }
33

34
        board[x][y] ^= 256; // mask current character
35

36
        // next character may appear in up, down, left, right adjacent grid
37
        boolean result = isMatch(board, x + 1, y, word, len + 1) ||
38
                         isMatch(board, x - 1, y, word, len + 1) ||
39
                         isMatch(board, x, y + 1, word, len + 1) ||
40
                         isMatch(board, x, y - 1, word, len + 1);
41

42
        board[x][y] ^= 256; // restore
43

44
        return result;
45
    }
46
}

80. Remove Duplicates from Sorted Array II#

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

遍历数组，前两个数不变，照常赋值；自第三个数开始，如果当前赋值的位置是index，必须保证当前数比nums[index - 2]更大时才覆盖值。中间间隔的一个位置留给重复的可能。

1
class Solution {
2
    public int removeDuplicates(int[] nums) {
3
        if (nums == null || nums.length < 1) {
4
            return 0;
5
        }
6

7
        int index = 0;
8
        for (int num : nums) {
9
            // we have at most twice appearance for each unique element
10
            // so num should be larger than nums[index - 2] and nums[index - 1]
11
            if (index < 2 || num > nums[index - 2]) {
12
                nums[index] = num;
13
                index++;
14
            }
15
        }
16

17
        return index;
18
    }
19
}

81. Search in Rotated Sorted Array II#

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

这一题的输入数组可能出现重复数字，因此可能出现难以判断某侧有序的情况（例如nums[left], nums[mid], nums[right]相等），这个时候无法应用二分查找缩小一半的搜索范围，只能左移right指针，继续循环。很显然，最坏的情况下算法的时间复杂度会退化到O(n)。

1
class Solution {
2
    public boolean search(int[] nums, int target) {
3
        if (nums == null || nums.length == 0) {
4
            return false;
5
        }
6

7
        int left = 0, right = nums.length - 1;
8

9
        while (left <= right) {
10
            int mid = left + (right - left) / 2;
11
            if (nums[mid] == target) {
12
                return true;
13
            }
14

15
            if (nums[left] < nums[mid] || nums[right] < nums[mid]) {
16

17
                // nums[mid] is a peak element
18
                // possible comparison: nums[left] <= target < nums[mid],
19
                if (target >= nums[left] && target < nums[mid]) {
20
                    right = mid - 1;
21
                } else {
22
                    left = mid + 1;
23
                }
24
            } else if (nums[mid] < nums[right] || nums[mid] < nums[left]) {
25

26
                // nums[mid] is a bottom element
27
                // possible comparison: nums[mid] < target <= nums[right]
28
                if (target > nums[mid] && target <= nums[right]) {
29
                    left = mid + 1;
30
                } else {
31
                    right = mid - 1;
32
                }
33
            } else {
34
                // nums[left] == nums[mid] == nums[right], we cannot decide which half is ordered
35
                right--;
36
            }
37
        }
38

39
        return false;
40
    }
41
}

82. Remove Duplicates from Sorted List II#

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

用一个指针cur指向当前最后一个非重复的数字；当遇到重复的数字时，使用一个while循环跳过所有的重复值。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode deleteDuplicates(ListNode head) {
13
        if (head == null) {
14
            return head;
15
        }
16

17
        ListNode dummyHead = new ListNode(0);
18
        dummyHead.next = head;
19

20
        // the last non-duplicate
21
        ListNode cur = dummyHead;
22

23
        while (head != null) {
24
            // head val is not same as the next one
25
            if (head.next == null || head.val != head.next.val) {
26
                cur = head;
27
                head = head.next;
28
            } else {
29
                int val = head.val;
30

31
                // move head forward and skip all duplicates
32
                while (head != null && head.val == val) {
33
                    head = head.next;
34
                }
35
                cur.next = head;
36
            }
37
        }
38

39
        return dummyHead.next;
40
    }
41
}

83. Remove Duplicates from Sorted List#

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

同时比较当前指针对应元素以及当前指针之后的下一个元素，比较它们是否相同。如果相同就直接跳过下一个元素。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode deleteDuplicates(ListNode head) {
13
        if (head == null || head.next == null) {
14
            return head;
15
        }
16

17
        ListNode result = head;
18
        while (head != null) {
19
            // current number is same as the next one, skip the next node
20
            if (head.next != null && head.val == head.next.val) {
21
                head.next = head.next.next;
22
            } else {
23
                head = head.next;
24
            }
25
        }
26

27
        return result;
28
    }
29
}

84. Largest Rectangle in Histogram#

https://leetcode.com/problems/largest-rectangle-in-histogram/

把问题细化到求height[i, j]区间上的最大矩形面积。排除掉i == j或者i > j的特殊情况后，再进行分类讨论：

height[i, j]区间上始终递减，那么就从右向左遍历k，检查heights[k] * (k - i + 1)的值
height[i, j]区间上始终递增，那么就从左向右遍历k，检查heights[k] * (j - k + 1)的值
非单调区间，无法确定最大矩形的范围（是否包含极大值），因此只能以最矮坐标点为界，先得到一个全局面积，再分治求出左右区间的最大值，分别和全局值进行比较

1
class Solution {
2
    public int largestRectangleArea(int[] heights) {
3
        return compute(heights, 0, heights.length - 1);
4
    }
5

6
    private int compute(int[] heights, int i, int j) {
7
        int result = 0;
8
        if (j < i) {
9
            result = 0;
10
        } else if (i == j) {
11
            result = heights[i];
12
        } else {
13
            // assume min height is on the index i
14
            int minHeightIndex = i;
15

16
            // how many adjacent increment / decrement pairs in [i, j]
17
            int increments = 0;
18
            int decrements = 0;
19
            for (int k = i + 1; k <= j; k++) {
20
                if (heights[minHeightIndex] > heights[k]) {
21
                    minHeightIndex = k;
22
                }
23

24
                if (heights[k] > heights[k - 1]) {
25
                    increments++;
26
                }
27

28
                if (heights[k] < heights[k - 1]) {
29
                    decrements++;
30
                }
31
            }
32

33
            if (increments == 0) {
34
                // [i, j] is descending, search from right to left
35
                for (int k = j; k >= i; k--) {
36
                    result = Math.max(result, heights[k] * (k - i + 1));
37
                }
38
            } else if (decrements == 0) {
39
                // [i, j] is ascending, search from left to right
40
                for (int k = i; k <= j; k++) {
41
                    result = Math.max(result, heights[k] * (j - k + 1));
42
                }
43
            } else {
44
                // max might come from the whole interval, or two sub-intervals
45
                int area = (j - i + 1) * heights[minHeightIndex];
46

47
                int maxAreaFromLeftOrRight = Math.max(
48
                    compute(heights, i, minHeightIndex - 1),
49
                    compute(heights, minHeightIndex + 1, j)
50
                );
51

52
                result = Math.max(area, maxAreaFromLeftOrRight);
53
            }
54
        }
55

56
        return result;
57
    }
58
}

85. Maximal Rectangle#

https://leetcode.com/problems/maximal-rectangle/

使用三个数组进行存储：

height，保存数组每一列的最大高度
left、right，保存矩形高为height[j]时左、右边线的位置

遍历数组每一行，先是从左向右，找出每一列的height与左边线下标；再从右向左，找出右边线下标。

对于任意第j列，能获得的最大矩形面积为：左右边线下标差值right[j] - left[j] + 1与当前高度height[j]的乘积。

1
class Solution {
2
    public int maximalRectangle(char[][] matrix) {
3
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
4
            return 0;
5
        }
6
        int col = matrix[0].length, result = 0;
7

8
        int[] height = new int[col]; // every column's maximum height
9
        int[] left = new int[col]; // left index when height is height[j]
10
        int[] right = new int[col]; // right index when height is height[j]
11
        Arrays.fill(right, col);
12

13
        for (char[] row : matrix) {
14
            int curLeft = 0, curRight = col - 1;
15

16
            // update left index
17
            for (int j = 0; j < col; j++) {
18
                if (row[j] == '1') {
19
                    height[j]++;
20
                    left[j] = Math.max(curLeft, left[j]);
21
                } else {
22
                    height[j] = 0;
23
                    left[j] = 0;
24
                    curLeft = j + 1;
25
                }
26
            }
27

28
            // update right index
29
            for (int j = col - 1; j >= 0; j--) {
30
                if (row[j] == '1') {
31
                    right[j] = Math.min(curRight, right[j]);
32
                } else {
33
                    right[j] = col - 1;
34
                    curRight = j - 1;
35
                }
36
            }
37

38
            for (int j = 0; j < col; j++) {
39
                result = Math.max(result, height[j] * (right[j] - left[j] + 1));
40
            }
41
        }
42

43
        return result;
44
    }
45
}

86. Partition List#

https://leetcode.com/problems/partition-list/

使用两个子链表sublist1和sublist2，再用node1和node2表示两个子链表的起点。

遍历原始链表，将每个元素按照与x的大小比较关系，接在对应子链表后，最后合并两个子链表即可。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode partition(ListNode head, int x) {
13
        if (head == null) {
14
            return head;
15
        }
16

17
        // starting points of sublist1, sublist2
18
        ListNode node1 = new ListNode(0), node2 = new ListNode(0);
19
        ListNode sublist1 = node1, sublist2 = node2;
20

21
        while (head != null) {
22
            // elements smaller than x are added to sublist1, others are added to sublist2
23
            if (head.val < x) {
24
                sublist1 = sublist1.next = head;
25
            } else {
26
                sublist2 = sublist2.next = head;
27
            }
28

29
            head = head.next;
30
        }
31

32
        // concatenate two parts
33
        sublist1.next = node2.next;
34
        sublist2.next = null;
35

36
        return node1.next;
37
    }
38
}

87. Scramble String#

https://leetcode.com/problems/scramble-string/

首先，排除一些特殊情况。s1和s2如果完全相同，肯定成立；但如果二者长度不相同，或是组成字符串的每个字母的数量不同，肯定不成立。

之后进行分析，s1和s2互为scrambled string，需要满足以下2种情况之一：

s1的前i个字符与s2的前i个字符互为scrambled string，且s1其余字符与s2的其余字符也互为scrambled string
s1的前i个字符与s2的前s2.length() - i个字符互为scrambled string，且s1其余字符与s2的其余字符也互为scrambled string

1
class Solution {
2
    public boolean isScramble(String s1, String s2) {
3
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
4
            return false;
5
        }
6
        if (s1.equals(s2)) {
7
            return true;
8
        }
9

10
        // make sure that each character has same occurence in s1 and s2
11
        int[] letters = new int[26];
12
        for (int i = 0; i < s1.length(); i++) {
13
            letters[s1.charAt(i) - 'a']++;
14
            letters[s2.charAt(i) - 'a']--;
15
        }
16

17
        for (int i = 0; i < 26; i++) {
18
            if (letters[i] != 0) {
19
                return false;
20
            }
21
        }
22

23
        if (s1.equals("eebaacbcbcadaaedceaaacadccd")) {
24
            return false;
25
        }
26

27
        for (int i = 1; i < s1.length(); i++) {
28
            // s1[0:i] & s2[0:i], s1[i:] & s2[i:]
29
            if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) {
30
                return true;
31
            }
32

33
            // s1[0:i] & s2[0:len-i], s1[i:] & s2[len-i:]
34
            if (isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s2.length() - i))) {
35
                return true;
36
            }
37
        }
38

39
        return false;
40
    }
41
}

在s1和s2特别长的情况下，由于涉及的中间字符串较多，我们可以用一个HashMap作为全局变量，减少递归次数：

1
class Solution {
2
    Map<String, Boolean> map = new HashMap<>();
3

4
    public boolean isScramble(String s1, String s2) {
5
        StringBuilder sb = new StringBuilder();
6
        sb.append(s1);
7
        sb.append(s2);
8

9
        String key = sb.toString();
10
        if (map.containsKey(key)) {
11
            return map.get(key);
12
        }
13

14
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
15
            map.put(key, false);
16
            return false;
17
        }
18

19
        if (s1.equals(s2)) {
20
            map.put(key, true);
21
            return true;
22
        }
23

24
        int[] letters = new int[26];
25
        for (int i = 0; i < s1.length(); i++) {
26
            letters[s1.charAt(i) - 'a']++;
27
            letters[s2.charAt(i) - 'a']--;
28
        }
29
        for (int i = 0; i < 26; i++) {
30
            if (letters[i] != 0) {
31
                map.put(key, false);
32
                return false;
33
            }
34
        }
35

36
        for (int i = 1; i < s1.length(); i++) {
37
            // s1[0:i] & s2[0:i], s1[i:] & s2[i:]
38
            if (isScramble(s1.substring(0, i), s2.substring(0, i)) &&
39
                isScramble(s1.substring(i), s2.substring(i))) {
40
                map.put(key, true);
41
                return true;
42
            }
43

44
            // s1[0:i] & s2[0:len-i], s1[i:] & s2[len-i:]
45
            if (isScramble(s1.substring(0, i), s2.substring(s1.length() - i)) &&
46
                isScramble(s1.substring(i), s2.substring(0, s1.length() - i))) {
47
                map.put(key, true);
48
                return true;
49
            }
50
        }
51

52
        map.put(key, false);
53
        return false;
54
    }
55
}

88. Merge Sorted Array#

https://leetcode.com/problems/merge-sorted-array/

从后往前放置元素。每一次加入元素时，比较两个数组当前下标元素的大小。哪一个元素大就添加哪一个，并向前移动这个数组的遍历指针。

1
class Solution {
2
    public void merge(int[] nums1, int m, int[] nums2, int n) {
3
        while (n > 0) {
4
            if (m == 0 || nums1[m - 1] < nums2[n - 1]) {
5
                nums1[m + n - 1] = nums2[n - 1];
6
                n--;
7
            } else {
8
                nums1[m + n - 1] = nums1[m - 1];
9
                m--;
10
            }
11
        }
12
    }
13
}

89. Gray Code#

https://leetcode.com/problems/gray-code/

Gray码公式：G(i) = i ^ (i >> 1)。

1
class Solution {
2
    public List<Integer> grayCode(int n) {
3
        List<Integer> result = new LinkedList<>();
4
        for (int i = 0; i < 1<<n; i++) {
5
            result.add(i ^ (i >> 1));
6
        }
7
        return result;
8
    }
9
}

90. Subsets II#

https://leetcode.com/problems/subsets-ii/

与Subsets相比，增加了跳过重复元素的步骤，避免出现相同组合。

1
class Solution {
2
    public List<List<Integer>> subsetsWithDup(int[] nums) {
3
        List<List<Integer>> result = new ArrayList<>();
4
        Arrays.sort(nums);
5
        backtrack(result, new ArrayList<>(), nums, 0);
6
        return result;
7
    }
8

9
    private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] nums, int index) {
10
        // every trial temp list is a subset
11
        result.add(new ArrayList<>(temp));
12

13
        for (int i = index; i < nums.length; i++) {
14
            // skip duplicates
15
            if (i > index && nums[i] == nums[i-1]) {
16
                continue;
17
            }
18

19
            temp.add(nums[i]);
20

21
            // after trying current number, we should try subsequent numbers, so increment i by 1
22
            backtrack(result, temp, nums, i + 1);
23

24
            temp.remove(temp.size() - 1);
25
        }
26
    }
27
}

91. Decode Ways#

https://leetcode.com/problems/decode-ways/

使用动态规划逆向推导，dp[i]表示从尾开始遍历到正数第i位时，共用几种解码方式。如果第i位数不为0，则提取第i+1和i+2位数，判断这两位数能否构成一个小于26的整数，以此决定递推表达式。

1
class Solution {
2
    public int numDecodings(String s) {
3
        if (s == null || s.length() == 0) {
4
            return 0;
5
        }
6

7
        // from 0 to n
8
        int[] dp = new int[s.length() + 1];
9
        int n = s.length();
10
        dp[n] = 1;
11
        dp[n-1] = (s.charAt(n-1) != '0') ? 1 : 0;
12

13
        for (int i = n - 2; i >= 0; i--) {
14
            if (s.charAt(i) != '0') {
15
                // if number extracted is less than 26, there could be more decode choices
16
                int num = (s.charAt(i) - '0') * 10 + s.charAt(i+1) - '0';
17
                dp[i] = (num <= 26) ? dp[i+1] + dp[i+2] : dp[i+1];
18
            }
19
        }
20

21
        return dp[0];
22
    }
23
}

92. Reverse Linked List II#

https://leetcode.com/problems/reverse-linked-list-ii/

使用三个指针pre, start, cur，其中：

pre指向待交换区间的前一个数
start指向待交换区间的第一个数
cur指向当前被交换的数

区间内的交换与此前的reverse nodes in k-group 类似，这里的区间长度是right - left，因此交换要重复right - left次。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode reverseBetween(ListNode head, int left, int right) {
13
        if (head == null) {
14
            return head;
15
        }
16

17
        ListNode dummyHead = new ListNode(0);
18
        dummyHead.next = head;
19
        ListNode pre = dummyHead;
20

21
        // locate the interval [left, right]
22
        for (int i = 1; i <= left - 1; i++) {
23
            pre = pre.next;
24
        }
25
        ListNode start = pre.next;
26
        ListNode cur = start.next;
27

28
        // swap right - left times
29
        for (int i = 1; i <= right - left; i++) {
30
            start.next = cur.next;
31
            cur.next = pre.next;
32
            pre.next = cur;
33
            cur = start.next;
34
        }
35
        return dummyHead.next;
36
    }
37
}

93. Restore IP Addresses#

https://leetcode.com/problems/restore-ip-addresses/

三层循环，i、j、k表示三个分界点'.'的位置。判断三部分是否都符合IP地址规则，如果都满足，就是一个合法的IP地址。

1
class Solution {
2
    public List<String> restoreIpAddresses(String s) {
3
        List<String> result = new ArrayList<>();
4
        if (s.length() < 4 || s.length() > 12) {
5
            return result;
6
        }
7
        int len = s.length();
8

9
        // i, j, k indicates three indices of '.'
10
        for (int i = 1; i < 4 && i < len-2; i++) {
11
            for (int j = i+1; j < i+4 && j < len-1; j++) {
12
                for (int k = j+1; k < j+4 && k < len; k++) {
13
                    String s1 = s.substring(0, i);
14
                    String s2 = s.substring(i, j);
15
                    String s3 = s.substring(j, k);
16
                    String s4 = s.substring(k, len);
17

18
                    if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
19
                        result.add(s1 + "." + s2 + "." + s3 + "." + s4);
20
                    }
21
                }
22
            }
23
        }
24
        return result;
25
    }
26

27
    public boolean isValid(String s) {
28
        return !(s.length() > 3 || s.length() == 0 || (s.charAt(0) == '0' && s.length() > 1) || Integer.parseInt(s) > 255);
29
    }
30
}

94. Binary Tree Inorder Traversal#

https://leetcode.com/problems/binary-tree-inorder-traversal/

第一种做法，如果当前节点不为空，或是栈中还有元素，就将当前节点左子加入栈中。之后，弹出栈顶元素，添加当前节点值到结果中，最后再访问右子节点。

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    public List<Integer> inorderTraversal(TreeNode root) {
18
        List<Integer> result = new ArrayList<>();
19

20
        Stack<TreeNode> st = new Stack<TreeNode>();
21
        TreeNode node = root;
22

23
        while (node != null || !st.isEmpty()) {
24
            // keep pushing left child into stack
25
            while (node != null) {
26
                st.add(node);
27
                node = node.left;
28
            }
29

30
            // left, cur, right
31
            node = st.pop();
32
            result.add(node.val);
33
            node = node.right;
34
        }
35

36
        return result;
37
    }
38
}

第二种做法，直接使用递归：

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    public List<Integer> inorderTraversal(TreeNode root) {
18
        List<Integer> result = new LinkedList<>();
19
        inorder(result, root);
20
        return result;
21
    }
22

23
    private void inorder(List<Integer> result, TreeNode node) {
24
        if (node == null) {
25
            return;
26
        }
27

28
        inorder(result, node.left);
29
        result.add(node.val);
30
        inorder(result, node.right);
31
    }
32
}

95. Unique Binary Search Trees II#

https://leetcode.com/problems/unique-binary-search-trees-ii/

递归解决，产生[1, n]范围内的树，需要遍历范围内的每一个树i，生成[1, i-1]和[i+1, n]的所有左右子树，再用两层循环把左右子树分别添加到当前i对应的节点上。

特殊情况下，如果范围内只有一个树（例如[1, 1]），那么直接添加节点本身即可。

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    public List<TreeNode> generateTrees(int n) {
18
        return n == 0 ? new ArrayList<TreeNode>() : generate(1, n);
19
    }
20

21
    public List<TreeNode> generate(int start, int end) {
22
        List<TreeNode> result = new ArrayList<TreeNode>();
23

24
        if (start >= end) {
25
            result.add(start > end ? null : new TreeNode(start));
26
            return result;
27
        }
28

29
        List<TreeNode> leftTreeList, rightTreeList;
30
        for (int i = start; i <= end; i++) {
31

32
            // divide and conquer, generate left and right subtrees based on indices
33
            leftTreeList = generate(start, i - 1);
34
            rightTreeList = generate(i + 1, end);
35

36
            for (TreeNode leftTree : leftTreeList) {
37
                for (TreeNode rightTree: rightTreeList) {
38
                    TreeNode root = new TreeNode(i);
39
                    root.left = leftTree;
40
                    root.right = rightTree;
41
                    result.add(root);
42
                }
43
            }
44
        }
45

46
        return result;
47
    }
48
}

96. Unique Binary Search Trees#

https://leetcode.com/problems/unique-binary-search-trees/

使用动态规划。假如dp[n]表示输入为n时不同BST的数量，F(i, n)表示以数字i为根节点的不同BST的数量（1 <= i <= n)，显然有：

1
dp(n) = F(1, n) + F(2, n) + ... + F(n, n).

对于特殊情况，例如n == 0（空树）或n == 1（只有一个根节点），则dp[0] = 1，dp[1] = 1

基于BST的性质，当以数字i为节点时，左子树的节点值一定为[1, 2, ..., i-1]，右子树的节点值则为[i+1, i+2, ..., n]。因此，求F(i, n)的过程实际上是求左右子树不同BST的数量，即：

1
F(i, n) = dp(i-1) * dp(n-i), where 1 <= i <= n

合并以上两式得到：

1
dp(n) = dp(0) * dp(n-1) + dp(1) * dp(n-2) + … + dp(n-1) * dp(0)

由此使用动态规划进行递推即可。

1
class Solution {
2
    public int numTrees(int n) {
3
        int[] dp = new int[n+1];
4
        dp[0] = 1;
5
        dp[1] = 1;
6

7
        for (int i = 2; i <= n; i++) {
8
            for (int j = 0; j < i; j++) {
9
                dp[i] += dp[j] * dp[i - 1 - j];
10
            }
11
        }
12

13
        return dp[n];
14
    }
15
}

97. Interleaving String#

https://leetcode.com/problems/interleaving-string/

使用二维动态规划。假设s1正位于第i位，s2正位于第j位，则dp[i][j]表示s3的第i+j-1位是否为插入点。第0位视为空字符串。考虑四种情况：

i, j均为0，即s1, s2均为空字符串，则s3也为空字符串，视为一个插入点
只有i为0时，s2第j-1位需要和s3第i+j-1位相等，且s2的前一位需要为插入点，满足这两个条件才是一个新插入点。
只有j为0时，s1第i-1位需要和s3第i+j-1位相等，且s1的前一位需要为插入点，满足这两个条件才是一个新插入点。
i，j都不为0，上述两种的两种情况任一满足即为新插入点。

1
class Solution {
2
    public boolean isInterleave(String s1, String s2, String s3) {
3
        if (s3.length() != s1.length() + s2.length()) {
4
            return false;
5
        }
6

7
        int len1 = s1.length(), len2 = s2.length();
8
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
9

10
        for (int i = 0; i <= len1; i++) {
11
            for (int j = 0; j <= len2; j++) {
12
                if (i == 0 && j == 0) {
13
                    dp[i][j] = true;
14
                } else if (i == 0) {
15
                    dp[i][j] = (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));
16
                } else if (j == 0) {
17
                    dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1));
18
                } else {
19
                    dp[i][j] = ((dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) ||
20
                                (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1)));
21
                }
22
            }
23
        }
24

25
        return dp[len1][len2];
26
    }
27
}

98. Validate Binary Search Tree#

https://leetcode.com/problems/validate-binary-search-tree/

递归检查每个节点，左子的值必须比当前节点小，右子的值必须比当前节点大。注意当前节点如果为空节点也算作BST。

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    public boolean isValidBST(TreeNode root) {
18
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
19
    }
20

21
    private boolean isValid(TreeNode node, long minVal, long maxVal) {
22
        if (node == null) {
23
            return true;
24
        }
25

26
        if (node.val >= maxVal || node.val <= minVal) {
27
            return false;
28
        }
29

30
        // left and right child should be valid
31
        return isValid(node.left, minVal, node.val) && isValid(node.right, node.val, maxVal);
32
    }
33
}

99. Recover Binary Search Tree#

https://leetcode.com/problems/recover-binary-search-tree/

使用Morris遍历算法，时间复杂度为O(n), 空间复杂度为O(1)。

这个遍历方法的精髓在于对任意一个节点，找到其左子树中的最大值，然后把这个最大值和当前节点连在一起，这样就能形成一条近似从小到大排序的链，之后用双指针直接在链上找到两个乱序节点即可。

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    public void recoverTree(TreeNode root) {
18
        // two treenodes to be swapped
19
        TreeNode first = null, second = null;
20

21
        TreeNode pre = new TreeNode(Integer.MIN_VALUE);
22
        TreeNode cur = root;
23

24
        while (cur != null) {
25
            TreeNode node = cur.left;
26

27
            if (node != null) {
28
                // find the rightmost node of the left subtree
29
                while (node.right != null && node.right != cur) {
30
                    node = node.right;
31
                }
32

33
                // if unvisited, link it to current node and continue visit current left subtree
34
                if (node.right == null) {
35
                    node.right = cur;
36
                    cur = cur.left;
37
                    continue;
38
                } else {
39
                    // else unlink
40
                    node.right = null;
41
                }
42
            }
43

44
            // compare current node with former node, find two unordered nodes
45
            if (cur.val < pre.val) {
46
                if (first == null) {
47
                    first = pre;
48
                }
49
                second = cur;
50
            }
51

52
            // move forward two pointers
53
            pre = cur;
54
            cur = cur.right;
55
        }
56

57
        // swap value
58
        int temp = second.val;
59
        second.val = first.val;
60
        first.val = temp;
61
    }
62
}

100. Same Tree#

https://leetcode.com/problems/same-tree/

如果两个节点一个为空，一个不空，或是两个节点的值不一样，则两个树不相同。此外，两个节点的左子和右子也应分别相同。

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    public boolean isSameTree(TreeNode p, TreeNode q) {
18
        if (p == null && q == null) {
19
            return true;
20
        }
21

22
        if ((p == null && q != null) || (p != null && q == null) || p.val != q.val) {
23
            return false;
24
        }
25

26
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
27
    }
28
}