笺札

滚动哈希 基本概念 滚动哈希是一种高效的字符串匹配算法，常用于解决模式匹配、最长公共子串等问题。它通过哈希函数快速计算字符串的哈希值，并利用前后子串的关系，在常数时间内更新哈希值。 基本原理 滚动哈希的核心思想是将字符串映射为整数，并使用这个整数进行比较。常见的哈希函数包括直接哈希法、幂次哈希法和旋转哈希法。滚动哈希利用字符串前后子串的关系，只需 O(1) 的时间即可计算新的哈希值。 具体来说，滚动哈希的计算公式如下： hash(s)=(s[0]⋅basen−1+s[1]⋅basen−2+s[2]⋅basen−3+...+s[n−1])modmodhash(s)=(s[0]⋅basen−1+s[1]⋅basen−2+s[2]⋅basen−3+...+s[n−1])modmod hash(s)=(s[0]⋅basen−1+s[1]⋅basen−2+s[2]⋅basen−3+...+s[n−1])modmod 其中，hash(si…i+m−1) 表示从第 i 个字符开始长度为 m 的子串的哈希值，d 表示一个常数（通常取较大的质数，如 31、131 或 13331），si 和 ...

二叉堆实现的优先队列 二叉堆的定义 二叉堆是一种完全二叉树，分为两类： 大顶堆：每个节点值 ≥ 子节点值 小顶堆：每个节点值 ≤ 子节点值 基本操作 优先队列主要有两种操作： 入队（heappush）：将新元素加到数组末尾，然后从下往上调整，恢复堆结构。 出队（heappop）：将堆顶元素与末尾元素交换，弹出末尾元素，再对新堆顶自上而下调整，恢复堆结构。 内部实现： 使用heapq模块实现优先队列 heapq.heappush(heap, item)：将元素 item 压入堆 heap 中，保持堆结构。 heapq.heappop(heap)：弹出并返回堆中的最小元素。 注意事项： heapq 默认是小顶堆，即每次弹出的是最小值。 如果需实现「大顶堆」（每次弹出最大优先级元素），可将优先级取负数存入堆中。 为保证当优先级相同时元素的入队顺序，通常可额外存储一个自增索引。 123456789101112import heapqclass PriortyQueue: def __init__(self): self.queue=[] self.index=0 ...

Rabin Karp 算法 基本概念 Rabin Karp（RK）算法：由 Michael Oser Rabin 与 Richard Manning Karp 于 1987 年提出，是一种利用哈希快速筛查匹配起点的单模式串匹配算法。 Rabin Karp 算法核心思想：给定文本串 T 与模式串 p，先计算 p 的哈希值，再对T的所有长度为 m=∣p∣的子串高效计算哈希。借助「滚动哈希」在 O(1)时间更新相邻子串的哈希，用哈希相等作为快速筛选，仅在相等时再逐字符比对以排除哈希冲突。 算法步骤 设n=∣T∣、m=∣p∣ 计算模式串哈希H(p) 计算文本首个长度为m的字串T[0,m−1]​T[0,m−1]​T[0,m−1]​的哈希 H(T[0,m−1])H(T[0,m−1])H(T[0,m−1]),并用滚动哈希依次得到其余n-m个相邻字串的哈希 逐一比较H(T[i,i+m−1])H(T_{[i,i+m-1]})H(T[i,i+m−1]​)与H(p): 如果不相等，跳过 如果相等，逐字符核验：完全相同则返回起点i，否则继续 全部位置检查后仍未匹配，返回-1 内部实...

