leetcode 笔记

technology
刷题

这是我早就想干的一件事，leetcode 刷了很多，但是没有系统记录，就记录在这里吧。

  • 按顺序记录；
  • 隐去如 Node 之类的内部类信息；

2. Add Two Sum

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

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode sentinel = new ListNode(0);
    ListNode d = sentinel;
    ListNode c1 = l1;
    ListNode c2 = l2;
    int sum = 0;
    while (c1 != null || c2 != null) {
        sum /= 10;
        if (c1 != null) {
            sum += c1.val;
            c1 = c1.next;
        }
        if (c2 != null) {
            sum += c2.val;
            c2 = c2.next;
        }
        d.next = new ListNode(sum % 10);
        d = d.next;
    }
    if (sum / 10 == 1) {
        d.next = new ListNode(1);
    }
    return sentinel.next;
}

Tag:

Linked List

Thinking:

这道题好在已经给出了链表的逆序，按位相加即可，把 sum 的个位保留，十位进位，注意最后如果十位还有数字，最多仅为 1 。

3. Longest Substring Without Repeating Characters

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

1
2
3
4
5
6
7
8
9
10
11
12
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    int res = 0;
    while (right < s.length()) {
        // 移入字符
        Character c = s.charAt(right);
        right++;
        // 更新滑窗
        window.put(c, window.getOrDefault(c, 0) + 1);
        // 收缩
        while (window.get(c).compareTo(1) > 0) {
            Character d = s.charAt(left);
            left++;
            // 更新滑窗
            window.put(d, window.get(d) - 1);
        }
        res = Math.max(res, right - left);
    }
    return res;
}

Tag:

Two Pointers Sliding Window Hash Table String

Thinking:

无重复最长子串问题，用滑窗比较好理解点。

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

1
2
3
4
5
6
7
8
9
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public double findMedianSortedArrays(int[] A, int[] B) {
    if (A.length > B.length) return findMedianSortedArrays(B, A);
    int x = A.length;
    int y = B.length;
    int low = 0;
    int high = x;
    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (x + y + 1) / 2 - partitionX;
        int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : A[partitionX - 1];
        int minRightX = (partitionX == x) ? Integer.MAX_VALUE : A[partitionX];
        int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : B[partitionY - 1];
        int minRightY = (partitionY == y) ? Integer.MAX_VALUE : B[partitionY];
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 == 0) {
                return (double)(Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }
    return 0.0;
}

Tag:

Binary Search Divide and Conquer Array

Thinking:

求两个数组的中位数。这里 i 是 partitionX，j 是 partitionY ，我们要做的就是找到 B[j-1] <= A[i] && A[i-1] <= B[j] ，保证左边最大值小于右边最小值即可。

这里保证 A 长度小于 B 长度，是为了保证 j 不为负数。

1
2
3
      left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

1
2
3
4
5
6
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private int begin, maxLen;

public String longestPalindrome(String s) {
    int length = s.length();
    if (length < 2) return s;
    for (int i = 0; i < length; ++i) {
        extendPalindrome(s, i, i);
        extendPalindrome(s, i, i + 1);
    }
    return s.substring(begin, begin + maxLen);
}

private void extendPalindrome(String s, int i, int j) {
    while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
        i--;
        j++;
    }
    if (maxLen < j - i - 1) {
        begin = i + 1;
        maxLen = j - i - 1;
    }
}

Tag:

String

Thinking:

想法有点粗暴，extendPalindrome 方法的作用是找中心以 i j 为中心向两边扩展，而 i+1 是为了保证在数组长度为偶数时的适配性。

8. String to Integer (atoi)

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

  • Only the space character ' ' is considered as whitespace character.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Input: "42"
Output: 42

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int myAtoi(String str) {
    char[] chars = str.toCharArray();
    if (chars.length == 0) return 0;
    int sign = 1, base = 0, i = 0;
    while (i < chars.length && chars[i] == ' ') i++;
    if (i < chars.length && (chars[i] == '-' || chars[i] == '+')) {
        sign = 1 - (chars[i++] == '-' ? 1 : 0) * 2;
    }
    while (i < chars.length && chars[i] >= '0' && chars[i] <= '9') {
        if (base > Integer.MAX_VALUE / 10 || (base == Integer.MAX_VALUE / 10 && chars[i] - '0' > 7)) {
            if (sign > 0) return Integer.MAX_VALUE;
            else return Integer.MIN_VALUE;
        }
        base = base * 10 + (chars[i++] - '0');
    }
    return sign * base;
}

