前言
首先这是一份面向 面试 的 算法题 ，题目主要选自 leetcode 中 hot 100 | 腾讯精选50题 | 精选Top面试题 | 剑指offer | 面试中遇到的一些算法题 ,全文 119 题，基本涵盖了前端面试中的算法题分类。因为个人能力有限，所以题目几乎是 easy | mid ，并且搬运了一些优秀的题解 均在参考文献中 。如果对你有帮助的话 点个👍和收藏吧❤️

目录
dp
思想
感觉很像时高中数列的思想，给出首项，以及一个递推式子，让你求任意项的值。

步骤基本是： 寻找状态转移方程 => 建立合适的数据结构表 => 填表

爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢

dp[0] = 0 dp[1] = 1 dp[2] = 2
dp[n] = dp[n-1] + dp[n-2] // 到达第n阶楼梯有从n-1阶走一步和从第n-2阶走两步两种情况
var climbStairs = function(n) {
let dp = [];
dp[0] = 0,dp[1] = 1,dp[2] = 2;
for(let i = 3;i <= n;i++){
dp[i] = dp[i-2] + dp[i-1];
}
return dp[n];
};
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额

// 动态规划方程：dp[n] = MAX( dp[n-1], dp[n-2] + num )
// 由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可***的最大值，要么就是 n-1 房屋可***的最大值，要么就是 n-2 房屋可***的最大值加上当前房屋的值，二者之间取最大值
// 举例来说：1 号房间可***最大值为 33 即为 dp[1]=3，2 号房间可***最大值为 44 即为 dp[2]=4，3 号房间自身的值为 22 即为 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5，3 号房间可***最大值为 55

var rob = function(nums) {
if(nums.length === 0) return 0;
if(nums.length === 1) return nums[0];
if(nums.length === 2) return Math.max(nums[0],nums[1]);
if(nums.length === 3) return Math.max(nums[0] + nums[2],nums[1]);
let dp = [nums[0],nums[1],Math.max(nums[0] + nums[2],nums[1])];
for(let i = 3;i < nums.length;i++){
dp[i] = nums[i] + Math.max(dp[i-2],dp[i-3]);
}
return Math.max(dp[nums.length-1],dp[nums.length-2]);
};
最大正方形
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积

const maximalSquare = (matrix) => {
if (!matrix.length) return 0

let maxsqlen = 0
let rowLength = matrix.length, colLength = matrix[0].length
for (let row = 0; row < rowLength; row++) {
for (let col = 0; col < colLength; col++) {
if (matrix[row][col] === ‘1’) {
matrix[row][col] = Number(matrix[row][col])
if (row != 0 && col != 0) {
matrix[row][col] = Math.min(matrix[row-1][col], matrix[row-1][col-1], matrix[row][col-1]) + 1
}
maxsqlen = Math.max(maxsqlen, matrix[row][col])
}
}
}
return maxsqlen**2

}

