日拱两卒（四）

70#

最小栈。让栈能额外支持一个操作，返回栈内最小值。

栈内多维护一个“前缀最小值”即可。

1
class MinStack:
2

3
    def __init__(self):
4
        self.stack = [(0, float("inf"))]
5

6
    def push(self, value: int) -> None:
7
        self.stack.append((value, min(self.stack[-1][1], value)))
8

9
    def pop(self) -> None:
10
        self.stack.pop()
11

12
    def top(self) -> int:
13
        return self.stack[-1][0]
14

15
    def getMin(self) -> int:
16
        return self.stack[-1][1]

69#

有效的括号。

给一个含有三种括号的序列，判断是否合法。

1
class Solution:
2
    def isValid(self, s: str) -> bool:
3
        stack = []
4
        need = {
5
            "}" : "{",
6
            "]" : "[",
7
            ")" : "("
8
        }
9
        for c in s:
10
            if c == '(' or c == '[' or c == '{':
11
                stack.append(c)
12
            else:
13
                if not stack:
14
                    return False
15
                if stack[-1] != need[c]:
16
                    return False
17
                stack.pop()
18
        return not stack

68#

寻找两个正序数组的中位数。

类似快速选择每次丢一半的思想。

1
class Solution:
2
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
3
        def findkth(k):
4
            start1 = 0
5
            start2 = 0
6
            while True:
7
                if start1 == len(nums1):
8
                    return nums2[start2 + k - 1]
9
                if start2 == len(nums2):
10
                    return nums1[start1 + k - 1]
11
                if k == 1:
12
                    return min(nums1[start1], nums2[start2])
13
                half = k // 2
14
                idx1 = min(start1 + half, len(nums1)) - 1
15
                idx2 = min(start2 + half, len(nums2)) - 1
16
                if nums1[idx1] < nums2[idx2]:
17
                    k -= idx1 - start1 + 1
18
                    start1 = idx1 + 1
19
                else:
20
                    k -= idx2 - start2 + 1
21
                    start2 = idx2 + 1
22

23

24
        total = len(nums1) + len(nums2)
25
        if total & 1:
26
            return findkth((1 + total) >> 1)
27
        else:
28
            left = findkth(total >> 1)
29
            right = findkth((total >> 1) + 1)
30
            return (left + right) / 2.0

67#

寻找旋转排序数组中的最小值。

这里旋转一次的定义是把一个末尾元素放到头部。

问题是一开始有一个排序数组，现在被旋转了未知的次数，要找到最小值。

被旋转后的数组的“形状”大概是先升再掉到最低点，再升。

所以可以每次二分的时候和最后一个元素比较。

如果当前位置更大，说明最低点在右边。

如果当前位置更小，说明最低点在左边。

1
class Solution:
2
    def findMin(self, nums: List[int]) -> int:
3
        l = 0
4
        r = len(nums)
5

6
        while l < r:
7
            mid = (l + r) >> 1
8
            if nums[mid] <= nums[-1]:
9
                r = mid
10
            else:
11
                l = mid + 1
12

13
        return nums[l]

66#

搜索旋转排序数组。

数组和上一题一样，但这次不是找最小值而是找目标值。

思路是先找出最小值，分两段做简单二分。

1
class Solution:
2
    def findMin(self, nums: List[int]) -> int:
3
        l = 0
4
        r = len(nums)
5

6
        while l < r:
7
            mid = (l + r) >> 1
8
            if nums[mid] <= nums[-1]:
9
                r = mid
10
            else:
11
                l = mid + 1
12

13
        return l
14

15
    def search(self, nums: List[int], target: int) -> int:
16
        min_idx = self.findMin(nums)
17
        min_v = nums[min_idx]
18
        if target <= nums[-1]:
19
            l = min_idx
20
            r = len(nums)
21
            while l < r:
22
                mid = (l + r) >> 1
23
                if nums[mid] >= target:
24
                    r = mid
25
                else:
26
                    l = mid + 1
27
            if l < len(nums) and nums[l] == target:
28
                return l
29
        else:
30
            l = 0
31
            r = min_idx - 1
32
            while l < r:
33
                mid = (l + r) >> 1
34
                if nums[mid] >= target:
35
                    r = mid
36
                else:
37
                    l = mid + 1
38
            if l < len(nums) and nums[l] == target:
39
                return l
40

41
        return -1

65#

在排序数组中查找元素的第一个和最后一个位置。

简单二分。

1
class Solution:
2
    def searchRange(self, nums: List[int], target: int) -> List[int]:
3
        l, r = 0, len(nums)
4
        while l < r:
5
            mid = (l + r) >> 1
6
            if nums[mid] >= target:
7
                r = mid
8
            else:
9
                l = mid + 1
10
        if l >= len(nums) or nums[l] != target:
11
            return [-1, -1]
12
        ans1 = l
13
        l, r = 0, len(nums)
14
        while l < r:
15
            mid = (l + r) >> 1
16
            if nums[mid] > target:
17
                r = mid
18
            else:
19
                l = mid + 1
20
        return [ans1, l - 1]

64#

搜索二维矩阵。

有一个排序的二维数组，问有没有目标值。

每次和右上角比对，排除一行或一列。

1
class Solution:
2
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
3
        i, j = 0, len(matrix[0]) - 1
4
        while i < len(matrix) and j >= 0:
5
            if matrix[i][j] == target:
6
                return True
7
            if matrix[i][j] < target:
8
                i += 1
9
            elif matrix[i][j] > target:
10
                j -= 1
11
        return False

63#

搜索插入位置。

最最简单的二分。

1
class Solution:
2
    def searchInsert(self, nums: List[int], target: int) -> int:
3
        l, r = 0, len(nums)
4
        while l < r:
5
            mid = (l + r) >> 1
6
            if nums[mid] >= target:
7
                r = mid
8
            else:
9
                l = mid + 1
10
        return l

62#

N皇后。

经典搜索。

1
class Solution:
2
    def solveNQueens(self, n: int) -> List[List[str]]:
3
        board = [['.' for _ in range(n)] for _ in range(n)]
4
        ans = []
5

6
        col = [False] * n
7
        dia1 = [False] * (2 * n - 1)
8
        dia2 = [False] * (2 * n - 1)
9

10
        def dfs(u):
11
            if u == n:
12
                ans.append([''.join(row) for row in board])
13
                return
14
            for i in range(n):
15
                if col[i] or dia1[i - u + n - 1] or dia2[i + u]:
16
                    continue
17

18
                board[u][i] = 'Q'
19
                col[i] = True
20
                dia1[i - u + n - 1] = True
21
                dia2[i + u] = True
22

23
                dfs(u + 1)
24

25
                board[u][i] = '.'
26
                col[i] = False
27
                dia1[i - u + n - 1] = False
28
                dia2[i + u] = False
29

30
        dfs(0)
31
        return ans

61#

分割回文串。

经典搜索。

1
class Solution:
2
    def partition(self, s: str) -> List[List[str]]:
3
        ans = []
4
        tmp = []
5
        n = len(s)
6

7
        def check(s) -> bool:
8
            for i in range(len(s) // 2):
9
                if s[i] != s[len(s) - 1 - i]:
10
                    return False
11
            return True
12

13
        def dfs(u):
14
            if u >= n:
15
                ans.append(tmp[:])
16
            for length in range(1, n - u + 1):
17
                if check(s[u:u + length]):
18
                    tmp.append(s[u:u + length])
19
                    dfs(u + length)
20
                    tmp.pop()
21

22
        dfs(0)
23
        return ans