Tag:

Math String

Thinking:

小模拟，把字符串变成数字，可以用最简单的 if 嵌套来做，我们知道 32 位的 int 是 2147483647 ，随意其实就是一个字符转数字的问题。注意数组越界即可。

10. Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

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

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

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public boolean isMatch(String s, String p) {
    if (s == null || p == null) return false;
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    dp[0][0] = true;
    for (int i = 0; i < p.length(); ++i) {
        if (p.charAt(i) == '*' && dp[0][i - 1]) {
            dp[0][i + 1] = true;
        }
    }
    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < p.length(); j++) {
            if (p.charAt(j) == '.') {
                dp[i + 1][j + 1] = dp[i][j];
            }
            if (p.charAt(j) == s.charAt(i)) {
                dp[i + 1][j + 1] = dp[i][j];
            }
            if (p.charAt(j) == '*') {
                if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {
                    dp[i + 1][j + 1] = dp[i + 1][j - 1];
                } else {
                    dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1]);
                }
            }
        }
    }
    return dp[s.length()][p.length()];
}

Tag:

String Dynamic Programming

Thinking:

正则表达式的处理，用一个二维数组处理一下，leetcode 上的解答非常好，直接抄了。

1
2
3
4
5
6
7
8
9
1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*': 
   here are two sub conditions:
               1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
               2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
                              dp[i][j] = dp[i-1][j]   //in this case, a* counts as multiple a 
                           or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
                           or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty

11. Container With Most Water

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

1
2
3
4
Input: [1,8,6,2,5,4,8,3,7]
Output: 49

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Solution:

1
2
3
4
5
6
7
8
9
10
public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;
    while (left < right) {
        maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
        if (height[left] < height[right]) left++;
        else right--;
    }
    return maxArea;
}

Tag:

Array Two Pointer

Thinking:

从题意知数组内容为每一条线的长度，所以设置两个指针左右逼近，逼近的一方为短的一方，贪心即可。

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

PS: The solution set must not contain duplicate triplets.

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();

    for (int i = 0; i + 2 < nums.length; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int j = i + 1, k = nums.length - 1;
        int target = -nums[i];
        while (j < k) {
            if (nums[j] + nums[k] == target) {
                result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                j++;
                k--;
                while (j < k && nums[j] == nums[j - 1]) j++;
                while (j < k && nums[k] == nums[k + 1]) k--;
            } else if (nums[j] + nums[k] > target) {
                k--;
            } else {
                j++;
            }
        }
    }

    return result;
}

Tag:

Array Two Pointer

Thinking:

求三数和的数组，且结果不重复。首先排序，可以先枚举第一个元素，然后剩下两个元素双指针枚举数组。

19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

PS: Given n will always be valid.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    for (int i = 0; i < n; ++i) {
        first = first.next;
    }
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

Tag:

Linked List Two Pointers

Thinking:

删除链表中倒数第n个节点，两个指针一起跑，O(n)即可完成。

22. Generate Parentheses

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

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

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backTrack(result, "", 0, 0, n);
    return result;
}

public void backTrack(List<String> list, String str, int open, int close, int max) {
    if (str.length() == max * 2) {
        list.add(str);
        return;
    }
    if (open < max) {
        backTrack(list, str + "(", open + 1, close, max);
    }
    if (open > close) {
        backTrack(list, str + ")", open, close + 1, max);
    }
}

Tag:

String Backtracking

Thinking:

既然是枚举就肯定躲不开回溯，有左括号的同时补上右括号。我们知道如果输入长度 n ，那么实际输出应该是 2n ，记得条件约束，加左括号是 ( < n 时，加右括号是 ( > ) 时。

23. Merge k Sorted Lists

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

1
2
3
4
5
6
7
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public ListNode mergeKLists(ListNode[] lists) {
    return partition(lists, 0, lists.length - 1);
}

private ListNode partition(ListNode[] lists, int start, int end) {
    if (start == end) return lists[start];
    if (start < end) {
        int mid = start + (end - start) / 2;
        ListNode l1 = partition(lists, start, mid);
        ListNode l2 = partition(lists, mid + 1, end);
        return merge(l1, l2);
    }
    return null;
}

private ListNode merge(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = merge(l1.next, l2);
        return l1;
    } else {
        l2.next = merge(l1, l2.next);
        return l2;
    }
}