/** DP

题目要求最大正方形面积，面积 = 边长 * 边长，也就是求最大正方形的边长
所以也就变成了，在矩阵中找最大正方形，矩阵中只有0｜1两种值，全部为1的才是正方形
如何知道矩阵中哪里是1，哪里是0，只能穷举，但要聪明的穷举，这不就是动态规划的本质嘛！
动态规划第一步，先假象我们创建了一个二维数组dp，用来存储「这个点为右下角的最大正方形的边长」
下面开始找 状态转换方程
思路：假设有如下矩阵
1 0 1 1 1
1 1 1 1 1
1 1 1 1 1
1 0 0 1 1
随便找一个点，直观地，我们先找最右下角的点，设该点的最大正方形边长为 dp[i][j], 我们用肉眼看一下，dp[i][j] 应该等于 2
为什么等于2，是因为我们看了 dp[i-1][j], dp[i-1][j-1], dp[i][j-1] 这三个点都为1，而又因为dp[i][j-2] 为0，所以
我们知道dp[i][j]最大就为2了。也就是我们不能只看dp[i][j]相邻的三个点，而应该看「这三个相邻点为正方形右下角」的边长情况，
取最小边长进行求解 dp[i][j] 的最大正方形边长。（看，我们找到了重叠子问题和最优子结构）
所以，状态转换方程为：dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
下一步，需要根据矩阵数据，进行选择和明确 base case 即可
*/
零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1
var coinChange = function(coins, amount) {
let dp = new Array( amount + 1 ).fill( Infinity );
dp[0] = 0;

for (let i = 1; i <= amount; i++) {
for (let coin of coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}

return dp[amount] === Infinity ? -1 : dp[amount];
}
不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径

var uniquePaths = function(m, n) {
if(m === 1 && n === 1) return 1;
let data = [],rows = [0];
for(let i = 0;i < n-1;i++){
rows.push(1);
}
data.push(rows);
for(let i = 0;i < m-1;i++){
data.push([1]);
}
for(let i = 1;i < m;i++){
for(let j = 1;j < n;j++){
data[i][j] = data[i-1][j] + data[i][j-1];
}
}
return data[m-1][n-1];
};
股票题状态机
本文就来告诉你这个框架，然后带着你一道一道秒杀。

这 6 道股票买卖问题是有共性的，我们通过对第四题（限制最大交易次数为 k）的分析一道一道解决。因为第四题是一个最泛化的形式，其他的问题都是这个形式的简化。

第一题是只进行一次交易，相当于 k = 1；第二题是不限交易次数，相当于 k = +infinity（正无穷）；第三题是只进行 2 次交易，相当于 k = 2；剩下两道也是不限次数，但是加了交易「冷冻期」和「手续费」的额外条件，其实就是第二题的变种，都很容易处理。

一、穷举框架
首先，还是一样的思路：如何穷举？这里的穷举思路和上篇文章递归的思想不太一样。

递归其实是符合我们思考的逻辑的，一步步推进，遇到无法解决的就丢给递归，一不小心就做出来了，可读性还很好。缺点就是一旦出错，你也不容易找到错误出现的原因。比如上篇文章的递归解法，肯定还有计算冗余，但确实不容易找到。

而这里，我们不用递归思想进行穷举，而是利用「状态」进行穷举。我们具体到每一天，看看总共有几种可能的「状态」，再找出每个「状态」对应的「选择」。我们要穷举所有「状态」，穷举的目的是根据对应的「选择」更新状态。听起来抽象，你只要记住「状态」和「选择」两个词就行，下面实操一下就很容易明白了。

for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for …
dp[状态1][状态2][…] = 择优(选择1，选择2…)
比如说这个问题， 每天都有三种「选择」 ：买入、卖出、无操作，我们用 buy, sell, rest 表示这三种选择。但问题是，并不是每天都可以任意选择这三种选择的，因为 sell 必须在 buy 之后，buy 必须在 sell 之后。那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。而且别忘了，我们还有交易次数 k 的限制，就是说你 buy 还只能在 k > 0 的前提下操作。

很复杂对吧，不要怕，我们现在的目的只是穷举，你有再多的状态，老夫要做的就是一把梭全部列举出来。 这个问题的「状态」有三个 ，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：

dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 为天数，大 K 为最多交易数
此问题共 n × K × 2 种状态，全部穷举就能搞定。

for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
而且我们可以用自然语言描述出每一个状态的含义，比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。很容易理解，对吧？

我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。读者可能问为什么不是 dp[n - 1][K][1]？因为 [1] 代表手上还持有股票，[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。

记住如何解释「状态」，一旦你觉得哪里不好理解，把它翻译成自然语言就容易理解了。

二、状态转移框架
现在，我们完成了「状态」的穷举，我们开始思考每种「状态」有哪些「选择」，应该如何更新「状态」。只看「持有状态」，可以画个状态转移图。
通过这个图可以很清楚地看到，每种状态（0 和 1）是如何转移而来的。根据这个图，我们来写一下状态转移方程：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
max( 选择 rest , 选择 sell )

解释：今天我没有持有股票，有两种可能：
要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
max( 选择 rest , 选择 buy )

解释：今天我持有着股票，有两种可能：
要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。
这个解释应该很清楚了，如果 buy，就要从利润中减去 prices[i]，如果 sell，就要给利润增加 prices[i]。今天的最大利润就是这两种可能选择中较大的那个。而且注意 k 的限制，我们在选择 buy 的时候，把 k 减小了 1，很好理解吧，当然你也可以在 sell 的时候减 1，一样的。

现在，我们已经完成了动态规划中最困难的一步：状态转移方程。 如果之前的内容你都可以理解，那么你已经可以秒杀所有问题了，只要套这个框架就行了 。不过还差最后一点点，就是定义 base case，即最简单的情况。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
var maxProfit = function(prices) {
let dp_i_0 = 0,dp_i_1 = -Infinity;
for(let i = 0;i < prices.length;i++){
dp_i_0 = Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1 = Math.max(dp_i_1,-prices[i]);
}
return dp_i_0;
};
买卖股票的最佳时机 II

只要股票价格上涨，上涨的部分就是我的利润，可以理解为上涨期间第一天买入，然后一直持有到上涨最后一天即下跌前一天再卖出
只要股票价格下跌，那我肯定在下跌前一天卖了，而且下跌期间永远不会买入
var maxProfit = function(prices) {
let profit = 0;
for (let i = 0; i < prices.length - 1; i++) {
if (prices[i + 1] > prices[i]) profit += prices[i + 1] - prices[i];
}
return profit;
};
贪心
思想
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解最优解
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m] 。请问 k[0] k[1] …*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
剪绳子
var cuttingRope = function(number) {
if(number === 2 || number === 3) return number - 1;
let a = number % 3;
let b = parseInt(number / 3);
if(a === 0){
return 3 ** b;
}else if(a === 1){
return 2 * 2 * (3 ** (b - 1));
}else{
return 2 * (3 ** b);
}
};
跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

使用一个变量保存当前可到达的最大位置
时刻更新最大位置
可达位置小于数组长度返回false，反之即反
var canJump = function(nums) {
let k = 0;
for(let i = 0;i < nums.length;i++){
if(i > k) return false;
k = Math.max(k,i + nums[i]);
}
return true;
};
加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1

gas - cost >= 0才能绕场一周，以此思想判断能否行驶一周

从正确初始位置开始，拥有的汽油总是比消耗的汽油多,以此思想寻找初始位置
var canCompleteCircuit = function(gas, cost) {
let cur = 0,total = 0,start = 0;
for(let i = 0;i < gas.length;i++){
total += gas[i] - cost[i];
if(cur < 0){
cur = gas[i] - cost[i];
start = i;
}else cur += gas[i] - cost[i];
}
return total >= 0 ? start : -1;
};
二分
思想
针对有序数列进行查找时，优先考虑二分
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素
// 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
// NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
//把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
//10111

原数据为旋转数组，所以分界点前后都是有序的

进行二分查找，注意因为找最小值，high赋值时应该从mid开始取，mid可能是最小值
function minNumberInRotateArray(rotateArray)
{
if(!rotateArray.length) return 0;
let left = 0,right = rotateArray.length-1;
while(left < right){
let mid = Math.floor((right+left) >> 1);
if(rotateArray[left] <= rotateArray[right]){
return rotateArray[left];
}
if(rotateArray[left] < rotateArray[mid]){
left = mid + 1;
}else if(rotateArray[right] > rotateArray[mid]){
right = mid;
}else{
left++;
}
}
}
统计一个数字在排序数组中出现的次数
function GetNumberOfK(data, k)
{
let low = 0,high = data.length-1;
let pos,count = 0;
while(low < high){
let mid = Math.floor((low+high)>>1);
if(data[mid] === k){
pos = mid;
break;
}else if(data[mid] < k){
low = mid + 1;
}else{
high = mid-1;
}
}
if(pos !== undefined){
count++;
let left = pos,right = pos;
while(left–){
if(data[left] === k){
count++;
}else{
break;
}
}
while(right++){
if(data[right] === k){
count++;
}else{
break;
}
}
return count;
}else return 0;
}
0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字

var missingNumber = function(nums) {
let left = 0,
right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (mid === nums[mid]) {
left = mid + 1;
} else if (mid < nums[mid]) {
right = mid - 1;
}
}
return left;
};
最长上升子序列

