2024.6.19刷题记录

目录

一、835. Trie字符串统计 - AcWing题库

二、143. 最大异或对 - AcWing题库

三、836. 合并集合 - AcWing题库

四、837. 连通块中点的数量 - AcWing题库

---

一、835. Trie字符串统计 - AcWing题库

不会，线段树讲解来自题解（AcWing 835. 如何理解单(双)链表，Trie树和堆中的idx？ - AcWing）。代码来自题解（AcWing 835. Trie字符串统计 - AcWing）。

# 线段树
N = int(1e5 + 5)    # 节点数
son = [[0 for _ in range(26)] for _ in range(N)]    # N行26列，每一行是一个节点，26种指向
cnt = [0 for _ in range(N)]     # 节点值，个数
idx = 0     # 新建节点下标
 
# 插入
def insert(x: str):
    global idx
    p = 0   # 从0开始搜索
    for i in range(len(x)):
        t = ord(x[i]) - ord('a')
        if not son[p][t]:
            # 不存在节点，创造一个节点
            # 在没有时才需新建节点
            idx += 1
            son[p][t] = idx
        p = son[p][t]   # 递归下一个节点
    cnt[p] += 1     # 最后一个节点个数加一
 
# 询问
def query(x: str):
    p = 0   # 从0开始搜索
    for i in range(len(x)):
        t = ord(x[i]) - ord('a')
        if not son[p][t]:
            return 0
        p = son[p][t]
    return cnt[p]
    
n = int(input())
for _ in range(n):
    q, s = input().split()
    if q == 'I':
        insert(s)
    else:
        print(query(s))

二、143. 最大异或对 - AcWing题库

不会，思路来自题解（AcWing 143. 最大异或对（好题） - AcWing）和题解（AcWing 143. 最大异或对 - AcWing）。代码参考思路题解自写。

N = int(1e5 + 10)   # 二进制个数
M = N * 31      # 一个十进制数转为二进制最多31位，最高位符号位
# M代表一个数字串二进制可以到多长
son = [[0 for _ in range(2)] for _ in range(M)]
idx = 0
 
def insert(x: int):
    global idx
    p = 0
    for i in range(30, -1, -1):     # 注意30开始
        # 从最高位开始找
        v = x >> i & 1      # 模板，获取第i位的值
        if not son[p][v]:
            idx += 1
            son[p][v] = idx
        p = son[p][v]
        
def search(x: int):
    p = 0
    ans = 0
    for i in range(30, -1, -1):
        # 同样从最高位找
        v = x >> i & 1
        '''
        要理解到字典树本质是树，要从树的思维去思考，而不是数组，数组只是实现
        从最高位开始找，保证当前最大
        从低位开始不一定最大
        因为是树，所以要先走异或路，并且要走到异或路去
        '''
        if son[p][v ^ 1]:
            # 和该位不同的存在
            ans = ans * 2 + 1   # 十进制,该位异或值为1
            p = son[p][v ^ 1]   # 走到异或路
        else:
            # 不存在就找相同的
            ans = ans * 2 + 0
            p = son[p][v]
    return ans
    
n = int(input())
nums = list(map(int, input().split()))
ans = 0
for i in range(n):
    # 边插入，边搜索
    # 每次找当前最大，不用返回去重复找
    # a ^ b == b ^ a
    insert(nums[i])
    ans = max(ans, search(nums[i]))
print(ans)

三、836. 合并集合 - AcWing题库

不会，来自题解（AcWing 836. 基础_并查集_合并集合java_python_c++ - AcWing）和其评论。

# 树
n, m = map(int, input().split())
p = [i for i in range(n + 1)]  # 父节点
 
def find(x: int):
    # 查找父节点并路径压缩
    # 路径压缩是因为我们只需在意是否在同一父节点下
    # 递推而不是递归，递归的最大深度为1000，会爆栈
    global p
    root = x
    # 寻找根节点
    # 根节点的父节点是自己
    while root != p[root]:    # 不是根节点
        root = p[root]
    # 将叶子节点的父节点均指向root
    while x != root:
        nxt = p[x]    # 记录父节点，防止丢失
        p[x] = root
        x = nxt     # 迭代下一个
    return root
 
for _ in range(m):
    q, a, b = input().split()
    a, b = int(a), int(b)
    if q == 'M':
        p[find(a)] = find(b)    # 合并两树
    elif q == 'Q':
        if find(a) == find(b):
            print("Yes")
        else:
            print("No")

四、837. 连通块中点的数量 - AcWing题库

节点数合并处参考题解（AcWing 837. 连通块中点的数量 - AcWing）。 

n, m = map(int, input().split())
p = [i for i in range(n + 1)]
cnt = [1 for _ in range(n + 1)]     # 储存含有多少个子节点
 
def find(x: int):
    global p, cnt
    root = x
    # 寻找root
    while root != p[root]:
        root = p[root]
    while x != root:
        nxt = p[x]
        p[x] = root
        x = nxt
    return root
 
for _ in range(m):
    q = list(input().split())
    if q[0] == 'C':
        a, b = int(q[1]), int(q[2])
        if find(a) == find(b):
            continue
        # 合并根节点时，合并子节点数，b祖先节点合并到a祖先节点上
        cnt[find(a)] += cnt[find(b)]    
        p[find(b)] = find(a)
    elif q[0] == 'Q1':
        a, b = int(q[1]), int(q[2])
        print("Yes" if find(a) == find(b) else "No")
    elif q[0] == 'Q2':
        a = int(q[1])
        print(cnt[find(a)])

 完

感谢你看到这里！一起加油吧！