Tag:

Linked Lisk Divide and Conquer Heap

Thinking:

要求是把多个链表合并成一个，可以容易想到归并，时间复杂度是 nlogk ，其中 k 是链表数，n 是节点数。

29. Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

1
2
3
4
5
6
7
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.
  • Both dividend and divisor will be 32-bit signed integers.
  • The divisor will never be 0.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int divide2(int dividend, int divisor) {
    if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
    long dvd = Math.abs((long) dividend), dvs = Math.abs((long) divisor);
    int ans = 0;
    int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
    while (dvd >= dvs) {
        long temp = dvs, m = 1;
        while (temp << 1 <= dvd) {
            temp <<= 1;
            m <<= 1;
        }
        dvd -= temp;
        ans += m;
    }
    return sign == 1 ? ans : -ans;
}

Tag:

Math Binary Search

Thinking:

手动实现一个除法，我们知道任何一个正整数都可以用 2 的幂次方表示，可以以此进行递归。

比如被除数是 15 ，除数是 3 ，那么首先是 15 - 3 ，接着是 15 - 6 ，然后 15 - 12 ，到这里都符合 3 n^k ，这里 n^k = 4 ，m 累计为 4 ，接着被除数变成 15 - 3 4 = 3 ，m 累计到 5 ，被除数为 0 < 3 退出。

33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

1
2
3
4
5
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int num = nums[mid];
        if ((nums[mid] < nums[0]) != (target < nums[0])) {
            num = target < nums[0] ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        }
        if (num < target) lo = mid + 1;
        else if (num > target) hi = mid - 1;
        else return mid;
    }
    return -1;
}

Tag:

Array Binary Search

Thinking:

旋转数组获得指定元素下标，老二分了。

我们可以想象一下，假设有这样一个数组 [12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

我们想要找 14 ，那么这个数组可以这样设置 [12, 13, 14, 15, 16, 17, 18, 19, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

我们想要找 7 ，那么这个数组就这样设置 [-inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

现在它就符合二分了，关键在于判断 nums[mid] 与 target 是否在同一侧，如果在同一侧，我们的 nums[mid] 自然就是有效的；如果不在同一侧，判断 target 的位置，target 在数组后半部分 nums[mid] 用 -inf ，反之用 inf 代替。

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

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

1
2
3
4
5
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] searchRange(int[] nums, int target) {
    int start = firstGreaterEqual(nums, target);
    if (start == nums.length || nums[start] != target) {
        return new int[]{-1, -1};
    }
    return new int[]{start, firstGreaterEqual(nums, target + 1) - 1};
}

private int firstGreaterEqual(int[] nums, int target) {
    int low = 0, high = nums.length;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

Tag:

Array Binary Search

Thinking:

不是单独找一个数字下标，而是找数字下标的区间，可以用二分做，两次二分，第一次找目标位置，第二次找下一个数字的前一位。

36. Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

PS:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isValidSudoku(char[][] board) {
    Set seen = new HashSet<>();
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] != '.') {
                String b = "(" + board[i][j] + ")";
                if (!seen.add(i + b) 
                        || !seen.add(b + j) 
                        || !seen.add(i / 3 + b + j / 3)) {
                    return false;
                }
            }
        }
    }
    return true;
}

Tag:

Hash Table

Thinking:

数独是否成立的判断，根据文意，每一个用例都是 9x9 ，行、列、块均不重复，简单用 O(n^3) 模拟一下。这里用 (x) 作为某一个数，前面放行数 n ，后面放列数 m ，即 n(x)m ，保证不重复即满足。

41. First Missing Positive

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

1
2
3
4
5
6
7
8
Input: [1,2,0]
Output: 3

Input: [3,4,-1,1]
Output: 2