维护一个子序列存放当前的上升序列
将当前数与子序列最大值比较，如果比最大值大之间加入队尾，如果更新则找一个合适的位置替换当前位置的元素
var lengthOfLIS = function(nums) {
let n = nums.length;
if(n <= 1){
return n;
}
let tail = [nums[0]];
for(let i = 0;i < n;i++){
if(nums[i] > tail[tail.length-1]){
tail.push(nums[i]);
}else{
let left = 0;
let right = tail.length-1;
while(left < right){
let mid = (left + right) >> 1;
if(tail[mid] < nums[i]){
left = mid + 1;
}else{
right = mid;
}
}
tail[left] = nums[i];
}
}
return tail.length;
};
搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。

每列的元素从上到下升序排列。

输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

选取左下角的值作为初始值key
如果目标值大于key，因为是最左边的值（最小），所以col++
如果目标值小于，那么更小的值只可能是上一行，所以row–
function Find(target,array){
let rows = array.length;
if(rows <= 0) return false;
let cols = array[0].length;
if(cols <= 0) return false;
let row = rows - 1;
let col = 0;
while(row >= 0 && col < cols){
if(array[row][col] > target){
row–;
}else if(array[row][col] < target){
col++;
}else{
return true;
}
}
return false;
}
Pow(x, n)
实现 pow( x , n ) ，即计算 x 的 n 次幂函数
//快速幂算法
var myPow = function(x, n) {
if (!x) return 0;
if (x === 1) return 1;
if (x === -1) return (n & 1) ? -1 : 1;
if (n == 2147483647) return 0;
if (n == -2147483648) return x === 2 ? 0 : 1;
if (n < 0) {
x = 1 / x;
n = -n;
}
let res = 1;
while(n) {
if (n & 1) res *= x;
x *= x;
n >>= 1;
}
return res;
}
求交集
function intersection(…args){
if(!args.length) return [];
let res = [],left = args[0][0],right = args[0][1];
for(let i = 1;i < args.length;i++){
if(right >= args[i][0] || left <= args[i][1]){
left = Math.max(left,args[i][0]);
right = Math.min(right,args[i][1]);
res = [left,right];
}else{
return [];
}
}
return res;
}
回溯算法
解题思路
全局变量：保存结果

