头像

yuchang




离线:7小时前


最近来访(2)
用户头像
AANDA
用户头像
小郑同学


yuchang
1天前

字典树用来维护一个具有相同模式的元素的集合是非常有效的

常用技巧:

  • u = x>>i&1:提取bin(x)的从低往高数第i+1
  • python的取反不能not u,这样输出的结果是布尔量,需要int(not u)得到的才是0和1
n = int(input())
a = [int(x) for x in input().split()]
son = [[0, 0] for _ in range(100010*31)]
idx = 0
res = -1

def insert(x):
    global idx
    p = 0
    for i in range(30, -1, -1):
        u = x>>i&1
        if not son[p][u]:
            idx += 1
            son[p][u] = idx
        p = son[p][u]

def find(x):
    global idx
    p, tmp = 0, 0
    for i in range(30, -1, -1):
        u = x>>i&1
        if not son[p][int(not u)]:
            p = son[p][u]
            tmp = tmp*2
        else:
            p = son[p][int(not u)]
            tmp = tmp*2+1
    return tmp


for i in a:
    insert(i)

for i in a:
    res = max(res, find(i))
print(res)


活动打卡代码 AcWing 143. 最大异或对

yuchang
1天前
n = int(input())
a = [int(x) for x in input().split()]
son = [[0, 0] for _ in range(100010*31)]
idx = 0
res = -1

def insert(x):
    global idx
    p = 0
    for i in range(30, -1, -1):
        u = x>>i&1
        if not son[p][u]:
            idx += 1
            son[p][u] = idx
        p = son[p][u]

def find(x):
    global idx
    p, tmp = 0, 0
    for i in range(30, -1, -1):
        u = x>>i&1
        if not son[p][int(not u)]:
            p = son[p][u]
            tmp = tmp*2
        else:
            p = son[p][int(not u)]
            tmp = tmp*2+1
    return tmp


for i in a:
    insert(i)

for i in a:
    res = max(res, find(i))
print(res)



yuchang
2天前

Trie树

https://www.acwing.com/problem/content/description/837/

①字典

常规哈希思路

n = int(input())
a = {}
for _ in range(n):
    o, query = map(lambda x: x[0], zip(input().split()))
    if o == 'I':
        if query in a:
            a[query] += 1
        else:
            a[query] = 1
    elif o == 'Q':
        if query not in a:
            print(0)
        else:
            print(a[query])

②Trie

难点主要在于理解idx, p的意义以及变化的规律

idx其实是对一棵树上的所有节点进行编号,p是在查找(广义的查找,包括插入和查询)时指向的当前的节点,每次进行比较的是p指向的节点的子节点与当前循环考察的字符

cnt[p]++意思是,通过考察insert函数传入的字符串,指针停留在了编号为p的节点的位置,这说明我们维护的集合中以编号为p结尾的字符串多了一个,又由于树的性质,一个节点能够确定唯一的一条由根节点到其的序列,我们也可以据此维护一个cnt数组来统计字符串集合中的字符串的数量

n = int(input())
N = 100010
son = [[0]*26 for _ in range(N)]
cnt, idx = [0]*N, 0

def insert(s):
    global idx
    p = 0
    for c in s:
        # 如果当前指针指向的节点的儿子没有这个当前需要处理的数组则创建该儿子
        if not son[p][ord(c)-ord('a')]:
            idx += 1
            son[p][ord(c)-ord('a')] = idx
        # p指向下一个节点,注意不能是else,因为你创建一个节点之后需要在此基础上继续插入节点
        p = son[p][ord(c)-ord('a')]
        # 以p为结尾的字符串又多了一个
    cnt[p] += 1

def find(s):
    p = 0
    for c in s:
        # 如果当前节点的儿子没有与当前需要处理的字符的儿子,则说明字符串不存在于集合中,直接返回0
        if not son[p][ord(c) - ord('a')]:
            return 0    
        else:
            p = son[p][ord(c) - ord('a')]
    # 返回以p为结尾的字符串的个数
    return cnt[p]

for _ in range(n):
    o, query = map(lambda x: x[0], zip(input().split()))
    if o == 'I':
        insert(query)
    elif o == 'Q':
        print(find(query))


活动打卡代码 AcWing 835. Trie字符串统计

yuchang
2天前
n = int(input())
a = {}
for _ in range(n):
    o, query = map(lambda x: x[0], zip(input().split()))
    if o == 'I':
        if query in a:
            a[query] += 1
        else:
            a[query] = 1
    elif o == 'Q':
        if query not in a:
            print(0)
        else:
            print(a[query])




yuchang
4天前

KMP

字符串匹配问题的朴素解法是两个指针i j,分别扫描字符串s和模式串p,如果s以下标为i的子串与p完全一样则返回i否则i++, j = 0(子串开头指针后移,模式串指针归零)反复执行一直到扫描完所有子串。

KMP对过程的优化主要体现在模式串每次移动的距离,如果我们能判断下一次模式串的头部应该停在什么地方,而不是每次都向右一格,向右一格......就能降低时间复杂度。根据分析我们得知移动的距离只与模式串本身有关,所以可以使用预处理输入的思想,即构造next数组

谈谈自己对ij意义的理解:在模式串需要移动的时候,i指向的是本次匹配中s第一个不匹配的元素的下标,而j指向的是模式串中本次匹配中最后一个匹配的元素在p中的下标,两者是一前一后的,所以我们在循环匹配的过程中比较的一直都是a[i]p[j+1],所以在模式串移动( j = ne[j] )之后指向的正好是本次模式串正确匹配的最后一位,此时的j+1a[i]又能构成正确的比较关系。

