写了也挺久的了吧，今天终于把牛客TOP101道题给写完了，算是有了一些基础编程能力了吧。因为大大小小的事耽误着，其实还写了蛮多天的，写完确实能感觉到有所收获。按时间顺序，也其实就是题目的顺序把剩下的解法都记录在这里。

9月20日

BM 55 没有重复项数字的全排列

url：牛客 BM55

考察知识点：回溯法

做了这题之后我才发现全排列就是原来数组进行两两交换之后的所有结果，当然也可以自己和自己交换，这样就是这步操作不改变结果。那第\(i\)次操作时总共有和后面\(n-i+1\)个元素（包括这个元素自己）进行交换的机会。

这个按字典序的意思就是按a-z，0-9的顺序排序，也就是在做之前排序一下元素即可。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def permute_item(self, base_num_list: List[int], pos: int, result: List[List[int]]):
        if pos == len(base_num_list)-1:
            # 这里应该是叶子节点了，准备加入result
            result.append(base_num_list)
            return None
        
        # 如果不是叶子节点就继续往更深的地方搜索
        # 根据base_num_list和需要变更的位置完成变更        
        for i in range(pos, len(base_num_list)):
            # 自己和自己交换也算一种变更
            num_list = base_num_list.copy()
            num_list[pos], num_list[i] = num_list[i], num_list[pos]
            # 继续往更深的地方搜索
            self.permute_item(num_list, pos+1, result)

    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        # 用回溯法进行全排列
        result = []
        
        # 排序
        num.sort()
        self.permute_item(num, 0, result)
        return result

用以前学的回溯法框架写了一下，这次不是两两交换，而是逐个加入直到全部加入：

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    result = []

    def backtrack(self, v):
        if len(v) == 0:
            print("the end...")
        else:
            del v[-1]

    def advance(self, v):
        # 因为没有重复数字，因此可以直接进来
        visited = set(v)
        return visited
    
    def get_all_next_adj(self, visited, num):
        wait_list = []
        # 编写新逻辑
        for i, item in enumerate(num):
            if item in visited:
                continue
            # 如果都满足就加入这个下标
            wait_list.append(i)
        # 都不满足就返回None
        return wait_list

    
    def dfs(self, v, num):
        visited = self.advance(v)
        n = len(num)
        if len(v) == len(num):
            self.result.append(v.copy())
            print(self.result)
        else:
            # 如果不是叶节点就开始回溯法
            # 即深度优先搜索
            wait_list = self.get_all_next_adj(visited, num)
            print(wait_list)
            e = 0
            while e < len(wait_list):
                v.append(num[wait_list[e]])
                self.dfs(v, num)
                e += 1
        self.backtrack(v)


    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        # 用回溯法进行全排列
        num.sort()
        self.dfs([], num)
        return self.result

BM 56 有重复项的全排列

url：牛客 BM 56

考察知识点：回溯法

似乎之前的BM55没有按字典序排序也过了，但BM56不行。我没想到怎么在中途对结果排序，于是就自己定义了一下比较方法然后在后面自己排序成字典序。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    has_visited = set()

    def permute_item(self, num: List[int], pos: int, result: List[List[int]]):
        if pos == len(num)-1:
            # 这里说明是叶子节点了
            if "".join([str(n) for n in num]) not in self.has_visited:
                # 如果和之前没有重复就加入
                result.append(num.copy())
                self.has_visited.add("".join([str(n) for n in num]))

            return None

        # 否则要遍历
        for i in range(pos, len(num)):
            # 继续往更深的地方搜索
            if i != pos and num[i] == num[pos]:
                continue
            num[i], num[pos] = num[pos], num[i]
            self.permute_item(num, pos+1, result)
            num[pos], num[i] = num[i], num[pos]
    
    def compare_result(self, r1: List[int], r2: List[int]):
        for i in range(len(r1)):
            if r1[i] < r2[i]:
                return 1
            elif r1[i] > r2[i]:
                return 0
            else:
                continue

    def sort_to_dict(self, result: List[List[int]]):
        # 用冒泡/选择排序
        N = len(result)
        for i in range(N):
            min_ = i
            for j in range(i+1, N):
                if self.compare_result(result[j], result[min_]):
                    min_ = j
            result[min_], result[i] = result[i], result[min_]
        return result

    def permuteUnique(self , num: List[int]) -> List[List[int]]:
        # write code here
        num.sort()
        self.has_visited = set()
        result = []
        self.permute_item(num, 0, result)
        return self.sort_to_dict(result)

能不能用列表自带的sort进行排序，然后指定比较接口呢？是可以的，但是有点烦，因为原来的key虽然支持传入函数，但是这个key的函数是要求在对元素计算一个可比较的数，要传入比较接口有两种办法，一种就是我们自己包装一下要比较的元素（我更推荐这种做法，因为后面字典也会要用到__hash__和__eq__来计算哈希值）。另一种就是用Python在functools里提供的cmp_to_key完成。第二种方法演示如下：

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
from functools import cmp_to_key
def compare_result(r1: List[int], r2: List[int]):
    for i in range(len(r1)):
        if r1[i] < r2[i]:
            return -1
        elif r1[i] > r2[i]:
            return 1
        else:
            continue

class Solution:
    has_visited = set()

    def permute_item(self, num: List[int], pos: int, result: List[List[int]]):
        if pos == len(num)-1:
            # 这里说明是叶子节点了
            if "".join([str(n) for n in num]) not in self.has_visited:
                # 如果和之前没有重复就加入
                result.append(num.copy())
                self.has_visited.add("".join([str(n) for n in num]))

            return None

        # 否则要遍历
        for i in range(pos, len(num)):
            # 继续往更深的地方搜索
            if i != pos and num[i] == num[pos]:
                continue
            num[i], num[pos] = num[pos], num[i]
            self.permute_item(num, pos+1, result)
            num[pos], num[i] = num[i], num[pos]
    

    def permuteUnique(self , num: List[int]) -> List[List[int]]:
        # write code here
        num.sort()
        self.has_visited = set()
        result = []
        self.permute_item(num, 0, result)
        result.sort(key=cmp_to_key(compare_result))
        return result

BM 57 岛屿数量

url：牛客 BM57

考察知识点：回溯法

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        num_of_island = 0
        n = len(grid)
        m = len(grid[0])

        def dfs(grid: List[List[str]], i: int, j: int):
            # 将该位置置为0
            grid[i][j] = "0"

            # 向上下左右四个方向搜索
            if j > 0 and grid[i][j-1] == "1":
                dfs(grid, i, j-1)
            if j < m-1 and grid[i][j+1] == "1":
                dfs(grid, i, j+1)
            if i > 0 and grid[i-1][j] == "1":
                dfs(grid, i-1, j)
            if i < n-1 and grid[i+1][j] == "1":
                dfs(grid, i+1, j)
        
        for l1 in range(n):
            for l2 in range(m):
                if grid[l1][l2] == "1":
                    num_of_island += 1
                    dfs(grid, l1, l2)
        return num_of_island

BM 58 字符串的排列

url：牛客 BM58

考察知识点：回溯法、排列问题

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @return string字符串一维数组
#
class Solution:
    def Permutation(self , str: str) -> List[str]:
        # write code here
        str_list = list(str)
        N = len(str_list)
        result = set()

        def dfs(str_list: List[str], pos: int, result):
            if pos == N - 1:
                target = "".join(str_list)
                result.add(target)
                return None
            
            # 深度优先搜索
            for i in range(pos, N):
                # 交换
                str_list[i], str_list[pos] = str_list[pos], str_list[i]
                dfs(str_list, pos+1, result)
                # 回溯
                str_list[pos], str_list[i] = str_list[i], str_list[pos]
        
        dfs(str_list, 0, result)
        return list(result)

BM 59 N皇后问题

url：牛客 BM59

考察知识点：回溯法

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 the n
# @return int整型
#
class Solution:
    def Nqueen(self , n: int) -> int:
        # write code here
        # 回溯法求解N皇后问题
        num_of_solution = 0

        def exceedBound(col: List[int]):
            # 检查当前是否越界
            if len(col) <= 1:
                return False
            else:
                # 检查新皇后是否越界
                q2 = [len(col)-1, col[-1]]
                for i in range(len(col)-1):
                    q1 = [i, col[i]]
                    # 检查对角线（列和行在之前检查过了）
                    if abs(q1[0] - q2[0]) == abs(q1[1] - q2[1]):
                        return True
                return False

        def dfs(col: List[int]):
            nonlocal num_of_solution, n
            # 检查当前解是否是叶子节点
            if len(col) == n:
                num_of_solution += 1
            else:
                # 这边还不是叶子节点，因此需要落子
                j = 0
                while j < n:
                    if j in col:
                        j += 1
                        continue
                    if not exceedBound(col + [j]):
                        # 落子并继续深度搜索
                        col.append(j)
                        dfs(col)
                    j += 1
            # 回溯
            if len(col) > 0:
                del col[-1]
        
        dfs([])
        return num_of_solution

BM 60 括号生成

url：牛客 BM60

考察知识点：回溯法、栈

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return string字符串一维数组
#
class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        str_list = []
        result = []

        def isValid(str_list):
            # 检查符号串是否合法
            stack = []
            for i in range(len(str_list)):
                if str_list[i] == "(":
                    stack.append("(")
                else:
                    if len(stack) > 0 and stack[-1] == "(":
                        stack.pop()
                    else:
                        # 这里是出问题了，所以不合法
                        return False
            return True

        def dfs(str_list, r_num):
            if len(str_list) == 2 * n:
                # 叶子节点
                result.append("".join(str_list))
            else:
                # 深度优先搜索
                next_list = ["(", ")"]
                for item in next_list:
                    if isValid(str_list + [item]):
                        if item == "(":
                            if r_num + 1 > n:
                                continue
                            str_list.append(item)
                            dfs(str_list, r_num+1)
                        else:
                            str_list.append(item)
                            dfs(str_list, r_num)

            # 回溯
            if len(str_list) > 0:
                del str_list[-1]
        
        dfs([], 0)
        return result

9月21日

BM 61 矩阵最长递增路径

url：牛客 BM61

考察知识点：回溯法、动态规划

先来一个暴力回溯的方法，这个方法从起点一直找递增路径，然后保存最长递增路径的长度并返回。复杂度很高，过不了所有的用例。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # write code here
        n = len(matrix)
        m = len(matrix[0])
        max_path_length = 0

        def isLeaf(v):
            # 判断是不是叶节点，主要看还有没有路可走
            if len(v) == 0:
                return False
            now_i, now_j = v[-1]
            now_v = matrix[now_i][now_j]
            if now_i > 0 and matrix[now_i-1][now_j] > now_v:
                return False
            elif now_j > 0 and matrix[now_i][now_j-1] > now_v:
                return False
            elif now_i < n-1 and matrix[now_i+1][now_j] > now_v:
                return False
            elif now_j < m-1 and matrix[now_i][now_j+1] > now_v:
                return False
            else:
                return True

        def all_next_point(v):
            points = []
            if len(v) == 0:
                # 如果没选择任何节点，那就可以从任意点出发
                for i in range(n):
                    for j in range(m):
                        points.append([i, j])
            else:
                # 取出现在的点
                now_i, now_j = v[-1]
                now_v = matrix[now_i][now_j]
                # 判断上下左右的值与现在点的关系
                if now_i > 0 and matrix[now_i-1][now_j] > now_v:
                    points.append([now_i-1, now_j])
                if now_j > 0 and matrix[now_i][now_j-1] > now_v:
                    points.append([now_i, now_j-1])
                if now_i < n-1 and matrix[now_i+1][now_j] > now_v:
                    points.append([now_i+1, now_j])
                if now_j < m-1 and matrix[now_i][now_j+1] > now_v:
                    points.append([now_i, now_j+1])
            return points

        def dfs(v):
            nonlocal max_path_length
            if isLeaf(v):
                if len(v) > max_path_length:
                    max_path_length = len(v)
            else:
                # 深度优先搜索
                points = all_next_point(v)
                for point in points:
                    # 之前判断过是否可行，因此不需要检查边界
                    v.append(point)
                    dfs(v)
            # 回溯
            if len(v) > 0:
                del v[-1]
        dfs([])
        return max_path_length