Input: [7,8,9,11,12]
Output: 1

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
  public int firstMissingPositive(int[] nums) {
    int n = nums.length;

    // 基本情况
    int contains = 0;
    for (int i = 0; i < n; i++)
      if (nums[i] == 1) {
        contains++;
        break;
      }

    if (contains == 0)
      return 1;

    // nums = [1]
    if (n == 1)
      return 2;

    // 用 1 替换负数，0，
    // 和大于 n 的数
    // 在转换以后，nums 只会包含
    // 正数
    for (int i = 0; i < n; i++)
      if ((nums[i] <= 0) || (nums[i] > n))
        nums[i] = 1;

    // 使用索引和数字符号作为检查器
    // 例如，如果 nums[1] 是负数表示在数组中出现了数字 `1`
    // 如果 nums[2] 是正数 表示数字 2 没有出现
    for (int i = 0; i < n; i++) {
      int a = Math.abs(nums[i]);
      // 如果发现了一个数字 a - 改变第 a 个元素的符号
      // 注意重复元素只需操作一次
      if (a == n)
        nums[0] = - Math.abs(nums[0]);
      else
        nums[a] = - Math.abs(nums[a]);
    }

    // 现在第一个正数的下标
    // 就是第一个缺失的数
    for (int i = 1; i < n; i++) {
      if (nums[i] > 0)
        return i;
    }

    if (nums[0] > 0)
      return n;

    return n + 1;
  }
}

Tag:

Array

Thinking:

找到数组中第一个缺失的正数。把负数和大于范围的数字都赋值1，nums[0] 表示的是第 n 个数，遍历第一个正数即缺失的数。

42. Trapping Rain Water

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

1
2
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int trap(int[] height) {
    int a = 0;
    int b = height.length - 1;
    int max = 0;
    int leftMax = 0;
    int rightMax = 0;
    while (a <= b) {
        leftMax = Math.max(leftMax, height[a]);
        rightMax = Math.max(rightMax, height[b]);
        if (leftMax < rightMax) {
            max += (leftMax - height[a]);
            a++;
        } else {
            max += (rightMax - height[b]);
            b--;
        }
    }
    return max;
}

Tag:

Array Two Pointers Stack

Thinking:

给一个数组，每一个值表示坐标上的高度，算出当前数组最多的储水总量。保持左右两个指针，同时记录左右的最高高度，两边低的部分向中心移动，同时计算漏出水的体积（底为 1 ），直到两个指针相遇，即填充了整个容器。

44. Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

1
2
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Input:
s = "acdcb"
p = "a*c?b"
Output: false

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public boolean isMatch(String str, String pattern) {
    int s = 0, p = 0, match = 0, starIdx = -1;
    while (s < str.length()){
      	// advancing both pointers
        if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
            s++;
            p++;
        }
        // * found, only advancing pattern pointer
        else if (p < pattern.length() && pattern.charAt(p) == '*'){
            starIdx = p;
            match = s;
            p++;
        }
        // last pattern pointer was *, advancing string pointer
        else if (starIdx != -1){
            p = starIdx + 1;
            match++;
            s = match;
        }
        //current pattern pointer is not star, last patter pointer was not *
        //characters do not match
        else return false;
    }
    //check for remaining characters in pattern
    while (p < pattern.length() && pattern.charAt(p) == '*')
      	p++;
    return p == pattern.length();
}

Tag:

String Dynamic Programming Backtracking Greedy

Thinking:

将 p 与 s 将两个串扫一遍，如果 * 则 p 动，此时如果 s 和 p 后面的值不同则 s 动，将两个串移到最后，如果 p 走完说明匹配上了。

46. Permutations

Given a collection of distinct integers, return all possible permutations.