KMP算法 基本概念 KMP 算法（全称 Knuth-Morris-Pratt 算法）：由 Donald Knuth、James H. Morris 和 Vaughan Pratt 三位学者于 1977 年联合提出，并以他们的名字命名。 KMP 算法核心思想：在字符串匹配过程中，当文本串 TT 的某个字符与模式串 pp 发生不匹配时，充分利用已匹配的前缀信息，通过预处理得到的「部分匹配表」（即 next 数组），避免文本指针的回退，从而高效地减少不必要的比较次数，实现快速匹配。 算法步骤 next数组的构造 假设模式串为p。用left表示当前已知的最大相等前后缀的长度，right 表示当前正在处理的字符下标。初始时left = 0,right = 1 比较 p[left]p[left]p[left]和p[right]p[right]p[right]: 如果p[left]==p[right]p[left]==p[right]p[left]==p[right],当前前后缀可以继续延长。此时left+1,将next[right]next[right]next[right...

Brute Force算法 基本概念 Brute Force 算法：简称为 BF 算法，也可以叫做「朴素匹配算法」。 Brute Force 算法核心思想：将模式串 pp 依次与文本串 TT 的每个起点对齐，从左到右逐字符比对；相等则继续，不等则把对齐起点右移一位，直到匹配成功或遍历完文本。 算法步骤 设文本串T长度为n，模式串p长度为m 设T的每个七点0…n-m依次与p对齐，逐字符比较：如果相等则继续，不相等则起点右移一位、p归零 如果某次对齐能把p的全部字符匹配完，则返回该起点；否则无解 内部实现： 1234567891011121314def bruteForce(T:str,p:str)->int: n,m=len(T),len(p) i,j=0,0 while i < n and j < m: if T[i]==p[j]: i+=1 j+=1 else: i=i-j+1 j=0 if j==m: return i-j else: return -1 复杂度分析 BF 简单直观，但因不匹配时会完全回退、重...

📊 第13周总结（3月23日 - 3月29日） 一、核心数据统计 维度 本周数据 上周对比 备注 专注时长（小时） 约15小时 ↑ 3h 按每天2.5小时，6天计算 代码提交次数 约18次 持平 每个题解对应一次完整提交 论文/书籍阅读 《原则》第三部分 — 继续阅读 二、重点项目复盘 1. 算法学习/项目 本周进展： 字符串匹配三连击：完整实现了 BF、RK、KMP 三种算法，并配套 LeetCode 28 题「找出字符串中第一个匹配项的下标」。你不仅写了代码，还为每种算法建立了独立的概念笔记（含原理、步骤、实现、复杂度、应用场景），这是从“会做”到“会讲”的关键一跃。 哈希表专题：完成了 6 道哈希表相关题解（存在重复元素I/II、两个数组的交集I/II、有效的数独、设计哈希映射），并撰写了 哈希表.md 概念文档，覆盖了哈希函数、冲突解决、核心操作。 优先队列/堆专题：完成了 3 道堆相关题解（数组中的第K个最大元素、前K个高频元素、根据字符出现频率排序），并撰写了 优先队列.md 和 二叉堆实现的优先队列.md，对比了数组/链表/堆...

找出字符串中第一个匹配项的下标 🎯 问题描述（来源于LeetCode） 描述： 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。 说明： 1 <= haystack.length, needle.length <= 104 haystack 和 needle 仅由小写英文字符组成 示例： 示例 1： 1234输入：haystack = "sadbutsad", needle = "sad"输出：0解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。 示例 2： 123输入：haystack = "leetcode", needle = "leeto"输出：-1解释："leeto" 没有在 "leetcode&...

重复的子字符串 🎯 问题描述（来源于LeetCode） 描述： 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。 说明： 1 <= s.length <= 104 s 由小写英文字母组成 示例： 示例 1： 123输入: s = "abab"输出: true解释: 可由子串 "ab" 重复两次构成 示例 2： 12输入: s = "aba"输出: false 💻 解题思路 思路1：巧思（看题解） 思路1：代码实现 123class Solution: def repeatedSubstringPattern(self, s: str) -> bool: return (s+s).find(s,1)!=len(s) 思路1：📊 性能分析 提交结果 运行时间：0ms击败100.00% 内存消耗：19.07MB击败55.90% 复杂度验证 时间复杂度：O(N)O(N)O(N) 空间复杂度：O(N)O(N)O(N) ...

反转字符串中的单词III 🎯 问题描述（来源于LeetCode） 描述： 给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。 说明： 1 <= s.length <= 5 * 104 s 包含可打印的 ASCII 字符。 s 不包含任何开头或结尾空格。 s 里 至少 有一个词。 s 中的所有单词都用一个空格隔开。 示例： 示例 1： 12输入：s = "Let's take LeetCode contest"输出："s'teL ekat edoCteeL tsetnoc" 示例 2： 12输入： s = "Mr Ding"输出："rM gniD" 💻 解题思路 思路1：遇到一个单词反转一个单词 思路1：代码实现 12345678910111213141516class Solution: def reverseString(self, s_list: List[str], le...

验证回文串 🎯 问题描述（来源于LeetCode） 描述： 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。 说明： 1 <= s.length <= 2 * 105 s 仅由可打印的 ASCII 字符组成 示例： 示例 1： 123输入: s = "A man, a plan, a canal: Panama"输出：true解释："amanaplanacanalpanama" 是回文串。 示例 2： 1234输入：s = " "输出：true解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。由于空字符串正着反着读都一样，所以是回文串。 💻 解题思路 思路1：对撞指针 思路1：代码实现 1234567891011121314class Solution:...