动态规划可以做这题。原因是地图确定后，从某个点出发能到达的最长路径值是固定的，而且和从哪来的没关系。这就使得这个问题具有最优子结构性质，即最优解中也存在所有子问题的最优解。比如一个路径是"1->3->5"是最长递增路径，那么从"1->3"和"3->5"必不可能存在更长的递增路径了，否则原路径就不是最长递增路径。通过这个性质我们可以把这个问题抽象为从一个点出发的最长路径是所有下一个能访问点的最长路径长度加一的最大值，用程序可以表示为：

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # write code here
        n = len(matrix)
        m = len(matrix[0])
        dp = [[0 for j in range(m)] for i in range(n)]
        next_ij = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(i, j):
            if dp[i][j] != 0:
                return dp[i][j]
            
            # 访问之后最小长度应该是1
            dp[i][j] += 1
            # 否则就递归计算该点出发的最长递增路径长度
            for k in range(4):
                next_i = i + next_ij[k][0]
                next_j = j + next_ij[k][1]

                if next_i >= 0 and next_i < n and \
                    next_j >= 0 and next_j < m and \
                    matrix[next_i][next_j] > matrix[i][j]:
                    # 看看哪个更大
                    dp[i][j] = max(dfs(next_i, next_j)+1, dp[i][j])
            return dp[i][j]

        for i in range(n):
            for j in range(m):
                dfs(i, j)
        print(dp)
        return max(map(max, dp))

BM 62 斐波拉契数列

url：牛客 BM62

考察知识点：动态规划

非常经典的一道题，其递归表达式就说明非常适合动态规划求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        dp = [0 for i in range(n)]

        for i in range(n):
            if i == 0 or i == 1:
                dp[i] = 1
            else:
                dp[i] = dp[i-1] + dp[i-2]
        
        return dp[-1]

BM 63 跳台阶

url：牛客 BM63

考察知识点：动态规划

这种题目就可以反着思考，比如我在离终点一格的地方有几种跳法呢，那就一种对吧，离终点两格的地方有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
26
27
28
29
30
31
32
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型
#
class Solution:
    def jumpFloor(self , number: int) -> int:
        # write code here
        dp = [0 for i in range(number)]

        def jump(k: int, number: int):
            # k是当前位置, number是目标位置
            if dp[k] != 0:
                return dp[k]

            diff = number - k

            if diff <= 0:
                return 0
            elif diff == 1:
                dp[k] = 1
            elif diff == 2:
                dp[k] = 2
            else:
                # 不是1或者2就要递归
                dp[k] = jump(k+1, number) + jump(k+2, number)
            return dp[k]
        
        jump(0, number)
        return dp[0]

BM 64 最小花费爬楼梯

url：牛客 BM64

考察知识点：动态规划

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param cost int整型一维数组 
# @return int整型
#
class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        n = len(cost)
        dp = [0 for i in range(n+1)]

        def climb(k: int):
            if dp[k] != 0:
                return dp[k]
            
            # 计算爬到第k阶最少要多少花费
            if k == 0 or k == 1:
                # 可以从一节或者二阶开始爬
                dp[k] = 0
            else:
                dp[k] = min(climb(k-1) + cost[k-1], climb(k-2) + cost[k-2])
            return dp[k]
        return climb(n)

BM 65 最长公共子序列（二）

url：牛客 BM65

考察知识点：动态规划、最长公共子序列

感觉可以写个专题，因为确实有点东西。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        # write code here
        n = len(s1)
        m = len(s2)
        dp = [[0]*(m+1) for i in range(n+1)]

        for i in range(1, n+1):
            for j in range(1, m+1):
                # 判断字符是否在最长子序列中
                if s1[i-1] == s2[j-1]:
                    # 该字符一定在最长子序列中
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    # 如果不等的话有3种情况，
                    # s1[i]是、s2[j]是或者两者都不是
                    # 第三种情况可以被前两种组合表示
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        
        # 通过回溯构造解
        i, j = n, m
        k = dp[i][j]
        lcs = ""
        while i > 0 and j > 0 and k > 0:
            while dp[i][j] == dp[i-1][j] and i > 0:
                i = i - 1
            while dp[i][j] == dp[i][j-1] and j > 0:
                j = j - 1

            lcs = s1[i-1] + lcs
            i -= 1
            j -= 1
            k -= 1

        return lcs if lcs else "-1"

BM 66 最长公共子串

url：牛客 BM66

考察知识点：动态规划