参数：递归函数的参数选择，通常是两种参数。

状态变量： result需要保存的值
条件变量： 判断搜索是否完毕以及搜索是否合法
完成条件： 完成条件是决定状态变量和条件变量取何值时可以判断整个搜索流程结束。整个搜索流程结束有两个含义：搜索成功并保存结果何搜索失败并返回上一次状态。

递归过程： 传递当前状态给下一次递归进行搜索。

模板
let res = []; //存储结果

function backtrack(path,condition,…){
if(judge(condition)){ //满足条件
res.push(path);
return;
}
for(let select of selectList){
if(剪枝条件) break;
path.push(select); // 走某条路
backtrack(path,newSelectList);
path.pop(); //返回上一个十字路口
}
}
适用场景
排列，组合
数组，字符串，给定一个特定的规则，尝试找到某个解
二维数组下的DFS搜索
怎么套用模板
我筛选了leetCode中hot和面试常考题库中关于回溯的题目，题目由易到难，覆盖每个使用场景。

子集
给定一组 不含重复元素 的整数数组 nums ，返回该数组所有可能的子集（幂集）。

定义res数组存储结果
每个子集为状态变量，集合的元素个数为条件变量
子集的元素数量小于等于集合的元素数量为限制条件，满足条件时添加到结果数组，否则回退到上一步
下一层搜索的集合需要去掉已添加到状态变量中的元素
var subsets = function(nums) {
let res = [];
let n = nums.length;
function back(path,i){
if(i <= n){
res.push(path);
}
for(let j = i;j < n;j++){
path.push(nums[j]);
back(path.slice(0),j+1);
path.pop();
}
}
back([],0);
return res;
};
针对这道题还有一种比较酷的解法，利用二进制

一个集合的右2^n个子集

使用二进制模拟，每位为取或不取

举个例子：[1,2,3] => 符号位： 001 010 100 => 0-7与之&