1
2
3
4
5
6
7
8
9
10
Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        // Arrays.sort(nums);
        backtrack(list, new ArrayList<>(), nums);
        return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {
        if (tempList.size() == nums.length) {
            list.add(new ArrayList<>(tempList));
        } else {
            for (int i = 0; i < nums.length; ++i) {
                if (tempList.contains(nums[i])) {
                    // element already exists, skip
                    continue;
                }
                tempList.add(nums[i]);
                backtrack(list, tempList, nums);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

Tag:

Backtracking

Thinking:

算一个数组的全排列，这个是递归的套路题，递归函数需要：return 内容、当前排列、排列元素。然后去重、增加当前排列、递归、回溯。

48. Rotate Image

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

Rotate the image by 90 degrees (clockwise).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void rotate(int[][] matrix) {
    // reverse matrix
    int begin = 0, end = matrix.length - 1;
    while (begin < end) {
        int[] temp = matrix[begin];
        matrix[begin] = matrix[end];
        matrix[end] = temp;
        begin++;
        end--;
    }
    // swap i j
    for (int i = 0; i < matrix.length; ++i) {
        for (int j = i + 1; j < matrix[i].length; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

Tag:

Array

Thinking:

将一个 n*n 的矩阵顺时针旋转 90° ，有一种通用的解法：

1
2
3
4
> 1 2 3     7 8 9     7 4 1
> 4 5 6  => 4 5 6  => 8 5 2
> 7 8 9     1 2 3     9 6 3
>

首先把每一行的顺序逆序排列，再将每一个元素的 i j 交换即可。

49. Group Anagrams

Given an array of strings, group anagrams together.

1
2
3
4
5
6
7
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
  • All inputs will be in lowercase.
  • The order of your output does not matter.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<List<String>> groupAnagrams(String[] strs) {
    if (strs == null || strs.length == 0) return new ArrayList<>();
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        char[] chars = new char[26];
        for (char c : str.toCharArray()) {
            chars[c - 'a']++;
        }
        String keyStr = Arrays.toString(chars);
        if (!map.containsKey(keyStr)) {
            map.put(keyStr, new ArrayList<>());
        }
        map.get(keyStr).add(str);
    }
    return new ArrayList<>(map.values());
}

Tag:

Hash Table String

Thinking:

把数组中排列的字符串分类输出。将每一个字符串用 char[26] 保存每一组的 key ，用 map 保存每一组，最后用 map.values 输出所有组。

50. Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (x^n).

1
2
3
4
5
6
7
8
9
Input: 2.00000, 10
Output: 1024.00000

Input: 2.10000, 3
Output: 9.26100

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−2^31, 2^31 − 1]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public double myPow(double x, int n) {
    long N = n;
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    double ans = 1;
    double currentProduct = x;
    // 快速幂
    // /2 = 向右平移
    for (long i = N; i > 0; i /= 2) {
        if ((i & 1) == 1) {
            ans *= currentProduct;
        }
        currentProduct *= currentProduct;
    }
    return ans;
}

Tag:

Math Binary Search

Thinking:

题面很简单，计算 x 的 n 次幂。
如果 n < 0 ，则将 x 变为 1/x ，同时 n 变为 -n ，简化问题。
快速幂，把每一个数字想象成 2 进制，只有 1 的位置需要计算。

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
    int sum = 0;
    int ans = nums[0];
    for (int num : nums) {
        if (sum > 0) {
            sum += num;
        } else {
            sum = num;
        }
        ans = Math.max(ans, sum);
    }
    return ans;
}

Tag:

Array Divide and Conquer Dynamic Programming

Thinking:

求最大子序和，用 dp 反而简单点，用一个 ans 和一个 temp sum 两个值判断，如果 temp sum > 0 就累加当前值，否则 temp sum 重新从当前位置开始取值，同时 ans 一直取 temp sum 与 ans 中的较大值。

54. Spiral Matrix

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> ans = new ArrayList<>();
    if (matrix.length == 0) return ans;
    int R = matrix.length, C = matrix[0].length;
    boolean[][] seen = new boolean[R][C];
    // 右、下、左、上 顺时针
    int[] dr = {0, 1, 0, -1};
    int[] dc = {1, 0, -1, 0};
    int r = 0, c = 0, di = 0;
    for (int i = 0; i < R * C; ++i) {
        ans.add(matrix[r][c]);
        seen[r][c] = true;
        int cr = r + dr[di];
        int cc = c + dc[di];
        if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]) {
            r = cr;
            c = cc;
        } else {
            di = (di + 1) % 4;
            r += dr[di];
            c += dc[di];
        }
    }
    return ans;
}

Tag:

Array

Thinking:

输出螺旋矩阵，模拟过程即可。假设有 R 行 C 列，当前位置为 (r, c) ，前进方向是 di ，下一个位置是 (cr, cc) ，如果该没位置没有被访问过则进入，否则前进防线顺时针旋转 90 度。

55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

1
2
3
4
5
6
7
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
  • 1 <= nums.length <= 3 * 10^4
  • 0 <= nums[i][j] <= 10^5

Solution:

1
2
3
4
5
6
7
8
public boolean canJump(int[] nums) {
    int k = 0;
    for (int i = 0; i < nums.length; ++i) {
        if (k < i) return false;
        k = Math.max(k, nums[i] + i);
    }
    return true;
}

Tag:

Array Greedy

