基础算法

1、加密算法
1.1【问】请介绍一下你知道的加密算法
参考回答：
一般分类如下

1. 对称加密
2. 非对称加密
3. 哈希摘要
4. 电子签名
5. 密码存储
   其中
   ● 对称加密常见的有：DES、AES 等，国家标准有 SM4
   ● 非对称加密常见的有：RSA，ECDSA 等，国家标准有 SM2
   ● 哈希摘要有：MD5、SHA-2、SHA-3 等，国家标准有 SM3
   ● 电子签名有：通常会结合 RSA、ECDSA 和哈希摘要完成签名，或者是 HMAC
   ● 密码存储：直接使用哈希摘要作为密码存储、加盐存储、BCrypt

1.2【追问】解释对称加密、非对称加密、哈希摘要
● 对称加密
○ 加密和解密的密钥使用同一个
○ 因为密钥只有一个，所以密钥需要妥善保管
○ 加解密速度快
● 非对称加密
○ 密钥分成公钥、私钥，其中公钥用来加密、私钥用来解密
○ 只需将私钥妥善保管，公钥可以对外公开
○ 如果是双向通信保证传输数据安全，需要双方各产生一对密钥
■ A 把 A公钥 给 B，B 把 B公钥 给 A，他们各自持有自己的私钥和对方的公钥
■ A 要发消息给 B，用 B公钥 加密数据后传输，B 收到后用 B私钥 解密数据
■ 类似的 B 要发消息给 A，用 A公钥 加密数据后传输，A 收到后用 A私钥 解密数据
○ 相对对称加密、加解密速度慢
● 哈希摘要，摘要就是将原始数据的特征提取出来，它能够代表原始数据，可以用作数据的完整性校验
○ 举个例子，张三对应着完整数据
○ 描述张三时，会用它的特征来描述：他名叫张三、男性、30多岁、秃顶、从事 java 开发、年薪百万，这些特征就对应着哈希摘要，以后拿到这段描述，就知道是在说张三这个人
○ 为什么说摘要能区分不同数据呢，看这段描述：还是名叫张三、男性、30多岁、秃顶、从事 java 开发、月薪八千，有一个特征不符吧，这时可以断定，此张三非彼张三

1.3【追问】解释签名算法
电子签名，主要用于防止数据被篡改。
先思考一下单纯用摘要算法能否防篡改？例如

● 发送者想把一段消息发给接收者
● 中途 message 被坏人改成了 massage（摘要没改）
● 但由于发送者同时发送了消息的摘要，一旦接收者验证摘要，就可以发现消息被改过了
坏人开始冒坏水

● 但摘要算法都其实都是公开的（例如 SHA-256），坏人也能用相同的摘要算法
● 一旦这回把摘要也一起改了发给接收者，接收者就发现不了
怎么解决？

● 发送者这回把消息连同一个密钥一起做摘要运算，密钥在发送者本地不随网络传输
● 坏人不知道密钥是什么，自然无法伪造摘要
● 密钥也可以是两把：公钥和私钥。私钥留给发送方签名，公钥给接收方验证签名，参考下图
○ 注意：验签和加密是用对方公钥，签名和解密是用自己私钥。不要弄混

1.4【追问】你们项目中密码如何存储？
● 首先，明文肯定是不行的
● 第二，单纯使用 MD5、SHA-2 将密码摘要后存储也不行，简单密码很容易被彩虹表攻击，例如
○ 攻击者可以把常用密码和它们的 MD5 摘要结果放在被称作【彩虹表】的表里，反查就能查到原始密码
加密结果 原始密码
e10adc3949ba59abbe56e057f20f883e 123456
e80b5017098950fc58aad83c8c14978e abcdef
... ...
因此
● 要么提示用户输入足够强度的密码，增加破解难度
● 要么我们帮用户增加密码的复杂度，增加破解难度
○ 可以在用户简单密码基础上加上一段盐值，让密码变得复杂
○ 可以进行多次迭代哈希摘要运算，而不是一次摘要运算
● 还有一种办法就是用 BCrypt，它不仅采用了多次迭代和加盐，还可以控制成本因子来增加哈希运算量，让攻击者知难而退

