算法复杂度
详情可参考：前端算法与数据结构面试 - 修言小册
评价算法的两个重要依据——时间复杂度和空间复杂度。
时间复杂度
示例如下规模为 n*n 的二维数组的遍历：A
上述代码的总执行次数：
T(n) = 1 + 1 + (n+1) + n + n + n + n*(n+1) + n*n + n*n = 3n^2 + 5n + 3代码的执行次数，可以反映出代码的执行时间。算法的时间复杂度，它反映的不是算法的逻辑代码到底被执行了多少次，而是随着输入规模的增大，算法对应的执行总次数的一个变化趋势。要想反映趋势，直接抓主要矛盾就行。我们可以尝试对 T(n) 做如下处理：
- 若 T(n) 是常数，那么无脑简化为1
- 若 T(n) 是多项式，比如 3n^2 + 5n + 3，我们只保留次数最高那一项，并且将其常数系数无脑改为1。
T(n) 就被简化为了 O(n)：
T(n) = 3n^2 + 5n + 3
O(n) = n^2常见的时间复杂度按照从小到大的顺序排列，有以下几种：
空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。和时间复杂度相似，它是内存增长的趋势。常见的空间复杂度有 O(1)、O(n) 和 O(n^2)。
示例：初始化一个规模为 n 的数组，并且要求这个数组的每个元素的值与其索引始终是相等关系
function init(n) {
var arr = []
for(var i=0;i<n;i++) {
arr[i] = i
}
return arr
}在这个 init 中，涉及到的占用内存的变量有以下几个：
n
arr
i这个 arr，它并不是一个一成不变的数组。arr最终的大小是由输入的 n 的大小决定的，它会随着 n 的增大而增大、呈一个线性关系。因此这个算法的空间复杂度就是 O(n)。
数组
基础知识
详情可参考：前端算法与数据结构面试 - 修言小册
一维数组
1、一维数组的创建
// 方式一
const arr = []
// 方式二：常用于创造指定长度的空数组，如下传入一个参数，就表示能得到多大的数组
const arr = new Array(7);创建一个确定的数组
// 创建一个长度为7、同时每一个元素的值都为1的数组
const arr = (new Array(7)).fill(1)2、数组的访问
arr[0] // 访问索引下标为0的元素3、数组的遍历
（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 方法
其主要相当于在遍历数组的基础上“再加工”。可以根据传入的函数逻辑对数组中每个元素进行处理、进而返回一个全新的数组。
const newArr = arr.map((item, index)=> {
// 输出数组的元素值，输出当前索引
console.log(item, index)
// 在当前元素值的基础上加1
return item+1
})建议：如果没有特殊需要，最好统一使用 for 循环来实现遍历。因为从性能上看，for 循环遍历起来是最快的。
4、数组新增元素
const arr = [1,2]
// 方式1：unshift 方法-添加元素到数组的头部
arr.unshift(0) // [0,1,2]
// 方式2：push 方法-添加元素到数组的尾部
arr.push(3) // [1,2,3]
// 方式3：splice 方法-添加元素到数组的任何位置
arr.splice(1,0,3)
consoloe.log(arr); // // [1,3,2]1、splice 语法，第一个入参是起始的索引值，第二个入参表示从起始索引开始需要删除的元素个数，第三个参数是用于在删除的同时新增数组元素，从第三个位置开始的入参，都代表着需要添加到数组里的元素的值。2、返回删除的元素数组，会改变原始数组。
5、数组删除元素
const arr = [1,2,3]
// 方式1：shift 方法-删除数组头部的元素
arr.shift() // [2,3]
// 方式2：pop 方法-删除数组尾部的元素
arr.pop() // [1,2]
// 方式3：splice 方法-删除数组任意位置的元素
app.splice(1, 1);
consoloe.log(arr); // [1,3]二维数组
二维数组其实就是数组套数组，也就是每个元素都是数组的数组。别名叫“矩阵”。
const arr = [
[1,2,3,4,5],
[1,2,3,4,5],
[1,2,3,4,5],
]1、二维数组的创建及初始化
const arr = new Array(7);
const len = arr.length;
for(let i = 0; i < len; i++) {
// 将数组的每一个坑位初始化为数组
arr[i] = []
}在初始化时，不要使用fill([]) 去填充二维数组元素，因为如果当想修改某一个二维数组中的值时，使用 arr[0][0] = 1 这种方式，会把一整列的元素都被设为了 1，这是由于当你给 fill 传递一个入参时，如果这个入参的类型是引用类型，那么 fill 在填充坑位时填充的其实就是入参的引用。
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、几乎所有的求和问题，都可以转化为求差问题。 2、双指针法。【关键字：“有序”和“数组”】 （1）普通双指针法【两个指针在数组尾端或起端】。 （2）对撞双指针法【左右指针一起从两边往中间位置相互迫近】
1、两数之和
可以在遍历数组的过程中，增加一个 Map 来记录已经遍历过的数字及其对应的索引值。然后每遍历到一个新数字的时候，都回到 Map 里去查询 targetNum 与该数的差值是否已经在前面的数字中出现过了。若出现过，则得到答案。
/** map妙用
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
if (map.has(target - nums[i])) {
return [i, map.get(target - nums[i])];
}
map.set(nums[i], i);
}
};
/** 对象字面量定义，实现类似map的效果
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum = function(nums, target) {
// 这里我用对象来模拟 map 的能力
const diffs = {}
// 缓存数组长度
const len = nums.length
// 遍历数组
for(let i=0;i<len;i++) {
// 判断当前值对应的 target 差值是否存在（是否已遍历过）
if(diffs[target-nums[i]]!==undefined) {
// 若有对应差值，那么答案get！
return [diffs[target - nums[i]], i]
}
// 若没有对应差值，则记录当前值
diffs[nums[i]]=i
}
};2、合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
首先定义两个指针，各指向两个数组生效部分的尾部，每次只对指针所指的元素进行比较，取其中较大的元素，把它从 nums1 的末尾往前面填补。
为什么是从后往前填补？因为是要把所有的值合并到 nums1 里，所以说我们这里可以把 nums1 看做是一个“容器”。但是这个容器，它不是空的，而是前面几个坑有内容的。如果我们从前往后填补，就没法直接往对应的坑位赋值了（会产生值覆盖）。从后往前填补，我们填的都是没有内容的坑，这样会省掉很多麻烦。
由于 nums1 的有效部分和 nums2 并不一定是一样长的。我们还需要考虑其中一个数组提前到头的这种情况：
- 如果提前遍历完的是 nums1 的有效部分，剩下的是 nums2。那么这时意味着 nums1 的头部空出来了，直接把 nums2 整个补到 nums1 前面去即可。
- 如果提前遍历完的是 nums2，剩下的是 nums1。由于容器本身就是 nums1，所以此时不必做任何额外的操作。
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
const merge = function(nums1, m, nums2, n) {
// 初始化两个指针的指向，初始化 nums1 尾部索引k
let i = m - 1, j = n - 1, k = m + n - 1
// 当两个数组都没遍历完时，指针同步移动
while(i >= 0 && j >= 0) {
// 取较大的值，从末尾往前填补
if(nums1[i] >= nums2[j]) {
nums1[k] = nums1[i]
i--
k--
} else {
nums1[k] = nums2[j]
j--
k--
}
}
// nums2 留下的情况，特殊处理一下
while(j>=0) {
nums1[k] = nums2[j]
k--
j--
}
};3、三数求和
我们可以把求和问题变成求差问题——固定其中一个数，在剩下的数中寻找是否有两个数和这个固定数相加是等于0的。
首先，对于无序数组，先将数组排序，然后，对数组进行遍历，每次遍历到哪个数字，就固定哪个数字。然后把左指针指向该数字后面一个坑里的数字，把右指针指向数组末尾，让左右指针从起点开始，向中间前进：
每次指针移动一次位置，就计算一下两个指针指向数字之和加上固定的那个数之后，是否等于0。如果是，那么我们就得到了一个目标组合；否则，分两种情况来看：
- 相加之和大于0，说明右侧的数偏大了，右指针左移
- 相加之和小于0，说明左侧的数偏小了，左指针右移
此外，还要注意还需要做一个重复元素的跳过处理。
/**
* @param {number[]} nums
* @return {number[][]}
*/
const threeSum = function(nums) {
// 用于存放结果数组
let res = []
// 给 nums 排序
nums = nums.sort((a,b)=>{
return a-b
})
// 缓存数组长度
const len = nums.length
// 注意我们遍历到倒数第三个数就足够了，因为左右指针会遍历后面两个数
for(let i=0;i<len-2;i++) {
// 左指针 j
let j=i+1
// 右指针k
let k=len-1
// 如果遇到重复的数字，则跳过
if(i>0&&nums[i]===nums[i-1]) {
continue
}
while(j<k) {
// 三数之和小于0，左指针前进
if(nums[i]+nums[j]+nums[k]<0){
j++
// 处理左指针元素重复的情况
while(j<k&&nums[j]===nums[j-1]) {
j++
}
} else if(nums[i]+nums[j]+nums[k]>0){
// 三数之和大于0，右指针后退
k--
// 处理右指针元素重复的情况
while(j<k&&nums[k]===nums[k+1]) {
k--
}
} else {
// 得到目标数字组合，推入结果数组
res.push([nums[i],nums[j],nums[k]])
// 左右指针一起前进
j++
k--
// 若左指针元素重复，跳过
while(j<k&&nums[j]===nums[j-1]) {
j++
}
// 若右指针元素重复，跳过
while(j<k&&nums[k]===nums[k+1]) {
k--
}
}
}
}
// 返回结果数组
return res
};详情可参考：前端算法与数据结构面试 - 修言小册
栈
基础知识
栈是一种后进先出(LIFO，Last In First Out)的数据结构，它有两个特征：
- 只允许从尾部添加元素
- 只允许从尾部取出元素
对应到数组的方法，刚好就是 push 和 pop。因此，我们可以认为在 JavaScript 中，栈就是限制只能用 push 来添加元素，同时只能用 pop 来移除元素的一种特殊的数组。
// 初始状态，栈空
const stack = []
// 入栈过程
stack.push('东北大板')
stack.push('可爱多')
stack.push('巧乐兹')
stack.push('冰工厂')
stack.push('光明奶砖')
// 出栈过程，栈不为空时才执行
while(stack.length) {
// 单纯访问栈顶元素（不出栈）
const top = stack[stack.length-1]
console.log('现在取出的冰淇淋是', top)
// 将栈顶元素出栈
stack.pop()
}
// 栈空
stack // []栈专题应用
详情可参考：前端算法与数据结构面试 - 修言小册
总结归纳 1、题目中若涉及括号问题，则很有可能和栈相关。 2、考虑维护一个辅助栈、递减栈，利用空间换时间。
使用栈实现，思路就是在遍历字符串的过程中，往栈里 push 括号对应的配对字符。比如如果遍历到了 (，就往栈里 push )。当字符串遍历得到的是右括号时，看栈顶出栈得到的数据和遍历的数据是否一致，如果一直则继续遍历对比，直到全部对比完成。不一致则说明配对失败，返回false。
// 用一个 map 来维护左括号和右括号的对应关系
const leftToRight = {
"(": ")",
"[": "]",
"{": "}"
};
/**
* @param {string} s
* @return {boolean}
*/
const isValid = function(s) {
// 结合题意，空字符串无条件判断为 true
if (!s) {
return true;
}
// 初始化 stack 数组
const stack = [];
// 缓存字符串长度
const len = s.length;
// 遍历字符串
for (let i = 0; i < len; i++) {
// 缓存单个字符
const ch = s[i];
// 判断是否是左括号，这里我为了实现加速，没有用数组的 includes 方法，直接手写判断逻辑
if (ch === "(" || ch === "{" || ch === "[") stack.push(leftToRight[ch]);
// 若不是左括号，则必须是和栈顶的左括号相配对的右括号
else {
// 若栈不为空，且栈顶的左括号没有和当前字符匹配上，那么判为无效
if (!stack.length || stack.pop() !== ch) {
return false;
}
}
}
// 若所有的括号都能配对成功，那么最后栈应该是空的
return !stack.length;
};暴力遍历法：直接两层遍历，第一层定位一个温度，第二层定位离这个温度最近的一次升温是哪天，然后求出两个温度对应索引的差值即可。
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function(temperatures) {
const len = temperatures.length;
const res = (new Array(len)).fill(0);
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if (temperatures[j] > temperatures[i]) {
res[i] = j - i;
break;
}
}
}
return res;
};使用栈实现。尝试去维持一个递减栈。
/**
* @param {number[]} T
* @return {number[]}
*/
// 入参是温度数组
const dailyTemperatures = function(T) {
const len = T.length // 缓存数组的长度
const stack = [] // 初始化一个栈
const res = (new Array(len)).fill(0) // 初始化结果数组，注意数组定长，占位为0
for(let i=0;i<len;i++) {
// 若栈不为0，且存在打破递减趋势的温度值
while(stack.length && T[i] > T[stack[stack.length-1]]) {
// 将栈顶温度值对应的索引出栈
const top = stack.pop()
// 计算 当前栈顶温度值与第一个高于它的温度值 的索引差值
res[top] = i - top
}
// 注意栈里存的不是温度值，而是索引值，这是为了后面方便计算
stack.push(i)
}
// 返回结果数组
return res
};暴力解法
/**
* 初始化你的栈结构
*/
const MinStack = function() {
this.stack = []
};
/**
* @param {number} x
* @return {void}
*/
// 栈的入栈操作，其实就是数组的 push 方法
MinStack.prototype.push = function(x) {
this.stack.push(x)
};
/**
* @return {void}
*/
// 栈的入栈操作，其实就是数组的 pop 方法
MinStack.prototype.pop = function() {
this.stack.pop()
};
/**
* @return {number}
*/
// 取栈顶元素，咱们教过的哈，这里我本能地给它一个边界条件判断（其实不给也能通过，但是多做不错哈）
MinStack.prototype.top = function() {
if(!this.stack || !this.stack.length) {
return
}
return this.stack[this.stack.length - 1]
};
/**
* @return {number}
*/
// 按照一次遍历的思路取最小值
MinStack.prototype.getMin = function() {
let minValue = Infinity
const { stack } = this
for(let i=0; i<stack.length;i++) {
if(stack[i] < minValue) {
minValue = stack[i]
}
}
return minValue
};使用辅助栈 stack2。实现的是一个从栈底到栈顶呈递减趋势的栈。
- 取最小值：由于整个栈从栈底到栈顶递减，因此栈顶元素就是最小元素。
- 若有新元素入栈：判断是不是比栈顶元素还要小，否则不准进入
stack2。 - 若有元素出栈：判断是不是和栈顶元素相等，如果是的话，
stack2也要出栈。
const MinStack = function() {
this.stack = [];
// 定义辅助栈
this.stack2 = [];
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x);
// 若入栈的值小于当前最小值，则推入辅助栈栈顶
if(this.stack2.length == 0 || this.stack2[this.stack2.length-1] >= x){
this.stack2.push(x);
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
// 若出栈的值和当前最小值相等，那么辅助栈也要对栈顶元素进行出栈，确保最小值的有效性
if(this.stack.pop() == this.stack2[this.stack2.length-1]){
this.stack2.pop();
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length-1];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
// 辅助栈的栈顶，存的就是目标中的最小值
return this.stack2[this.stack2.length-1];
};详情可参考：前端算法与数据结构面试 - 修言小册
队列
基础知识
队列是一种先进先出（FIFO，First In First Out）的数据结构。它也有两个特征：
- 只允许从尾部添加元素
- 只允许从头部移除元素
对应到数组方法，就是数组的 push 和 shift 方法。因此，我们可以认为在 JavaScript 中，栈就是限制只能用 push 来添加元素，同时只能用shift来移除元素的一种特殊的数组。
const queue = []
queue.push('小册一姐')
queue.push('小册二姐')
queue.push('小册三姐')
while(queue.length) {
// 单纯访问队头元素（不出队）
const top = queue[0]
console.log(top,'取餐')
// 将队头元素出队
queue.shift()
}
// 队空
queue // []队列专题应用
详情可参考：前端算法与数据结构面试 - 修言小册
总结归纳 1、题目中若涉及括号问题，则很有可能和栈相关。 2、
用栈实现队列，说白了就是用栈实现先进先出的效果，再说直接点，就是想办法让栈底的元素首先被取出，也就是让出栈序列被逆序。
/**
* 初始化构造函数
*/
const MyQueue = function () {
// 初始化两个栈
this.stack1 = [];
this.stack2 = [];
};
/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
// 直接调度数组的 push 方法
this.stack1.push(x);
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function () {
// 假如 stack2 为空，需要将 stack1 的元素转移进来
if (this.stack2.length <= 0) {
// 当 stack1 不为空时，出栈
while (this.stack1.length !== 0) {
// 将 stack1 出栈的元素推入 stack2
this.stack2.push(this.stack1.pop());
}
}
// 为了达到逆序的目的，我们只从 stack2 里出栈元素
return this.stack2.pop();
};
/**
* Get the front element.
* @return {number}
* 这个方法和 pop 唯一的区别就是没有将定位到的值出栈
*/
MyQueue.prototype.peek = function () {
if (this.stack2.length <= 0) {
// 当 stack1 不为空时，出栈
while (this.stack1.length != 0) {
// 将 stack1 出栈的元素推入 stack2
this.stack2.push(this.stack1.pop());
}
}
// 缓存 stack2 的长度
const stack2Len = this.stack2.length;
return stack2Len && this.stack2[stack2Len - 1];
};
/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
// 若 stack1 和 stack2 均为空，那么队列空
return !this.stack1.length && !this.stack2.length;
};双指针 + 遍历实现。定义一个 left 左指针、定义一个 right 右指针，分别指向窗口的两端，接下来我们可以把这个窗口里的数字取出来，直接遍历一遍、求出最大值，然后把最大值存进结果数组。这样第一个窗口的最大值就有了。然后左右指针再前进一步，重复上述过程。
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
const maxSlidingWindow = function (nums, k) {
// 缓存数组的长度
const len = nums.length;
// 定义结果数组
const res = [];
// 初始化左指针
let left = 0;
// 初始化右指针
let right = k - 1;
// 当数组没有被遍历完时，执行循环体内的逻辑
while (right < len) {
// 计算当前窗口内的最大值
const max = calMax(nums, left, right);
// 将最大值推入结果数组
res.push(max);
// 左指针前进一步
left++;
// 右指针前进一步
right++;
}
// 返回结果数组
return res;
};
// 这个函数用来计算最大值
function calMax(arr, left, right) {
// 处理数组为空的边界情况
if (!arr || !arr.length) {
return;
}
// 初始化 maxNum 的值为窗口内第一个元素
let maxNum = arr[left];
// 遍历窗口内所有元素，更新 maxNum 的值
for (let i = left; i <= right; i++) {
if (arr[i] > maxNum) {
maxNum = arr[i];
}
}
// 返回最大值
return maxNum;
}双端队列实现。双端队列就是允许在队列的两端进行插入和删除的队列。
字符串
详情可参考：前端算法与数据结构面试 - 修言小册
基本算法
总结归纳 1、回文字符串对称性。 2、双指针法。 3、正则表达式。
/**
* @param {character[]} s 输入字符数组 s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
return s.reverse();
};
// 输入字符串 str: abcde
var reverseString = function(str) {
return str.split('').reverse().join('');
};回文字符串，就是正着读和倒着读都一样的字符串。
// 方式1 反转字符串和原字符串对比
function isPalindrome(str) {
//先替换掉所有非字母和数字,再替换掉所有的空格
s = s.replace(/[^a-zA-Z0-9]/g,"").replace(/\s/g,"").toLowerCase();
// 先反转字符串
const reversedStr = str.split('').reverse().join('')
// 判断反转前后是否相等
return reversedStr === str
}
// 方式2 对称性
function isPalindrome(str) {
//先替换掉所有非字母和数字,再替换掉所有的空格
s = s.replace(/[^a-zA-Z0-9]/g,"").replace(/\s/g,"").toLowerCase();
// 缓存字符串的长度
const len = str.length
// 遍历前半部分，判断和后半部分是否对称
for(let i=0;i<len/2;i++) {
if(str[i]!==str[len-i-1]) {
return false
}
}
return true
}使用对称性和双指针方法实现。首先是初始化两个指针，一个指向字符串头部，另一个指向尾部：
如果两个指针所指的字符恰好相等，那么这两个字符就符合了回文字符串对对称性的要求，跳过它们往下走即可。如果两个指针所指的字符串不等，那么就意味着不对称发生了，意味着这是一个可以“删掉试试看”的操作点。我们可以分别对左指针字符和右指针字符尝试进行“跳过”，看看区间在 [left+1, right] 或 [left, right-1] 的字符串是否回文。如果是的话，那么就意味着如果删掉被“跳过”那个字符，整个字符串都将回文。
const validPalindrome = function(s) {
// 缓存字符串的长度
const len = s.length
// i、j分别为左右指针
let i=0, j=len-1
// 当左右指针均满足对称时，一起向中间前进
while(i<j&&s[i]===s[j]) {
i++
j--
}
// 尝试判断跳过左指针元素后字符串是否回文
if(isPalindrome(i+1,j)) {
return true
}
// 尝试判断跳过右指针元素后字符串是否回文
if(isPalindrome(i,j-1)) {
return true
}
// 工具方法，用于判断字符串是否回文
function isPalindrome(st, ed) {
while(st<ed) {
if(s[st] !== s[ed]) {
return false
}
st++
ed--
}
return true
}
// 默认返回 false
return false
};Step1：计算最大值和最小值
Step2：解析字符串：可能存在的空格+正负号+数字字符串+其它字符内容
\s这个符号，意味着空字符，它可以用来匹配回车、空格、换行等空白区域，这里，它用来被匹配空格。*这个符号，跟在其它符号后面，意味着“前面这个符号可以出现0次或多次。[]中的匹配符之间是“或”的关系，[-\+]表示允许字符串的第一个有效字符为“+”或者“—”。[0-9]*是0-9之间的整数，能匹配到0个或多个就算匹配成功。.是任意字符的意思，.*用于字符串尾部匹配非数字的任意字符。我们看到.*是被排除捕获组之外的，所以说这个东西其实也不会被额外存储，它被“摘除”了。
Step3：获取捕获结果
JS 的正则相关方法中， test()方法返回的是一个布尔值，单纯判断“是否匹配”。
要想获取匹配的结果，我们需要调度match()方法，match() 方法是一个在字符串中执行查找匹配的String方法，它返回一个数组，在未匹配到时会返回 null。
如果我们的正则表达式尾部有 g 标志，match()会返回与完整正则表达式匹配的所有结果，但不会返回捕获组。
这里我们没有使用g标志，match()就会返回第一个完整匹配（作为数组的第0项）及其相关的捕获组（作为数组的第1及第1+项）。这里我们只定义了一个捕获组，因此可以从 groups[1] 里拿到我们捕获的结果。
/**
* @param {string} str
* @return {number}
*/
const strToInt = function(str) {
// 编写正则表达式
const reg = /\s*([-\+]?[0-9]*).*/
// 得到捕获组
const groups = str.match(reg)
// 计算最大值
const max = Math.pow(2,31) - 1
// 计算最小值
const min = -max - 1
// targetNum 用于存储转化出来的数字
let targetNum = 0
// 如果匹配成功
if(groups) {
// 尝试转化捕获到的结构
targetNum = +groups[1]
// 注意，即便成功，也可能出现非数字的情况，比如单一个'+'
if(isNaN(targetNum)) {
// 不能进行有效的转换时，请返回 0
targetNum = 0
}
}
// 卡口判断
if(targetNum > max) {
return max
} else if( targetNum < min) {
return min
}
// 返回转换结果
return targetNum
};链表
详情可参考：前端算法与数据结构面试 - 修言小册
在链表中，数据单位的名称叫做“结点”，而结点和结点的分布，在内存中可以是离散的，链表同数组类似，都是线性结构（有且仅有一个前驱、有且仅有一个后继）。
基础知识
1、链表和数组的区别
数组在内存中最为关键的一个特征，就是它一般是对应一段位于自己上界和下界之间的、一段连续的内存空间。由于数组中的元素是连续的，每个元素的内存地址可以根据其索引距离数组头部的距离来计算出来。因此对数组来说，每一个元素都可以通过数组的索引下标直接定位。
数组的访问效率较高，而插入效率较低。
而链表中的结点，则允许散落在内存空间的各个角落里。元素和元素之间似乎毫无内存上的瓜葛可言，没有关联，因此需要创建关联。在链表中，每一个结点的结构都包括了两部分的内容：数据域和指针域。
链表的插入/删除效率较高，而访问效率较低。
2、JS链表实现
以嵌套的对象形式来实现，如下：
{
// 数据域
val: 1,
// 指针域，指向下一个结点
next: {
val:2,
next: ...
}
} 数据域存储的是当前结点所存储的数据值，而指针域则代表下一个结点（后继结点）的引用。
3、链表结点的创建
function ListNode(val) {
this.val = val;
this.next = null;
}在使用构造函数创建结点时，传入 val （数据域对应的值内容）、指定 next （下一个链表结点）即可：
const node1 = new ListNode(1);
const node2 = new ListNode(2);
node1.next = node2;4、链表元素的添加
// 方式一：链表尾部添加结点，直接改变尾部的一个next 指针就行
const node3 = new ListNode(3);
node2.next = node3;
// 方式二：任意两结点间插入一个新结点(包括头结点)
// 如果目标结点本来不存在，那么记得手动创建
const node3 = new ListNode(3);
// 把node3的 next 指针指向 node2（即 node1.next）
node3.next = node1.next;
// 把node1的 next 指针指向 node3
node1.next = node3;5、链表元素的删除
把上边添加进来的 node3 从现在的链表里删掉
// 方式一：链表尾部删除结点，直接改变尾部的一个next 指针就行
node2.next = null;
// 方式二：任意两结点间插入一个新结点(包括头结点)
node1.next = node3.next注意点：在涉及链表删除操作的题目中，重点不是定位目标结点，而是定位目标结点的前驱结点。做题时，完全可以只使用一个指针（引用），这个指针用来定位目标结点的前驱结点。
// 利用 node1 可以定位到 node3
const target = node1.next
node1.next = target.next6、链表和数组的辨析
在大多数的计算机语言中，我们假设数组的长度是 n，那么因增加/删除操作导致需要移动的元素数量，就会随着数组长度 n 的增大而增大，呈一个线性关系。所以说数组增加/删除操作对应的复杂度就是 O(n)。
但 JS 中不一定是。 如果我们在一个数组中只定义了一种类型的元素，如纯数字数组 arr = [1,2,3]，那么对应的确实是连续内存。
但如果我们定义了不同类型的元素，如下：
const arr = ['haha', 1, {a:1}]它对应的就是一段非连续的内存。此时，JS 数组不再具有数组的特征，其底层使用哈希映射分配内存空间，是由对象链表来实现的。
所以，“JS 数组未必是真正的数组”。
链表专题应用
总结归纳 1、链表循环，大部分都用 while 循环。 2、处理链表的本质，是处理链表结点之间的指针关系。 3、惯用 dummy 结点【人为制造出来的链表第一个结点的前驱结点】，解决链表头结点不存在前驱结点问题，尤其是涉及结点删除的题目。 4、涉及反复遍历的题目常用快慢指针或者多指针法解决。 5、环形链表可通过立flag的方式进行判断。
链表基本处理
详情可参考：前端算法与数据结构面试 - 修言小册
处理链表的本质，是处理链表结点之间的指针关系。两个链表如果想要合并为一个链表，我们恰当地补齐双方之间结点 next 指针的指向关系，然后通过比较链表值进行穿针。
同时我们还要考虑 l1 和 l2 两个链表长度不等的情况：若其中一个链表已经完全被串进新链表里了，而另一个链表还有剩余结点，考虑到该链表本身就是有序的，我们可以直接把它整个拼到目标链表的尾部。
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
const mergeTwoLists = function(l1, l2) {
// 定义头结点，确保链表可以被访问到
let head = new ListNode()
// cur 这里就是咱们那根“针”
let cur = head
// “针”开始在 l1 和 l2 间穿梭了
while(l1 && l2) {
// 如果 l1 的结点值较小
if(l1.val<=l2.val) {
// 先串起 l1 的结点
cur.next = l1
// l1 指针向前一步
l1 = l1.next
} else {
// l2 较小时，串起 l2 结点
cur.next = l2
// l2 向前一步
l2 = l2.next
}
// “针”在串起一个结点后，也会往前一步
cur = cur.next
}
// 处理链表不等长的情况
cur.next = l1!==null?l1:l2
// 返回起始结点
return head.next
};删除链表元素，将需要删除的目标结点的前驱结点 next 指针往后指一格。判断两个元素是否重复，由于此处是已排序的链表，我们直接判断前后两个元素值是否相等即可。
/**
* @param {ListNode} head
* @return {ListNode}
*/
const deleteDuplicates = function(head) {
// 设定 cur 指针，初始位置为链表第一个结点
let cur = head;
// 遍历链表
while(cur != null && cur.next != null) {
// 若当前结点和它后面一个结点值相等（重复）
if(cur.val === cur.next.val) {
// 删除靠后的那个结点（去重）
cur.next = cur.next.next;
} else {
// 若不重复，继续遍历
cur = cur.next;
}
}
return head;
};我们要删除某一个目标结点时，必须知道它的前驱结点。如果是链表的第一个结点，因为没有前驱结点，这时我们就可以用一个 dummy 结点来解决这个问题。
/**
* @param {ListNode} head
* @return {ListNode}
*/
const deleteDuplicates = function(head) {
// 极端情况：0个或1个结点，则不会重复，直接返回
if(!head || !head.next) {
return head
}
// dummy 登场
let dummy = new ListNode()
// dummy 永远指向头结点
dummy.next = head
// cur 从 dummy 开始遍历
let cur = dummy
// 当 cur 的后面有至少两个结点时
while(cur.next && cur.next.next) {
// 对 cur 后面的两个结点进行比较
if(cur.next.val === cur.next.next.val) {
// 若值重复，则记下这个值
let val = cur.next.val
// 反复地排查后面的元素是否存在多次重复该值的情况
while(cur.next && cur.next.val===val) {
// 若有，则删除
cur.next = cur.next.next
}
} else {
// 若不重复，则正常遍历
cur = cur.next
}
}
// 返回链表的起始结点
return dummy.next;
};链表的反转及其衍生题目
详情可参考：前端算法与数据结构面试 - 修言小册
考虑到咱们的遍历不可能从后往前走，因此这个“倒数第 N 个” 咱们完全可以转换为“正数第 len - n + 1“个。
首先设定两个指针 slow 和 fast，全部指向链表的起始位——dummy 结点。然后快指针先出发，闷头走上 n 步，在第 n 个结点处打住。然后，快慢指针一起前进，当快指针前进到最后一个结点处时，两个指针再一起停下来。此时，慢指针所指的位置，就是倒数第 n 个结点的前一个结点，此时执行删除操作即可。
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
const removeNthFromEnd = function(head, n) {
// 初始化 dummy 结点
const dummy = new ListNode()
// dummy指向头结点
dummy.next = head
// 初始化快慢指针，均指向dummy
let fast = dummy
let slow = dummy
// 快指针闷头走 n 步
while(n!==0){
fast = fast.next
n--
}
// 快慢指针一起走
while(fast.next){
fast = fast.next
slow = slow.next
}
// 慢指针删除自己的后继结点
slow.next = slow.next.next
// 返回头结点
return dummy.next
};使用多指针法。我们需要用到三个指针，它们分别指向目标结点（cur）、目标结点的前驱结点（pre）、目标结点的后继结点（next）。
/**
* @param {ListNode} head
* @return {ListNode}
*/
const reverseList = function(head) {
// 初始化前驱结点为 null
let pre = null;
// 初始化目标结点为头结点
let cur = head;
// 只要目标结点不为 null，遍历就得继续
while (cur !== null) {
// 记录一下 next 结点
let next = cur.next;
// 反转指针
cur.next = pre;
// pre 往前走一步
pre = cur;
// cur往前走一步
cur = next;
}
// 反转结束后，pre 就会变成新链表的头结点
return pre
};局部反转链表需要考虑的是局部反转链表的前驱和后继指向。
/**
* @param {ListNode} head
* @param {number} m
* @param {number} n
* @return {ListNode}
*/
// 入参是头结点、m、n
const reverseBetween = function(head, m, n) {
// 定义pre、cur，用leftHead来承接整个区间的前驱结点
let pre,cur,leftHead
// 别忘了用 dummy 嗷
const dummy = new ListNode()
// dummy后继结点是头结点
dummy.next = head
// p是一个游标，用于遍历，最初指向 dummy
let p = dummy
// p往前走 m-1 步，走到整个区间的前驱结点处
for(let i=0;i<m-1;i++){
p = p.next
}
// 缓存这个前驱结点到 leftHead 里
leftHead = p
// start 是反转区间的第一个结点
let start = leftHead.next
// pre 指向start
pre = start
// cur 指向 start 的下一个结点
cur = pre.next
// 开始重复反转动作
for(let i=m;i<n;i++){
let next = cur.next
cur.next = pre
pre = cur
cur = next
}
// leftHead 的后继结点此时为反转后的区间的第一个结点
leftHead.next = pre
// 将区间内反转后的最后一个结点 next 指向 cur
start.next=cur
// dummy.next 永远指向链表头结点
return dummy.next
};链表成环问题及其衍生题目
详情可参考：前端算法与数据结构面试 - 修言小册
遍历一个环形链表，判断是否有flag，如果有flag，则说明是环形链表，如果结点没有flag，则设立flag。
/**
* @param {ListNode} head
* @return {boolean}
*/
// 入参是头结点
const hasCycle = function(head) {
// 只要结点存在，那么就继续遍历
while(head){
// 如果 flag 已经立过了，那么说明环存在
if(head.flag){
return true;
}else{
// 如果 flag 没立过，就立一个 flag 再往
下走
head.flag = true;
head = head.next;
}
}
return false;
};我们从头开始遍历一个链表，假如途中进入了一个环，那么首先被打上 flag 标签的其实就是环的起点。待我们遍历完这个环时，即便环上所有的结点都已经被立了 flag，但起点处的 flag 一定最先被我们定位到。因此，我们只需要在第一次发现 flag 已存在时，将对应的结点返回即可。
/**
* @param {ListNode} head
* @return {ListNode}
*/
const detectCycle = function(head) {
while(head){
if(head.flag){
return head;
}else{
head.flag = true;
head = head.next;
}
}
return null;
};快慢指针实现。我们使用两个指针，fast与 slow。它们起始都位于链表的头部。整个链表的长度为s，随后，slow 指针每次向后移动一个位置，移动到链表尾部需要t次，而 fast 指针向后移动两个位置，移动到链表尾部需要2t次。如果链表中存在环，则 2t - t = s 即 t = s 的时候，fast 指针最终将再次与 slow 指针在环中相遇。
当发现 slow与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
let slow = head;
let fast = head;
if (head === null) {
return null;
}
while (fast !== null) {
slow = slow.next;
if (fast.next !== null) {
fast = fast.next.next;
} else {
return null;
}
if (fast === slow) {
let ptr = head;
while (ptr !== slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
};树
详情可参考：前端算法与数据结构面试 - 修言小册
基础知识
计算机世界的树结构是对现实世界中树的一层简化：把树根抽象为“根结点”，树枝抽象为“边”，树枝的两个端点抽象为“结点”，树叶抽象为“叶子结点”。
树的关键特性有以下几点：
- 树的层次计算规则：根结点所在的那一层记为第一层，其子结点所在的就是第二层，以此类推。
- 结点和树的“高度”计算规则：叶子结点高度记为1，每向上一层高度就加1，逐层向上累加至目标结点时，所得到的的值就是目标结点的高度，即叶子结点和根节点的层数。树中结点的最大高度，称为“树的高度”。
- “度”的概念：一个结点开叉出去多少个子树，被记为结点的“度”。比如我们上图中，根结点的“度”就是3。
- “叶子结点”：叶子结点就是度为0的结点。在上图中，最后一层的结点的度全部为0，所以这一层的结点都是叶子结点。
二叉树创建
二叉树是指满足以下要求的树：
- 它可以没有根结点，作为一棵空树存在
- 如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。
注意，二叉树不能被简单定义为每个结点的度都是2的树。普通的树并不会区分左子树和右子树，但在二叉树中，左右子树的位置是严格约定、不能交换的。
编码实现
在 JS 中，二叉树使用对象来定义。它的结构分为三块：
- 数据域
- 左侧子结点（左子树根结点）的引用
- 右侧子结点（右子树根结点）的引用
// 二叉树结点的构造函数
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}当你需要新建一个二叉树结点时，直接调用构造函数、传入数据域的值就行了：
const node = new TreeNode(1)一棵二叉树的实际形态如下：
二叉树的遍历
以一定的顺序规则，逐个访问二叉树的所有结点，这个过程就是二叉树的遍历。按照顺序规则的不同，遍历方式有以下四种：
- 先序遍历：根结点 -> 左子树 -> 右子树
- 中序遍历：左子树 -> 根结点 -> 右子树
- 后序遍历：左子树 -> 右子树 -> 根结点
- 层次遍历
按照实现方式的不同，遍历方式又可以分为以下两种：
- 递归遍历（先、中、后序遍历）
- 迭代遍历（层次遍历）
上面图例展示的二叉树结构，编码实现是下面的结构：
const root = {
val: "A",
left: {
val: "B",
left: {
val: "D"
},
right: {
val: "E"
}
},
right: {
val: "C",
right: {
val: "F"
}
}
};先序遍历
递归法：先序遍历编写递归函数编码实现，递归函数主要包括：递归式（每一次重复的内容是什么，在这里表示 根结点 -> 左子树 -> 右子树）和递归边界（指的是什么时候停下来）。
// 先序遍历核心伪代码
function preorder(root) {
// 递归边界，root 为空
if(!root) {
return
}
// 输出当前遍历的结点值
console.log('当前遍历的结点值是：', root.val)
// 递归遍历左子树
preorder(root.left)
// 递归遍历右子树
preorder(root.right)
}
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
let res = [];
const preOrder = (root) => {
if (root === null) return [];
res.push(root.val);
preOrder(root.left);
preOrder(root.right);
}
preOrder(root);
return res;
};迭代法：递归和栈有着脱不开的干系。本题的思路就是通过合理地安排入栈和出栈的时机、使栈的出栈序列符合二叉树的前序遍历规则。
先序遍历规则 根→ 左 → 右 即为出栈序列，那么入栈序列就应该为 右→左→根，因此最终的出入栈顺序应该是这样的：
- 将根结点入栈
- 取出栈顶结点，将结点值
push进结果数组 - 若栈顶结点有右孩子，则将右孩子入栈
- 若栈顶结点有左孩子，则将左孩子入栈
/**
* @param {TreeNode} root
* @return {number[]}
*/
const preorderTraversal = function(root) {
// 定义结果数组
const res = []
// 处理边界条件
if(!root) {
return res
}
// 初始化栈结构
const stack = []
// 首先将根结点入栈
stack.push(root)
// 若栈不为空，则重复出栈、入栈操作
while(stack.length) {
// 将栈顶结点记为当前结点
const cur = stack.pop()
// 当前结点就是当前子树的根结点，把这个结点放在结果数组的尾部
res.push(cur.val)
// 若当前子树根结点有右孩子，则将右孩子入栈
if(cur.right) {
stack.push(cur.right)
}
// 若当前子树根结点有左孩子，则将左孩子入栈
if(cur.left) {
stack.push(cur.left)
}
}先序遍历结果：ABDECF
中序遍历
递归法：递归式为左子树 -> 根结点 -> 右子树，递归边界照旧，编码实现如下：
// 所有遍历函数的入参都是树的根结点对象
function inorder(root) {
// 递归边界，root 为空
if(!root) {
return
}
// 递归遍历左子树
inorder(root.left)
// 输出当前遍历的结点值
console.log('当前遍历的结点值是：', root.val)
// 递归遍历右子树
inorder(root.right)
}迭代法：中序遍历的序列规则是 左 -> 中 -> 右 ，这意味着我们必须首先定位到最左的叶子结点。在这个定位的过程中，必然会途径目标结点的父结点、爷爷结点和各种辈分的祖宗结点。 途径过的每一个结点，我们都要及时地把它入栈。这样当最左的叶子结点出栈时，第一个回溯到的就是它的父结点。
/**
* @param {TreeNode} root
* @return {number[]}
*/
const inorderTraversal = function(root) {
// 定义结果数组
const res = []
// 初始化栈结构
const stack = []
// 用一个 cur 结点充当游标
let cur = root
// 当 cur 不为空、或者 stack 不为空时，重复以下逻辑
while(cur || stack.length) {
// 这个 while 的作用是把寻找最左叶子结点的过程中，途径的所有结点都记录下来
while(cur) {
// 将途径的结点入栈
stack.push(cur)
// 继续搜索当前结点的左孩子
cur = cur.left
}
// 取出栈顶元素
cur = stack.pop()
// 将栈顶元素入栈
res.push(cur.val)
// 尝试读取 cur 结点的右孩子
cur = cur.right
}
// 返回结果数组
return res
};中序遍历结果：DBEACF
后序遍历
递归法：递归式为左子树 -> 右子树 -> 根结点 ，递归边界照旧，编码实现如下：
function postorder(root) {
// 递归边界，root 为空
if(!root) {
return
}
// 递归遍历左子树
postorder(root.left)
// 递归遍历右子树
postorder(root.right)
// 输出当前遍历的结点值
console.log('当前遍历的结点值是：', root.val)
}迭代法：同先序遍历实现方式，后序遍历是 左→右→根，我们可以直接把 pop 出来的当前结点 unshift 进 res 的头部，然后左右结点的入栈顺序。
/**
* @param {TreeNode} root
* @return {number[]}
*/
const postorderTraversal = function(root) {
// 定义结果数组
const res = []
// 处理边界条件
if(!root) {
return res
}
// 初始化栈结构
const stack = []
// 首先将根结点入栈
stack.push(root)
// 若栈不为空，则重复出栈、入栈操作
while(stack.length) {
// 将栈顶结点记为当前结点
const cur = stack.pop()
// 当前结点就是当前子树的根结点，把这个结点放在结果数组的头部
res.unshift(cur.val)
// 若当前子树根结点有左孩子，则将左孩子入栈
if(cur.left) {
stack.push(cur.left)
}
// 若当前子树根结点有右孩子，则将右孩子入栈
if(cur.right) {
stack.push(cur.right)
}
}
// 返回结果数组
return res
};后序遍历结果：DEBFCA
层序遍历
按照层次的顺序，从上到下，从左到右地遍历一个二叉树，使用队列存储，编码实现如下：
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
let results = [];
if (root == null) {
return results;
}
//定义队列
let queue = [];
//如果root不为null，往队列添加root
queue.push(root)
while (queue.length > 0) {
//记录当前层中节点的个数
let size = queue.length;
//从队列中弹出当前层中的元素
while (size > 0) {
let node = queue.shift();
result.push(node.val);
//将弹出节点的左右孩子添加到队列中
if (node.left != null) {
queue.push(node.left);
}
if (node.right != null) {
queue.push(node.right);
}
//每弹出该层一个元素，size需要更新
size--;
}
//将每层元素的结果放入results数组
results.push(result);
}
return results;
};后序遍历结果：ABCDEF
DFS和BFS
练习题目没太看明白，需要多刷几遍
DFS：深度优先遍历
深度优先搜索的过程可以转化为一系列的入栈、出栈操作。DFS 中，我们往往使用递归来模拟入栈、出栈的逻辑。深度优先搜索过程就类似于树的先序遍历、是树的先序遍历的推广。
BFS：广度优先遍历
广度优先搜索每次以“广度”为第一要务、雨露均沾，一层一层地扫描。
在分层遍历的过程中，会发现两个规律：
- 每访问完毕一个坐标，这个坐标在后续的遍历中都不会再被用到了，也就是说它可以被丢弃掉。
- 站在某个确定坐标的位置上，我们所观察到的可直接抵达的坐标，是需要被记录下来的，因为后续的遍历还要用到它们。
丢弃已访问的坐标、记录新观察到的坐标，这个顺序毫无疑问符合了“先进先出”的原则，因此整个 BFS 算法的实现过程，和队列有着密不可分的关系。
function BFS(root) {
const queue = [] // 初始化队列queue
// 根结点首先入队
queue.push(root)
// 队列不为空，说明没有遍历完全
while(queue.length) {
const top = queue[0] // 取出队头元素
// 访问 top
console.log(top.val)
// 如果左子树存在，左子树入队
if(top.left) {
queue.push(top.left)
}
// 如果右子树存在，右子树入队
if(top.right) {
queue.push(top.right)
}
queue.shift() // 访问完毕，队头元素出队
}
}