Thinking:

从数组的第一个位置起跳，每个数字代表可以跳跃最远的距离，判断是否可以到达数组的最后。
如果某一个位置是 3 ，那么后面 3 个位置都能作为起跳点，可以尝试从每一个起跳点，保存可以跳到最远的地方。能唱过当前下标即成功。

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

1
2
3
4
5
6
7
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[][] merge(int[][] intervals) {
    // 起始位置排序
    Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
    // 遍历区间
    int[][] res = new int[intervals.length][2];
    int idx = -1;
    for (int[] interval : intervals) {
        // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
        // 则不合并，直接将当前区间加入结果数组。
        if (idx == -1 || res[idx][1] < interval[0]) {
            res[++idx] = interval;
        } else {
            res[idx][1] = Math.max(res[idx][1], interval[1]);
        }
    }
    // 消除多余的长度
    return Arrays.copyOf(res, idx + 1);
}

Tag:

Array Sort

Thinking:

合并数组的重合部分，重合只有三种情况，第一种互不相交，第二种部分相交，第三种完全包含。第一种情况时只需要把这一部分的 interval 加入，另外两种情况处理方法完全相同。

62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

1
2
3
4
5
6
7
8
9
10
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Input: m = 7, n = 3
Output: 28
  • 1 <= m, n <= 100
  • It’s guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    // 第一行第一列
    for (int i = 0; i < m; ++i) {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; ++i) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

Tag:

Array Dynamic Programming

Thinking:

在 m*n 的网格里，从左上角到右下角所有的路径。有两种解法，因为固定左上到右下所以向右和向下的次数是固定的，因此可以得到公式，并不通用；通过动态规划可以知道，为了达到位置 (i,j) 方式有从 (i-1,j) 和 (i,j-1) 两种，即 dp(i,j)=dp(i-1,j)+dp(i,j-1) 。

66. Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

1
2
3
4
5
6
7
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution:

1
2
3
4
5
6
7
8
9
10
public int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >= 0; --i) {
        digits[i]++;
        digits[i] %= 10;
        if (digits[i] != 0) return digits;
    }
    digits = new int[digits.length + 1];
    digits[0] = 1;
    return digits;
}

Tag:

Array

Thinking:

字面意思的数组数字加一，唯一需要注意的就是可能数组长度要变。

69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

1
2
3
4
5
6
7
Input: 4
Output: 2

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int mySqrt(int x) {
    if (x == 0) return 0;
    long left = 0;
    long right = x / 2 + 1;
    while (left < right) {
        long mid = (left + right + 1) >>> 1;
        long square = mid * mid;
        if (square > x) {
            right = mid - 1;
        } else {
            left = mid;
        }
    }
    return (int)left;
}

Tag:

Math Binary Search

Thinking:

给 x 开根号，取最近值的下限，用二分即可，这里的二分是 jdk 的二分可以背下来， >>> 不用担心 left + right 数值越界。

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

1
2
3
4
5
6
7
8
9
10
11
12
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Solution:

