今天也更新两道题，过的速度真是有够慢的。经典的算法还挺多的，每个回顾起来都花不少时间。

BM 48 数据流的中位数

url：牛客 BM48

考察知识点：插入排序、堆

方法一：插入排序

插入排序的方法比较好想到，因为中位数就是排序好的数组中间位置的数嘛。

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
# -*- coding:utf-8 -*-
class Solution:
    num_list = []
    def Insert(self, num):
        # write code here
        # 用插入排序做一次
        num_length = len(self.num_list)
        for i in range(num_length):
            if self.num_list[i] >= num:
                self.num_list.insert(i, num)
                break
        # 如果之前都没插进去，那就是最后一个元素了
        if num_length == len(self.num_list):
            self.num_list.append(num)

    def GetMedian(self):
        # write code here
        num_length = len(self.num_list)

        if num_length % 2 == 1:
            # 奇数，取一个即可
            return self.num_list[num_length // 2]
        else:
            # 偶数取平均值
            return (self.num_list[num_length // 2] + self.num_list[num_length // 2 - 1]) / 2

方法二：两个堆（前面的数维护一个大根堆，后面的数维护一个小根堆）

这种两个堆的想法确实还比较巧妙。它的核心思想是，如果将排序完成的数组一分为：如果是奇数个元素则允许前面的数组多一个元素，那前面数组的最大值就是这个数组的中位数。如果是偶数个元素，那么前后数组的个数都相等，前面数组的最大值和后面数组的最小值的平均值就是这个数组的中位数。

那么要完成这样的事可以通过两个堆实现，前面的是大根堆，可以弹出最大元素，后面的则是小根堆，弹出最小元素。然后为了达到两个堆的是将排序好的数组均分的效果，应该先插入到前面的大根堆中，再将原来大根堆中最大的元素插入后面的小根堆中。最后为了平衡，如果大根堆元素少于小根堆，就从小根堆中拿一个最小元素到大根堆中平衡数目。

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
# -*- coding:utf-8 -*-
import heapq
class Solution:
    front = []   # 前面是大根堆
    back = []    # 后面是小根堆

    def Insert(self, num):
        # write code here
        # 两个堆的方法
        heapq.heappush(self.front, (-1*num, num))
        transfer_num = heapq.heappop(self.front)[1]
        heapq.heappush(self.back, (transfer_num, transfer_num))

        # 平衡两个堆
        if len(self.back) > len(self.front):
            transfer_num = heapq.heappop(self.back)[1]
            heapq.heappush(self.front, (-1 * transfer_num, transfer_num))


    def GetMedian(self):
        # write code here
        if len(self.front) > len(self.back):
            return self.front[0][1]
        else:
            return (self.front[0][1] + self.back[0][1]) / 2

BM 49 表达式求值

url：牛客 BM49

考察知识点：逆波兰表达式、栈

通过调度场算法将中缀表达式转化为后缀表达式（逆波兰表达式），之后对逆波兰表达式求值。写了一版粗略的，后面可能给这题新开个帖子吧，毕竟表达式求值确实是挺有意思的一件事。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
class Solution:
    def op_priority(self, c):
        if c == "*":
            return 2
        elif c == "+" or c == "-":
            return 1
        else:
            # 非运算符，返回0
            return 0

    def solve(self , s: str) -> int:
        # write code here
        output_queue = []
        op_stack = []

        i = 0
        while i < len(s):
            c = s[i]
            if c == "(":
                op_stack.append(c)
                i += 1
            elif c.isdigit():
                # 一直读入数据直到下一个值不是数字为止
                num_str = ""
                while i < len(s) and s[i].isdigit():
                    num_str += s[i]
                    i += 1
                # 将操作数加入栈
                output_queue.append(int(num_str))
            elif c in "+-*":
                if len(op_stack) > 0:
                    if self.op_priority(op_stack[-1]) >= self.op_priority(c):
                        output_queue.append(op_stack.pop())
                op_stack.append(c)
                i += 1
            elif c == ")":
                while len(op_stack) > 0 and op_stack[-1] != "(":
                    output_queue.append(op_stack.pop())
                if len(op_stack) == 0:
                    raise Exception("括号不匹配!")
                else:
                    # 弹出多余的左括号
                    op_stack.pop()
                i += 1
        while len(op_stack) > 0:
            if op_stack[-1] == "(":
                raise Exception("括号不匹配!")
            else:
                output_queue.append(op_stack.pop())
        # print(output_queue)

        # 开始计算逆波兰表达式
        calc_stack = []
        for item in output_queue:
            if str(item) in "+-*":
                if len(calc_stack) < 2:
                    raise Exception("没有输入足够的操作数")
                a = calc_stack.pop()
                b = calc_stack.pop()

                if item == "+":
                    calc_stack.append(b+a)
                elif item == "-":
                    calc_stack.append(b-a)
                elif item == "*":
                    calc_stack.append(b*a)
            else:
                calc_stack.append(item)
        if len(calc_stack) == 1:
            return calc_stack.pop()
        else:
            raise Exception("输入了多余的操作数!")

这些题在Leetcode上还有多种变种，不用会员的有：227. 基本计算器 II、224. 基本计算器、770. 基本计算器 IV、150. 逆波兰表达式求值，有空新开个帖子写一下这些题。