家人们谁懂啊，同样的算法就Python超时...

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# longest common substring
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        # write code here
        n = len(str1)
        m = len(str2)

        dp = [[0]*(m+1) for i in range(n+1)]

        # 回溯构造最长公共字串
        max_, max_i = 0, 0

        for i in range(1, n+1):
            for j in range(1, m+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    if dp[i][j] > max_:
                        max_i = i
                        max_ = dp[i][j]
                else:
                    # 不等的话怎么办呢
                    # 可能是位置没对齐之类的，但似乎不用管
                    pass
        
        return str1[max_i-max_: max_i]

官方提供的非动态规划版本，理论时间复杂度是\(O(m^2n)\)，但是却能过...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# longest common substring
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        # write code here
        #让str1为较长的字符串
        if len(str1) < len(str2):
            str1, str2 = str2, str1
        res = ''
        max_len = 0
        #遍历str1的长度
        for i in range(len(str1)):
            #查找是否存在
            if str1[i - max_len : i + 1] in str2:
                res = str1[i - max_len : i + 1]
                max_len += 1
        return res

BM 67 不同路径的数目（一）

url：牛客 BM67

考察知识点：排列组合、动态规划

这道题还是有点意思，直接从左上角移动到右下角，只能进行向下或者向右的操作。路径的数目只和向下和向右的组合顺序有关，对于\(m*n\)的图，向下操作要进行\(m-1\)次，向右操作要进行\(n-1\)次。所以路径总数相当于把\(m-1\)个小球放入\(m-n-2\)个位置里，即有： \[ C_{m-n-2}^{m-1}=\frac{(m-n-2)!}{(m-1)!(n-1)!} \] 种不同的路径。

写代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param m int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        # write code here
        import math
        return math.factorial(m+n-2) // (math.factorial(m-1) * math.factorial(n-1))

如果要用动态规划老实操作呢，也可以做到。需要注意的是从出生点开始走只有1种走法，然后如果走到一个点那个点的走法种数是其左边和上边的走法之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param m int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        # write code here
        dp = [[1]*n for i in range(m)]

        for i in range(m):
            for j in range(n):
                if i > 0 and j > 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                elif i > 0:
                    dp[i][j] = dp[i-1][j]
                elif j > 0:
                    dp[i][j] = dp[i][j-1]
        
        return dp[m-1][n-1]

9月22日

BM 68 矩阵最小路径和

url：牛客 BM68

考察知识点：动态规划

和BM67类似，理清动态规划的递推关系即可。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        # write code here
        n = len(matrix)
        m = len(matrix[0])
        dp = [[0]*m for i in range(n)]

        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0:
                    dp[i][j] = matrix[i][j]
                elif i == 0:
                    dp[i][j] = dp[i][j-1] + matrix[i][j]
                elif j == 0:
                    dp[i][j] = dp[i-1][j] + matrix[i][j]
                else:
                    # 是上方和左方的最小值加上该点花费
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
        
        return dp[n-1][m-1]

BM 69 把数字翻译成字符串

url：牛客 BM69

考察知识点：动态规划

这个题目是很体现重叠子问题的一道题，不管先解码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
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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 解码
# @param nums string字符串 数字串
# @return int整型
#
class Solution:
    def solve(self , nums: str) -> int:
        # write code here
        dp = {}

        def decode(s):
            # 返回译码种数
            if len(s) == 1:
                if s[0] != "0":
                    return 1
                else:
                    return 0
            elif len(s) == 2:
                if s[0] == "0":
                    return 0
                elif int(s) <= 26:
                    if s[1] != "0":
                        return 2
                    else:
                        return 1
                elif int(s) > 26:
                    if s[1] != "0":
                        return 1
                    else:
                        return 0
            else:
                # 大于2的情况
                prefix = s[:2]
                num = 0
                if s in dp:
                    return dp[s]
                if prefix[0] == "0":
                    num = 0
                elif int(prefix) <= 26:
                    if prefix[1] == "0":
                        num = decode(s[2:])
                    else:
                        num = decode(s[2:]) + decode(s[1:])
                else:
                    num = decode(s[1:])
                # 记录
                dp[s] = num
                return num
        
        return decode(nums)

看了题解，貌似题解还有问题，解码“120”的时候官方的题解结果是2，但实际是1。其原因就是当前数字是"0"是一个特殊的分支，它要单独考虑，看了评论区的一个题解不错，注释也挺清楚，贴上来：

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 解码
# @param nums string字符串 数字串
# @return int整型
#
class Solution:
    def solve(self , nums: str) -> int:
        l = len(nums)
        dp = [1 for _ in range(l+1)]
        for i in range(1, l+1):
            if i == 1:
                # 如果第一个数字是0，不存在可行的翻译
                if nums[i-1] == '0':
                    return 0
            else:
                # 任何一个’0‘，都依赖于其前面一个数字，先讨论当前数字为0的情况
                if nums[i-1] == '0':
                    # 如果当前0不能和前一个数字组合
                    if (int(nums[i-2]) > 2 or nums[i-2] == '0'):
                        return 0
                    # 当前0和前一个数字组合
                    else:
                        dp[i] = dp[i-2]
                # 再讨论当前数字不为0的情况
                else:
                    # 如果当前数字不能和前一个数字组合
                    if nums[i-2] == '0' or int(nums[i-2]+nums[i-1]) > 26:
                        dp[i] = dp[i-1]
                    # 当前数字和前一个数字组合或者不组合
                    else:
                        dp[i] = dp[i-2] + dp[i-1]    
        return dp[-1]

BM 70 兑换零钱（一）

url：牛客 BM70

考察知识点：动态规划

先看一下不要求零钱数为整数的解法，该解法通过字典来记录子问题的解法，我觉得这道题用这种方法灵活度更高一些。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        # 排序一下面额，先从大面额的开始试
        arr.sort(reverse=True)

        # 零钱备忘录
        dp = {0: 0}

        # 递归最少找零
        def give_change(aim):
            if aim in dp:
                return dp[aim]

            result = []
            for i in range(len(arr)):
                if aim >= arr[i]:
                    pr = give_change(aim-arr[i])
                    if pr != -1:
                        result.append(1 + pr)

            if len(result) == 0:
                dp[aim] = -1
                return -1
            else:
                dp[aim] = min(result)
                return dp[aim]

        return give_change(aim)

当然，aim为整数也可以利用这个性质为aim建个动态规划的数组，更省空间一些。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        dp = [-1 for i in range(aim+1)]
        
        # 基本案例
        dp[0] = 0
        for i in range(aim+1):
            if i in arr:
                # 如果是面额里的零钱直接找一张就可以了
                dp[i] = 1
            else:
                # 如果不是那就需要组合
                # 因为有找不开的情况因此开个列表记录一下找零情况
                result = []
                for j in arr:
                    if j <= i and dp[i-j] != -1:
                        result.append(dp[i-j] + 1)
                # 取能找开情况下的最小值
                if len(result) > 0:
                    dp[i] = min(result)
        return dp[aim]

BM 71 最长上升子序列（一）

url：牛客 BM71

考察知识点：动态规划

动态规划里很经典的题，思考的方式是先看看之前的数组中的上升子序列能不能拼入该元素，然后取能拼入该元素的最长上升子序列长度作为以该元素结尾的最长上升子序列长度。整个问题的答案是dp数组中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 给定数组的最长严格上升子序列的长度。
# @param arr int整型一维数组 给定的数组
# @return int整型
#
class Solution:
    def LIS(self , arr: List[int]) -> int:
        # write code here
        dp = [1 for i in range(len(arr))]

        for i in range(len(arr)):
            tmp_max_length = 1  # 最少是1
            for j in range(i):
                # 往前看看有没有比该元素更小的元素
                # 有的话加入该元素可以组成一个新的更长的严格上升子序列
                if arr[j] < arr[i] and dp[j] + 1 > tmp_max_length:
                        tmp_max_length = dp[j] + 1
            dp[i] = tmp_max_length
        
        return max(dp) if len(dp) > 0 else 0

BM 72 连续子数组的最大和

url：牛客 BM72

考察知识点：动态规划、贪心算法

核心是观察出对于某个位置结尾的和最大子数组，它要么是前一个元素子数组的最大和子数组拼上自己，要么是它本身。那可以写出动态规划版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型
#
class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        # write code here
        dp = [-101 for i in range(len(array))]

        for i in range(len(array)):
            if i == 0:
                dp[i] = array[0]
            else:
                # 对于非第一个元素来说，
                # 最大值要么是前面最长的数组拼上自己
                # 要么是自己本身
                dp[i] = max(dp[i-1]+array[i], array[i])
        
        return max(dp)

当然，也可以取缔掉整个dp数组转而只维护之前的子数组最大值和全局子数组最大值，因为我们只关心dp数组中的上一个值和最大值嘛。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型
#
class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        # write code here
        last_max = array[0]
        max_value = array[0]

        for i in range(1, len(array)):
            # 非最大元素要么是之前的最大值拼上自己要么是自己本身
            if last_max > 0:
                last_max = last_max + array[i]
            else:
                last_max = array[i]
            
            # 判断一下是不是全局最大
            if last_max > max_value:
                max_value = last_max

        return max_value

BM 73 最长回文字符串

url：BM 73

考察知识点：动态规划

先用暴力解法做一遍，关键是判断回文字符串。所谓回文字符串就是正向遍历和反向遍历相同的字符串：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        max_length = 0
        n = len(A)

        for i in range(n):
            for j in range(i, n):
                if (i == 0 and A[i:j+1] == A[j: : -1]) or \
                    (i > 0 and A[i:j+1] == A[j: i-1: -1]):
                    # 回文字符
                    if j - i + 1 > max_length:
                        max_length = j - i + 1
        return max_length

这里判断回文字符串实际上还需要一次循环，因此这个代码复杂度实际来到\(O(n^3)\)了，比较坏。可以使用扩散中心法来确定回文串长度，所谓扩散中心法就是把当前（或当前元素及其前一个元素）当作回文串的中心，然后向两边扩散直到不满足回文串定义。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        max_length = 1
        n = len(A)

        def helper(left: int, right: int):
            # 扩散中心法求回文串长度
            while left >= 0 and right < n and A[right] == A[left]:
                left -= 1
                right += 1
            return right - left - 1

        for i in range(1, n):
            cur = max(helper(i, i), helper(i-1, i))
            if cur > max_length:
                max_length = cur

        return max_length

动态规划的写法稍微有点点麻烦，不过核心是\(dp[i][j]\)代表什么，如果\(dp[i][j]\)代表以i开头，以j结尾的字符子串是否为回文字符串的话就会豁然开朗。当A[i]=A[j]时，就有可能产生回文串。如果\(j-i+1 = 2\)也即字符串长度等于2时，那么肯定是回文串，或者如果\(dp[i+1][j-1]\)是回文串的话那\(dp[i][j]\)也为回文串。有了这个想法，可以编写代码：

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        max_length = 1
        n = len(A)
        dp = [[False]*n for i in range(n)]

        # 基础用例
        for i in range(n):
            dp[i][i] = True
        
        # 注意dp[i][j]代表字符串s的i..j位置是否为回文串
        # 而dp[i][j]需要dp[i+1][j-1]的信息
        # 因此i需要逆序遍历，j需要顺序遍历
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                if A[i] == A[j]:
                    if j -i + 1 == 2 or dp[i+1][j-1]:
                        # 长度为2或者里面的子串是回文串则当前串是回文串
                        dp[i][j] = True
                
                # 更新最大长度
                if dp[i][j] and j - i + 1 > max_length:
                    max_length = j -i + 1

        return max_length

BM 74 数字字符串转化成IP地址

url：牛客 BM74

考察知识点：回溯法

这道题完全不知道怎么用动态规划做，先写了一版用回溯法做的。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        result = []

        def dfs(v, s):
            if len(v) == 4:
                if len(s) == 0:
                    # 这里是合格叶节点
                    result.append(".".join(v))
            else:
                # 深度优先搜索
                for i in range(3):
                    # 判断字符串够不够长
                    if len(s) < i+1:
                        continue
                    
                    region = s[:i+1]
                    next_s = s[i+1: ]

                    # 判断是否为合格的域
                    if len(region) > 1 and region[0] == "0":
                        # 以0开头的数字必须只有一位
                        continue
                    elif int(region) > 255:
                        # 大于255的也不是合格数组
                        continue
                    
                    # 进入下一层
                    v.append(region)
                    dfs(v, next_s)
            # 回溯
            if len(v) > 0:
                del v[-1]
        
        dfs([], s)

        return result

原来不是用动态规划解的，那没事了。补充一种3分割点的循环方法吧。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        result = []

        for i in range(1, 4):
            for j in range(i+1, i+4):
                for k in range(j+1, j+4):
                    # 观察k后面是否越界
                    if k > len(s)-1:
                        continue
                    
                    # 没越界的话划分各个region
                    regions = [s[:i], s[i: j], s[j: k], s[k:]]
                    
                    # 检查各个region是否合法
                    vaild = True
                    for region in regions:
                        if len(region) > 3:
                            vaild = False
                            break
                        elif len(region) > 1 and region[0] == "0":
                            vaild = False
                            break
                        elif int(region) > 256:
                            vaild = False
                            break
                    
                    # 如果每个region都合法就是正确的IP组合
                    if vaild:
                        result.append(".".join(regions))

        return result

9月23日

BM 75 编辑距离（一）

url：牛客 BM75

考察知识点：动态规划

本题的关键就是明白三个编辑操作实际上起到什么作用，插入是往str1中加入一个字符，那么str2的指针后移一位，str1指针不动；删除则是删除str1的一个字符，那么str1指针后移一位，str2指针不动；替换是将str1位置指针元素替换为str2的对应元素，两个字符串指针都后移一位。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str1 string字符串 
# @param str2 string字符串 
# @return int整型
#
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        # write code here
        n = len(str1)
        m = len(str2)
        dp = [[0]*(m+1) for i in range(n+1)]

        for i in range(n+1):
            for j in range(m+1):
                if i == 0:
                    dp[i][j] = j
                elif j == 0:
                    dp[i][j] = i
                else:
                    # 判断两个位置的字符是否相同
                    if str1[i-1] == str2[j-1]:
                        # 相同就什么也不做继续判断下一位
                        dp[i][j] = dp[i-1][j-1]
                    else:
                        # 反之则尝试进行编辑
                        # 分别对应删除、插入和替换操作
                        dp[i][j] = min(dp[i-1][j] + 1, 
                                        dp[i][j-1] + 1, 
                                        dp[i-1][j-1] + 1)
        
        return dp[n][m]

9月25日

BM 76 正则表达式匹配

url：牛客 BM76

考察知识点：正则表达式原理、动态规划

在《算法 （第4版）》的字符串章节有详细介绍正则表达式的原理，系统性地学习了一下可以编写如下代码：

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @param pattern string字符串 
# @return bool布尔型
#
from typing import Union, List

class Digraph:
    """用邻接表储存有向图的数据结构"""
    def __init__(self, V: int):
        self.V = V
        self.E = 0
        # 邻接表
        self.adj = [set() for i in range(V)]
        
    def add_edge(self, v: int, w: int):
        """添加边"""
        self.adj[v].add(w)
        self.E += 1

    def get_adj(self, v: int):
        """获取边的邻接表"""
        return self.adj[v]


class DirectedDFS:
    """判断有向图可达性的API"""
    def __init__(self, G: Digraph, sources: Union[int, List[int]]):
        """sources可以是单个数字，代表单点。也可以是一个列表，代表多点情况下的可达性"""
        self.marked_list = [False for i in range(G.V)]
        # 把单点情况处理为多点
        if isinstance(sources, int):
            sources = [sources]

        # 多点可达性DFS
        for s in sources:
            if not self.marked_list[s]:
                self.dfs(G, s)


    def marked(self, v: int):
        """返回该点是否可达"""
        return self.marked_list[v]

    def dfs(self, G: Digraph, v: int):
        """用深度优先搜索判断可达性"""
        self.marked_list[v] = True
        for w in G.adj[v]:
            if not self.marked_list[w]:
                self.dfs(G, w)


class Solution:
    def match(self , str1: str, pattern: str) -> bool:
        # write code here
        def recognizes(txt: str, G: Digraph, re: List[str]):
            """通过NFA判断文本txt来是否能识别"""
            pc = set()
            dfs = DirectedDFS(G, 0)
            M = len(re)

            for v in range(G.V):
                if dfs.marked(v):
                    pc.add(v)
            
            for i in range(len(txt)):
                # 计算txt[i+1]能够到达的所有NFA状态
                match_list = set()
                for v in pc:
                    if v < M:
                        # 字符或.号就match到v+1
                        if re[v] == txt[i] or re[v] == ".":
                            match_list.add(v+1)
                
                pc = set()
                dfs = DirectedDFS(G, match_list)
                # 计算新一轮可到达状态
                for v in range(G.V):
                    if dfs.marked(v):
                        pc.add(v)
            
            # 判断是否到达接受状态
            if M in pc:
                return True
            else:
                return False

        def NFA(regexp: str):
            """根据给定表达式构造NFA(非确定有限自动机)"""
            ops = []
            re = list(regexp)
            M = len(re)
            G = Digraph(M+1)  # 最后加一个接受状态

            for i in range(M):
                lp = i
                if re[i] == "(" or re[i] == "|":
                    ops.append(i)
                elif re[i] == ")":
                    op_i = ops.pop()
                    if re[op_i] == "|":
                        lp = ops.pop()
                        G.add_edge(lp, op_i+1)
                        G.add_edge(op_i, i)
                    else:
                        lp = op_i
                
                if i < M-1 and re[i+1] == "*":  # 查看下一个字符
                    G.add_edge(lp, i+1)
                    G.add_edge(i+1, lp)
                
                if re[i] == "(" or re[i] == "*" or re[i] == ")":
                    G.add_edge(i, i+1)
            
            return G, re


        def match0(regexp: str, txt: str):
            """返回字符串txt是否满足表达式regexp的结果"""
            G, re = NFA("(" + regexp + ")")
            return recognizes(txt, G, re)

        return match0(pattern, str1)

具体而言，主要使用了非确定有限状态机(NFA)和图的多点可达性性质，如果到达接受状态就是匹配上了，反之没匹配上。

这个是相对完整的正则表达式实现，如果只有通配符"."和闭包"*"的话应该能简单不少。我们看看动态规划版本的实现。

动态规划版本的实现比较巧妙，充分利用了"."和"*"的特性。

如果str1和pattern最末尾都是字符而且不匹配的话，那它们一定不匹配。如果是字符或通配符而且匹配的话，那就看str1[:-1]和pattern[:-1]是否匹配即可。

如果pattern最末尾是"*"号，那么有两种情况，一种就是pattern上一个字符和现在str1最末尾的字符匹配，那么它可以重复至少一次或者不重复，即为其上方和左二位置取或操作。另一种就是pattern上一个字符和现在str1最末尾的字符不匹配，那么它不能重复，就只能取左二位置的值。

实现如下：

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @param pattern string字符串 
# @return bool布尔型
#
class Solution:
    def match(self , str1: str, pattern: str) -> bool:
        # write code here
        n = len(str1)
        m = len(pattern)
        dp = [[False]*(m+1) for i in range(n+1)]

        # 初始值
        dp[0][0] = True
        # 初始化第0列，即pattern为空字符串不为空的情况，初始化的时候本来就是False，初始化已经做到了所以不额外写了
        # 初始化第0行
        for j in range(1, m+1):
            # 空字符串和pattern的匹配情况
            if pattern[j-1] == "*":
                dp[0][j] = dp[0][j-2]

        # 动态规划递推
        for i in range(1, n+1):
            for j in range(1, m+1):
                if pattern[j-1] == "*":
                    # 如果是*而且前一个字符与当前字符相同
                    # 观察其上方和左二的值
                    if pattern[j-2] == "." or pattern[j-2] == str1[i-1]:
                        dp[i][j] = dp[i-1][j] or dp[i][j-2]
                    else:
                        # 反之则只能令该字符重复0次
                        dp[i][j] = dp[i][j-2]
                elif pattern[j-1] == str1[i-1] or pattern[j-1] == ".":
                    # 如果是字符/通配符而且二者匹配时
                    dp[i][j] = dp[i-1][j-1]
                else:
                    # 不是通配符而且二者不匹配
                    dp[i][j] = False
        
        return dp[n][m]

BM 77 最长的括号子串

url：牛客 BM77

考察知识点：动态规划

这题还挺难的，我写了一版好难到\(O(n)\)复杂度，总是要\(O(n^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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return int整型
#
class Solution:
    def longestValidParentheses(self , s: str) -> int:
        # write code here
        n = len(s)
        # dp[i]以0..i-1的最长的格式正确子串
        dp = [0 for i in range(n+1)]
        
        def get_max(end: int):
            # 通过栈来检测该字符串是否合法
            stack = []

            # 倒序检查
            j = end
            max_ = 0
            while j >= 0:
                if s[j] == ")":
                    stack.append(")")
                else:
                    if len(stack) == 0:
                        # 如果不匹配那就直接返回
                        break
                    else:
                        stack.pop()
                        if len(stack) == 0:
                            max_ = end - j + 1 + dp[j]
                            break
                j -= 1

            return max_

        print(n)

        for i in range(1, n+1):
            if s[i-1] == ")":
                dp[i] = get_max(i-1)

        return max(dp)

大致的想法就是倒序检查，如果遇到能闭合的那就说明这段可以不用考虑了，以该元素结尾的最长的子串就是这段的长度加上它后面最长的子串。

这个方法是\(O(n^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
26
27
28
29
30
31
32
33
34
35
36
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return int整型
#
class Solution:
    def longestValidParentheses(self , s: str) -> int:
        # write code here
        n = len(s)
        # dp[i]以0..i-1的最长的格式正确子串
        dp = [0 for i in range(n+1)]
        
        def get_max(end: int):
            # 通过栈来检测该字符串是否合法
            stack = []

            # 倒序检查
            j = end
            if j < 1:
                return 0
            elif s[j] == "(":
                return 0
            elif s[j] == ")" and s[j-1] == "(":
                return dp[j-1] + 2
            elif s[j-1] == ")" and j - dp[j] - 1 >= 0 and s[j-dp[j]-1] == "(":
                return dp[j-dp[j]-1] + dp[j] + 2
            else:
                return 0


        for i in range(1, n+1):
            dp[i] = get_max(i-1)

        return max(dp)

上面这样可以通过所有的测试用例了，然后每次也不涉及到变量j的迭代，因此复杂度被控制在\(O(n)\)了。但是显然如果考虑到以j结尾的最长子串后，实际上不需要这个栈来检验了。跳过已经匹配了的子串后所有的匹配都是朴实的"()"匹配。

因此，我们可以重新写一下这个动态规划版本，不需要这些栈来辅助检查了。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return int整型
#
class Solution:
    def longestValidParentheses(self , s: str) -> int:
        # write code here
        n = len(s)
        # dp[i]以0..i-1的最长的格式正确子串
        dp = [0 for i in range(n+1)]
        
        for i in range(2, n+1):
            # 直接从第二个数开始检查
            if s[i-1] == ")":
                if s[i-2] == "(":
                    # 左右匹配那是最好的，直接跳到后面的子串长度问题
                    dp[i] = dp[i-2] + 2
                else:
                    # 如果不匹配得看跳过已经匹配的子串后是否匹配
                    if i - dp[i-1] - 2 >= 0 and s[i-dp[i-1]-2] == "(":
                        dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
        return max(dp)

有点烦的就是注意为了避免\(i==2\)时的边界检查，我们将dp数组特地申请长了一位。然后这样会导致字符串是从\(i-1\)位开始的，因此在"如果不匹配得看跳过已经匹配的子串后是否匹配"那里实际上是在算\(i-1 - dp[i-1] -1\)的下标。因为\(i-1\)是当前位置，\(dp[i-1]\)是当前位置前一个字符组成的最长子串长度，也即要跳过的字符长度，然后跳过之后再往前一位才是与当前位置匹配的括号位置，因此是\(i-dp[i-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
26
27
28
29
30
31
32
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return int整型
#
class Solution:
    def longestValidParentheses(self , s: str) -> int:
        # write code here
        res = 0
        start = -1
        stack = []
        n = len(s)

        for i in range(n):
            if s[i] == "(":
                stack.append(i)
            else:
                if len(stack) == 0:
                    # 说明左括号不够用，已经不合法了
                    # 只能在这之前匹配
                    start = i
                else:
                    stack.pop()
                    if len(stack) == 0:
                        # 如果是空的那就说明到达了开始位置
                        res = max(res, i - start)
                    else:
                        # 如果非空只能匹配到上一个左括号的位置
                        res = max(res, i-stack[-1])
        return res

BM 78 打家劫舍（一）

url：牛客 BM78

考察知识点：动态规划

我们可以从是否要打劫第i家开始考虑，如果要打劫第i家，必须放弃第i-1家的打劫，只能获取从开始到第i-2家的收益。反之，如果不打劫第i家，那么可以获取从开始到第i-1家的收益。那么走到第i家的最大收益就是前面两种情况的最大值，也即： \[ dp[i] = max(dp[i-1], dp[i-2]+nums[i]) \] 那为了避免处理只有一家或者只有两家之类的边界条件，我们可以人为在nums最开头插入两户虚拟人家，价值都是0，然后直接从第三户开始考虑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def rob(self , nums: List[int]) -> int:
        # write code here
        # 创建两个虚拟的0节点，兼容不同数量
        nums.insert(0, 0)
        nums.insert(0, 0)
        n = len(nums)
        dp = [0 for i in range(n)]

        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        
        return dp[-1]

这样应该是本问题的最优解了。但是如果不插入虚拟节点呢，也即如果没有这两户虚拟人家dp数组该怎么初始化呢？这里有个隐藏的bug，就是如果认为在第2家的时候不打劫第2家，那就亏了！因此会把dp的前两个数组初始化为： \[ dp[0]=nums[0], dp[1]=nums[1] \] 但这实际上埋下祸根，我们考虑一下这样的nums: \([5, 1, 3, 7]\)。按照之前的初始化dp数组为：\([5, 1, 8, 8]\)，所以最后最大结果是8。但打劫第1家和第4家的话结果是12，与结果不同。问题出在哪了呢？走到第2家时非要打劫第2家吗，我们也可以打劫第1家，只要第1家比第2家值钱，那么就应该打劫第1家而放弃第2家。弄清楚这个问题之后可以知道初始化应该是： \[ dp[0]=nums[0],dp[1]=max(nums[0], nums[1]) \] 实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def rob(self , nums: List[int]) -> int:
        # write code here
        # 创建两个虚拟的0节点，兼容不同数量
        n = len(nums)
        dp = [0 for i in range(n)]

        for i in range(n):
            if i == 0:
                dp[0] = nums[0]
            elif i == 1:
                dp[1] = max(nums[0], nums[1])
            else:
                dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        
        return dp[-1]

BM 79 打家劫舍（二）

url：牛客 BM79

考察知识点：动态规划

相比一把场景换成圆形的了。圆形的同时偷第一个和偷最后一个就会冲突。如果分成两个子问题考虑就可以剪断这个环，一是我从第一家走到第n-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
26
27
28
29
30
31
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def rob(self , nums: List[int]) -> int:
        # write code here
        n = len(nums)

        # 分成两部分考虑，一是不偷第一家，考虑1..n的最大值
        # 二是不偷最后一家，考虑0..n-1的最大值
        dp1 = [0] * n
        dp2 = [0] * n

        for i in range(n):
            if i == 0:
                dp2[i] = nums[0]
            elif i == 1:
                dp2[i] = max(dp2[0], nums[i])
                dp1[i] = nums[i]
            elif i == n-1:
                dp2[i] = dp2[i-1]
                dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i])
            else:
                dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i])
                dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i])

        return max(dp1[-1], dp2[-1])

9月26日

BM 80 买卖股票的最好时机（一）

url：牛客 BM80

考察知识点：动态规划、贪心算法

第一眼看上去似乎可以先求前后一天利润的diff数组，买进卖出一次也可以看作是买进那天买入，然后每天执行买入卖出操作直到真正卖出那天。这样问题就转化为了求这个diff数组的最大和子数组了，这个问题我们在BM 72 连续子数组的最大和中解决过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        n = len(prices)
        diff = [0]

        for i in range(1, n):
            diff.append(prices[i] - prices[i-1])

        # 转为求该数组的最大和子数组
        dp = [0 for i in range(n)]

        for i in range(1, n):
            dp[i] = max(dp[i-1]+diff[i], diff[i])
        
        return max(dp)

也可以换一种思路，我们要求的就是最大卖出价和最小买入价的差值，限制就是这个卖出操作不能先于买入操作发生。那我们可以使用两个数组buy和sell，其中buy数组记录前i天的最低买入价，sell数组记录从第i天到最后一天的最高卖出价。然后两个数组做差取最大值即可。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        n = len(prices)
        buy = [0]*n
        sell = [0]*n

        # 顺序求最低买入价
        for i in range(n):
            if i == 0:
                buy[0] = prices[0]
            else:
                buy[i] = min(prices[i], buy[i-1])
        
        # 倒序求最高卖出价
        for j in range(n-1, -1, -1):
            if j == n - 1:
                sell[j] = prices[j]
            else:
                sell[j] = max(prices[j], sell[j+1])

        _max = 0
        for i in range(n):
            if sell[i] - buy[i] > _max:
                _max = sell[i] - buy[i]
        return _max

但是怎么用O(1)的空间复杂度完成这件事呢，根本想不到。

看了题解之后发现一种更清晰的dp：

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        n = len(prices)
        dp = [[0]*2 for i in range(n)]

        # 初始值
        dp[0][1] = -prices[0]

        # 进行操作
        for i in range(1, n):
            # 该天或者之前卖出
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            # 该天或者之前买入
            dp[i][1] = max(dp[i-1][1], -prices[i])
        
        # 返回最后不持股的状态
        return dp[n-1][0]

然后也知道了用O(1)复杂度的方法，就是实际在历史最高卖出价是不需要维护的，因为我们可以记录下之前的最低买入价，然后尝试每天卖出，碰到更大的收益就记下来，最后返回最大收益。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        n = len(prices)
        _max = 0
        best_buy_price = float('inf')

        for i in range(n):
            # 先更新最优买入价
            if best_buy_price > prices[i]:
                best_buy_price = prices[i]
            
            # 查看该天卖出收益是否大于最高收益
            if prices[i] - best_buy_price > _max:
                _max = prices[i] - best_buy_price
        
        return _max

BM 81 买卖股票的最好时机（二）

url：牛客 BM81

考察知识点：动态规划、贪心算法

接着BM80的想法，唯一的区别就是可以卖了再买，所以买入的时候考虑一下之前的卖出后剩下的余额即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算最大收益
# @param prices int整型一维数组 股票每一天的价格
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        n = len(prices)
        dp = [[0]*2 for i in range(n)]

        # 初始值
        dp[0][1] = -prices[0]

        for i in range(1, n):
            # 卖出股票
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            # 买入股票，这里和（一）有区别就是可以多次买入
            # 因此要考虑上次卖出后的余值
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
        
        return dp[n-1][0]

之前diff数组的思想也可以用上，如果允许多次买入卖出的话那也不需要连续子数组了，直接子序列的最大和即可。那啥时候子序列和最大，把数组里面的正数全算上就最大了啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算最大收益
# @param prices int整型一维数组 股票每一天的价格
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        n = len(prices)
        diff = [0]*n

        for i in range(1, n):
            diff[i] = prices[i] - prices[i-1]

        # 可以考虑最大和子序列，这里允许多次买卖所以不需要连续了
        # 实际上就是把diff为正的全加一遍
        _max = 0
        for i in range(1, n):
            if diff[i] > 0:
                _max += diff[i]

        return _max

这时候空间复杂度O(1)的解法也呼之欲出了，如果每次我们都直接算diff[i]然后直接判断要不要进行买卖操作即可O(1)空间复杂度完成问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算最大收益
# @param prices int整型一维数组 股票每一天的价格
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        n = len(prices)
        _max = 0

        for i in range(1, n):
            diff = prices[i] - prices[i-1]
            if diff > 0:
                _max += diff
        
        return _max

BM 82买卖股票的最好时机（三）

url：牛客 BM82

考察知识点：动态规划

在（二）的基础上又加了个次数约束，我们也在（二）的dp基础上加了几个新的框用于考虑不同情况，感觉写得不优雅，但是能解决问题。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 两次交易所能获得的最大收益
# @param prices int整型一维数组 股票每一天的价格
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        n = len(prices)

        # dp[][0]代表不持有股票的初始状态
        # dp[][1]代表第一次持有股票
        # dp[][2]代表第一次持有股票后卖出
        # dp[][3]代表第二次持有股票
        # dp[][4]代表第二次持有股票后卖出
        dp = [[0]*5 for i in range(n)]

        # 初始值
        dp[0][1] = -prices[0]
        # 不可到达的值要置为负无穷
        dp[0][2], dp[0][3], dp[0][4] = -float("inf"), -float("inf"), -float("inf")

        for i in range(1, n):
            dp[i][1] = max(dp[i-1][1], -prices[i])
            dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
            dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])
            dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])
        
        return max(dp[-1][0], dp[-1][2], dp[-1][4])

