【剑指Offer】——拆解算法的常见套路

Bertha 。 2023-01-18 04:15 44阅读 0赞

前面一段时间咱们整体的把面向Offer中的所有算法题给看了一遍，想必大家都有了一定的印象，那么今天我们就来整体的回顾一下这所有的算法题，并且结合我面试过程中的常考题目进行一个总结。看看那些题目是比较经典和典型的。又有那些算法思想是我们要学习和掌握的。

那么接下来让我们开始吧。注意的是因为篇幅的关系这里仅做思路的讲解，具体的代码和细节建议回看之前总结的文章。还没有关注公众号的建议抓紧关注【Java冢狐】

### 单例模式 ###

*  对应题目 NO.2 单例模式

首先要说的就是单例模式，因为他实在是太重要了，面试中常常会让你手撕一个单例模式，这个真的是我们必备的知识。

说到单例模式无非就是饿汉式和懒汉式，从名字中也能知道他们的区别。

#### 饿汉式 ####

顾名思义饿汉式就是太饿了太需要了，所以一开始就先进行初始化，这样避免了多线程同步的问题，但是也存在内存浪费的可能性。

#### 懒汉式 ####

同样顾名思义，懒汉式就是一开始并不初始化，而是什么时候使用到了什么时候再进行初始化，这样就避免了内存浪费的可能性。

在手撕代码的时候，推荐使用双重检查懒汉式，这样才能更好的理解算法和展示你的实力。

### 哈希表 ###

哈希表可以说是我们的老朋友，在很多的算法题中或者算法实现中都经常碰到，由于其key-value的数据结构使其能够在查找中具有很强的

*  对应题目 NO.3 数组中重复的数字

最简单的哈希表的应用，后续很多题目都是这个题目的变种

*  对应题目 NO.50 只出现一次的字符

这个在其中还有一层小小的优化，不过![img][]影响不大

### 动态规划 ###

动态规划，算是算法中的老熟人了，在前面的文章中也有过介绍。主要就是四个步骤：状态表示、转移方程、初始状态、最终状态。其中初始状态和转移方程算是其中的重点。转移方程是解题的核心，初始状态是正确退出的关键。

*  对应问题 NO.10 斐波拉契数列

最简单的动态规划问题，因为把最最核心的转移方程都给出来了，所以只需要注意初始状态，即可简单写出。

*  对应问题 NO.14 剪绳子 ；NO.42 连续子数组的最大和；NO.47 礼物的最大价值

这个就是一个正常难度的动态规划问题，需要你通过题目找出其关键的转移方程然后去实现它。

*  对应问题 NO.19 正则表达式匹配

这个算是动态规划中比较难得问题，因为刚开始在看这个问题的时候很容易想不到动态规划，或者就算想到了也不好去找其转移方程。但是其实是仔细的分类以后还是比较容易的。

### 滑动窗口 ###

滑动窗口模式是使用在给定数据或链表的特定窗口大小所执行的操作。

往往从第一个元素开始滑动窗口并逐个元素地向右滑，并根据你所求解的问题来调整窗口的长度。

*  对应题目 NO.48 最长不含重复字符的子字符串

典型的滑动窗口的题目。

#### 问题特征 ####

*  问题的输入是一种线性的数据结构
 *  被要求查找最长/最短的子字符串、子数组或所需的值

#### 典型问题 ####

### 链表问题 ###

#### 翻转链表 ####

*  对应题目 NO.6 从尾到头打印链表；NO.24翻转链表

这个算是翻转链表中最简单的应用，后续很多链表题目其实实际上都是在翻转链表的基础上进行的改进

### 双指针\\快慢指针 ###

双指针是使用两个指针一前一后、一快一慢、一正一反来在数据结构中迭代，直到达到某种条件或者遍历完全。

通常在排序数组或者链表中搜索配对时十分的有用。相较于单指针来说，能够有更好的时间复杂度。

#### 双指针 ####

可用于处理排序数组（链表）并需要找满足某些约束的一组元素的问题；数组中的元素集是配对、三元甚至子数组。

*  对应问题 NO.21 调整数组顺序

这个算是双指针的典型应用场景。

#### 快慢指针 ####

处理链表或者数组中循环问题；当需要知道特定元素的位置或链表的总长度时

*  对应问题 NO.22 链表中倒数第K个节点 ；NO.23 链表中环的入口节点

这个也是快慢指针的典型应用场景

### 前K个元素 ###

这个在之前的思维私塾系列中也有所涉及，其常见的解决方法就是大小堆、快排、二叉搜索树。可以回顾一下以前的文章

*  对应题目 NO.40 最小K个数

### BFS和DFS ###

#### BFS ####

宽度优先搜索，遍历一个树并使用一个队列来跟踪一个层级的所有节点，然后再跳转道下一个层级。

主要的工作方式就是使用队列。

#### DFS ####

深度优先搜索，使用递归来在遍历期间保持对所有之前节点的跟踪。

*  相关题目 NO.13 机器人的运动路径

这个算是十分经典的深度/宽度有限搜索算法。不难但是十分经典。

### 栈与队列 ###

栈与队列是很基础的数据结构，在很多算法中我们常常要用的栈或者队列来存储运算过程中的中间数据，所以要对着两个队列的操作十分熟悉

*  对应题目 NO.9 用两个栈实现队列

这个题目加上其镜像问题基本就把常见的队列和栈的操作给覆盖完全了，要是很很好的掌握这个算法问题，那么想必对于栈和队列的问题都能手到擒来

### 二分查找 ###

只要涉及到有序的查找，一定要尽可能的使用二分查找的思想来缩短遍历的范围

*  相关题目 NO.11 旋转数组的最小数字

这个算是用二分查找中比较复杂的问题，因为涉及到的情况还是比较多的，但是仔细思考后还是比较简单的。

*  相关题目 NO.53 在排序数组中查找数字

这个题目竟然和鸡贼的用了两次二分查找，往往很多人能想到用二分查找来解决问题，然后后面就放松警惕了，没想到后续还是需要一次二分查找的。

### 最后 ###

*  如果觉得看完有收获，希望能关注一下，顺便给我点个赞，这将会是我更新的最大动力，感谢各位的支持
 *  欢迎各位关注我的公众号【java冢狐】，专注于java和计算机基础知识，保证让你看完有所收获，不信你打我
 *  求一键三连：点赞、转发、在看。
 *  如果看完有不同的意见或者建议，欢迎多多评论一起交流。感谢各位的支持以及厚爱。

——我是冢狐，和你一样热爱编程。

![image][]

[img]: 
[image]: /images/20221021/2513955278a542d29d74d04a861d7b26.png