1.5【追问】比较一下 DES、AES、SM4
它们都是对称加密算法
● DES（数据加密标准）使用56位密钥，已经不推荐使用
● AES（高级加密标准）支持 128、192、256位密钥长度，在全球范围内广泛使用
● SM4（国家商用密码算法）支持 128位密钥，在中国范围内使用

1.6【追问】比较一下 RSA、ECDSA 和 SM2
它们都是非对称加密算法
● RSA 的密钥长度通常为 1024~4096，而 SM2 的密钥长度是 256
● SM2 密钥长度不需要那么长，是因为它底层依赖的是椭圆曲线、离散对数，反过来 RSA 底层依赖的是大数分解，前者在相同安全级别下有更快的运算效率
● SM2 是中国国家密码算法，在国内受政策支持和推广
● ECDSA 与 SM2 实现原理类似

2、排序
2.1 【问】请介绍一下你知道的排序算法有哪些
初级答法
常见的排序算法有：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等
P.S.
● 适合对以上排序算法一知半解，不太自信的同学，所谓言多必失，回答基本的就行
● 但要对接下来【各种排序的时间复杂度】的追问做到心中有数，这个必须背一背（参考后面的表格）

进阶答法
排序算法大致可分为两类：
● A. 基于比较的排序算法
● B. 非比较排序算法
比较排序算法有：快排、归并、堆排序、插入排序等
非比较排序算法有：计数排序、桶排序、基数排序等
比较排序算法中
● 快排、归并、堆排序能够达到 $$O(n \cdot \log{n})$$的（平均）时间复杂度
● 而插入排序的（平均）时间复杂度是 $$O(n^2$$
● 但并不是说复杂度高的算法就差，这要看数据规模和数据有序度，例如
○ 数据量小，或是有序度高的数据就适合用插入排序
○ 同样是数据量大的数据排序，如果数据的有序度高，归并优于快排
○ 快排虽然是比较排序中最快的算法，但若是分区选取不好，反而会让排序效率降低
○ 工业级的排序都是混合多种排序算法，例如 java 排序的实现就是混合了插入、归并与快排，不同的数据规模、不同场景下切换不同的排序算法
至于计数、桶、基数可以达到进一步让时间复杂度降至$$O(n$$，当然这与被排序数字的位数、范围等都有关系，您想知道的话，咱们可以细聊。
P.S.
● 适合对这些排序算法非常熟悉的同学，这时应注重回答的条理性
○ 首先，对算法进行简单分类，让答案更为清晰
○ 其次，不要等面试官来继续追问，而是主动回答各个算法的时间复杂度和适用场景，体现你对它们的熟悉
○ 第三，一定要对各个算法的细节有充分准备，否则问到答不出来就尴尬了，这时不如降级为【初级答法】

2.2【问】请说说 XX 算法最好、平均、最差时间复杂度、是否稳定 ...
此时的回答参考下面两张表
表A 比较排序算法
算法 最好 最坏 平均 空间 稳定 思想 注意事项
冒泡 n n^2 n^2 1 是 比较 数据有序，就能达到最好情况
选择 n^2 n^2 n^2 1 否 选择 交换次数一般少于冒泡
堆 n log n n log n n log n 1 否 选择
插入 n n^2 n^2 1 是 比较 数据有序，就能达到最好情况
希尔 n log n 1 否 插入 有多种步长序列，它们的时间复杂度略有差异
归并 n log n n log n n log n n 是 分治
快速 n log n n^2 n * log n log n 否 分治 快排通常用递归实现，空间复杂度中的 $$\log{n}$$ 就是递归栈所花费的额外空间
表B 非比较排序算法
计数排序
● 平均时间复杂度：O(n+r)，其中 r 是数字的范围
● 空间复杂度: O(n+r)
桶排序
● 最糟时间复杂度：所有数字放入一个桶，此时又变成了一个桶内的比较排序，时间复杂度取决于桶内排序算法
● 平均时间复杂度：，若桶的个数 k ≈ n，则可以认为整体时间复杂度为 O(n)
● 空间复杂度：O(n+k)
基数排序
● 一般配合桶排序实现，因此也会涉及到桶个数 k
● 平均时间复杂度：，其中 w 是待排序数字的位数
● 空间复杂度：与桶排序空间复杂度相同，每次按位排序时，桶可以重用

2.3【问】冒泡排序的实现思路
参考下图

1. 将整个数组分成【未排序】和【已排序】两个区域
2. 每一轮冒泡在【未排序】中从左向右，相邻两数进行比较（图中的 i 与 i+1 处），若它们逆序则交换位置，当这一轮结束时，【未排序】中最大的数会交换至【已排序】
3. 这样进行多轮冒泡操作，【已排序】逐渐扩大，而【未排序】逐渐缩小，直至缩减为一，算法结束

P.S.
● 本图只展示了第一轮冒泡
● 上述回答话术偏向书面化，实际回答时应当更自由、更口语化一些，这样可以避免回答时刻板、雷同，但回答中的关键点不能少，这些关键点列举如下：
○ 强调把数组分成两个区域：已排序、未排序
○ 强调每轮冒泡是从左向右，两两比较
○ 每轮冒泡的结果：会将本次最大的数字交换到右侧
● 参考代码

2.4【追问】冒泡排序如何优化
怎么优化呢？每次循环时，若能给【未排序区】确定更合适的边界，则可以减少冒泡轮数
看下面的图

● 以前的实现，每轮只能冒泡一个数字
● 用 x 记录最后一次交换时 i 的位置（索引1处），白话讲就是未排序区的右侧
● 后续比较 3与4 未交换、4与5 未交换，说明它们都有序，相当于一轮就冒泡了3个数字
● 实施此优化后，遇到有序数组，则排序时间复杂度可以降至$$O(n$$

2.5【追问】冒泡排序与其它排序算法比较
● 与选择比
○ 时间复杂度：都是 O(n^2)
○ 交换
■ 冒泡在相邻元素两两比较时，遇到逆序元素，立刻就要进行交换
■ 选择可以每轮的结束时，把最大元素交换到已排序区
■ 选择的交换次数（或者说元素的移动次数）更少
○ 稳定性
■ 冒泡是稳定排序
■ 选择是不稳定排序
○ 对有序数组排序
■ 冒泡可以优化，时间复杂度能降至O(n)
■ 选择不能优化
● 与插入比
○ 时间复杂度：都是 O(n^2)
○ 交换
■ 插入的交换次数更少
○ 稳定性
■ 二者都是稳定排序算法
○ 对有序数组排序
■ 都可以只比较一轮，无需交换，时间复杂度达到$$O(n$$
● 与剩余的排序算法比较
○ 时间复杂度不在同一级别，无可比性

2.6【问】选择排序的实现思路
参考下图

1. 将整个数组分成【未排序】和【已排序】两部分
2. 每一轮选出【未排序】中最大的元素，交换到【已排序】
3. 这样进行多轮选择操作，【已排序】逐渐扩大，而【未排序】逐渐缩小，直至缩减为一，算法结束

P.S.
● 图中展示了 4 轮选择，直至有序
● 还是建议在理解了关键点的基础上自由发挥，用自己语言描述算法
● 回答关键点
○ 两个区域：已排序、未排序
○ 每次选中未排序区域中最大元素（也可以选最小元素），交换至已排序区域
● 参考代码

2.7【追问】解释什么是不稳定排序
什么是稳定及不稳定排序算法，参照下图进行回答
● 有两个排序时取值相等的元素，比如图中的红桃五和黑桃五
● 如果这些相等元素排序前后的相对位置没有改变（都是红五前、黑五后）那么该排序算法是稳定的
● 如果这些相等元素排序前后的相对位置发生了改变（排序后变成了黑五前、红五后）那么该排序算法不稳定

2.8【追问】为啥说选择排序是不稳定的
初始状态如下

● 最初 3 在 3' 的左边
● 第一轮选中最大的5，交换4
● 第二轮选中最大的4，交换了 3'
● ...
● 排序结束，3' 跑到了 3 的左侧
过程可以参考下面的动画效果

2.9【追问】选择排序与其它排序算法比较
● 同级别像插入、冒泡等都是稳定排序算法，而选择属于不稳定排序算法
● 它们的时间复杂度都一样，平均时间复杂度都是O(n^2)，不咋地
● 选择排序还应当与堆排序比较
○ 相似点：都是每轮选出最大元素，交换至已排序区域
○ 不同点：数据结构不同，选择排序底层是线性结构，而堆排序结构是大顶堆，这就造成每次选择的效率是堆结构更高

2.10【问】插入排序的实现思路
参考下图

1. 将数组分成【已排序】（左边）和【未排序】（右边）两个区域
2. 每次从【未排序】的最左边拿出一个数，与已排序的数自右向左比较，直至找到合适位置，插入即可
3. 这样进行多轮插入操作，直至【未排序】中没有数，算法结束

P.S.
● 图中 low 指向的是【未排序】区域的最左侧，t 的值即要插入的值
● 回答前想一想自己平时是怎么摸牌、打牌的
○ 手上已经有 2、3、4、5 这几张排好的牌，又摸到一张 A，此时应该把它插到哪？
○ 手上的牌就是已排序区域，摸的新牌来自未排序区，从右找的话，那么就找比新牌小的那个位置插入
● 参考代码

2.11【追问】插入排序的适用场景

1. 数据规模较小
2. 数据有序度高
3. 链表排序

2.12【追问】插入排序与其它排序算法比较

1. 插入排序优于时间复杂度同级的冒泡、选择，它既是稳定排序算法、又能对已排序数据达到$$O(n$$的复杂度
2. 插入排序还经常与希尔排序比较，希尔排序可以看作插入排序的增强版
3. 工业排序实现中，会结合插入、快排、归并做混合排序

2.13【问】归并排序的实现思路
参考下图，关键就三点：

1. 分 - 一开始数组很大，不知道如何排序？
   a. 没事，每次从数组中间切一刀，处理的数据减少一半，数组划分成小数组
   b. 小数组若还是太大，继续划分。
2. 治 - 小数组可以直接排序时，停止划分，每个小数组排好序。
3. 合 - 已有序小数组两两合并，越合越大，最终求得整个问题的解。

P.S.
● 上图中，先执行【分】，把原始数组划分成 8、7、5、4、3、2、1、6 八个小数组，分到无可再分
● 每个小数组认为已有序，小数组已经【治】，开始【合】
● 两两合并：
○ 8 7 => 78
○ 5 4 => 45
○ 3 2 => 23
○ 1 6 => 16
○ 78 45 => 4578
○ 23 16 => 1236
○ 4578 1236 => 12345678
● 参考代码

2.14【追问】归并排序与其它排序算法比较
常见的是把它与快速排序比较

1. 相同点是，二者都基于分治思想，平均时间复杂度都能达到O(n * log{n})
2. 分治细节不同
   a. 归并是分到分无可分、在合并的过程中逐渐有序
   b. 快排是在每次分区时，就将比基准点小的换到左边分区，比基准点大的换到右边分区，不需要后面合的过程
3. 稳定性不同
   a. 归并是稳定的
   b. 快排是不稳定的
4. 时间复杂度有差异
   a. 归并，时间复杂度总会保持 O(n * log{n})
   b. 快排，若基准点选择不好，两个分区划分不均匀，则会退化至 O(n^2)

2.15【追问】归并排序能做哪些优化

1. 一种常见的优化是，如果切分后的小数组元素较少，可以切换为插入排序，而不必一定要等到元素个数切分至1
2. 归并排序通常用递归实现，可以考虑修改为迭代实现，减少递归开销
3. 归并排序可以改进为并行归并算法，提升多核 cpu 下的排序能力

2.16【问】快速排序的实现思路
参考下图

1. 分区
   a. 在未排序区域内，选择最左侧元素作为基准点
   b. 把区域内比基准点小的元素交换到它左边，比基准点大的元素交换到它右边
   c. 分区结束，基准点已经排到了它正确的位置
2. 在基准点两边的区域重复上述分区过程，直至分区内只剩一个或没有元素时结束

P.S.
● 参考代码

2.17【追问】快速排序还有哪些优化手段

1. 分区不均衡会让快排效率变低。使用随机数作为基准点，避免选中最值基准点导致的分区不均衡
2. 如果基准点的重复值较多，则原来算法中的分区效果也不好，要想办法让这些重复值也分布均匀
3. 当分区内元素少到一定程度，可以切换为插入排序

2.18【问】堆排序的实现思路
参考下图

1. 首先建立一个大顶堆，堆顶元素就是最大元素，把它交换到数组尾部，最大元素就排好序了
2. 交换到堆顶的元素破坏了堆特性，对它下潜，下潜完成后堆顶就成了第二大元素，再把它交换到数组尾部，二大元素也排好了
3. 这样依此类推，下潜=>堆顶元素交换=>下潜=>堆顶元素交换 ... 直至剩余一个元素，算法结束

P.S.
● 参考代码

2.19【追问】堆排序与其它排序算法比较
● 堆排序同级别排序方法有快排、归并等，它们的时间复杂度都是 O(n * log{n})
● 堆排序中的下潜操作涉及到父元素与它的左右孩子交换，数据量较大时，父元素距离它的孩子较远，这样可能会造成（CPU）缓存未命中，增加内存访问成本。快排和归并则没有这个问题
P.S.
● 个人认为，堆相对于堆排序更为重要，它可以应用于优先级队列、TopK 问题 ...

3、字符串类
3.1、字符串反转
● 源于 Leetcode 344 题
● 举一反三 Leetcode 151 题（反转单词）
● 思路 - 双指针
○ 一开始，i 指针指向数组起始元素，j 指针指向数组结束元素，交换 i、j 指向的元素。
○ i 向后移动，j 向前移动，重复以上过程 ，直至 i、j 相遇，算法结束。
● 参考代码
spring.threads.virtual.enabled=true
@Bean
public TomcatProtocolHandlerCustomizer<?> tomcatProtocolHandlerCustomizer() {
return protocolHandler -> protocolHandler
.setExecutor(Executors.newVirtualThreadPerTaskExecutor());
}
static void bubbleSort(int[] arr) {
// n 为数组长度
int n = arr.length;
// 外层循环控制冒泡次数，是数组长度减一
for (int j = 0; j < n-1; i++) {
// 内层循环表示本轮两两比较的次数，首轮 n-1, 次轮 n-2, 再次轮 n-3 ...
for (int i = 0; i < n-1-j; i++) {
// 若相邻数字逆序
if (arr[i] > arr[i+1]) {
// 交换
swap(arr, i, i+1);
}
}
}
}
static void sort(int[] a) {
// n 为数组长度
int n = a.length;
// 进行 n - 1 轮选择，left 代表已排序区域的最左侧
for (int left = n - 1; left > 0 ; left--) {
// 每次找到最大元素的索引
int max = left;
for (int i = 0; i < left; i++) {
if (a[i] > a[max]) {
max = i;
}
}
// 本轮结束前，将最大元素交换到已排序区域的最左侧
swap(a, max, left);
}
}
static void sort(int[] a) {
// n 为数组长度
int n = a.length;
// low 代表未排序区域的最左侧
for (int low = 1; low < n; low++) {
// t 代表要插入的值
int t = a[low];
// i 是已排序区域指针
int i = low - 1;
// 从右向左找比 t 小的位置
while (i >= 0 && a[i] > t) {
// 没找到，需要把当前的数向右移动一格，把位置空出来
a[i + 1] = a[i];
i--;
}
// i 在循环内多减了一次，因此 i+1 是插入位置
a[i + 1] = t;
}
}
static void sort(int[] a1) {
// a1 是原始数组，a2 是临时数组
int[] a2 = new int[a1.length];
split(a1, 0, a1.length - 1, a2);
}

static void split(int[] a1, int left, int right, int[] a2) {
int[] array = Arrays.copyOfRange(a1, left, right + 1);
// 2. 治：当 left == right 表示只剩一个元素，此时已有序
if (left == right) {
return;
}
// 1. 分：m 表示每次划分的中间索引，然后两边继续递归，直到【治】后返回
int m = (left + right) >>> 1;
split(a1, left, m, a2);
split(a1, m + 1, right, a2);
// 3. 合：合并两个有序区间子数组，注意合并的结果暂存在 a2，要拷贝回 a1
merge(a1, left, m, m + 1, right, a2);
System.arraycopy(a2, left, a1, left, right - left + 1);
}

// 合并数组中两个有序区间 [iStart,iEnd] 和 [jStart,jEnd]
static void merge(int[] a1, int iStart, int iEnd, int jStart, int jEnd, int[] a2) {
int k = iStart;
int i = iStart;
int j = jStart;
while (i <= iEnd && j <= jEnd) {
if (a1[i] < a1[j]) {
a2[k] = a1[i];
i++;
} else {
a2[k] = a1[j];
j++;
}
k++;
}
if (i > iEnd) {
System.arraycopy(a1, j, a2, k, jEnd - j + 1);
}
if (j > jEnd) {
System.arraycopy(a1, i, a2, k, iEnd - i + 1);
}
}
static void sort(int[] a) {
quick(a, 0, a.length - 1);
}

static void quick(int[] a, int left, int right) {
if (left >= right) {
return;
}
int p = partition(a, left, right);
quick(a, left, p - 1);
quick(a, p + 1, right);
}

// 分区方法，在区域 left~right 内，找到基准点正确的索引值
static int partition(int[] a, int left, int right) {
int i = left;
int j = right;
// pv 代表基准点的值
int pv = a[left];
while (i < j) {
// 从右找到 j 处比基准点小（或等于）的元素
while (i < j && a[j] > pv) {
j--;
}
// 从左找到 i 处比基准点大的元素
while (i < j && a[i] <= pv) {
i++;
}
// 它们位置不正确，交换
swap(a, i, j);
}
// 把基准点交换到中间
swap(a, left, j);
// 此时，基准点左边都是比它小的，右边都是比它大的，返回基准点索引
return j;
}
public static void sort(int[] a) {
heapify(a, a.length);
for (int right = a.length - 1; right > 0; right--) {
swap(a, 0, right);
down(a, 0, right);
}
}

// 建堆 O(n)
private static void heapify(int[] array, int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
down(array, i, size);
}
}

// 下潜 O(log n)
private static void down(int[] array, int parent, int size) {
// 比较 parent 和它的左、右孩子
while (true) {
int left = parent * 2 + 1;
int right = left + 1;
// max 代表 parent 和它的左、右孩子中最大值
int max = parent;
if (left < size && array[left] > array[max]) {
max = left;
}
if (right < size && array[right] > array[max]) {
max = right;
}
// 最大的就是 parent 自己
if (max == parent) {
break;
}
// parent 与孩子中较大者交换
swap(array, max, parent);
// 继续下潜
parent = max;
}
}
static void reverseString(char[] s) {
reverseString(s, 0, s.length - 1);
}

static void reverseString(char[] s, int begin, int end) {
int i = begin;
int j = end;
while (i < j) {
swap(s, i, j);
i++;
j--;
}
}

static void swap(char[] array, int i, int j) {
char c = array[i];
array[i] = array[j];
array[j] = c;
}
3.2、【问】说说你的项目中，哪里用到了字符串匹配技术
参考回答：
我的项目中，很多地方都会用到字符串匹配技术，主要采用正则匹配，例如：

1. 表单提交时，用它来校验数据，比如邮箱地址、电话号码、身份证号码等
2. 网页爬取时，使用正则抽取网页中的图片链接
3. 日志处理时，提取日志中的特定信息
4. 一些框架的配置路由规则时，是使用正则表达式来定义
5. 数据清洗时，使用正则表达式转换或清洗文本数据
6. 编辑代码时，使用正则来完成搜索或批量替换等操作
   P.S.
   ● 以上 6 点，不必面面俱到，应该是自己熟悉哪块，就重点准备哪块。

例1：表单校验，例如要校验手机号，则正则写作
/^1\d{10}$/.test(手机号)
解释：

1. 其中 ^ $ 用来匹配开始和结束位置
2. 假设手机号规则是 1 开头，后面 10 位数字，因此这里用 \d{10} 匹配后 10 个数字

例2：网页爬取时，抽取下面 html 代码中的图片链接
const html = <img src="image1.jpg" alt="Image 1"> <img src='image2.jpg' alt='Image 2'/>
正则写作
const htmlPattern = /<img src=(['"])(.+?)\1(.*?)>/g
let groups
while ((groups = htmlPattern.exec(html)) !== null) {
console.log(${groups[2]})
}
有一定难度，解释如下

1. (['"])用来匹配单引号或双引号，最外层的 () 是对它分组，即第一组
2. 与第一组呼应的，\1 代表引用第一组，前面是单引号 \1 就是单引号，前面是双引号 \1 就是双引号
3. (.+?)是第二组，就是引号中图片地址，其中 ? 用来避免贪婪
4. (.*?)是第三组，代表 alt 这部分内容
5. 最后遍历每次匹配结果，取到其中第二组，即为图片地址

例3：提取日志文件中的信息
日志文件如下
const logData = [2022-01-01 12:30:45] - GET /home 200 OK [2022-01-01 12:31:02] - POST /login 401 Unauthorized [2022-01-01 12:32:15] - GET /products/123 404 Not Found
正则写作
const logPattern = /[.*?] - (\w+) (\/\S+) (\d{3}) (\w+)/g;
let groups;
while ((groups = logPattern.exec(logData)) !== null) {
console.log(Method: ${groups[1]}, Path: ${groups[2]}, Status: ${groups[3]} ${groups[4]});
}
解释：正则表达式共分了 4 组
● 第一组匹配【请求方法】
● 第二组匹配【请求路径】，第一个 / 要转义，\S表示非空格字符，不用\w的原因是路径中可能有第二层/
● 第三组匹配【响应码】
● 第四组匹配【响应消息】

4、搜索类
4.1、【问】请介绍一下二分查找算法
参考回答：
● 二分查找也称之为折半查找，是一种在有序数组内查找特定元素的搜索算法，非常高效，时间复杂度是$$O(\log{n}$$
● 它具体实现步骤是：
○ 定义两个指针 i、j，分别指向有序数组的起始和结束位置
○ 找到指针范围内中间元素
■ 如果目标 < 中间元素，则在左半部分继续搜索
■ 如果目标 > 中间元素，则在右半部分继续搜索
■ 如果目标 = 中间元素，则找到目标，算法结束
参考代码：

// a 为已排序数组，target 为搜索目标
static int binarySearch(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
// m 为中间索引，无符号右移是避免整数除法溢出
int m = (i + j) >>> 1;
// 目标小于中间元素，改动右边界（下次循环在左边搜索）
if (target < a[m]) {
j = m - 1;
}
// 目标大于中间元素，改动左边界（下次循环在右边搜索）
else if (a[m] < target) {
i = m + 1;
}
// 找到
else {
return m;
}
}
// 未找到
return -1;
}
4.2、【问】请介绍什么是回溯算法
参考回答：
● 在求解问题的过程中，要记录每一步的状态，因为接下来的尝试有可能不成功，这时就需要回溯（其实就是撤销）到之前的某一步，换另一种方法继续尝试。
● 回溯通常结合递归来实现，因为递归栈保存了递归方法上次调用时各个变量的状态，用来实现回溯更为自然
● 回溯里还有个常见术语叫做剪枝。在递归过程中，通过条件检查减少一些不必要的递归，这称为剪枝
○ 因为多路递归的执行通常用一棵递归树表示，因此术语剪枝非常形象。
回溯举例，$$$$ 皇后问题（在$$N \cdot N$$的棋盘上放置$$$$个皇后，保证同一行、同一列、同一斜线上只有一个皇后）