看了题解，本来以为有啥贪心的方法能达到\(O(1)\)复杂度，结果并不是靠贪心算法来搞的，而是就在原动态规划的基础上就能做得到。因为最后的结果只看最后一行的几个位置，而且迭代的时候也只需要上一行的数据就能迭代，因此可以只用两行dp数组实现。这个想法确实很有启发意义，如果对于任意下一行只依赖上一行而且结果在最后一行的动态规划算法，都可以通过两行dp数组代替那个大的dp矩阵（这样的叫法也许比较合适）来达到缩减空间复杂度的目的。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 两次交易所能获得的最大收益
# @param prices int整型一维数组 股票每一天的价格
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        n = len(prices)

        # dp[0]代表不持有股票的初始状态
        # dp[1]代表第一次持有股票
        # dp[2]代表第一次持有股票后卖出
        # dp[3]代表第二次持有股票
        # dp[4]代表第二次持有股票后卖出
        dp = [0, -prices[0], -float("inf"), -float("inf"), -float("inf")]

        for i in range(1, n):
            # 这里每次只用了dp数组的上一行，因此可以两行dp交替达到O(1)复杂度
            dp_i = [0]*5
            dp_i[1] = max(dp[1], -prices[i])
            dp_i[2] = max(dp[2], dp[1] + prices[i])
            dp_i[3] = max(dp[3], dp[2] - prices[i])
            dp_i[4] = max(dp[4], dp[3] + prices[i])
            dp = dp_i
        
        return max(dp[0], dp[2], dp[4])

