Merge branch 'main' of https://github.com/itcharge/LeetCode-Py

itcharge · May 11, 2024 · d8789df · d8789df
2 parents 59a43c9 + 1019ae9
commit d8789df
Show file tree

Hide file tree

Showing 12 changed files with 206 additions and 182 deletions.
diff --git a/Contents/06.String/01.String-Basic/01.String-Basic.md b/Contents/06.String/01.String-Basic/01.String-Basic.md
@@ -20,7 +20,7 @@ str = "Hello World"
 
 在示例代码中，$str$ 是一个字符串的变量名称，`Hello World` 则是该字符串的值，字符串的长度为 $11$。该字符串的表示如下图所示：
 
-![](https://qcdn.itcharge.cn/images/20220117141211.png)
+![字符串](https://qcdn.itcharge.cn/images/20240511114722.png)
 
 可以看出来，字符串和数组有很多相似之处。比如同样使用 **名称[下标]** 的方式来访问一个字符。
 
@@ -116,7 +116,7 @@ ASCII 编码可以解决以英语为主的语言，可是无法满足中文编
 
 字符串的顺序存储结构如下图所示。
 
-![](https://qcdn.itcharge.cn/images/20220118151100.png)
+![字符串的顺序存储](https://qcdn.itcharge.cn/images/20240511114747.png)
 
 如上图所示，字符串的顺序存储中每一个字符元素都有自己的下标索引，下标所以从 $0$ 开始，到 $\text{字符串长度} - 1$ 结束。字符串中每一个「下标索引」，都有一个与之对应的「字符元素」。
 
@@ -130,7 +130,7 @@ ASCII 编码可以解决以英语为主的语言，可是无法满足中文编
 
 字符串的链式存储结构图下图所示。
 
-![](https://qcdn.itcharge.cn/images/20220118152105.png)
+![字符串的链式存储](https://qcdn.itcharge.cn/images/20240511114804.png)
 
 如上图所示，字符串的链式存储将一组任意的存储单元串联在一起。链节点之间的逻辑关系是通过指针来间接反映的。
 

diff --git a/Contents/06.String/02.String-Single-Pattern-Matching/01.String-Brute-Force.md b/Contents/06.String/02.String-Single-Pattern-Matching/01.String-Brute-Force.md
@@ -4,7 +4,7 @@
 >
 > - **BF 算法思想**：对于给定文本串 $T$ 与模式串 $p$，从文本串的第一个字符开始与模式串 $p$ 的第一个字符进行比较，如果相等，则继续逐个比较后续字符，否则从文本串 $T$ 的第二个字符起重新和模式串 $p$ 进行比较。依次类推，直到模式串 $p$ 中每个字符依次与文本串 $T$ 的一个连续子串相等，则模式匹配成功。否则模式匹配失败。
 
-![](https://qcdn.itcharge.cn/images/20220205003716.png)
+![朴素匹配算法](https://qcdn.itcharge.cn/images/20240511154456.png)
 
 ## 2. Brute Force 算法步骤
 

diff --git a/Contents/06.String/02.String-Single-Pattern-Matching/02.String-Rabin-Karp.md b/Contents/06.String/02.String-Single-Pattern-Matching/02.String-Rabin-Karp.md
@@ -32,17 +32,17 @@ RK 算法中的滚动哈希算法主要是利用了 **「Rabin fingerprint 思
 
 比如 `"cat"` 的哈希值就可以表示为：
 
-$\begin{aligned} Hash(cat) &= c \times 26 \times 26 + a \times 26 + t \times 1 \cr &= 2 \times 26 \times 26 + 0 \times 26 + 19 \times 1 \cr &= 1371 \end{aligned}$
+$$\begin{aligned} Hash(cat) &= c \times 26 \times 26 + a \times 26 + t \times 1 \cr &= 2 \times 26 \times 26 + 0 \times 26 + 19 \times 1 \cr &= 1371 \end{aligned}$$
 
 这种按位计算哈希值的哈希函数有一个特点：在计算相邻子串时，可以利用上一个子串的哈希值。
 
 比如说 $cat$ 的相邻子串为 `"ate"`。按照刚才哈希函数计算，可以得出 `"ate"` 的哈希值为：
 
-$\begin{aligned} Hash(ate) &= a \times 26 \times 26 + t \times 26 + e \times 1 \cr &= 0 \times 26 \times 26 + 19 \times 26 + 4 \times 1 \cr &= 498 \end{aligned}$
+$$\begin{aligned} Hash(ate) &= a \times 26 \times 26 + t \times 26 + e \times 1 \cr &= 0 \times 26 \times 26 + 19 \times 26 + 4 \times 1 \cr &= 498 \end{aligned}$$
 
 如果利用上一个子串 `"cat"` 的哈希值计算 `"ate"`，则 `"ate"` 的哈希值为：
 
-$\begin{aligned} Hash(ate) &= (Hash(cat) - c \times 26 \times 26) * 26 + e \times 26 \cr &= (1371 - 2 \times 26 \times 26) \times 26 + 4 \times 1 \cr &= 498 \end{aligned}$
+$$\begin{aligned} Hash(ate) &= (Hash(cat) - c \times 26 \times 26) * 26 + e \times 26 \cr &= (1371 - 2 \times 26 \times 26) \times 26 + 4 \times 1 \cr &= 498 \end{aligned}$$
 
 可以看出，这两种方式计算出的哈希值是相同的。但是第二种计算方式不需要再遍历子串，只需要进行一位字符的计算即可得出整个子串的哈希值。这样每次计算子串哈希值的时间复杂度就降到了 $O(1)$。然后我们就可以通过滚动哈希算法快速计算出子串的哈希值了。
 

diff --git a/Contents/06.String/02.String-Single-Pattern-Matching/03.String-KMP.md b/Contents/06.String/02.String-Single-Pattern-Matching/03.String-KMP.md
@@ -8,7 +8,7 @@
 
 在朴素匹配算法的匹配过程中，我们分别用指针 $i$ 和指针 $j$ 指示文本串 $T$ 和模式串 $p$ 中当前正在对比的字符。当发现文本串 $T$ 的某个字符与模式串 $p$ 不匹配的时候，$j$ 回退到开始位置，$i$ 回退到之前匹配开始位置的下一个位置上，然后开启新一轮的匹配，如图所示。
 
-![](https://qcdn.itcharge.cn/images/20220205003716.png)
+![朴素匹配算法](https://qcdn.itcharge.cn/images/20240511154456.png)
 
 这样，在 Brute Force 算法中，如果从文本串 $T[i]$ 开始的这一趟字符串比较失败了，算法会直接开始尝试从 $T[i + 1]$ 开始比较。如果 $i$ 已经比较到了后边位置，则该操作相当于将指针 $i$ 进行了回退操作。
 
@@ -33,7 +33,7 @@
 
 那么我们就可以将文本串中的 $T[i + 5]$ 对准模式串中的 $p[2]$，继续进行对比。这样 $i$ 就不再需要回退了，可以一直向右移动匹配下去。在这个过程中，我们只需要将模式串 $j$ 进行回退操作即可。
 
-![](https://qcdn.itcharge.cn/images/20220205003701.png)
+![KMP 匹配算法移动过程 1](https://qcdn.itcharge.cn/images/20240511155900.png)
 
 KMP 算法就是使用了这样的思路，对模式串 $p$ 进行了预处理，计算出一个 **「部分匹配表」**，用一个数组 $next$ 来记录。然后在每次失配发生时，不回退文本串的指针 $i$，而是根据「部分匹配表」中模式串失配位置 $j$ 的前一个位置的值，即 $next[j - 1]$ 的值来决定模式串可以向右移动的位数。
 
@@ -59,7 +59,7 @@ KMP 算法就是使用了这样的思路，对模式串 $p$ 进行了预处理
 
 在之前的例子中，当 $p[5]$ 和 $T[i + 5]$ 匹配失败后，根据模式串失配位置 $j$ 的前一个位置的值，即 $next[4] = 2$，我们直接让 $T[i + 5]$ 直接对准了 $p[2]$，然后继续进行比对，如下图所示。
 
-![](https://qcdn.itcharge.cn/images/20220205003647.png)
+![KMP 匹配算法移动过程 2](https://qcdn.itcharge.cn/images/20240511161310.png)
 
 **但是这样移动的原理是什么？**
 
@@ -142,7 +142,7 @@ print(kmp("ababbbbaaabbbaaa", "bbbb"))
 
 - KMP 算法在构造前缀表阶段的时间复杂度为 $O(m)$，其中 $m$ 是模式串 $p$ 的长度。
 - KMP 算法在匹配阶段，是根据前缀表不断调整匹配的位置，文本串的下标 $i$ 并没有进行回退，可以看出匹配阶段的时间复杂度是 $O(n)$，其中 $n$ 是文本串 $T$ 的长度。
-- 所以 KMP 整个算法的时间复杂度是 $O(n + m)$，相对于朴素匹配算法的 $O(n * m)$ 的时间复杂度，KMP 算法的效率有了很大的提升。
+- 所以 KMP 整个算法的时间复杂度是 $O(n + m)$，相对于朴素匹配算法的 $O(n \times m)$ 的时间复杂度，KMP 算法的效率有了很大的提升。
 
 ## 参考资料