Skip to content

Commit 4b87b62

Browse files
SnailclimbSnailclimb
committed
docs: 统一计算机基础文档排版 — 提升阅读一致性
1 parent 5790fb2 commit 4b87b62

26 files changed

Lines changed: 245 additions & 245 deletions

‎docs/cs-basics/algorithms/10-classical-sorting-algorithms.md‎

Lines changed: 14 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -60,7 +60,7 @@ head:
6060

6161
非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
6262

63-
## 冒泡排序 (Bubble Sort)
63+
## 冒泡排序（Bubble Sort）
6464

6565
冒泡排序是一种简单的排序算法。它重复地遍历要排序的序列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历序列的工作是重复地进行直到没有再需要交换为止，此时说明该序列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端。
6666

@@ -114,7 +114,7 @@ public static int[] bubbleSort(int[] arr) {
114114
- **空间复杂度**：$O(1)$
115115
- **排序方式**：In-place
116116

117-
## 选择排序 (Selection Sort)
117+
## 选择排序（Selection Sort）
118118

119119
选择排序是一种简单直观的排序算法，无论什么数据进去都是 $O(n^2)$ 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
120120

@@ -161,7 +161,7 @@ public static int[] selectionSort(int[] arr) {
161161
- **空间复杂度**：$O(1)$
162162
- **排序方式**：In-place
163163

164-
## 插入排序 (Insertion Sort)
164+
## 插入排序（Insertion Sort）
165165

166166
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 $O(1)$ 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
167167

@@ -211,9 +211,9 @@ public static int[] insertionSort(int[] arr) {
211211
- **空间复杂度**：$O(1)$
212212
- **排序方式**：In-place
213213

214-
## 希尔排序 (Shell Sort)
214+
## 希尔排序（Shell Sort）
215215

216-
希尔排序是希尔 (Donald Shell) 于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为递减增量排序算法，同时该算法是冲破 $O(n^2)$ 的第一批算法之一。
216+
希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为递减增量排序算法，同时该算法是冲破 $O(n^2)$ 的第一批算法之一。
217217

218218
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序。
219219

@@ -267,9 +267,9 @@ public static int[] shellSort(int[] arr) {
267267
- **时间复杂度**：最佳：$O(nlogn)$，最差：$O(n^2)$，平均：$O(nlogn)$
268268
- **空间复杂度**：$O(1)$
269269

270-
## 归并排序 (Merge Sort)
270+
## 归并排序（Merge Sort）
271271

272-
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 (Divide and Conquer) 的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 - 路归并。
272+
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 - 路归并。
273273

274274
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 $O(nlogn)$ 的时间复杂度。代价是需要额外的内存空间。
275275

@@ -350,7 +350,7 @@ public static int[] merge(int[] arr_1, int[] arr_2) {
350350
- **时间复杂度**：最佳：$O(nlogn)$，最差：$O(nlogn)$，平均：$O(nlogn)$
351351
- **空间复杂度**：$O(n)$
352352

353-
## 快速排序 (Quick Sort)
353+
## 快速排序（Quick Sort）
354354

355355
快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。
356356

@@ -439,7 +439,7 @@ class Solution {
439439
- **时间复杂度**：最佳：$O(nlogn)$，最差：$O(n^2)$，平均：$O(nlogn)$
440440
- **空间复杂度**：$O(logn)$
441441

442-
## 堆排序 (Heap Sort)
442+
## 堆排序（Heap Sort）
443443

444444
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足**堆的性质**：即**子结点的值总是小于（或者大于）它的父节点**。
445445

@@ -528,11 +528,11 @@ public static int[] heapSort(int[] arr) {
528528
- **时间复杂度**：最佳：$O(nlogn)$，最差：$O(nlogn)$，平均：$O(nlogn)$
529529
- **空间复杂度**：$O(1)$
530530

531-
## 计数排序 (Counting Sort)
531+
## 计数排序（Counting Sort）
532532

533-
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，**计数排序要求输入的数据必须是有确定范围的整数**。
533+
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，**计数排序要求输入的数据必须是有确定范围的整数**。
534534

535-
计数排序 (Counting sort) 是一种稳定的排序算法。计数排序使用一个额外的数组 `C`，其中第 `i` 个元素是待排序数组 `A` 中值等于 `i` 的元素的个数。然后根据数组 `C` 来将 `A` 中的元素排到正确的位置。**它只能对整数进行排序**。
535+
计数排序（Counting sort）是一种稳定的排序算法。计数排序使用一个额外的数组 `C`，其中第 `i` 个元素是待排序数组 `A` 中值等于 `i` 的元素的个数。然后根据数组 `C` 来将 `A` 中的元素排到正确的位置。**它只能对整数进行排序**。
536536

537537
### 算法步骤
538538

@@ -608,7 +608,7 @@ public static int[] countingSort(int[] arr) {
608608
- **时间复杂度**：最佳：$O(n+k)$，最差：$O(n+k)$，平均：$O(n+k)$
609609
- **空间复杂度**：$O(k)$
610610

611-
## 桶排序 (Bucket Sort)
611+
## 桶排序（Bucket Sort）
612612

613613
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
614614

@@ -691,7 +691,7 @@ public static List<Integer> bucketSort(List<Integer> arr, int bucket_size) {
691691
- **时间复杂度**：最佳：$O(n+k)$，最差：$O(n^2)$，平均：$O(n+k)$
692692
- **空间复杂度**：$O(n+k)$
693693

694-
## 基数排序 (Radix Sort)
694+
## 基数排序（Radix Sort）
695695

696696
基数排序也是非比较的排序算法，对元素中的每一位数字进行排序，从最低位开始排序，复杂度为 $O(n×k)$，$n$ 为数组长度，$k$ 为数组中元素的最大的位数；
697697

‎docs/cs-basics/algorithms/linkedlist-algorithm-problems.md‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -175,9 +175,9 @@ public class Solution {
175175
176176
### 问题分析
177177

178-
> **链表中倒数第 k 个节点也就是正数第(L-K+1)个节点，知道了这一点，这一题基本就没问题！**
178+
> **链表中倒数第 k 个节点也就是正数第（L-K+1）个节点，知道了这一点，这一题基本就没问题！**
179179
180-
首先两个节点/指针，一个节点 node1 先开始跑，指针 node1 跑到 k-1 个节点后，另一个节点 node2 开始跑，当 node1 跑到最后时，node2 所指的节点就是倒数第 k 个节点也就是正数第(L-K+1)个节点。
180+
首先两个节点/指针，一个节点 node1 先开始跑，指针 node1 跑到 k-1 个节点后，另一个节点 node2 开始跑，当 node1 跑到最后时，node2 所指的节点就是倒数第 k 个节点也就是正数第（L-K+1）个节点。
181181

182182
### Solution
183183

@@ -250,15 +250,15 @@ public class Solution {
250250

251251
### 问题分析
252252

253-
我们注意到这个问题可以容易地简化成另一个问题：删除从列表开头数起的第 (L - n + 1)个结点，其中 L 是列表的长度。只要我们找到列表的长度 L，这个问题就很容易解决。
253+
我们注意到这个问题可以容易地简化成另一个问题：删除从列表开头数起的第（L - n + 1）个结点，其中 L 是列表的长度。只要我们找到列表的长度 L，这个问题就很容易解决。
254254

255255
![图 1. 删除列表中的第 L - n + 1 个元素](https://oss.javaguide.cn/github/javaguide/cs-basics/algorithms/94354387.jpg)
256256

257257
### Solution
258258

259259
**两次遍历法**
260260

261-
首先我们将添加一个 **哑结点** 作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中，我们找出列表的长度 L。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 (L - n) 个结点那里。**我们把第 (L - n)个结点的 next 指针重新链接至第 (L - n + 2)个结点，完成这个算法。**
261+
首先我们将添加一个 **哑结点** 作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中，我们找出列表的长度 L。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第（L - n）个结点那里。**我们把第（L - n）个结点的 next 指针重新链接至第（L - n + 2）个结点，完成这个算法。**
262262

263263
```java
264264
/**
@@ -299,7 +299,7 @@ public class Solution {
299299

300300
**进阶——一次遍历法：**
301301

302-
> 链表中倒数第 N 个节点也就是正数第(L - n + 1)个节点。
302+
> 链表中倒数第 N 个节点也就是正数第（L - n + 1）个节点。
303303
304304
其实这种方法就和我们上面第四题找“链表中倒数第 k 个节点”所用的思想是一样的。**基本思路就是：** 定义两个节点 node1、node2；node1 节点先跑，node1 节点跑到第 n+1 个节点的时候，node2 节点开始跑。当 node1 节点跑到最后一个节点时，node2 节点所在的位置就是第（L - n）个节点（L 代表总链表长度，也就是倒数第 n + 1 个节点）。
305305

‎docs/cs-basics/algorithms/the-sword-refers-to-offer.md‎

Lines changed: 15 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -69,14 +69,14 @@ public int Fibonacci(int n) {
6969

7070
正常分析法：
7171

72-
> a.如果两种跳法，1 阶或者 2 阶，那么假定第一次跳的是一阶，那么剩下的是 n-1 个台阶，跳法是 f(n-1);
73-
> b.假定第一次跳的是 2 阶，那么剩下的是 n-2 个台阶，跳法是 f(n-2)
74-
> c.由 a，b 假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
72+
> a.如果两种跳法，1 阶或者 2 阶，那么假定第一次跳的是一阶，那么剩下的是 n-1 个台阶，跳法是 f（n-1）;
73+
> b.假定第一次跳的是 2 阶，那么剩下的是 n-2 个台阶，跳法是 f（n-2）
74+
> c.由 a，b 假设可以得出总跳法为: f(n) = f（n-1） + f（n-2）
7575
> d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
7676
7777
找规律分析法：
7878

79-
> f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5， 可以总结出 f(n) = f(n-1) + f(n-2)的规律。但是为什么会出现这样的规律呢？假设现在 6 个台阶，我们可以从第 5 跳一步到 6，这样的话有多少种方案跳到 5 就有多少种方案跳到 6，另外我们也可以从 4 跳两步跳到 6，跳到 4 有多少种方案的话，就有多少种方案跳到 6，其他的不能从 3 跳到 6 什么的啦，所以最后就是 f(6) = f(5) + f(4)；这样子也很好理解变态跳台阶的问题了。
79+
> f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5，可以总结出 f(n) = f（n-1） + f（n-2） 的规律。但是为什么会出现这样的规律呢？假设现在 6 个台阶，我们可以从第 5 跳一步到 6，这样的话有多少种方案跳到 5 就有多少种方案跳到 6，另外我们也可以从 4 跳两步跳到 6，跳到 4 有多少种方案的话，就有多少种方案跳到 6，其他的不能从 3 跳到 6 什么的啦，所以最后就是 f(6) = f(5) + f(4)；这样子也很好理解变态跳台阶的问题了。
8080
8181
**所以这道题其实就是斐波那契数列的问题。**
8282

@@ -114,15 +114,15 @@ int jumpFloor(int number) {
114114
**问题分析：**
115115

116116
假设 n>=2，第一步有 n 种跳法：跳 1 级、跳 2 级、到跳 n 级
117-
跳 1 级，剩下 n-1 级，则剩下跳法是 f(n-1)
118-
跳 2 级，剩下 n-2 级，则剩下跳法是 f(n-2)
117+
跳 1 级，剩下 n-1 级，则剩下跳法是 f（n-1）
118+
跳 2 级，剩下 n-2 级，则剩下跳法是 f（n-2）
119119
……
120120
跳 n-1 级，剩下 1 级，则剩下跳法是 f(1)
121121
跳 n 级，剩下 0 级，则剩下跳法是 f(0)
122122
所以在 n>=2 的情况下：
123-
f(n)=f(n-1)+f(n-2)+...+f(1)
124-
因为 f(n-1)=f(n-2)+f(n-3)+...+f(1)
125-
所以 f(n)=2\*f(n-1) 又 f(1)=1,所以可得**f(n)=2^(number-1)**
123+
f(n)=f（n-1）+f（n-2）+...+f(1)
124+
因为 f（n-1）=f（n-2）+f（n-3）+...+f(1)
125+
所以 f(n)=2\*f（n-1） 又 f(1)=1,所以可得**f(n)=2^（number-1）**
126126

127127
**示例代码：**
128128

@@ -189,9 +189,9 @@ public boolean Find(int target, int [][] array) {
189189

190190
**问题分析：**
191191

192-
这道题不难，我们可以通过循环判断字符串的字符是否为空格，是的话就利用 append()方法添加追加"%20"，否则还是追加原字符。
192+
这道题不难，我们可以通过循环判断字符串的字符是否为空格，是的话就利用 append() 方法添加追加"%20"，否则还是追加原字符。
193193

194-
或者最简单的方法就是利用：replaceAll(String regex, String replacement)方法了，一行代码就可以解决。
194+
或者最简单的方法就是利用：replaceAll（String regex, String replacement）方法了，一行代码就可以解决。
195195

196196
**示例代码：**
197197

@@ -233,9 +233,9 @@ public String replaceSpace(StringBuffer str) {
233233
**问题解析：**
234234

235235
这道题算是比较麻烦和难一点的一个了。我这里采用的是**二分幂**思想，当然也可以采用**快速幂**。
236-
根据剑指 Offer 书中细节，该题的解题思路如下：1. 当底数为 0 且指数<0 时，会出现对 0 求倒数的情况，需进行错误处理，设置一个全局变量； 2. 判断底数是否等于 0，由于 base 为 double 型，所以不能直接用==判断 3. 优化求幂函数（二分幂）。
237-
当 n 为偶数，a^n =（a^n/2）\*（a^n/2）；
238-
当 n 为奇数，a^n = a^[(n-1)/2]\* a^[(n-1)/2] \* a。时间复杂度 O(logn)
236+
根据剑指 Offer 书中细节，该题的解题思路如下：1. 当底数为 0 且指数<0 时，会出现对 0 求倒数的情况，需进行错误处理，设置一个全局变量；2. 判断底数是否等于 0，由于 base 为 double 型，所以不能直接用==判断 3. 优化求幂函数（二分幂）。
237+
当 n 为偶数，a^n =(a^n/2)\*(a^n/2)；
238+
当 n 为奇数，a^n = a^[（n-1）/2]\* a^[（n-1）/2] \* a。时间复杂度 O(logn)
239239

240240
**时间复杂度**：O(logn)
241241

@@ -367,7 +367,7 @@ public class Solution {
367367

368368
1. 设两个都指向 head 的指针 p1 和 p2，当 p1 走了 k-1 步的时候，停下来。p2 之前一直不动。
369369
2. p1 的下一步是走第 k 步，这个时候，p2 开始一起动了。至于为什么 p2 这个时候动呢？看下面的分析。
370-
3. 当 p1 走到链表的尾部时，即 p1 走了 n 步。由于我们知道 p2 是在 p1 走了 k-1 步才开始动的，也就是说 p1 和 p2 永远差 k-1 步。所以当 p1 走了 n 步时，p2 走的应该是在 n-(k-1) 步。即 p2 走了 n-k+1 步，此时巧妙的是 p2 正好指向的是规律一的倒数第 k 个结点处。
370+
3. 当 p1 走到链表的尾部时，即 p1 走了 n 步。由于我们知道 p2 是在 p1 走了 k-1 步才开始动的，也就是说 p1 和 p2 永远差 k-1 步。所以当 p1 走了 n 步时，p2 走的应该是在 n-（k-1）步。即 p2 走了 n-k+1 步，此时巧妙的是 p2 正好指向的是规律一的倒数第 k 个结点处。
371371
这样是不是很好理解了呢？
372372

373373
**考察内容：**

‎docs/cs-basics/data-structure/tree.md‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ head:
3535
- **节点的层数**：节点的深度+1。
3636
- **树的高度**：根节点的高度。
3737

38-
> 关于树的深度和高度的定义可以看 stackoverflow 上的这个问题：[What is the difference between tree depth and height?](https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height) 。
38+
> 关于树的深度和高度的定义可以看 stackoverflow 上的这个问题：[What is the difference between tree depth and height?](https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height)。
3939
4040
## 二叉树的分类
4141

@@ -49,13 +49,13 @@ head:
4949

5050
### 满二叉树
5151

52-
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是 **满二叉树**。也就是说，如果一个二叉树的层数为 K，且结点总数是 `2^k -1` ，则它就是 **满二叉树**。如下图所示：
52+
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是 **满二叉树**。也就是说，如果一个二叉树的层数为 K，且结点总数是 `2^k -1`，则它就是 **满二叉树**。如下图所示：
5353

5454
![满二叉树](https://oss.javaguide.cn/github/javaguide/cs-basics/data-structure/full-binary-tree.png)
5555

5656
### 完全二叉树
5757

58-
除最后一层外，若其余层都是满的，并且最后一层是满的或者是在右边缺少连续若干节点，则这个二叉树就是 **完全二叉树** 。
58+
除最后一层外，若其余层都是满的，并且最后一层是满的或者是在右边缺少连续若干节点，则这个二叉树就是 **完全二叉树**。
5959

6060
大家可以想象为一棵树从根结点开始扩展，扩展完左子节点才能开始扩展右子节点，每扩展完一层，才能继续扩展下一层。如下图所示：
6161

‎docs/cs-basics/network/application-layer-protocol.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -320,7 +320,7 @@ DNS 通常使用 UDP，默认端口是 53。之所以优先使用 UDP，是因
320320
- RFC 8446：TLS 1.3
321321
- RFC 9000：QUIC
322322
- RFC 3550：RTP: A Transport Protocol for Real-Time Applications
323-
- RFC 4571：Framing Real-time Transport Protocol (RTP) and RTP Control Protocol (RTCP) Packets over Connection-Oriented Transport
323+
- RFC 4571：Framing Real-time Transport Protocol （RTP） and RTP Control Protocol （RTCP） Packets over Connection-Oriented Transport
324324
- RFC 6891：Extension Mechanisms for DNS (EDNS(0))
325325

326326
<!-- @include: @article-footer.snippet.md -->

‎docs/cs-basics/network/can-tcp-and-udp-use-the-same-port.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -89,7 +89,7 @@ TCP 和 UDP 之间不冲突，不代表端口可以随便重复绑定。
8989

9090
如果两个进程绑定的是不同本地 IP，同协议同端口也可能成立，例如 `192.168.1.10:8080` 和 `192.168.1.11:8080` 都是 TCP。
9191

92-
还有一个容易被忽略的点：IPv6 的通配地址 `[::]:8080` 在一些环境下可能同时接收 IPv6 和 IPv4-mapped 地址，`IPV6_V6ONLY` 会影响它是否和 IPv4 socket 冲突。排查时可以用 `ss -tulnp` 同时看 `0.0.0.0:端口` 和 `[::]:端口`。
92+
还有一个容易被忽略的点：IPv6 的通配地址 `[::]:8080` 在一些环境下可能同时接收 IPv6 和 IPv4-mapped 地址，`IPV6_V6ONLY` 会影响它是否和 IPv4 socket 冲突。排查时可以用 `ss -tulnp` 同时看 `0.0.0.0:端口 ` 和 `[::]:端口`。
9393

9494
`SO_REUSEADDR`、`SO_REUSEPORT` 也会改变绑定规则，常用于快速重启、多进程监听、负载分摊等场景。这里小 G 建议先记住：
9595

0 commit comments

Comments
 (0)