题单来自灵神(灵茶山艾府)

分享｜如何科学刷题？

完整题单

• 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
• 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
• 单调栈（基础/矩形面积/贡献法/最小字典序）
• 常用数据结构（枚举技巧/前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
• 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
• 网格图（DFS/BFS/综合应用）
• 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
• 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
• 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
• 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
• 位运算（基础/性质/拆位/试填/恒等式/思维）
• 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

滑动窗口(双指针)

定长滑动窗口

核心思想：去除左元素，添加右元素

while r < len:
    delete left_element
    add right_element
    l++, r++

不定长滑动窗口

核心思想：与定长滑动窗口一样，不过指针的移动是有条件的

for r in range(len)
    while condition is true:
        do something
        update l

相向双指针

窗口内跳过重复元素

15. 三数之和

while l < r:
    if nums[l] + nums[r] > target:
        r -= 1
    elif nums[l] + nums[r] < target:
        l += 1
    else:
        # 这样判断会超时
        # if [x, nums[l], nums[r]] not in arr:
        #     arr.append([x, nums[l], nums[r]])
        arr.append([x, nums[l], nums[r]])
        l += 1
        while l < r and nums[l] == nums[l - 1]: l += 1
        r -= 1
        while l < r and nums[r] == nums[r + 1]: r -= 1

窗口内重复元素的计数

923. 三数之和的多种可能与1577. 数的平方等于两数乘积的方法数计数一样

while l < r:
    if arr[l] + arr[r] > tg:
        r -= 1
    elif arr[l] + arr[r] < tg:
        l += 1
    else:
        index1 = bisect_right(arr, arr[l]) - 1
        index2 = bisect_left(arr, arr[r])
        if arr[l] == arr[r]:
            diff = r - l
            cnt += diff * (diff + 1) // 2
        else:
            cnt += (index1 - l + 1) * (r - index2 + 1)
        l = index1 + 1
        r = index2 - 1

切片后的两种组合

1616. 分割两个字符串得到回文串

def check(a: str, b: str) -> bool:
    l, r = 0, len(a) - 1

    while l < r and a[l] == b[r]:
        l += 1
        r -= 1
        # 为什么这里需要判断a和b中间的片段而不是只判断b的呢？
        # "aejbaal  flrmkswrydwdkdwdyrwskmrlf  qizjezd"
        # "uvebspq  ckawkhbrtlqwblfwzfptanhig  laabjea"
        # 因为a_pre 可以是aejbaal 也可以是aejbaal + flrmkswrydwdkdwdyrwskmrlf
    return isPalind(a[l: r + 1]) or isPalind(b[l: r + 1])

原地修改

核心思想：使用cur存储实际的索引，遍历过程仅需判定不满足condition的情况

for i in range(len):
    if not satisfy condition:
        do something
        cur++