算法基础课-第二章复盘

一、栈

（一）单调栈

特点：栈内元素以递增或递减的形式排序。
应用：求解下一个更大元素、下一个更小元素、最大子数组和等问题。
题目示例：

代码逻辑：1、采用递增排序的单调栈，栈顶元素是栈内最大元素。2、循环读入列表元素，在单调栈非空的情况下，如果栈顶元素大于当前元素，将栈顶元素弹出栈，直到栈空或者栈顶元素小于当前元素。3、判断是栈空还是找到了小于当前元素的前序栈中元素。若栈空tt=-1，表明前面没有比当前元素小的。4、将当前元素压入栈中。

def main():
    N=100010;s=[0]*N;tt=-1;ans=[]
    n=int(input())
    nums=list(map(int,input().split()))
    for num in nums:
        while tt>-1 and num<=s[tt]:
            tt-=1
        if tt==-1:
            ans.append(-1)
        else:
            ans.append(s[tt])
        tt+=1;s[tt]=num
    print(" ".join(map(str,ans)))   
main()

（二）表达式求值

数据结构：操作符栈op，操作数栈num，字典priority存放操作符的优先级。
方法：1、循环读入串中字符，利用Python中的isdigit方法判断当前字符是否为数字字符，若是数字字符则循环判断累加数值。2、若非数字字符，则为操作符：①若为左括号，无条件压入。②若为右括号，在操作符栈非空且栈顶元素不是左括号的情况下，不断弹出操作符和操作数进行运算。最后将栈顶的左括号弹出栈（在一切操作合法的前提下）。③若为其他操作符，在栈非空且栈顶元素不是左括号的前提下，如果当前读入的操作符的优先级小于等于操作符栈顶元素的优先级，则不断弹出操作符和操作数进行运算。最后将当前读入的操作符压入操作符栈中。③检查操作符栈是否为空，若非空，弹出操作符和操作数进行计算。④最终操作数栈顶元素就是最终值。
题目

from collections import deque
op=deque();num=deque()
priority={'+':0,'-':0,'*':1,'/':1}
def cal():
    global op,num
    ins=op.pop()
    b=num.pop()
    a=num.pop()
    if ins=='+':
        a+=b
    elif ins=='-':
        a-=b
    elif ins=='*':
        a*=b
    else:
        a=int(a/b)
    num.append(a)
def main():
    char=input();i=0
    while i<len(char):
        if char[i].isdigit():
            res=0
            #比如1+23456，其中23456就需要如下操作得到
            while i<len(char) and char[i].isdigit():
                res=res*10+int(char[i])
                i+=1
            #i回退一位，防止后续字符被越位
            i-=1
            num.append(res)
        else:
            if char[i]=='(':
                op.append(char[i])
            elif char[i]==')':
                while op and op[-1]!='(':
                    cal()
                op.pop()
            else:
                while op and op[-1]!='(' and priority[char[i]]<=priority[op[-1]]:
                    cal()
                op.append(char[i])
        i+=1
    while op:
        cal()
    print(num[-1])
main()

二、滑动窗口

实现：使用动态队列实现
应用：

最大/最小子数组问题：例如，找出数组中和最大的连续子数组（最大子数组和问题）。
窗口内元素的统计：比如，给定一个数组和两个整数 k 和 t，找出数组中是否存在长度为 k 的连续子数组，使得子数组内所有元素的和至少为 t。
满足特定条件的子数组：例如，找出数组中所有连续子数组，使得子数组内所有元素的乘积不超过给定的阈值。
字符串问题：比如，找出字符串中最长的不含有重复字符的子串。
数据流问题：在处理数据流时，滑动窗口可以用来计算最近一段时间内的统计数据，如移动平均值。
时间序列分析：在时间序列数据中，滑动窗口可以用来分析一段时间内的趋势或周期性变化。

题目

方法：比如要输出每个窗口内的最小值，就创建一个递增的动态队列，每个队列的队头元素就是每个窗口内的最小值的索引（需要维护边界，保证每个队列的队头是在窗口的左窗台以内）。

代码：

def main():
    n,k=map(int,input().split())
    nums=list(map(int,input().split()))
    q=[0]*1001000
    hh=0;tt=-1;i=0
    while i<n:
        while hh<=tt and q[hh]<i-k+1:
            hh+=1
        while hh<=tt and nums[q[tt]]>=nums[i]:
            tt-=1
        tt+=1;q[tt]=i
        if i-k+1>=0:
            print(nums[q[hh]],end=" ")
        i+=1
    print()
    hh=0;tt=-1;i=0
    while i<n:
        while hh<=tt and q[hh]<i-k+1:
            hh+=1
        while hh<=tt and nums[q[tt]]<=nums[i]:
            tt-=1
        tt+=1;q[tt]=i
        if i-k+1>=0:
            print(nums[q[hh]],end=" ")
        i+=1
main()

三、KMP

应用：字符串匹配，返回匹配的下标值
主要思想：

