10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#动态规划
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        s, p = '0'+s, '0'+p   #用'0'来代替''，使得题解更清晰
        m, n = len(s), len(p)
        #dp[i][j]表明s[:i+1]是否与p[:j+1]匹配，因为我们前面加上了'0'，所以这里dp[i][j]与s[i],p[j]关联
        dp = [[False ] * n for _ in range(m)]  
        dp[0][0] = True
        for j in range(2, n, 2):  #初始化首行
            dp[0][j] = dp[0][j-2] and p[j] == '*'  # 'x*'可视为''
        for i in range(1,m):
            for j in range(n):
                if p[j] == '*':
                    if dp[i][j-2] or (dp[i-1][j] and p[j-1] in [s[i],'.']):
                        dp[i][j] = True
                else:
                    if dp[i-1][j-1] and p[j] in [s[i],'.']:
                        dp[i][j] = True
        return dp[-1][-1]

154. 寻找旋转排序数组中的最小值 II

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
  • 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须尽可能减少整个过程的操作步骤。

1
2
3
4
5
6
7
8
9
10
#二分法
class Solution:
    def findMin(self, nums: [int]) -> int:
        i, j = 0, len(nums) - 1
        while i < j:
            m = (i + j) // 2
            if nums[m] > nums[j]: i = m + 1
            elif nums[m] < nums[j]: j = m
            else: j -= 1
        return nums[i]

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class MedianFinder:

    def __init__(self):
        self.small = []  #储存较小一半的数，大根堆，堆顶为最大值
        self.big = []   #储存较大一半的数，小根堆，堆顶为最小值

    def addNum(self, num: int) -> None:
        if len(self.small) != len(self.big):
            heappush(self.big, num)
            heappush(self.small, -heappop(self.big))
        else:
            heappush(self.small, -num)
            heappush(self.big, -heappop(self.small))

    def findMedian(self) -> float:
        return self.big[0] if len(self.small) != len(self.big) else (self.big[0] - self.small[0]) / 2  #大顶堆存的值为负数

297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

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
55
56
57
58
59
60
61
62
63
class Codec:

    def serialize(self, root):
        #使用BFS层级遍历将二叉树转化为字符串
        if not root: return ''
        #定义函数求二叉树的深度
        def depth(root):
            if not root: return 0
            return max(depth(root.left), depth(root.right)) + 1
        n = depth(root)
        f, stack, queue = 1, [], deque([root])  #f用来确定层数，在最后一层不添加n
        #BFS
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                if node == 'n':
                    stack.append(node)
                    continue
                stack.append(str(node.val))
                if node.left: queue.append(node.left)
                elif f < n: queue.append('n')   #添加n表明空子树
                if node.right: queue.append(node.right)
                elif f < n : queue.append('n')   #添加n表明空子树
            f += 1
        while stack[-1] == 'n':   #删除栈顶的无用n
            stack.pop()
        print(stack)
        return '*'.join(stack)   #用*分隔每棵树
        
    def deserialize(self, data):
        #按照层级遍历的模式还原二叉树
        if not data: return
        #将字符串转化为队列
        data = data.split('*')
        lst = deque(data)
        #root定位根节点
        root = TreeNode(int(lst.popleft()))
        queue= deque([root])
        #层级遍历
        while queue:
            node = queue.popleft()

            if not lst:   #已经遍历结束
                node.left = None
            else:
                node_left = lst.popleft()
                if node_left == 'n':   #子树为空
                    node.left = None
                else: node.left = TreeNode(int(node_left))   #左节点指向一个值为node_left的新节点

            if not lst:   #已经遍历结束
                node.right = None
            else:
                node_right = lst.popleft()
                if node_right == 'n':   #子树为空
                    node.right = None
                else: node.right = TreeNode(int(node_right))  #右节点指向一个值为node_right的新节点

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return root

2386. 找出数组的第 K 大和

给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。

数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复）

返回数组的 第 k 大和 。

子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。

**注意：**空子序列的和视作 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def kSum(self, nums: List[int], k: int) -> int:
        #求出最大值s，并且把所有负数转为正数，这样统一只需要做减法即可
        sum = 0
        for i, x in enumerate(nums):
            if x >= 0:
                sum += x
            else:
                nums[i] = -x
        nums.sort()

        #以累加和来排列子序列，排到第k个终止
        stack = [(0,0)]  #空子序列,一个用来装子序列和,一个装下标
        for _ in range(k-1):   #已经有一个（0,0）,所以只需要循环k-1次
            s, i = heappop(stack)
            if i < len(nums):   #子序列下标不超过原序列下标
                # 在子序列的末尾添加 nums[i]
                heappush(stack, (s + nums[i] , i+1) )  # 下一个添加/替换的元素下标为 i+1
                if i:   # 替换子序列的末尾元素为 nums[i]
                    heappush(stack, (s + nums[i] - nums[i-1], i+1) )
        return sum - stack[0][0]