第二章 基础算法

3.2、【问】说说你的项目中，哪里用到了字符串匹配技术
参考回答：
我的项目中，很多地方都会用到字符串匹配技术，主要采用正则匹配，例如：
表单提交时，用它来校验数据，比如邮箱地址、电话号码、身份证号码等
网页爬取时，使用正则抽取网页中的图片链接
日志处理时，提取日志中的特定信息
一些框架的配置路由规则时，是使用正则表达式来定义
数据清洗时，使用正则表达式转换或清洗文本数据
编辑代码时，使用正则来完成搜索或批量替换等操作
P.S.
以上 6 点，不必面面俱到，应该是自己熟悉哪块，就重点准备哪块。
例1：表单校验，例如要校验手机号，则正则写作
解释：
其中 ^ $ 用来匹配开始和结束位置
假设手机号规则是 1 开头，后面 10 位数字，因此这里用 \d{10} 匹配后 10 个数字
例2：网页爬取时，抽取下面 html 代码中的图片链接
正则写作
有一定难度，解释如下
(['"])用来匹配单引号或双引号，最外层的 () 是对它分组，即第一组
与第一组呼应的，\1 代表引用第一组，前面是单引号 \1 就是单引号，前面是双引号 \1 就是双引号
(.+?)是第二组，就是引号中图片地址，其中 ? 用来避免贪婪
(.*?)是第三组，代表 alt 这部分内容
最后遍历每次匹配结果，取到其中第二组，即为图片地址
例3：提取日志文件中的信息
日志文件如下
正则写作
解释：正则表达式共分了 4 组
第一组匹配【请求方法】
第二组匹配【请求路径】，第一个 / 要转义，\S表示非空格字符，不用\w的原因是路径中可能有第二层/
第三组匹配【响应码】
第四组匹配【响应消息】
4、搜索类
4.1、【问】请介绍一下二分查找算法
参考回答：
二分查找也称之为折半查找，是一种在有序数组内查找特定元素的搜索算法，非常高效，时间复杂度是$$O(\log{n}$$
它具体实现步骤是：
定义两个指针 i、j，分别指向有序数组的起始和结束位置
找到指针范围内中间元素
如果目标 < 中间元素，则在左半部分继续搜索
如果目标 > 中间元素，则在右半部分继续搜索
如果目标 = 中间元素，则找到目标，算法结束
参考代码：
4.2、【问】请介绍什么是回溯算法
参考回答：
在求解问题的过程中，要记录每一步的状态，因为接下来的尝试有可能不成功，这时就需要回溯（其实就是撤销）到之前的某一步，换另一种方法继续尝试。
回溯通常结合递归来实现，因为递归栈保存了递归方法上次调用时各个变量的状态，用来实现回溯更为自然
回溯里还有个常见术语叫做剪枝。在递归过程中，通过条件检查减少一些不必要的递归，这称为剪枝
因为多路递归的执行通常用一棵递归树表示，因此术语剪枝非常形象。
回溯举例，$$$$ 皇后问题（在$$N \cdot N$$的棋盘上放置$$$$个皇后，保证同一行、同一列、同一斜线上只有一个皇后）
初始状态（图中白色表示没有冲突可以放置的格子，而红色表示不能放）
第二行，第三列的格子放了一个皇后，可以看到接下来第三行格子冲突了，因此需要进行回溯撤销
回溯到初始状态
这回换成向第二行，第四列的格子放皇后，可以预见，接下来可以有一个解