20210831每日总结

DP、DFS、BFS练手

• DP路径问题复习：给定起点和移动规则，求路径数目

  • LC62 不同路径 状态转移方程、初始化都没问题，双循环的时候，ij的起点从1开始，容易忽略。
  • LC63 不同路径2、LC64最小路径和
  • LC120最小三角形路径和、LC931 下降路径最小和：分类讨论+动态规划
  • LC1289下降路径最小和2：要求不能与上一行重复，需要枚举上一行的不重复位置的值。

• DP问题：没有具体移动规则，可以胡乱移动

  • LC576 出界的路径数：
    • 记忆化DFS：把每次返回的路径数保存到数组里，深搜到这个相同位置，就返回已有的数据
    • 动态规划：三维dp数组，分类讨论边界上和中间的情况。

• LC417 太平洋大西洋水流问题

  • BFS从每一个点开始搜会超时，换个思路，从两种边界开始搜，搜到的点标记，最后找出标记过两次的点即可。

• LC1020 飞地的数量

  • 同样是从边界开始的bfs，遍历一次把连着的标记上，再遍历一次找到没标记过的。

• 剑指offer13 机器人移动

  • 限定好返回条件，编一个取数位的函数，用dfs深搜。

  ACM模式接收输入

  • 输入空格隔开的字符串，用列表接收：

    wordList = input().split()
    

  • 输入多行整数，用列表接收：

    • for循环+append

  • 输入同行整数，用空格隔开，用 列表 / 整数 接收：

    nums = list(map(int, input().split()))  # 多个整数
    x, y = map(int, input().split())  # 两个整数
    

  • 输入整数矩阵，每行用空格隔开，用列表接收：

    grid = []
    for i in range(n):
        grid.append(list(map(int, input().split())))
    

  单调栈题目复习

  • 注意要素
    • 遇到需要操作的元素，用while来判断栈是否为空，待入栈元素能不能一直干掉栈内元素。等到全部干掉（栈为空）或者干不动了（不满足大小关系），才把待入栈元素加进去。
    • 注意辨别栈内加入的是下标，比较元素大小时，加上数组名称不能忘。