while j and ...的目的是防止初始时a[i] == p[j+1] => a[0] == p[1]是恒成立的

构造next和使用next的板子是几乎一样的

m = int(input())
ne = [0]*(m+1)
p = list(input())
p.insert(0, '\0')
n = int(input())
a = list(input())
a.insert(0, '\0')

i, j = 2, 0
while i <= m:
    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, j = 1, 0

while i <= n:
    while j and a[i] != p[j+1]:
        j = ne[j]
    if a[i] == p[j+1]:
        j += 1
    if j == m:
        print(i-j, end=" ")
        j = ne[j]
    i += 1



活动打卡代码 AcWing 831. KMP字符串

yuchang
4天前

KMP

字符串匹配问题的朴素解法是两个指针i j,分别扫描字符串s和模式串p,如果s以下标为i的子串与p完全一样则返回i否则i++, j = 0(子串开头指针后移,模式串指针归零)反复执行一直到扫描完所有子串。

KMP对过程的优化主要体现在模式串每次移动的距离,如果我们能判断下一次模式串的头部应该停在什么地方,而不是每次都向右一格,向右一格......就能降低时间复杂度。根据分析我们得知移动的距离只与模式串本身有关,所以可以使用预处理输入的思想,即构造next数组

构造next和使用next的板子是几乎一样的

m = int(input())
ne = [0]*(m+1)
p = list(input())
p.insert(0, '\0')
n = int(input())
a = list(input())
a.insert(0, '\0')

i, j = 2, 0
while i <= m:
    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, j = 1, 0

while i <= n:
    while j and a[i] != p[j+1]:
        j = ne[j]
    if a[i] == p[j+1]:
        j += 1
    if j == m:
        print(i-j, end=" ")
        j = ne[j]
    i += 1




yuchang
5天前

单调队列

滑动窗口求窗口最大最小值题目

队列实现的方式:hh=0, tt=-1头尾指针初始化,每次从队尾入队q[++tt],从队首出队hh++,队列判空tt<hh

滑动窗口主要的行为:

顺序访问需要处理的数组的每一个数字,每次访问某个数的时候执行:

  • 判断队首是否收缩:若队列不为空且当前队首距离当前处理元素超过窗口的大小则队首收缩
  • 判断队尾是否收缩:若当前考虑的元素加入队尾后队列无法满足需要的单调性则持续收缩队尾,直到当前考虑的元素加入后满足队列的单调性
  • 将当前考虑的元素加入队尾
  • 取队首元素作为考虑了当前位置后输出的答案

while循环里的判空是为了防止a[q[tt]]数组越界

n, m = map(int, input().split())
a = [int(x) for x in input().split()]
q = [0] * 10001000
hh, tt = 0, -1
for i in range(n):
    # 如果队首出队,队首收缩
    if m < i - q[hh] + 1:
        hh += 1
    while hh <= tt and a[q[tt]] >= a[i]:
        tt -= 1
    tt += 1
    q[tt] = i
    if i+1 >= m:
        print(a[q[hh]], end=" ")
print()
hh, tt = 0, -1
for i in range(n):
    # 如果队首出队,队首收缩
    if m < i - q[hh] + 1:
        hh += 1
    while hh <= tt and a[q[tt]] <= a[i]:
        tt -= 1
    tt += 1
    q[tt] = i
    if i+1 >= m:
        print(a[q[hh]], end=" ")


活动打卡代码 AcWing 154. 滑动窗口

yuchang
5天前
n, m = map(int, input().split())
a = [int(x) for x in input().split()]
q = [0] * 10001000
hh, tt = 0, -1
for i in range(n):
    # 如果队首出队,队首收缩
    if hh <= tt and m < i - q[hh] + 1:
        hh += 1
    while hh <= tt and a[q[tt]] >= a[i]:
        tt -= 1
    tt += 1
    q[tt] = i
    if i+1 >= m:
        print(a[q[hh]], end=" ")
print()
hh, tt = 0, -1
for i in range(n):
    # 如果队首出队,队首收缩
    if hh <= tt and m < i - q[hh] + 1:
        hh += 1
    while hh <= tt and a[q[tt]] <= a[i]:
        tt -= 1
    tt += 1
    q[tt] = i
    if i+1 >= m:
        print(a[q[hh]], end=" ")


活动打卡代码 AcWing 830. 单调栈

yuchang
5天前
n = int(input())
a = [int(x) for x in input().split()]
st, top = [0]*n, 0
res = []
for i in a:
    while top and st[top] >= i:
        top -= 1
    res.append(st[top] if top else -1)
    top += 1
    st[top] = i

print(" ".join(str(x) for x in res))


活动打卡代码 AcWing 829. 模拟队列

yuchang
5天前
N = 100010
q = [0] * N
hh, tt = 0, -1

def main():
    global q, tt, hh
    m = int(input())
    while(m):
        m -= 1
        s = list(input().split(" "))
        opt = s[0]
        if(opt == "push"):
            x = s[1]
            tt += 1
            q[tt] = x
        elif(opt == "pop"):
            hh += 1
        elif(opt == "empty"):
            if(hh <= tt): print("NO")
            else: print("YES")
        else:
            print(q[hh])

main()