=> [] [001] [010] [001,010] [100] [001,100] [010,100] [001,010,100] 刚好八种，并且对应数组下标。

var subsets = function(nums) {
let n = 1 << nums.length;
let res = [];
for(let i = 0;i < n;i++){
let temp = [];
for(let j = 0;j < nums.length;j++){
if(i & (1 << j)){
temp.push(nums[j]);
}
}
res.push(temp);
}
return res;
};
全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。

定义res
每个排列序列为状态变量，排列序列中集合的个数为条件变量
当排列序列的元素个数等于给定序列时，满足条件
下一层递归依赖于上一层递归传递的路径
var permute = function(nums) {
let len = nums.length;
let res = [];

function back(path){
if(path.length === len){
res.push(path);
return;
}
for(let i = 0;i < len;i++){
if(path.indexOf(nums[i]) === -1){ //这里的判断很精髓
path.push(nums[i]);
back(path.slice());
path.pop();
}
}
}
back([]);
return res;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
};
组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

定义res
每个子数组为状态变量，目标值为条件变量
子数组中的值相加等于目标值则满足要求
下一层递归的tar（与目标值相差的数目）依赖于上一层递归的选择
var combinationSum = function(candidates, target) {
let res = [];
let len = candidates.length;
//这里排序是为了防止在for循环if判断时直接跳出了，比如这样的样例[8,7,4,3],11
candidates.sort((x,y) => x-y);
function back(path,i,tar){
if(tar === 0){
res.push(path);
return;
}
for(let j = i;j < len;j++){
//判断是否当前的路口都是通向死路
if(tar < candidates[j]) break;
path.push(candidates[j]);
back(path.slice(),j,tar-candidates[j]);
path.pop();
}
}
back([],0,target);

return res;
1
};
分割回文串
给定一个字符串 s ，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

定义res
状态变量为回文子串集，条件变量为子串集的字符串数目
当子串集的字符串数目与目标串长度相同时，满足要求
下层递归的开始位置由上层递归决定
var partition = function(str){
let res = [];
function isPalindrome(s){
let head = 0;
let tail = s.length-1;
while(head <= tail){
if(s[head] !== s[tail]) return false;
head++;
tail–;
}
return true;
}
function backtrack(path,start){
if(start === str.length) res.push(path);
for(let i = start;i < str.length;i++){
if(!isPalindrome(str.slice(start,i+1))) continue;
path.push(str.slice(start,i+1));
backtrack(path.slice(),i+1);
path.pop();
}
}
backtrack([],0);
return res;
}
单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

状态变量为一条通路，条件变量为通路的长度
当通路与目标词汇长度一致时，满足条件
下一层递归的初始坐标和通路长度由上层递归决定
var exist = function (board, word) {
//越界处理
board[-1] = []
board.push([])

//寻找首个字母
for (let y = 0; y < board.length; y++) {
for (let x = 0; x < board.length; x++) {
if (word[0] === board[y][x] && backtrack(y, x, 0)) return true
}
}

//回溯
function backtrack(y, x, i) {
//回溯终止
if (i + 1 === word.length) return true

//保存字母
var tmp = board[y][x]
board[y][x] = false

if (board[y][x + 1] === word[i + 1] && backtrack(y, x + 1, i + 1)) return true
if (board[y][x - 1] === word[i + 1] && backtrack(y, x - 1, i + 1)) return true
if (board[y + 1][x] === word[i + 1] && backtrack(y + 1, x, i + 1)) return true
if (board[y - 1][x] === word[i + 1] && backtrack(y - 1, x, i + 1)) return true

//复原字母
board[y][x] = tmp
1
2
3
4
5
6
7
8
9
10
11
}

return false
};
排序算法
冒泡排序
比较两个记录键值的大小，如果这两个记录键值的大小出现逆序，则交换这两个记录


function bubbleSort(arr){
for(let i = 1;i < arr.length;i++){
for(let j = i;j > 0;j–){
if(arr[j] < arr[j-1]){
[arr[j],arr[j-1]] = [arr[j-1],arr[j]];
}
}
}
return arr;
}
快排