栈

表达式解析

leetcode 1006
逆波兰表达式需要维护数字和操作符两个栈，这题由于操作符顺序是固定的，可以不用操作符栈。
题目乘法和除法是连在一起算的，加法是单独算的，减法减去的值总是乘除的结果，模拟一下即可。
需要注意除法的负数取值。
leetcode 394
可以dfs也可以用栈迭代模拟，新学了这种dfs的方法叫递归下降解析，“下降”指的是我们从最高层级，一层层往下去匹配，是用来处理嵌套解析的一种方式。
特点是维护全局index，相比每次都去搜索匹配右括号（O(n^2)），这种全局index扫描的方法因为每个字符只被处理一次，所以保证了O(n)的线性时间复杂度，效率最高。
注意如

Read more

滑动窗口和双指针

分组循环

一种特殊情况的同向双指针，可以优化一个指针

适用场景

数组会被分割成若干组，每一组处理逻辑是相同的。

核心思想

外层循环负责遍历组之前的准备工作（记录开始位置），和遍历组之后的统计工作（更新答案最大值）。
内层循环负责遍历组，找出这一组最远在哪结束。

模板

n = len(nums)
i = 0
while i < n:
    start = i
    while i < n and ...:
        i += 1
    # 从 start 到 i-1 是一组
    # 下一组从 i 开始，无需 i += 1

题目

leetc

Read more

题意：从起点按序输出唯一路径
python写一直re，后面发现需要使用sys.setrecursionlimit(int(2 * 10**5))扩大python默认递归深度限制，以达到题目要求
邻接表建图用字典的setdefault方法初始化空列表最简洁

import sys
sys.setrecursionlimit(int(2 * 10**5))
n = int(input())
vised = {}
graph = {}
in_degree = {}
for _ in range(n):
    c1, c2 = map(int, input().split())
    graph.s

Read more