算法日记（基础数据结构篇）

2022.12.31
2033.1.1

¶单链表：

模板
习题：
从尾到头打印链表
删除链表的倒数第 N 个结点
反转链表
合并两个有序链表
约瑟夫问题

¶双链表：

模板
习题：
约瑟夫问题
队列安排

---

2023.1.1:洛谷对python选手太不友好了 :-1:
2023.1.2
2023.1.3:达成成就（并没有这个成就）：成为在洛谷某道题用Python成功AC的第一人！！！

¶队列

模板
机器翻译
小组队列

¶单调队列（单调队列优化DP）

¶(在O(n)时间复杂度内动态求有限区间最值)

滑动窗口
最大子序和（不限制长度）
最大子序和（限制长度）
习题：
求m区间内的最小值
扫描
切蛋糕
好消息，坏消息

2023.1.4

¶栈

模拟栈
表达式求值题解 表达式求值Python代码
后缀表达式
表达式括号匹配
表达式的转换
用两个栈实现队列
包含min函数的栈
栈的压入、弹出序列
翻转单词顺序

¶单调栈

模板
仰望奶牛

¶二叉树

二叉树基础知识
二叉树遍历
FBI树
求先序排列
新二叉树
遍历问题
对称二叉树 (这题暴搜py超时，听说能哈希，但是不会……)

2023.1.5 poj里python交不了 :anger:
洛谷通过100题！！！(虽然一半是入门题……)
2023.1.6 一壶茶，一台电脑，一道题，写一天……
“如果PriorityQueue会爆TLE，为什么不去试试heapq呢？”——我自己说的。
为什么要让我遇到py的快读快写板子！！！害得我把之前过不了的题目都重调了一遍！！！一个都过不了！！！还浪费了我学习的时间！！！cnm!!!还我时间！！！

¶哈夫曼树和哈夫曼编码

哈夫曼树和哈夫曼编码基础知识
Safe Or Unsafe
荷马史诗

2023.1.7 嘿嘿嘿，快读板子真好用~~~
2023.1.8 摆烂好几天了……

¶堆

堆基础知识
堆排序
模拟堆
习题：
合并果子
动态中位数
最小函数值
蚯蚓
2023.1.9 学了10天，终于结束一章，太废啦！！！

¶KMP

KMP字符串

朴素做法($O(mn)$)

n=int(input())
p=' '+input()
m=int(input())
s=' '+input()
for i in range(1,m+1):
    flag=True
    for j in range(1,n+1):
        if i+j-1>m or s[i+j-1]!=p[j]:
            flag=False
            break
    if flag:
        print(i-1,end=' ')

KMP($O(m+n)$)

n=int(input())
p=' '+input()
m=int(input())
s=' '+input()
N=100010
ne=[0 for i in range(N)]
#求next过程
j=0
for i in range(2,n+1):
    while j and p[i]!=p[j+1]:
       j=ne[j]
    if p[i]==p[j+1]:
        j+=1
    ne[i]=j

#kmp匹配过程
j=0
for i in range(1,m+1):
    while j and s[i]!=p[j+1]:
        j=ne[j]
    if s[i]==p[j+1]:
        j+=1
    if j==n:
        print(i-n,end=' ')
        j=ne[j]

¶并查集

¶路径压缩($O(1)$~$O(log_2n)$)

def find(x):
    if p[x]!=x:
        p[x]=find(p[x])
    return p[x]

N=100010
p=[0]*N
for i in range(N):
    p[i]=i