2024.04.25_学习日记

天气：晴
学习地点：图书馆
学习时长：10h

学习内容

1. 二叉树高度
   

   class Node:  # 定义树节点的类
       def __init__(self, val=None):
           self.val = val  # 节点的值
           self.left = None  # 指向左子节点的指针
           self.right = None  # 指向右子节点的指针
   
   def buildtree(preorder, inorder):  # 构建树的函数
       if not preorder or not inorder:  # 如果先序或中序列表为空，返回None
           return None
       root_val = preorder[0]  # 根节点的值是先序列表的第一个元素
       index = inorder.index(root_val)  # 找到根节点在中序列表中的索引
       inorder_left = inorder[:index]  # 左子树的中序列表
       inorder_right = inorder[index+1:]  # 右子树的中序列表
       preorder_left = preorder[1:index+1]  # 左子树的先序列表
       preorder_right = preorder[index+1:]  # 右子树的先序列表
       root = Node(root_val)  # 创建一个以根节点值为值的节点
       root.left = buildtree(preorder_left, inorder_left)  # 递归构建左子树
       root.right = buildtree(preorder_right, inorder_right)  # 递归构建右子树
       return root  # 返回子树的根节点
   
   def getheight(root):  # 计算树的高度的函数
       if not root:  # 如果根节点为空，返回0
           return 0
       left = getheight(root.left)  # 计算左子树的高度
       right = getheight(root.right)  # 计算右子树的高度
       return max(left, right) + 1  # 返回左右子树高度的最大值加1
   
   while True:
       try:
           n = int(input())  # 输入n，表示节点数
           preorder = input()  # 输入先序遍历结果
           inorder = input()  # 输入中序遍历结果
           root = buildtree(preorder, inorder)  # 构建树
           print(getheight(root))  # 打印树的高度
       except:  # 捕获异常
           break  # 退出循环

2. 图
   

   def dfs(visited, x, y, graph, curres):
       if x == y:  # 如果当前节点为目标节点 y，则返回当前累积距离
           return curres
       visited[x] = True  # 将当前节点标记为已访问
       minres = float('inf')  # 初始化最小距离为无穷大
       for nxt, distance in graph[x]:  # 遍历当前节点的邻居节点及其距离
           if not visited[nxt]:  # 如果邻居节点未被访问过
               # 递归调用 DFS，并更新最小距离
               minres = min(minres, dfs(visited, nxt, y, graph, curres + distance))
       visited[x] = False  # 恢复当前节点的访问状态
       return minres  # 返回最小距离
   
   while True:
       try:
           n, m = map(int, input().split())  # 输入节点数和边数
           graph = {i: [] for i in range(1, n + 1)}  # 创建图的邻接表
           for i in range(m):  # 读取每条边的起点、终点和距离
               a, b, l = map(int, input().split())
               graph[a].append((b, l))  # 将边加入图的邻接表中
               graph[b].append((a, l))  # 无向图需双向添加
           x, y = map(int, input().split())  # 输入起点和终点
           visited = [False] * (1 + n)  # 初始化节点访问状态
           res = dfs(visited, x, y, graph, 0)  # 调用 DFS 查找最短路径长度
           if res == float('inf'):  # 如果最短路径长度为无穷大
               print('No path')  # 输出无法到达的提示
           else:
               print(res)  # 输出最短路径长度
       except:
           break  # 捕获异常并退出循环

3. 不知道第几次的KMP(lc28)

   class Solution:
       def strStr(self, haystack: str, needle: str) -> int:
           # 定义一个函数用于生成 needle 的 next 数组
           def getnext():
               nlen = len(needle)
               if nlen == 1:
                   return [-1]  # 特殊情况：needle 长度为 1
               nextlist = [0] * nlen  # 初始化 next 数组
               nextlist[0] = -1  # 初始值设为 -1
               nextlist[1] = 0  # next 数组的第二个元素设为 0
               cn = 0  # cn 表示当前 next 数组的索引
               i = 2  # 从第三个元素开始计算 next 数组
               while i < nlen:
                   if needle[i-1] == needle[cn]:
                       nextlist[i] = cn + 1  # 如果当前字符与前缀相等，更新 next 数组的值
                       i += 1
                       cn += 1
                   elif cn > 0:
                       cn = nextlist[cn]  # 回溯到前一个可能的相等前缀
                   else:
                       nextlist[i] = 0  # 如果没有相等前缀，将当前 next 数组值设为 0
                       i += 1
               return nextlist
           
           list1 = getnext()  # 调用函数生成 needle 的 next 数组
           i = 0
           j = 0
           mlen = len(haystack)  # haystack 的长度
           nlen = len(needle)  # needle 的长度
           if mlen < nlen:
               return -1  # 如果 haystack 的长度小于 needle 的长度，直接返回 -1
           while i < mlen and j < nlen:
               if haystack[i] == needle[j]:
                   i += 1
                   j += 1
               elif list1[j] == -1:  # 如果匹配失败且 next 数组的值为 -1，表示 needle 的第一个字符就不匹配
                   i += 1
               else:
                   j = list1[j]  # 回溯到可能的相等前缀的下一个位置
           return i - j if j == nlen else -1  # 返回最终匹配的位置，或者 -1 表示未找到

4. 重复子串(KMP lc459)

   class Solution:
       def repeatedSubstringPattern(self, s: str) -> bool:
           n = len(s)  # 获取字符串 s 的长度
           s1 = s + ' '  # 将字符串 s 后面添加一个空格，方便后续处理
           if n == 1:  # 如果字符串长度为 1，直接返回 False
               return False
           kmplist = [0] * (n + 1)  # 初始化一个长度为 n+1 的列表，用于存储 KMP 算法中的 next 数组
           kmplist[0] = -1  # 初始化第一个元素为 -1
           kmplist[1] = 0  # 初始化第二个元素为 0
           i = 2  # 从第三个元素开始计算 next 数组
           cn = 0  # 初始化当前 next 数组索引为 0
           while i < n + 1:  # 循环计算 next 数组的值
               if s[i - 1] == s[cn]:  # 如果当前字符与前缀相等
                   kmplist[i] = cn + 1  # 更新 next 数组的值
                   i += 1
                   cn += 1
               elif cn > 0:  # 如果当前字符不等于前缀的最后一个字符，但是 cn 大于 0
                   cn = kmplist[cn]  # 回溯到前一个可能的相等前缀
               else:  # 如果以上两个条件都不满足
                   kmplist[i] = 0  # 将当前 next 数组值设为 0
                   i += 1
           # 判断重复子字符串的条件：最后一个元素的值不为 0，并且字符串长度能整除 (长度 - 最后一个元素的值)
           if kmplist[-1] != 0 and (n % (n - kmplist[-1]) == 0):
               return True  # 满足条件则返回 True，表示存在重复子字符串
           else:
               return False  # 否则返回 False，表示不存在重复子字符串