1
2
3
4
5
6
7
8
9
10
public int climbStairs(int n) {
    if (n <= 1) return 1;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

Tag:

Dynamic Programming

Thinking:

爬楼梯，一次爬 1 节或 2 节，问爬完的方式有多少种。可以爆破， (i,n)=(i+1,n)+(i+2,n) ， i 表示当前阶数， n 表示目标阶数。用 dp 表示即 dp[i] = dp[i-1]+dp[i-2] 。

73. Set Matrix Zeroes

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]
  • A straight forward solution using O(mn) space is probably a bad idea.
  • A simple improvement uses O(m + n) space, but still not the best solution.
  • Could you devise a constant space solution?

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public void setZeroes(int[][] matrix) {
    boolean firstCol = false;
    for (int i = 0; i < matrix.length; ++i) {
        if (matrix[i][0] == 0) {
            firstCol = true;
        }
        for (int j = 1; j < matrix[i].length; ++j) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    for (int i = 1; i < matrix.length; ++i) {
        for (int j = 1; j < matrix[i].length; ++j) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    // 补第一行
    if (matrix[0][0] == 0) {
        for (int j = 0; j < matrix[0].length; ++j) {
            matrix[0][j] = 0;
        }
    }
    // 补第一列
    if (firstCol) {
        for (int i = 0; i < matrix.length; ++i) {
            matrix[i][0] = 0;
        }
    }

}

Tag:

Array

Thinking:

矩阵中如果某一个 (i,j) 为 0 ，另 i 行与 j 列都为 0 。如果分别记录 i 和 j ，那么空间复杂度肯定不是 O(1) ；而如果是找到 (i,j) 为 0 ，立即修改矩阵，那么空间复杂度又不仅仅是 O(m*n) ；因此，最好的办法是只标记一个位置，比如第一行第一列，然后统一处理。

特殊的地方在于第一行和第一列，第一行的 [0,0] 是第一行的标记，这里要单独判断，此外第一列没有额外的位置来说明第一列是否全 0 ，需要用一个标志位来判断。

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

1
2
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
  • A rather straight forward solution is a two-pass algorithm using counting sort.
    First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
  • Could you come up with a one-pass algorithm using only constant space?

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void sortColors(int[] nums) {
    int p0 = 0, p2 = nums.length - 1, cur = 0;
    int temp;
    while (cur <= p2) {
        if (nums[cur] == 0) {
            temp = nums[p0];
            nums[p0] = nums[cur];
            nums[cur] = temp;
            p0++;
            cur++;
        } else if (nums[cur] == 2) {
            temp = nums[p2];
            nums[p2] = nums[cur];
            nums[cur] = temp;
            p2--;
        } else {
            cur++;
        }
    }
}

Tag:

Array Sort Two Pointers

Thinking:

荷兰国旗问题，原地排序，顺序是 0 1 2 。我们用三个指针（p0, p2 和curr）来分别追踪 0 的最右边界，2 的最左边界和当前考虑的元素。

本解法的思路是沿着数组移动 curr 指针，若nums[curr] = 0，则将其与 nums[p0]互换；若 nums[curr] = 2 ，则与 nums[p2]互换。

值得注意的是如果和 p2 交换， cur 是不需要移动的。

76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

1
2
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
  • If there is no such window in S that covers all characters in T, return the empty string “”.
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
    // 记录匹配串
    for (Character c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    int left = 0, right = 0, valid = 0;
    int start = 0, len = Integer.MAX_VALUE;
    while (right < s.length()) {
        // 移入字符
        Character c = s.charAt(right);
        right++;
        // 更新滑窗
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }
        // 收缩
        while (valid == need.size()) {
            // 输出时的位置记录
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            Character d = s.charAt(left);
            left++;
            // 更新滑窗
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}

Tag:

Thinking:

找到 S 中全覆盖 T 的最小子串。

滑动窗口，[left,right) 被称为一个窗口。初始化 left = right = 0 。

第一步：先不断移动 right ，包含住所有的 T ；

第二步：接着不断移动 left 缩小窗口，直到窗口不再包含完整 T ；

重复第一步和第二步，不断找到解并优化解。

下面是滑窗问题的通用模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

模板中的 window 和 need 两个哈希表，记录窗口中的字符和需要凑齐的字符；

然后，使用 left 和 right 变量初始化窗口的两端，不要忘了，区间 [left, right) 是左闭右开的，所以初始情况下窗口没有包含任何元素；

其中 valid 变量表示窗口中满足 need 条件的字符个数，如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T 。

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

1
2
3
4
5
6
7
8
9
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int step = 1;
    int minStep = Integer.MAX_VALUE;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; ++i) {
            TreeNode node = q.poll();
            if (node.left == null && node.right == null) {
                minStep = Math.min(minStep, step);
            }
            if (node.left != null) {
                q.offer(node.left);
            }
            if (node.right != null) {
                q.offer(node.right);
            }
        }
        step++;
    }
    return minStep;
}

Tag:

Tree Depth-first Search Breadth-first Search

Thinking:

找二叉树最短路径，BFS 带走。

239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length
1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class TempQueue {
    Deque<Integer> data;

    TempQueue() {
        data = new LinkedList<>();
    }

    int max() {
        return data.getFirst();
    }

    void push(int n) {
        while (!data.isEmpty() && data.getLast() < n) {
            data.pollLast();
        }
        data.addLast(n);
    }

    void pop(int n) {
        if (!data.isEmpty() && data.getFirst() == n) {
            data.pollFirst();
        }
    }

    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("TempQueue{");
        sb.append("data=").append(data);
        sb.append('}');
        return sb.toString();
    }
}