预处理阶段（构建next数组）：
- 构建next数组，存储模式字符串的前缀和后缀的最长公共元素长度。前缀是指字符串开头到某个位置的子串，后缀是指字符串末尾到某个位置的子串。
- 能够根据next数组的信息，决定模式字符串应该向右滑动多少位。
字符串匹配阶段：
- 算法会使用next数组来指导模式字符串在文本字符串中的滑动。当模式字符串的某个字符与文本字符串的对应字符不匹配时，算法会查看部分匹配表，根据表中存储的信息，将模式字符串向右滑动适当的位数，而不是简单地滑动一位。
- 通过这种方式，KMP算法能够减少不必要的比较，提高字符串搜索的效率。

def main():
    N=100100;ne=[0]*N
    n=int(input())
    #第一个字符对应的下标变成1
    p=[x for x in input()];p=[0]+p
    m=int(input())
    s=[x for x in input()];s=[0]+s
    i=2;j=0
    while i<=n:
        while j and p[i]!=p[j+1]:
            j=ne[j]
        if p[i]==p[j+1]:
            j+=1
        ne[i]=j
        i+=1
    i=1;j=0
    while i<=m:
        while j and s[i]!=p[j+1]:
            j=ne[j]
        if s[i]==p[j+1]:
            j+=1
        if j==n:
            print(i-j,end=" ")
            j=ne[j]
        i+=1
main()

四、Trie树

数据结构：子节点指针数组son，子结点计数数组cnt，结点标记idx。
应用：字符串检索。
性质：

根节点不包含字符：除根节点外，每一个节点都只包含一个字符。‌
路径表示字符串：从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
子节点字符唯一性：每个节点的所有子节点包含的字符都不相同。‌

（一）字符串统计

题目：

思想：从根结点（标记为0）开始追溯，p表示当前结点。对于插入操作，循环读入字符，如果当前结点p的子节点指针数组son中并没有指向当前字符的指针（即son[p][u]=0，其中u可以由当前字符ASCII码减去'a'的ASCII码得到），那么创建结点（idx+=1,son[p][u]=idx，通过idx来标识结点）。如果已存在指针，p指向当前字符的结点。

代码：

N=100100;son=[[0]*26 for _ in range(N)]
cnt=[0]*N;idx=0
def insert(char):
    global son,cnt,idx
    p=0
    for ch in char:
        u=ord(ch)-ord('a')
        if not son[p][u]:
            idx+=1;son[p][u]=idx
        p=son[p][u]
    cnt[p]+=1
def query(char):
    global son,cnt,idx
    p=0;flag=True
    for ch in char:
        u=ord(ch)-ord('a')
        if not son[p][u]:
            flag=False;break
        p=son[p][u]
    if flag:
        print(cnt[p])
    else:
        print(0)
def main():
    global son,cnt,idx
    n=int(input())
    for _ in range(n):
        op,char=input().split()
        if op=='I':
            insert(char)
        else:
            query(char)
main()

（二）最大异或对

题目：

思路： 1、先用Trie树存储每个树的二进制表达，从最高位开始存储。2、再逐个比较得到的每个数的最大异或值，其中最大的数即为输出：初始化res=0，p指向根结点（p=0)。从最高位开始计算，如果存在相应位置i上与该位不同的值（比如0和1），则res加上1左移i位（1<<i)，当前结点指向异或结点。

代码：

N=3000000;s=[[0]*2 for _ in range(N)];idx=0
def insert(num):
    global s,idx
    p=0
    for i in range(30,-1,-1):
        x=num>>i&1
        if not s[p][x]:
            idx+=1;s[p][x]=idx
        p=s[p][x]
def query(num):
    global s,idx
    p=0;res=0
    for i in range(30,-1,-1):
        x=num>>i&1
        if s[p][1-x]:
            res+=1<<i
            p=s[p][1-x]
        else:
            p=s[p][x]
    return res
def main():
    n=int(input())
    nums=list(map(int,input().split()))
    for num in nums:
        insert(num)
    res=0
    for num in nums:
        res=max(res,query(num))
    print(res)
main()

五、并查集

数据结构：祖宗结点数组p
核心思想：1、初始化：每个结点的祖宗结点都是自身，以祖宗结点代表一个集合。2、并集：将其中一个集合的祖宗结点改成另外一个结点的祖宗结点。
核心代码：

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

题目：食物链

方法：1、利用并查集，将有关系的动物（吃与被吃，同类关系）纳入一个集合中，利用不同动物与祖宗结点之间的距离来标识关系（如果1吃2，则(d[1]-d[2]-1)%3=0；如果1和2是同类那么(d[1]-d[2])%3=0)。2、距离说明：①初始化距离全为0。②构建距离关系：（1）如果x与y是同类，目前尚未在同一个集合中，则将x的祖宗结点px改成y的祖宗结点py，即p[px]=py。已知d[x]是x到px的距离，d[y]是y到py的距离。由于将px与py相连，x与y是同类，d[px]=d[y]-d[x]（实际上是(d[y]-(d[px]+d[x]))%3=0,移项后可得到该公式。（2）如果x吃y，同理更改祖宗结点后，d[px]=d[y]-d[x]+1③判断距离关系（真话假话判断）