BM 83 字符串变形

url：牛客 BM83

考察知识点：字符串

感觉用Python的API可以很容易实现，但是如果不调Python的API真的会很难受！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param n int整型 
# @return string字符串
#
class Solution:
    def trans(self , s: str, n: int) -> str:
        # write code here
        s_list = s.split(" ")
        s_list.reverse()
        s = list(" ".join(s_list))

        for i in range(n):
            if ord(s[i]) >= ord('a') and ord(s[i]) <= ord('z'):
                s[i] = chr(ord(s[i]) - 32)
            elif ord(s[i]) >= ord('A') and ord(s[i]) <= ord('Z'):
                s[i] = chr(ord(s[i]) + 32)
        
        return "".join(s)

不用空格分割手动翻转了一下：

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param n int整型 
# @return string字符串
#
class Solution:
    def trans(self , s: str, n: int) -> str:
        # write code here
        res = []

        # 改变大小写
        for i in range(n):
            if s[i] >= 'a' and s[i] <= 'z':
                res.append(chr(ord(s[i]) - 32))
            elif s[i] >= 'A' and s[i] <= 'Z':
                res.append(chr(ord(s[i]) + 32))
            else:
                res.append(s[i])
        
        # 改变顺序
        res.reverse()

        # 将单词内部的顺序翻转回来
        i, j = 0, 0
        while i < n:
            j = i
            while j < n and res[j] != " ":
                j += 1
            temp_i, temp_j = i, j-1
            while temp_i < temp_j:
                res[temp_i], res[temp_j] = res[temp_j], res[temp_i]
                temp_i += 1
                temp_j -= 1
            i = j + 1
        
        return "".join(res)

BM 84 最长公共前缀

url：BM 84

考察知识点：字符串操作

好像没啥的，在\(O(n*len)\)复杂度下直接遍历就好了。甚至我觉得找最短字符串都有点浪费时间，不对的它自然就失败了。但是如果不先查找最短字符串的话每次还得判断下标是否越界，感觉多次调用len方法早就把找最短字符串偷的懒还回去了，因此感觉还是先找最短字符串比较好，省去内层循环判断越界。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param strs string字符串一维数组 
# @return string字符串
#
class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        # write code here
        n = len(strs)
        
        if n == 0:
            return ""

        # 先查找最短的字符串
        min_i = 0
        min_length = float("inf")

        for i, s in enumerate(strs):
            if len(s) < min_length:
                min_length = len(s)
                min_i = i
        
        # 用最短字符串的每个字符逐个匹配
        target = strs[min_i]
        j = 0
        while j < min_length:
            c = target[j]
            valid = True
            for s in strs:
                if s[j] != c:
                    valid = False
                    break
            if valid:
                j += 1
            else:
                break
        
        # 注意这里第j位是未通过验证或者等于字符串长度的
        # 配合Python的左闭右开字符串切片是刚好的
        return target[:j]

BM 85 验证IP地址

url：牛客 BM85

考察知识点：字符串操作

没啥好说的，按照题目要求验证即可。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 验证IP地址
# @param IP string字符串 一个IP地址字符串
# @return string字符串
#
class Solution:
    def solve(self , IP: str) -> str:
        # write code here
        # 按有没有.分成IPv4, IPv6和Neither
        if "." in IP:
            regions = IP.split(".")

            if len(regions) != 4:
                return "Neither"

            for region in regions:
                if len(region) > 1 and region[0] == "0":
                    return "Neither"
                elif not region.isdigit() or int(region) > 255:
                    return "Neither"
            return "IPv4"
        
        elif ":" in IP:
            regions = IP.split(":")
            if len(regions) != 8:
                return "Neither"
            
            for region in regions:
                if len(region) == 0:
                    return "Neither"
                elif len(region) >= 2 and region[:2] == "00":
                    return "Neither"
                for j in region:
                    if not (j.isdigit() or j in "abcdefABCDEF"):
                        return "Neither"
            
            return "IPv6"
        else:
            return "Neither"

BM 86 大数加法

url：BM 86

考察知识点：字符串操作、模拟

一开始没看到模拟，就直接转成数字然后相加了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算两个数之和
# @param s string字符串 表示第一个整数
# @param t string字符串 表示第二个整数
# @return string字符串
#
class Solution:
    def solve(self , s: str, t: str) -> str:
        # write code here
        if len(s) == 0:
            num_s = 0
        else:
            num_s = int(s)
        
        if len(t) == 0:
            num_t = 0
        else:
            num_t = int(t)

        return num_s + num_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
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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算两个数之和
# @param s string字符串 表示第一个整数
# @param t string字符串 表示第二个整数
# @return string字符串
#
class Solution:
    def solve(self , s: str, t: str) -> str:
        # write code here
        if len(s) < len(t):
            s, t = t, s
        
        n = len(s) - 1
        m = len(t) - 1
        # 加法进位符
        mt9 = False
        res = ""

        for i in range(len(t)):
            s_i = ord(s[n - i]) - ord('0')
            t_i = ord(t[m - i]) - ord('0')

            res_i = s_i + t_i
            # 考虑进位
            if mt9:
                res_i += 1
                mt9 = False
            
            # 考虑结果是否大于等于10
            if res_i >= 10:
                mt9 = True
                res_i -= 10
            
            # 加入结果字符串中
            res = f"{res_i}{res}"
        
        # 考虑剩余位数
        for j in range(len(t), len(s)):
            res_j = ord(s[n - j]) - ord('0')
            if mt9:
                res_j += 1
                mt9 = False
            
            if res_j >= 10:
                mt9 = True
                res_j -= 10
            
            # 加入结果字符串中
            res = f"{res_j}{res}"
        
        # 看看最后是否有剩余进位符
        if mt9:
            return f"1{res}"
        else:
            return res

BM 87 合并两个有序的数组

url：牛客 BM87

考察知识点：数组

比较新颖的地方就是要求就地插入，即后方元素必须右移。

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
#
# 
# @param A int整型一维数组 
# @param B int整型一维数组 
# @return void
#
class Solution:
    def merge(self , A, m, B, n):
        # write code here

        def move_element(start, end):
            # 将剩下的元素向后移动一位
            temp = end
            while temp > start:
                A[temp] = A[temp-1]
                temp -= 1
        
        i = 0
        for j in range(n):
            while i < m + j:    
                if A[i] >= B[j]:
                    # 如果大于则位置i应该放B[j]
                    # 此时算上即将插入的B[j]A数组中总共有m+j个有效元素
                    move_element(i, m+j)
                    A[i] = B[j]
                    break
                i += 1
            # 如果到后面的话直接插进去就行
            A[i] = B[j]

这里有个天才的想法，就是倒过来看！如果倒过来看A的加长部分，我们把两数组的最大元素依次往后挪，就可以轻松做到不挪动已有元素然后将数组he'bing排序到位！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#
# 
# @param A int整型一维数组 
# @param B int整型一维数组 
# @return void
#
class Solution:
    def merge(self , A, m, B, n):
        # write code here
        i, j = m-1, n-1

        for k in range(m+n-1, -1, -1):
            # 倒序合入两数组元素
            if i >= 0 and j >= 0 and A[i] > B[j]:
                A[k] = A[i]
                i -= 1
            elif j >= 0:
                A[k] = B[j]
                j -= 1
            else:
                # 如果i和j都小于0时停止
                break

9月28日

BM 88 判断是否为回文字符串

url：牛客 BM88

考察知识点：双指针

如果是链表的话需要从前往后遍历和从后往前遍历进行比较，如果是字符串这种可以用下标迭代的就用双指针即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 待判断的字符串
# @return bool布尔型
#
class Solution:
    def judge(self , str1: str) -> bool:
        # write code here
        i, j = 0, len(str1)-1

        while i < j:
            if str1[i] != str1[j]:
                return False
            
            i += 1
            j -= 1
        
        return True

BM 89 合并区间

url：牛客 BM89

考察知识点：双指针

一种方式时间复杂度是\(O(n\log n)\)，空间复杂度是\(O(n)\)，\(n\)为区间的数量。

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
# class Interval:
#     def __init__(self, a=0, b=0):
#         self.start = a
#         self.end = b
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param intervals Interval类一维数组 
# @return Interval类一维数组
#
class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        # write code here
        # 先对intervals的起点排序
        intervals.sort(key=lambda x: x.start)
        
        n = len(intervals)
        if n == 0:
            return []
        
        # 双指针合并
        j = 0
        merge_intervals = [intervals[0]]
        for i in range(1, n):
            if intervals[i].start <= merge_intervals[j].end:
                # 这里说明是可合并的
                # 可合并也有两种情况，一种是被上一个区间包含
                # 另外一种是有交集但没有完全包含
                # 所以这里取二者的最大值
                merge_intervals[j].end = max(merge_intervals[j].end, intervals[i].end)
            else:
                # 否则这就是一个新区间
                merge_intervals.append(intervals[i])
                j += 1
        return merge_intervals

10月2日

BM 90 最小覆盖子串

url：牛客 BM90

考察知识点：双指针、字符串、哈希

不知道有啥窍门，先写了一个比较暴力的。即检索以某处字符开头的最小覆盖子串。如果第一个字符不是目标字符串中的字符，那它肯定不是最小覆盖子串，因为去掉它也是可以的，这里应该是有最优子结构在的。然后就是逐个匹配，用哈希表一个个把字符消除掉，一直消除到字典是空的就说明字符攒够了，也即找到了以该位置开头的最小覆盖子串。然后需要找n次，所以最后复杂度应该是每次查找要\(O(n)\)然后要找n次，复杂度为\(O(n^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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        n = len(S)
        T_dict = {}
        for t in T:
            T_dict[t] = T_dict.get(t, 0) + 1

        min_length = 10000
        target_str = ""

        for i in range(n):
            if S[i] not in T_dict:
                continue
            
            char_set = T_dict.copy()

            # 一直往后搜索直到char_set第一次为空
            for j in range(i, n):
                if S[j] in char_set and char_set[S[j]] > 1:
                    char_set[S[j]] -= 1
                elif S[j] in char_set and char_set[S[j]] == 1:
                    char_set.pop(S[j])
                    if len(char_set) == 0:
                        # 空了就说明到以该字符开头的最短位置了
                        if j - i + 1 < min_length:
                            target_str = S[i: j+1]
                            min_length = j - i + 1
                        break
        
        return target_str if min_length < 10000 else ""

10月6日

BM 90 最小覆盖子串

url：牛客 BM90

考察知识点：双指针、字符串、哈希

不知道有啥窍门，先写了一个比较暴力的。即检索以某处字符开头的最小覆盖子串。如果第一个字符不是目标字符串中的字符，那它肯定不是最小覆盖子串，因为去掉它也是可以的，这里应该是有最优子结构在的。然后就是逐个匹配，用哈希表一个个把字符消除掉，一直消除到字典是空的就说明字符攒够了，也即找到了以该位置开头的最小覆盖子串。然后需要找n次，所以最后复杂度应该是每次查找要\(O(n)\)然后要找n次，复杂度为\(O(n^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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        n = len(S)
        T_dict = {}
        for t in T:
            T_dict[t] = T_dict.get(t, 0) + 1

        min_length = 10000
        target_str = ""

        for i in range(n):
            if S[i] not in T_dict:
                continue
            
            char_set = T_dict.copy()

            # 一直往后搜索直到char_set第一次为空
            for j in range(i, n):
                if S[j] in char_set and char_set[S[j]] > 1:
                    char_set[S[j]] -= 1
                elif S[j] in char_set and char_set[S[j]] == 1:
                    char_set.pop(S[j])
                    if len(char_set) == 0:
                        # 空了就说明到以该字符开头的最短位置了
                        if j - i + 1 < min_length:
                            target_str = S[i: j+1]
                            min_length = j - i + 1
                        break
        
        return target_str if min_length < 10000 else ""

接着10月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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        # 收缩窗口法
        # 核心是右指针一直移到满足条件的位置，然后驱动左指针收缩
        # 先建立字符哈希表
        char_dict = {}
        for char in T:
            char_dict[char] = char_dict.get(char, 0) - 1
        
        left, right = 0, 0
        n = len(S)
        min_length = 10001
        target = ""

        while right < n:
            if S[right] in char_dict:
                char_dict[S[right]] += 1
                
                # 验证当前字符串中是否已经包含所有字符了
                complete = True
                for char in char_dict:
                    if char_dict[char] < 0:
                        complete = False

                # 如果当前已经完成的话就收缩左指针
                if complete:
                    while S[left] not in char_dict or char_dict[S[left]] >= 1:
                        if S[left] in char_dict:
                            char_dict[S[left]] -= 1
                        left += 1
                        
                    # 这里就是以right指针结尾的最小覆盖子串了
                    if right - left + 1 < min_length:
                        min_length = right - left + 1
                        target = S[left: right + 1]
            
            right += 1
        
        return target

BM 91 反转字符串

url：牛客 BM91

考察知识点：字符串

还是比较基础的，甚至直接调用reverse就能反转过来，如果不讲究就像这样开个数组拼一下行了。但是对Python来说字符串是不可变的，因此不能像Java那样交换字符串的位置。要新开一个列表的话那就按逆序加入元素即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 反转字符串
# @param str string字符串 
# @return string字符串
#
class Solution:
    def solve(self , str1: str) -> str:
        # write code here
        str_list = []

        for char in str1:
            str_list.insert(0, char)

        return "".join(str_list)

BM 92 最长无重复子数组

url：牛客 BM92

考察知识点：哈希、双指针、数组

其实和BM90很类似，都是对所谓“子数组”的限制。这类问题一般可以抽象成一个滑动窗口，滑动窗口里维护一个字典或者集合，每次指针移动时就在字典或集合里更新现在字符串的状态。实现如下：

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxLength(self , arr: List[int]) -> int:
        # write code here
        T = set()

        left, right = 0, 0
        n = len(arr)
        max_length = 0

        while right < n:
            if arr[right] in T:
                # 如果到这了说明已经出现重复了，要开始统计以right-1结尾的子数组长度了
                # 结算从left到right-1的子数组长度
                if right - left > max_length:
                    max_length = right - left

                # 收缩left指针以便能加入right位置的元素
                while arr[left] != arr[right]:
                    T.remove(arr[left])
                    left += 1
                # 如果left不等于right的话依然要右移一位
                # 但反之则不需要
                if left != right:
                    left += 1
            else:
                # 没有触发相同时就一直向后移动直到退出
                T.add(arr[right])
            right += 1

        # 结束时也需要额外判断一下
        if right - left > max_length:
            max_length = right - left
        
        return max_length

大体做法就是right指针一直移动，直到发现right位置当前元素不能加入子数组为止。这时候以left开头的最长无重复子数组已经找出来了，就是从left到right-1里的所有元素构成的子数组。然后，我们需要收缩left指针，一直收缩到和right位置元素相同的元素位置为止，因为只有去掉这个元素，right位置的元素才能加入子数组。当然也有一个特殊情况，就是left已经缩到和right一样了，那left也不用继续缩了，因为此时就一个元素了。

BM 93 盛水最多的容器

url：牛客 BM93

考察知识点：双指针、数组、贪心算法

这题感觉比较难，一般的思路肯定就是先确定左边的木板，然后再确定右边的木板，遍历的话要\(O(n^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
26
27
28
29
30
31
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param height int整型一维数组 
# @return int整型
#
class Solution:
    def maxArea(self , height: List[int]) -> int:
        # write code here
        n = len(height)
        max_area = 0

        for i, h1 in enumerate(height):
            # 提前退出
            if h1 * (n - i) < max_area:
                continue

            for j in range(n-1, i, -1):
                h = min(h1, height[j])
                l = j - i
                if h * l > max_area:
                    max_area = h * l

                # 如果倒序遇到比它长的右木板了那之后的不用看了
                # 肯定是没这个容器能装的
                if height[j] >= h1 or h1 * (j - i) < max_area:
                    break

        
        return max_area

看了题解之后才知道，这题实际上隐含了一个最优子结构。假设我们已经找到了一个最大容积的容器，那在左边木板的左边部分不可能有不低于左木板的元素，同样右边部分不可能有低于右木板的元素。也就意味着如果我们从两端开始，然后尽可能地保留长边替换短边，是可以得到最优解的。因此，从左右两边开始，每次都把短的那边换成下一个边，往复直到左右指针相遇就可以获得最大容积的容器了。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param height int整型一维数组 
# @return int整型
#
class Solution:
    def maxArea(self , height: List[int]) -> int:
        # write code here
        n = len(height)
        max_area = 0

        left, right = 0, len(height) - 1

        while left < right:
            h = min(height[left], height[right])
            l = right - left

            if h * l > max_area:
                max_area = h * l
            
            # 换边，看哪边短换哪边
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return max_area

这个确实很巧妙，解法出来之后我还感觉会不会不能保证最优，想到容器左右两边都不可能有比它们高的元素了才觉得确实是合理的。

10月9日

BM 94 接雨水问题

url：牛客 BM94

考察知识点：双指针、动态规划

这题的常规思路就是双指针，和牛客 BM93类似，只不过现在底不是平的了，而且是要求所有桶能盛下的水。

可以这样思考，最开始左右两边肯定盛不了水，但它们可以作为桶的边。每次移动高度低的那边指针，并且观察新的位置是否超出桶的高度了，如果超出了则说明进入了一个新的桶，更新桶的高度。否则，就还在那个桶里面，更新雨水的量。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    def maxWater(self , arr: List[int]) -> int:
        # write code here
        n = len(arr)
        left, right = 0, n-1
        water = 0
        # 桶的高度
        h = min(arr[left], arr[right])

        while left < right:
            if arr[left] < arr[right]:
                left += 1
                if arr[left] < h:
                    # 现在仍然在桶里面
                    water += h - arr[left]
                else:
                    # 否则说明要更新桶的高度了
                    h = min(arr[left], arr[right])
            else:
                right -= 1
                if arr[right] < h:
                    # 现在仍然在桶里面
                    water += h - arr[right]
                else:
                    # 否则说明要更新桶的高度了
                    h = min(arr[left], arr[right])
        
        return water

另外一种办法就是先求出最高的柱子，然后以最高柱子为支点将原问题切分为左、右两个子问题。这样的好处就是简化思考，左边的子问题永远不需要动右边的柱子，只需要遇到比左边柱子高的值后将柱子更新过去即可，右边也是同理，不过要倒序遍历一下。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    def maxWater(self , arr: List[int]) -> int:
        # write code here
        n = len(arr)
        water = 0
        # 先找最高的柱子，把问题分解为左右两边的子问题
        top = 0
        for i in range(n):
            if arr[i] > arr[top]:
                top = i
        
        # 考虑top柱子左边的问题
        left = 0
        for i in range(top):
            if arr[i] >= arr[left]:
                # 更新左边的柱子
                left = i
            else:
                water += arr[left] - arr[i]
        
        # 考虑top柱子右边的问题
        right = n-1
        # 倒序遍历
        for i in range(n-2, top, -1):
            if arr[i] >= arr[right]:
                # 更新右边的柱子
                right = i
            else:
                water += arr[right] - arr[i]
        
        return water

动态规划的思路也很巧妙，就是如果一个位置要盛水，那肯定是在它左边和右边都有比它更高的柱子，它能装下的水的高度是左边和右边最高柱子的较小值。那么如果我们用一个dp数组维护该位置左边和该位置右边的最高柱子高度，那计算时只需要求二者的最小值然后判断与当前高度的相对大小关系即可。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    def maxWater(self , arr: List[int]) -> int:
        # write code here
        n = len(arr)

        # dp[i][0]代表i位置前面（不包括自身）最高的柱子
        # dp[i][1]代表i位置后面（不包括自身）最高的柱子
        dp = [[0, 0] for i in range(n)]

        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], arr[i-1])

        for j in range(n-2, -1, -1):
            dp[j][1] = max(dp[j+1][1], arr[j+1])

        water = 0
        
        for i in range(n):
            h = min(dp[i][0], dp[i][1])

            if h > arr[i]:
                water += h - arr[i]

        return water

BM 95 分糖果问题

url：牛客 BM95

考察知识点：贪心算法

先从右边倒数第二个人开始与右边的人比，如果分数多于右边而且糖果不多于右边就更新糖果为右边的糖果数+1。左边也类似，从左边第二个人开始与左边的人比，如果分数多于左边而且糖果不多于左边就更新糖果为左边的糖果数+1。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# pick candy
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def candy(self , arr: List[int]) -> int:
        # write code here
        n = len(arr)
        # 糖果数组
        c = [1] * n

        # 从最右边开始与右边的人比糖果多少
        for i in range(n-2, -1, -1):
            if arr[i] > arr[i+1] and c[i] <= c[i+1]:
                c[i] = c[i+1] + 1
        
        # 再从最左边开始与左边的人比糖果多少
        for j in range(1, n):
            if arr[j] > arr[j-1] and c[j] <= c[j-1]:
                c[j] = c[j-1] + 1
        
        return sum(c)

BM 96 主持人调度（二）

url：牛客 BM95

考察知识点：贪心算法、堆

大体做法就是先按开始时间将活动排序，之后安排主持人。安排过的主持人结束时间记录在一个小根堆中，然后每次要安排新主持人前查看是否有已经结束的主持人将已经结束的主持人重新加回来，之后再分配主持人。

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
import heapq
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算成功举办活动需要多少名主持人
# @param n int整型 有n个活动
# @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
# @return int整型
#
class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        # write code here
        # 按开始时间排序
        startEnd.sort(key=lambda x: x[0])

        # 当前剩余的主持人数量和总主持人数量
        cur_num = 0
        all_num = 0
        end_time = []

        for i in range(n):
            # 上岗时间
            cur = startEnd[i][0]

            # 归还上次活动结束的主持人
            while len(end_time) > 0 and end_time[0] <= cur:
                cur_num += 1
                heapq.heappop(end_time)
            
            # 结算主持人数量
            if cur_num == 0:
                # 如果现在没有主持人就要新增主持人
                all_num += 1
            else:
                # 有的话就先用着现有主持人
                cur_num -= 1
            
            # 记录归还时间
            heapq.heappush(end_time, startEnd[i][1])
        
        return all_num

BM 97 旋转数组

url：牛客 BM97

考察知识点：数组

如果没做过这道题，真的很难想明白旋转数组该怎么转！如果一直挪那个旧数组的话会发现怎么挪也挪不对。

看了题解之后发现3次翻转旧等同于进行这样的旋转了。第一步会把整个数组反转，之后把前m个元素反转，再之后把后n-m个元素反转即可。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 旋转数组
# @param n int整型 数组长度
# @param m int整型 右移距离
# @param a int整型一维数组 给定数组
# @return int整型一维数组
#
class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        # write code here
        # 如果循环次数超过n，则取余数即可
        m = m % n

        # 先把整个数组反转
        for i in range(n // 2):
            a[i], a[n-i-1] = a[n-i-1], a[i]

        # 翻转前m个元素
        for i in range(m // 2):
            a[i], a[m-i-1] = a[m-i-1], a[i]
        
        # 翻转后m+1到n的元素
        for i in range(m, (n+m)//2):
            a[i], a[n+m-i-1] = a[n+m-i-1], a[i]

        return a

BM 98 螺旋矩阵

url：牛客 BM98

考察知识点：数组

用一个矩阵记录是否访问过该元素，然后按向右走、向下走、向左走和向上走的流程来模拟螺旋数组的过程。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 
# @return int整型一维数组
#
class Solution:
    def spiralOrder(self , matrix: List[List[int]]) -> List[int]:
        # write code here
        m = len(matrix)
        if m == 0:
            return []
        n = len(matrix[0])

        visited = [[False]*n for i in range(m)]

        result = []
        i, j = 0, 0

        while i < m and j < n and not visited[i][j]:
            # 先向右走
            while j < n and not visited[i][j]:
                result.append(matrix[i][j])
                visited[i][j] = True
                j += 1
            j -= 1
            
            # 再向下走
            i += 1
            while i < m and not visited[i][j]:
                result.append(matrix[i][j])
                visited[i][j] = True
                i += 1
            i -= 1
    
            # 再向左走
            j -= 1
            while j >= 0 and not visited[i][j]:
                result.append(matrix[i][j])
                visited[i][j] = True
                j -= 1
            j += 1
            
            # 再向上走
            i -= 1
            while i >= 0 and not visited[i][j]:
                result.append(matrix[i][j])
                visited[i][j] = True
                i -= 1
            i += 1

            # 进入下一圈
            j += 1
        return result

每次都只有上下左右的边界会收缩，用visited这样的二维数组来记录是否访问确实有点浪费，实际上我们只需要up, down, right, left四个边界值记录边界即可。

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
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 
# @return int整型一维数组
#
class Solution:
    def spiralOrder(self , matrix: List[List[int]]) -> List[int]:
        # write code here
        m = len(matrix)
        if m == 0:
            return []
        n = len(matrix[0])

        # 上下左右4个边界
        up, down, left, right = 0, m-1, 0, n-1

        result = []
        i, j = 0, 0

        while i <= down and j <= right:
            # 先向右走
            while j <= right:
                result.append(matrix[i][j])
                j += 1
            # 上边界收缩，并复位到最后一列
            up += 1
            j -= 1
            if up > down:
                break
            
            
            # 再向下走
            i += 1
            while i <= down:
                result.append(matrix[i][j])
                i += 1
            # 右边界收缩，并复位到最后一行
            right -= 1
            i -= 1
            if left > right:
                break
    
            # 再向左走
            j -= 1
            while j >= left:
                result.append(matrix[i][j])
                j -= 1
            # 下边界收缩
            down -= 1
            j += 1
            if up > down:
                break
            
            # 再向上走
            i -= 1
            while i >= up:
                result.append(matrix[i][j])
                i -= 1
            # 左边界收缩
            left += 1
            i += 1
            if left > right:
                break

            # 进入下一圈
            j += 1
        return result

BM 99 顺时针旋转矩阵

url：牛客 BM99

考察知识点：数组

一个想法就是转置，之后行翻转就行了。转置时需要新申请一个和原矩阵一样的空间，所以空间复杂度达到\(O(n^2)\)，要操作每一个元素，时间复杂度为\(O(n^2)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param mat int整型二维数组 
# @param n int整型 
# @return int整型二维数组
#
class Solution:
    def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]:
        # write code here
        rotate_mat = []

        for j in range(n):
            rotate_row = [mat[i][j] for i in range(n)]
            rotate_row.reverse()
            rotate_mat.append(rotate_row)
        
        return rotate_mat

另外一种思路就是先进行行翻转，然后我们会发现目标矩阵和现在矩阵的差距就是需要进行反对角线元素的交换，那我们按反对角线进行元素交换即可。这种方法依然需要\(O(n^2)\)级别的时间复杂度，但只需要\(O(1)\)的空间复杂度，因为不涉及新空间的申请。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param mat int整型二维数组 
# @param n int整型 
# @return int整型二维数组
#
class Solution:
    def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]:
        # write code here
        # 先把每行都反转一下
        for mat_row in mat:
            mat_row.reverse()

        # 按反对角线交换元素
        for i in range(n):
            for j in range(n-i-2, -1, -1):
                # 交换关于反对角线对称的元素
                mat[i][j], mat[n-j-1][n-i-1] = mat[n-j-1][n-i-1], mat[i][j]
        
        return mat

看了题解之后发现自己多此一举了，转置不需要新申请数组也可以做呀，就是沿对角线交换，沿对角线交换的下标表示要简单很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param mat int整型二维数组 
# @param n int整型 
# @return int整型二维数组
#
class Solution:
    def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]:
        # write code here
        # 按对角线交换元素就是转置！
        for i in range(n):
            for j in range(i+1, n):
                # 交换关于对角线对称的元素
                mat[i][j], mat[j][i] = mat[j][i], mat[i][j]


        # 先把每行都反转一下
        for mat_row in mat:
            mat_row.reverse()
        
        return mat

10月10日

BM 100 设计LRU缓存

url：牛客 BM100

考察知识点：链表、哈希、模拟

这题的关键在于怎么标识最近最少使用的元素，而且需要以\(O(1)\)的复杂度来更新这个最近最少使用的状态结构。数组肯定是不行的，因为数组删除中间一个元素之后不可避免地会引起后面元素位置的移动。纯链表结构也不行，因为这样更新已有key的状态的时候还需要在链表里找那个元素，这样都会使最坏时间复杂度来到\(O(n)\)级别。

一种可行的办法是使用链表和字典配合来维护最近最少使用的元素，越靠近头节点的元素最近使用得越少，越靠近尾节点的元素最近使用得越频繁。在使用已有key时可用通过哈希表快速获得已有链表节点的引用，并将该节点插入到尾节点前面。

还有一个需要注意的点是LRU结构中，get和set方法都会更新节点使用情况。

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
class ListNode:
    def __init__(self, data) -> None:
        self.next = None
        self.prev = None
        self.key = data

class Solution:
    def __init__(self, capacity: int):
        # write code here
        self.capacity = capacity
        self.key_value_dict = {}
        # 创建最近使用的链表
        self.list_head = ListNode(None)
        self.list_tail = ListNode(None)
        self.list_head.next = self.list_tail
        self.list_tail.prev = self.list_head
        # 记录每个键对应值的引用
        self.key_pos = {}
        # 目前结构中键的数量
        self.num = 0

    def get(self, key: int) -> int:
        # write code here
        # get操作也会刷新缓存!
        if key in self.key_pos:
            update_node = self.key_pos[key]
            # 取出该元素并移到链表末尾
            update_node.next.prev = update_node.prev
            update_node.prev.next = update_node.next
            update_node.next = self.list_tail
            update_node.prev = self.list_tail.prev
            self.list_tail.prev.next = update_node
            self.list_tail.prev = update_node
        return self.key_value_dict.get(key, -1)

    def set(self, key: int, value: int) -> None:
        # write code here
        if self.num == self.capacity and key not in self.key_value_dict:
            # 如果满了要执行删除操作
            # 取出待删除的元素引用
            node = self.list_head.next
            # 先把该元素从链表中取出来，并重新链接剩余链表元素
            node.prev.next = node.next
            node.next.prev = node.prev
            # 删除该元素
            self.key_pos.pop(node.key)
            self.key_value_dict.pop(node.key)
            self.num -= 1
        
        # 为新元素计数并加入链表，为旧元素更新位置
        if key not in self.key_value_dict:
            self.num += 1
            insert_node = ListNode(key)
            # 插入链表尾节点前面
            insert_node.prev = self.list_tail.prev
            insert_node.next = self.list_tail
            self.list_tail.prev.next = insert_node
            self.list_tail.prev = insert_node
            # 更新该元素引用到位置字典中
            self.key_pos[key] = insert_node
        else:
            # 旧元素记得更新链表节点位置到链表尾部
            update_node = self.key_pos[key]
            # 取出链表元素
            update_node.prev.next = update_node.next
            update_node.next.prev = update_node.prev
            # 插入链表尾节点前面
            update_node.next = self.list_tail
            update_node.prev = self.list_tail.prev
            self.list_tail.prev.next = update_node
            self.list_tail.prev = update_node

        # 设置新元素键和值
        self.key_value_dict[key] = value

# Your Solution object will be instantiated and called as such:
# solution = Solution(capacity)
# output = solution.get(key)
# solution.set(key,value)

BM 101 设计LFU缓存结构

url：牛客 BM101

考察知识点：堆、哈希

我的实现是通过一个堆来记录插入元素的优先级，优先级低的就会被删除。为了实现先比较操作次数再比较操作时间，实现一个堆元素的对象并重写其__lt__来自定义比较行为。对于要修改堆中元素优先级的操作（比如获取LFU中已有元素或者更新LFU已有元素），采用Python文档里比较迂回的实现，即标记旧元素为删除后插入一个新的数据元素。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
import heapq
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class HeapElement:
    def __init__(self, call_num: int, call_time: int, key) -> None:
        self.call_num = call_num
        self.call_time = call_time
        self.key = key
        self.delete = False
    
    def __lt__(self, another):
        if not isinstance(another, HeapElement):
            raise Exception(f"无法比较的类型: {type(self)}, {type(another)}")
        
        # 先比较调用次数，调用次数相同之后再比较调用时间
        if self.call_num == another.call_num:
            return self.call_time < another.call_time
        else:
            return self.call_num < another.call_num

class Solution:
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        # 初始化堆，优先级为调用次数
        heap = []
        # 保存堆中元素的引用
        key2heap_element = {}

        # 保存键和值
        key2value = {}
        # 总容量和当前键数目
        capacity, key_num = k, 0

        # 保存结果
        res = []

        for i, op in enumerate(operators):
            if op[0] == 1:
                # 插入操作
                key, value = op[1], op[2]
                # 观察一下当前结构是否已满
                if key_num == capacity and key not in key2value:
                    # 这一步是要先删除元素了
                    heap_element = heapq.heappop(heap)
                    while heap_element.delete:
                        # 一直弹出直到遇到有效元素
                        heap_element = heapq.heappop(heap)
                    # 删除相应元素
                    key2value.pop(heap_element.key)
                    key_num -= 1
                
                if key in key2value:
                    # 如果已经有这个值了需要执行更新操作
                    # 似乎没办法确定位置，因此使用删除标记删除旧元素
                    # 并且新建一个元素插入堆中
                    update_element = key2heap_element.pop(key)
                    new_element = HeapElement(update_element.call_num + 1, i, key)
                    update_element.delete = True
                    # 更新入堆
                    heapq.heappush(heap, new_element)
                    key2heap_element[key] = new_element
                else:
                    # 没有的话执行插入即可
                    new_element = HeapElement(1, i, key)
                    heapq.heappush(heap, new_element)
                    key2heap_element[key] = new_element
                    # 更新键数量
                    key_num += 1
                # 更新值
                key2value[key] = value
            else:
                # 这里是get操作
                key = op[1]

                if key in key2value:
                    # 如果这个键是旧的，那需要更新一下优先级
                    update_element = key2heap_element.pop(key)
                    new_element = HeapElement(update_element.call_num + 1, i, key)
                    update_element.delete = True
                    # 更新入堆
                    heapq.heappush(heap, new_element)
                    key2heap_element[key] = new_element
                
                res.append(key2value.get(key, -1))
        
        return res

这个方法有个不好的点就是这边的堆在需要更新元素频率时是插入新元素并把旧元素标记为删除的。这在插入时依然能保持\(O(\log n)\)的复杂度，但是当需要从堆中弹出元素删除时，可能需要多次弹出被删除的元素，每次堆的弹出操作需要\(O(\log n)\)的时间复杂度，所以最坏情况下可能会超过\(O(\log n)\)的时间复杂度。

题解的做法是维护了一个最小频率的队列，但是从这个队列里面删除元素需要遍历一遍这个队列，假设所有已有元素频率都是1，那么更新一个键的频率的复杂度也可能达到\(O(n)\)，似乎没办法总是保证插入和获取键的最坏时间复杂度控制在\(O(\log n)\)。该方法实现如下：

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class HeapElement:
    def __init__(self, call_num: int, call_time: int, key) -> None:
        self.call_num = call_num
        self.call_time = call_time
        self.key = key
        self.delete = False
    
    def __lt__(self, another):
        if not isinstance(another, HeapElement):
            raise Exception(f"无法比较的类型: {type(self)}, {type(another)}")
        
        # 先比较调用次数，调用次数相同之后再比较调用时间
        if self.call_num == another.call_num:
            return self.call_time < another.call_time
        else:
            return self.call_num < another.call_num

class Solution:
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        # 频率字典
        freq2keys = {}
        key2freq = {}
        # 最低频率
        min_freq = 1

        # 保存键和值
        key2value = {}
        # 总容量和当前键数目
        capacity, key_num = k, 0

        # 保存结果
        res = []

        for i, op in enumerate(operators):
            if op[0] == 1:
                # 插入操作
                key, value = op[1], op[2]
                # 观察一下当前结构是否已满
                if key_num == capacity and key not in key2value:
                    # 这一步是要先删除元素了
                    remove_key = freq2keys[min_freq].pop(0)
                    # 删除相应元素
                    key2value.pop(remove_key)
                    key2freq.pop(remove_key)
                    key_num -= 1
                
                if key in key2value:
                    # 如果已经有这个值了需要执行更新操作
                    # 将数组元素元素从原位置移出
                    freq = key2freq[key]
                    freq2keys[freq].remove(key)
                    # 更新入新数组
                    freq = freq + 1
                    if freq not in freq2keys:
                        freq2keys[freq] = [key]
                    else:
                        freq2keys[freq].append(key)
                    # 更新键频率
                    key2freq[key] = freq
                    # 因为之前可能执行过删除操作，我们需要注意最小
                    # 频率那边还有没有元素，没有的话该元素为最小元素
                    if len(freq2keys[min_freq]) == 0:
                        min_freq = freq
                else:
                    # 没有的话执行插入即可
                    freq = 1
                    if freq not in freq2keys:
                        freq2keys[freq] = [key]
                    else:
                        freq2keys[freq].append(key)
                    # 更新键频率
                    key2freq[key] = freq
                    # 更新最小频率
                    min_freq = freq
                    # 更新键数量
                    key_num += 1
                # 更新值
                key2value[key] = value
            else:
                # 这里是get操作
                key = op[1]

                if key in key2value:
                    # 如果这个键是旧的，那需要更新一下优先级
                    freq = key2freq[key]
                    freq2keys[freq].remove(key)
                    # 更新入新数组
                    freq = freq + 1
                    if freq not in freq2keys:
                        freq2keys[freq] = [key]
                    else:
                        freq2keys[freq].append(key)
                    # 更新键频率
                    key2freq[key] = freq
                    # 因为之前可能执行过删除操作，我们需要注意最小
                    # 频率那边还有没有元素，没有的话该元素为最小元素
                    if len(freq2keys[min_freq]) == 0:
                        min_freq = freq
                
                res.append(key2value.get(key, -1))
        
        return res

结语

到这里牛客的面试TOP101就做完了，感觉做完之后确实也有不小的收获，但是仍然感觉手比较生，有一些问题依旧是比较模糊。

但是后面马上要开题了，精力可能得往写开题报告上转移，可能也没太多时间写面试编程题了。（再说找实习也并不顺利，投了简历半个多月没回应....）

后续（开题报告这阵子事忙完之后）可能我会回顾一下经典的NLP模型论文，尤其是大语言模型LLM路径上的一些关键模型的论文，比如BERT、RoBERTa、GPT、GPT3、T5、OPT、BLOOM、LLAMA等模型的论文，暂定这个系列为“朝花夕拾”吧。（虽然没把握能写完，但先挂在这，以后写不完再想办法）

再之后是代码实现系列，我准备用《三国演义》作为语料，然后实现一个256词表大小的中文nanoGPT，致敬一下Andrej Karpathy大佬的英文莎士比亚nanoGPT教程，也作为GPT这样的Decoder only transformer和自注意力机制的实现的训练。