public int[] maxSlidingWindow(int[] nums, int k) {
    TempQueue window = new TempQueue();
    int[] res = new int[nums.length - k + 1];
    int index = 0;
    for (int i = 0; i < nums.length; ++i) {
        if (i < k - 1) {
            window.push(nums[i]);
        } else {
            window.push(nums[i]);
            res[index++] = window.max();
            window.pop(nums[i - k + 1]);
        }
    }
    return res;
}

Tag:

Heap Sliding Window

Thinking:

滑窗问题，要求操作时间为 O(1) ，用单调队列即可。

438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public List<Integer> findAnagrams(String s, String p) {
    Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
    for (Character c : p.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    int left = 0, right = 0;
    int valid = 0;
    List<Integer> res = new ArrayList<>();
    while (right < s.length()) {
        // 填充
        Character c = s.charAt(right);
        right++;
        // 处理滑窗
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (need.get(c).equals(window.get(c))) {
                valid++;
            }
        }
        // 移除
        while (valid == need.size() && right - left >= p.length()) {
            if (right - left == p.length()) {
                res.add(left);
            }
            // 处理滑窗
            Character d = s.charAt(left);
            left++;
            if (need.containsKey(d)) {
                if (need.get(d).equals(window.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return res;
}

Tag:

Hash Table

Thinking:

在 s 中找到所有 p 的异位词起始下标。比如 cba 是 abc 的异位词。看到两个串匹配就是滑窗可以解决的问题。

567. Permutation in String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

1
2
3
4
5
6
Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Input:s1= "ab" s2 = "eidboaoo"
Output: False
  • The input strings only contain lower case letters.
  • The length of both given strings is in range [1, 10,000].

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public boolean checkInclusion(String s1, String s2) {
    Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
    for (Character c : s1.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    int left = 0, right = 0;
    int valid = 0;
    while (right < s2.length()) {
        // 填充
        Character c = s2.charAt(right);
        right++;
        // 更新滑窗
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (need.get(c).equals(window.get(c))) {
                valid++;
            }
        }
        // 移除
        while (valid == need.size()) {
            if (right - left == s1.length()) {
                return true;
            }
            Character d = s2.charAt(left);
            left++;
            // 更新滑窗
            if (need.containsKey(d)) {
                if (need.get(d).equals(window.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return false;
}

Tag:

Two Pointer Sliding Window

Thinking:

判断 s2 中是否包含 s1 的排列，又是一道滑窗。

752. Open the Lock

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. The wheels can rotate freely and wrap around: for example we can turn ‘9’ to be ‘0’, or ‘0’ to be ‘9’. Each move consists of turning one wheel one slot.

The lock initially starts at ‘0000’, a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.

Input: deadends = ["0000"], target = "8888"
Output: -1
  • The length of deadends will be in the range [1, 500].
  • target will not be in the list deadends.
  • Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities ‘0000’ to ‘9999’.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public int openLock(String[] deadends, String target) {
    Queue<String> q = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    Set<String> deads = new HashSet<>(Arrays.asList(deadends));
    q.offer("0000");
    visited.add("0000");
    int step = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; ++i) {
            String cur = q.poll();
            if (deads.contains(cur)) {
                continue;
            }
            if (cur.equals(target)) {
                return step;
            }
            for (int j = 0; j < 4; ++j) {
                String up = plusOne(cur, j);
                if (!visited.contains(up)) {
                    q.offer(up);
                    visited.add(up);
                }
                String down = minusOne(cur, j);
                if (!visited.contains(down)) {
                    q.offer(down);
                    visited.add(down);
                }
            }
        }
        step++;
    }
    return -1;
}

private static String plusOne(String str, int j) {
    char[] ch = str.toCharArray();
    if (ch[j] == '9') {
        ch[j] = '0';
    } else {
        ch[j] += 1;
    }
    return new String(ch);
}

private static String minusOne(String str, int j) {
    char[] ch = str.toCharArray();
    if (ch[j] == '0') {
        ch[j] = '9';
    } else {
        ch[j] -= 1;
    }
    return new String(ch);
}

Tag:

Breadth-first Search

Thinking:

BFS 套一下，简单题，注意加一减一的时候 9 和 0 的变化。

#. Name

Solution:

1
2


Tag:

Thinking:

#. Name

Solution:

1
2


Tag:

Thinking: