前端刷题记录（边刷边学JS算法基础）

前端刷题记录（边刷边学JS算法基础）

2024-12-26 03:39

2022.4.12（快速上手，从0到1掌握算法面试需要的数据结构）

（1）方括号加元素内容直接创建 const arr = [1, 2, 3, 4]

（2）大部分情况下初始化数组时不知道其中的元素内容，需要用到构造函数创建数组的方法

const arr = new Array()

它不传任何参数，是一个空数组，等价于const arr = []

（3）创造指定长度的数组，需要多长的数组就传多大的参数const arr = new Array(7)

（4）fill方法可以将每个坑都填上同样的值const arr = (new Array(7)).fill(1)

访问数组中的元素直接在中括号中指定索引值即可，从0开始

（1）for循环遍历，可以通过循环数组的下标来以此访问每个值

// 获取数组的长度

const len = arr.length

for(let i=0;i<len;i++) { // 输出数组的元素值，输出当前索引 console.log(arr[i], i) }

（2）forEach方法遍历，函数中有两个参数，分别是元素值和当前索引

arr.forEach((item, index)=> { // 输出数组的元素值，输出当前索引 console.log(item, index) })

（3）map方法可以根据传入的函数逻辑对数组中每个元素进行处理、进而返回一个全新的数组。

（1）二维数组初始化

const len = arr.length

for(let i=0;i<len;i++) { // 将数组的每一个坑位初始化为数组 arr[i] = [] }

（2）二维数组的访问

// 缓存外部数组的长度

const outerLen = arr.length

for(let i=0;i<outerLen;i++) { // 缓存内部数组的长度 const innerLen = arr[i].length

for(let j=0;j<innerLen;j++) { // 输出数组的值，输出数组的索引 console.log(arr[i][j],i,j) } }

（1）灵活增删数组

①unshift方法可以添加元素到数组头部

const arr = [1,2] arr.unshift(0) // [0,1,2]

②push方法可以添加元素到数组尾部

const arr = [1,2] arr.push(3) // [1,2,3]

③splice方法添加元素到数组任何位置

const arr = [1,2] arr.splice(1,0,3) // [1,3,2]，在索引1的位置删除0个元素并添加数字3

④shift 方法-删除数组头部的元素

const arr = [1,2,3] arr.shift() // [2,3]

⑤pop 方法-删除数组尾部的元素

const arr = [1,2,3] arr.pop() // [1,2]

⑥splice 方法-删除数组任意位置的元素

arr.splice(1,1)

（2）栈（Stack）——只用 pop 和 push 完成增删的“数组”

栈是一种后进先出(LIFO，Last In First Out)的数据结构。只允许从尾部添加或者取出元素

（3）队列（Queue）——只用 push 和 shift 完成增删的“数组”。先进先出

链表中，数据单位的名称叫做“结点”，而结点和结点的分布，在内存中可以是离散的。

（1）在链表中，每一个结点的结构都包括了两部分的内容：数据域和指针域。JS 中的链表，是以嵌套的对象的形式来实现的：

数据域存储的是当前结点所存储的数据值，而指针域则代表下一个结点（后继结点）的引用。

我们有时还会设定一个 head 指针来专门指向链表的开始位置。

（2）链表节点的创建

创建链表结点，咱们需要一个构造函数：

在使用构造函数创建结点时，传入 val （数据域对应的值内容）、指定 next （下一个链表结点）即可：

（3）链表元素的添加

（4）链表元素的删除

删除的标准是：在链表的遍历过程中，无法再遍历到某个结点的存在。按照这个标准，要想遍历不到 node3，我们直接让它的前驱结点 node1 的 next 指针跳过它、指向 node3 的后继即可：

node1.next = node3.next

在涉及链表删除操作的题目中，重点不是定位目标结点，而是定位目标结点的前驱结点。做题时，完全可以只使用一个指针（引用），这个指针用来定位目标结点的前驱结点。比如说咱们这个题里，其实只要能拿到 node1 就行了：

（5）链表和数组的辨析

在大多数的计算机语言中，数组都对应着一段连续的内存。如果我们想要在任意位置删除一个元素，那么该位置往后的所有元素，都需要往前挪一个位置；相应地，如果要在任意位置新增一个元素，那么该位置往后的所有元素也都要往后挪一个位置。我们假设数组的长度是 n，那么因增加/删除操作导致需要移动的元素数量，就会随着数组长度 n 的增大而增大，呈一个线性关系。所以说数组增加/删除操作对应的复杂度就是 O(n)。相对于数组来说，链表有一个明显的优点，就是添加和删除元素都不需要挪动多余的元素。链表的插入/删除效率较高，而访问效率较低；数组的访问效率较高，而插入效率较低。这个特性需要大家牢记，可能会作为数据结构选型的依据来单独考察。

（1）二叉树遍历

以一定的顺序规则，逐个访问二叉树的所有结点，这个过程就是二叉树的遍历。按照顺序规则的不同，遍历方式有以下四种：

先序遍历
中序遍历
后序遍历
层次遍历

按照实现方式的不同，遍历方式又可以分为以下两种：

递归遍历（先、中、后序遍历）
迭代遍历（层次遍历）

我们此处其实可以穷举一下，假如在保证“左子树一定先于右子树遍历”这个前提，那么遍历的可能顺序也不过三种：

根结点 -> 左子树 -> 右子树
左子树 -> 根结点 -> 右子树
左子树 -> 右子树 -> 根结点

上述三个遍历顺序，就分别对应了二叉树的先序遍历、中序遍历和后序遍历规则。

在这三种顺序中，根结点的遍历分别被安排在了首要位置、中间位置和最后位置。
所谓的“先序”、“中序”和“后序”，“先”、“中”、“后”其实就是指根结点的遍历时机。

①先序遍历，根结点 -> 左子树 -> 右子树

（1）力扣1，两数求和

map哈希表

（2）力扣88，合并两个有序数组

双指针

（3）力扣15，三数之和

有序和数组，除了双指针就选择指针碰撞

2022.4.13（快速上手，从0到1掌握算法面试需要的数据结构）

（1）翻转字符串

在 JS 中，反转字符串我们直接调相关 API 即可，相信不少同学都能手到擒来：

split("") ------根据字符串拆分数组
reverse()------数组反转元素位置
join("")-------数组转回字符串，不带分隔符

（2）判断一个字符串是否是回文字符串

结合这个定义，我们不难写出一个判定回文字符串的方法：

同时，回文字符串还有另一个特性：如果从中间位置“劈开”，那么两边的两个子串在内容上是完全对称的。因此我们也可以结合对称性来做判断：

字符串题干中若有“回文”关键字，那么做题时脑海中一定要冒出两个关键字——对称性 和 双指针。这两个工具一起上，足以解决大部分的回文字符串衍生问题。

编码实现

（3）字符串与数字之间转换问题

①首先来了解一下什么是正则表达式，正则是匹配模式，要么匹配字符串，要么匹配位置

比如/ab{2,5}c/表示：第一个字符是“a”，接下来是2到5个字符“b”，最后是字符“c”。

比如可以匹配如下三种字符串："a1b"、"a2b"、"a3b"。

比如，可以写成。用连字符来省略和简写。

例如，表示是一个除"a"、"b"、"c"之外的任意一个字符。字符组的第一位放（脱字符），表示求反的概念。

（脱字符）匹配开头，在多行匹配中匹配行开头。

（美元符号）匹配结尾，在多行匹配中匹配行结尾。

②直接上代码！

首先，这个符号，意味着空字符，它可以用来匹配回车、空格、换行等空白区域，这里，它用来被匹配空格。跟在其它符号后面，意味着“前面这个符号可以出现0次或多次。，这里的意思就是空格出现0次或多次，都可被匹配到。
JS 的正则相关方法中，方法返回的是一个布尔值，单纯判断“是否匹配”。要想获取匹配的结果，我们需要调度方法，方法是一个在字符串中执行查找匹配的String方法，它返回一个数组，在未匹配到时会返回 null。
这里注意！如果我们的正则表达式尾部有 g 标志，会返回与完整正则表达式匹配的所有结果，但不会返回捕获组。这里我们没有使用g标志，就会返回第一个完整匹配（作为数组的第0项）及其相关的捕获组（作为数组的第1及第1+项）。这里我们只定义了一个捕获组，因此可以从里拿到我们捕获的结果，内容是([-+]?[0-9]*)，就是提取到的数字内容部分，可以完成对后续卡口的判断和最终结果的输出。详情见资料图
捕获组就是把正则表达式中子表达式匹配的内容，保存到内存中以数字编号或显式命名的组里，方便后面引用。当然，这种引用既可以是在正则表达式内部，也可以是在正则表达式外部。
转自正则基础之——捕获组（capture group）_josjonah的博客-CSDN博客_正则捕获组

正则捕获组讲的很详细，可以参考，我只把本题需要的内容提取出来。

if(isNaN(targetNum)) {

// 不能进行有效的转换时，即match没有匹配到符合的数组，请返回 0

targetNum = 0 }

最后的卡口判断就很容易理解啦

（4）字符串匹配问题

①前置知识：原型链

·prototype：显式原型

·__隐式原型__

一般，构造函数的prototype和其实例的__proto__是指向同一个方向，这个地方叫做原型对象

构造函数就是可以用来new的函数。

讨论原型链之前，咱们先来聊聊这两个东西

Person.prototype，它是的原型对象
Function.prototype，他是的原型对象

都说了原型对象，原型对象，可以知道其实这两个本质都是

那既然是，本质肯定都是通过来创建的。既然是通过创建的，那就说明都是的实例。也就说明了他们两的都指向

2022.4.16

如果说在命题时，数组和字符串的角色往往是“算法思想的载体”，那么链表本身就可以被认为是“命题的目的”。单在真题归纳解读环节，我们能讲的技巧、能做的题目已经有很多。结合实际面试中的命题规律，我把这些题目分为以下三类：

链表的处理：合并、删除等（删除操作画个记号，重点中的重点！）
链表的反转及其衍生题目
链表成环问题及其衍生题目

链表的内存空间不是必须连续的，不需要在创建时就确定大小，但是访问任何一个元素都需要从头开始访问。链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。也就是说每一个节点自己有一个data，并且有一个指向下一个节点的指针next，next的指向默认为null。处理链表的本质就是处理链表节点之间的指针关系

我们是可以获取我们的下一个节点的值。我们可以把下一个节点的值给要删除的节点，之后删除下一个节点就可以了

通过双指针进行操作，设置中间值tem

声明两个指针，将两个指针对应的数字相加，把对应位置的相加放入新的链表中，当两个链表的长度不等时，没有节点的时候默认值为0。超过10，计入c中并加到下一个节点的计算中

我们只需要比较当前元素是否和下一个元元素的相等，如果相等就删除下一个元素，不相等，就移动指针继续比较。

我们可以声明两个指针，一快一慢，如果是环形，那总会相遇。

涉及反复遍历的题目，题目本身虽然不会直接跟你说“你好，我是一道需要反复遍历的题目”，但只要你尝试用常规的思路分析它，你会发现它一定涉及反复遍历；同时，涉及反复遍历的题目，还有一个更明显的特征，就是它们往往会涉及相对复杂的链表操作，比如反转、指定位置的删除等等。解决这类问题，我们用到的是双指针中的“快慢指针”。快慢指针指的是两个一前一后的指针，两个指针往同一个方向走，只是一个快一个慢。快慢指针严格来说只能有俩，不过实际做题中，可能会出现一前、一中、一后的三个指针，这种超过两个指针的解题方法也叫“多指针法”。

若需要删除链表倒数第n个结点并返回链表头结点，可以用到dummy，所谓 dummy 结点，就是咱们人为制造出来的第一个结点的前驱结点，这样链表中所有的结点都能确保有一个前驱结点，也就都能够用同样的逻辑来处理了。

let dummy=new ListNode()

dummy.next=head

运用多指针法，定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

这里重点说一下反转局部，反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回 null。

2022.4.17

：入栈 -> 添加一个/多个元素至栈顶
：出栈 -> 移除栈顶元素，并返回被移除的元素
：返回栈顶元素
：该栈是否存在元素
：移除栈中所有元素
：栈中元素个数

括号问题一般首选用栈来做，括号具有对称性，因为根据栈的先进后出特点，一组数据的入栈和出栈顺序刚好是对称的。

我们的思路就是在遍历字符串的过程中，往栈里 push 括号对应的配对字符。比如如果遍历到了，就往栈里 push 。如果括号符合要求，则push进去的

栈结构可以帮我们避免重复操作。
避免重复操作的秘诀就是及时地将不必要的数据出栈，避免它对我们后续的遍历产生干扰。

拿这道题来说，我们的思路就是：尝试去维持一个递减栈。
当遍历过的温度，维持的是一个单调递减的态势时，我们就对这些温度的索引下标执行入栈操作；只要出现了一个数字，它打破了这种单调递减的趋势，也就是说它比前一个温度值高，这时我们就对前后两个温度的索引下标求差，得出前一个温度距离第一次升温的目标差值。

pop在判断过程中已经出栈，不需要额外添加语句，增添新栈，对旧栈操作，新栈要同步更新，新栈仅用于储存最小值，其余操作均在旧栈进行，有数据变化需要同步更新即可

2022.4.21

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。

准备新旧两个栈，旧栈储存数据，新站倒序储存旧栈，旧栈进行操作时，新站同步更新，读取数据时不更新

双端队列就是允许在队列的两端进行插入和删除的队列。

体现在编码上，最常见的载体是既允许使用 pop、push 同时又允许使用 shift、unshift 的数组：

最好是维护一个有效的递减数列

检查队尾元素，看是不是都满足大于等于当前元素的条件。如果是的话，直接将当前元素入队。否则，将队尾元素逐个出队、直到队尾元素大于等于当前元素为止。
将当前元素入队
检查队头元素，看队头元素是否已经被排除在滑动窗口的范围之外了。如果是，则将队头元素出队。
判断滑动窗口的状态：看当前遍历过的元素个数是否小于。如果元素个数小于，这意味着第一个滑动窗口内的元素都还没遍历完、第一个最大值还没出现，此时我们还不能动结果数组，只能继续更新队列；如果元素个数大于等于，这意味着滑动窗口的最大值已经出现了，此时每遍历到一个新元素（也就是滑动窗口每往前走一步）都要及时地往结果数组里添加当前滑动窗口对应的最大值（最大值就是此时此刻双端队列的队头元素）。

①思想为“不撞南墙不回头”，只要没有碰壁，就决不选择其它的道路，而是坚持向当前道路的深处挖掘——像这样将“深度”作为前进的第一要素的搜索方法，就是所谓的“深度优先搜索”。深度优先搜索的核心思想，是试图穷举所有的完整路径。

②本质为栈结构，搜索时的前进与后退，和栈结构的入栈与出栈十分相似，在DFS中往往使用递归来模拟入栈和出栈的逻辑，在DFS中往往使用递归来模拟入栈和出栈的逻辑

③DFS与二叉树的遍历

首先函数调用的底层仍然是由栈来实现的，js会维护一个叫函数调用栈的东西，preorder每一次调用自己就会被push进函数调用栈中，执行完成后被pop出来。有一类情况会记录每一层递归式里路径的状态，因此需要依赖栈结构。

①广度优先搜索（BFS）并不执着于“一往无前”这件事情。它关心的是眼下自己能够直接到达的所有坐标，其动作有点类似于“扫描”，只会关注下一步的目标，不关心更远的目标。

②每访问完毕一个坐标，这个坐标在后续的遍历中都不会再被用到了，也就是说它可以被丢弃掉。站在某个确定坐标的位置上，我们所观察到的可直接抵达的坐标，是需要被记录下来的，因为后续的遍历还要用到它们。丢弃已访问的坐标，标记新观察到的坐标，符合“先进先出”的规则。

3.二叉树的层序遍历

2022.4.22

只要有重复的过程，都要想起递归

visited作为记录本次的数字是否使用，标记使用过在结束时需要重置

[...curr]的用法不改变全局本身来赋值

有时我们会去掉一些不符合题目要求的、没有作用的答案，进而得到正确答案。这个丢掉答案的过程，形似剪掉树的枝叶，所以这一方法被称为“剪枝”。

在这道题中，要做到剪枝，我们需要分别在组合问题的递归式和递归边界上动手脚：

递归式：普通组合问题，每到一个新的坑位处，我们都需要对组合结果数组进行更新；这道题中，当且仅当组合内数字个数为个时，才会对组合结果数组进行更新。
递归边界：只要组合内数字个数达到了个，就不再继续当前的路径往下遍历，而是直接返回。

看两个特征：

题目中暗示了一个或多个解，并且要求我们详尽地列举出每一个解的内容时，一定要想到 DFS、想到递归回溯。
题目经分析后，可以转化为树形逻辑模型求解。

递归与回溯的过程，本身就是穷举的过程。题目中要求我们列举每一个解的内容，解从哪来？解是基于穷举思想、对搜索树进行恰当地剪枝后得来的。

这里需要大家注意到另一种问法：不问解的内容，只问解的个数。这类问题往往不用 DFS 来解，而是用动态规划（我们后面会学）。这里，大家先记下这个辨析，对以后做题会有帮助。

一个模型——树形逻辑模型；两个要点——递归式和递归边界。

树形逻辑模型的构建，关键在于找“坑位”，一个坑位就对应树中的一层，每一层的处理逻辑往往是一样的，这个逻辑就是递归式的内容。至于递归边界，要么在题目中约束得非常清楚、要么默认为“坑位”数量的边界。

2022.4.23

经典命题方向：

迭代法实现二叉树的先、中、后序遍历
二叉树层序遍历的衍生问题
翻转二叉树

递归的方式很简单

下面来看迭代的方式

可以看到，前序遍历的规则是，先遍历根结点、然后遍历左孩子、最后遍历右孩子——这正是我们所期望的出栈序列。按道理，入栈序列和出栈序列相反，我们似乎应该按照这样的顺序将结点入栈。但其实将根结点压入记录后直接出栈，后续先压入右结点在压入左结点即可完成先序遍历

将根结点入栈
取出栈顶结点，将结点值进结果数组
若栈顶结点有右孩子，则将右孩子入栈
若栈顶结点有左孩子，则将左孩子入栈

从结果数组上入手：我们可以直接把出来的当前结点进的头部，改造后的代码会变成这样：

递归方法同样很简单

关键是迭代方法，中序遍历中，根结点不再出现在遍历序列的边界、而是出现在遍历序列的中间。这就意味着无论如何我们不能再将根结点作为第一个被出来的元素来处理了——出栈的时机被改变了，这意味着入栈的逻辑也需要调整。这一次我们不能再通过对动手脚来解决问题。需要直接对stack操作，中序遍历是左根右，首先要定位到最左的叶子结点，然后回溯父结点，再找兄弟结点。

两个：内层的的作用是在寻找最左叶子结点的过程中，把途径的所有结点都记录到里。记录工作完成后，才会走到外层的剩余逻辑里——这部分逻辑的作用是从最左的叶子结点开始，一层层回溯遍历左孩子的父结点和右侧兄弟结点，进而完成整个中序遍历任务。
外层的两个条件：的存在性和的存在性，各自是为了限制什么？
1. 的存在性比较好理解，中存储的是没有被推入结果数组的待遍历元素。只要不为空，就意味着遍历没有结束，遍历动作需要继续重复。
2. 的存在性就比较有趣了。它对应以下几种情况：
  1. 初始态，指向结点，只要不为空，就不为空。此时判断了存在后，就会开始最左叶子结点的寻找之旅。这趟“一路向左”的旅途中，始终指向当前遍历到的左孩子。
  2. 第一波内层循环结束，开始承担中序遍历的遍历游标职责。始终会指向当前栈的栈顶元素，也就是“一路向左”过程中途径的某个左孩子，然后将这个左孩子作为中序遍历的第一个结果元素纳入结果数组。假如这个左孩子是一个叶子结点，那么尝试取其右孩子时就只能取到，这个的存在，会导致内层循环被跳过，接着就直接回溯到了这个左孩子的父结点，符合的序列规则
  3. 假如当前取到的栈顶元素不是叶子结点，同时有一个右孩子，那么尝试取其右孩子时就会取到一个存在的结点。存在，于是进入内层循环，重复“一路向左”的操作，去寻找这个右孩子对应的子树里最靠左的结点，然后去重复刚刚这个或回溯、或“一路向左”的过程。如果这个右孩子对应的子树里没有左孩子，那么跳出内层循环之后，紧接着被纳入结果数组的就是这个右孩子本身，符合的序列规则

102是从上到下，107是从下到上

2022.4.24

二叉搜索树强调的是数据域的有序性。也就是说，二叉搜索树上的每一棵子树，都应该满足

这样的大小关系。

查找数据域为某一特定值的结点
插入新结点
删除指定结点

使用递归：

递归出口：当前节点为空
递归中做的事：
        若左子树为空，返回右子树
        若右子树为空，返回左子树
        左右子树都有值，拿到右子树的最左侧节点
        将要删除的节点的左子树，移到右子树的最左边
        返回右子树，代替当前节点
将当前节点返回上一级递归

它可以是一棵由根结点、左子树、右子树组成的树，同时左子树和右子树都是二叉搜索树，且左子树上所有结点的数据域都小于等于根结点的数据域，右子树上所有结点的数据域都大于等于根结点的数据域

平衡二叉树（又称 AVL Tree）指的是任意结点的左右子树高度差绝对值都不大于1的二叉搜索树。

平衡二叉树的出现，是为了降低二叉搜索树的查找时间复杂度。平衡二叉树由于利用了二分思想，查找操作的时间复杂度仅为 O(logN)。因此，为了保证二叉搜索树能够确实为查找操作带来效率上的提升，我们有必要在构造二叉搜索树的过程中维持其平衡度，这就是平衡二叉树的来由。

对特性的考察（本节以平衡二叉树的判定为例）
对操作的考察（本节以平衡二叉树的构造为例）

中序遍历求出有序数组
逐个将二分出来的数组子序列“提”起来变成二叉搜索树

2022.4.25

从第一层到倒数第二层，每一层都是满的，也就是说每一层的结点数都达到了当前层所能达到的最大值
最后一层的结点是从左到右连续排列的，不存在跳跃排列的情况（也就是说这一层的所有结点都集中排列在最左边）。

完全二叉树中有着这样的索引规律：假如我们从左到右、从上到下依次对完全二叉树中的结点从0开始进行编码：那么对于索引为的结点来说：

索引为的结点是它的父结点
索引的结点是它的左孩子结点
索为引的结点是它的右孩子结点

堆是完全二叉树的特例，分为大顶堆和小顶堆。如果一个完全二叉树，他的每个结点的结点值都不小于其左右孩子的结点值就叫做大顶堆，相反就是小顶堆。

③优先队列

基础排序算法：
- 冒泡排序
- 插入排序
- 选择排序
进阶排序算法
- 归并排序
- 快速排序

912排序题

遍历，遇到比后面大的就交换顺序

在范围内选出最小值将其和范围首部互换

插入排序的核心思想是“找到元素在它前面那个序列中的正确位置”。
具体来说，插入排序所有的操作都基于一个这样的前提：当前元素前面的序列是有序的。基于这个前提，从后往前去寻找当前元素在前面那个序列里的正确位置。

归并排序是对分治思想的典型应用，它按照如下的思路对分治思想“三步走”的框架进行了填充：

分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。（这里的“子问题”指的就是对每个子数组进行排序）。
合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组

快速排序会将原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。