前端算法

算法复杂度

console.time();
for (let a = 0; a <= 1000; a++) {
    for (let b = 0; b <=1000; b++) {
        for (let c = 0; c <= 1000; c++) {
            if (a + b + c === 1000 && Math.pow(a,2) + Math.pow(b,2) === Math.pow(c,2)) {
                console.log(`${a}平方 + ${b}平方 = ${c}平方 `)
            }
        }
    }
}
console.timeEnd()
//输出
//0平方 + 500平方 = 500平方
//200平方 + 375平方 = 425平方 
//375平方 + 200平方 = 425平方 
//500平方 + 0平方 = 500平方 
//default: 742.633ms

console.time();
for (let a = 0; a <= 1000; a++) {
    for (let b = 0; b <=1000; b++) {
        let c = 1000 - a - b;
            if (Math.pow(a,2) + Math.pow(b,2) === Math.pow(c,2)) {
                console.log(`${a}平方 + ${b}平方 = ${c}平方 `)
            }
    }
}
console.timeEnd()
//default: 11.982ms

可以看出少了一个for循环时间消耗少了不少。

一个优秀的算法应该占用较少的内存空间和时间去完成需求。评价算法的好坏我们需要将时间占用和空间占用量化，称为时间和空间复杂度分析。

时间复杂度：看作是一个代码的执行时间根据数据规模增长的趋势。执行次数与执行参数息息相关，如果一个问题的规模是n，解决这个问题的某一算法所需要的时间复杂度是T(n)。

T(n) = O(f(n)) //大O表示法，f(n)指明某个算法耗时与数据增长量之间的关系。

常见的时间复杂度：

1. 常数阶：O(1)。T(n) = O(1)。表示无论n的规模如何增长，它的执行时间基本是不变的。
2. 线性阶：O(n)，T(n) = O(n)。代表数据量增大几倍，耗时也增长几倍。比如遍历。
3. 平方阶：O(n2)，T(n) = O(n2)。代表数据量增大n倍，耗时也增长n的平方倍。比如两层循环。
4. 立方阶：O(n3)，T(n) = O(n3)。代表数据量增大n倍，耗时也增长n的立方倍。比如三层循环。
5. 对数阶：O(logn)，T(n) = O(logn)。代表数据量增大n倍，耗时增大logn倍。比如二分查找，n以倍数的规模递减。
6. 线性对数阶：O(nlogn)，T(n) = O(nlogn)。代表数据量增大n倍，耗时增大nlogn倍。
7. 指数阶：O(2n)。代表数据量增大n倍，耗时增大2n倍。

计算时间复杂度：

1. 基本操作：即只有常数项，认为这个时间复杂度就是O(1)
2. 顺序结构：时间复杂度按加法计算
3. 循环结构：按乘法计算
4. 分支结构：取最大值

只需取最高次项即可。

优劣：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)

空间复杂度：指一个算法在执行过程中临时占用存储空间大小的度量。

S(n) = O(f(n))

通常来讲，只要算法不涉及到动态的空间，比如递归，栈，空间复杂度通常为O(1)。
算法的空间复杂度并不是实际占用的空间，而是计算整个算法的辅助空间单元（变量）的个数，与问题规模无关，主要看新开辟的变量个数。

动态规划

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

方法一：动态规划
我们用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
f(x) = f(x - 1) + f(x - 2)
它意味着爬到第 x 级台阶的方案数是爬到第 x - 1 级台阶的方案数和爬到第 x - 2 级台阶的方案数的和。很好理解，因为每次只能爬 1 级或 2 级，所以 f(x) 只能从 f(x−1) 和 f(x−2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。
以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 0 级开始爬的，所以从第 0 级爬到第 0 级我们可以看作只有一种方案，即 f(0) = 1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1) = 1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。我们不妨写几项来验证一下，根据转移方程得到 f(2) = 2，f(3) = 3，f(4) = 5，……，我们把这些情况都枚举出来，发现计算的结果是正确的。
我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n) 的实现，但是由于这里的 f(x) 只和 f(x - 1) 与 f(x - 2) 有关，所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现。

var climbStairs = function(n) {
    let p = 0, q = 0, r = 1;
    for (let i = 1; i <= n; ++i) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
};
//  或者
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];
};

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

该问题是非常典型的、入门的动态规划问题。很多算法书上的都采用类似的例子来开始介绍动态规划。
设计动态规划的三个步骤

• 将问题分解成最优子问题；
• 用递归的方式将问题表述成最优子问题的解；
• 自底向上的将递归转化成迭代；（递归是自顶向下）

最优子问题
对于连续的 n 栋房子：H1,H2,H3……Hn ，小偷挑选要偷的房子，且不能偷相邻的两栋房子，方案无非两种：
方案一：挑选的房子中包含最后一栋；
方案二：挑选的房子中不包含最后一栋；
获得的最大收益的最终方案，一定在这两种方案中产生，用代码表述就是：
最优结果 = Math.max(方案一最优结果，方案二最优结果)
子问题的递归表述

var robTo = function (nums, lastIndex) {
    if (lastIndex === 0) {
        return nums[0];
    }
    // 方案一，包含最后一栋房子，则应该丢弃倒数第二栋房子
    let sum1 = robTo(nums, lastIndex - 2) + nums[lastIndex]; 
    // 方案二，不包含最后一栋房子，那么方案二的结果就是到偷到 lastIndex-1 为止的最优结果
    let sum2 = robTo(nums, lastIndex - 1); 
    return Math.max(sum1, sum2);
};

将问题表述成最优子问题的解后，这个问题就解决了：

var rob = function(nums) {
    return robTo(nums, nums.length - 1);
};

递归转迭代
到上一步为止，该问题就已经解决了。但是递归的方式性能太差，中间有太多重复的计算，所以还需要最后一步：将 自顶向下 的递归，转化成 自底向上 的迭代。

var rob = function(nums) {
    if (nums.length === 0) {
        return 0;
    }
    if (nums.length === 1) {
        return nums[0];
    }
    // 仍然用两个变量来存储方案一和方案二的最优结果
    // 不同的是，这次从0开始，lastIndex 取最小值 1
    let sum1 = nums[0];
    let sum2 = nums[1];
    // 然后通过迭代不断增大 lastIndex，过程中维护新的sum1，sum2，直到数组末尾
    for (let lastIndex=2; lastIndex<nums.length; lastIndex++) {
        let tmp = sum1;
        // 此时的方案一就是上一步中的方案二，
        // 但要求的是最优解，所以要判断前一步的 sum1 和 sum2 哪个更大
        if (sum2 > sum1) {
            sum1 = sum2;
        }
        // sum2 是包含最后一栋房子的方案， 
        // 每向后增加一栋房子，就是前一步的 sum1（不包含 lastIndex - 1 ） 
        // 加上当前 lastIndex 栋房子的金钱
        sum2 = tmp + nums[lastIndex]; 
    }
    return sum1 > sum2 ? sum1 : sum2;
    };

再复杂的动态规划问题，都可以通过这三步来解决。难点在于第一步，即将问题分解成最优子问题。找到了最优子问题，问题就解决了一大半。第二步不过是将第一步的思路用递归代码表述出来；至于第三步递归转迭代，毕竟有递归的基本逻辑可以参考，多加练习可以较熟练的掌握。

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

方法一：暴力法
由于正方形的面积等于边长的平方，因此要找到最大正方形的面积，首先需要找到最大正方形的边长，然后计算最大边长的平方即可。
暴力法是最简单直观的做法，具体做法如下：
遍历矩阵中的每个元素，每次遇到 1，则将该元素作为正方形的左上角；
确定正方形的左上角后，根据左上角所在的行和列计算可能的最大正方形的边长（正方形的范围不能超出矩阵的行数和列数），在该边长范围内寻找只包含 1 的最大正方形；
每次在下方新增一行以及在右方新增一列，判断新增的行和列是否满足所有元素都是 1。

var maximalSquare = function(matrix) {
    if(matrix.length == 0 || matrix[0].length == 0) return 0;
    let maxSide = 0, rows = matrix.length, columns = matrix[0].length;
    for(let i = 0; i < rows; i++) {
        for (let j = 0; j < columns; j++) {
            if(matrix[i][j] == '1') {
                //遇到一个1作为正方形左上角
                maxSide  = Math.max(maxSide,1);
                //计算可能的最大正方形边长(取行列最小值)
                let currentMaxSide = Math.min(rows - i, columns - j);
                for(let k = 1; k < currentMaxSide; k++) {
                    //判断新增的一行一列是否均为1
                    let flag = true;
                    if(matrix[i + k][j + k] == '0') break;  //元素的对角
                    for(let m = 0; m < k; m++) {
                        if(matrix[i+k][j+m] == '0' || matrix[i + m][j+k] == '0') {
                            flag = false;
                            break;
                        }
                    }
                    if(flag) {
                        maxSide = Math.max(maxSide,k + 1)
                    }
                    else break;
                }
            }
        }
    }
    let maxSquare = maxSide * maxSide;
    return maxSquare
};

方法二：动态规划
方法一虽然直观，但是时间复杂度太高，有没有办法降低时间复杂度呢？
可以使用动态规划降低时间复杂度。我们用 dp(i,j) 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。
那么如何计算 dp 中的每个元素值呢？对于每个位置 (i,j)，检查在矩阵中该位置的值：

• 如果该位置的值是 0，则 dp(i,j)=0，因为当前位置不可能在由 1 组成的正方形中；
• 如果该位置的值是 1，则 dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：
  dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1
  此外，还需要考虑边界条件。如果 i 和 j 中至少有一个为 0，则以位置 (i,j) 为右下角的最大正方形的边长只能是 1，因此dp(i,j)=1。

以下用一个例子具体说明。原始矩阵如下。
0 1 1 1 0
1 1 1 1 0
0 1 1 1 1
0 1 1 1 1
0 0 1 1 1
对应的 dp 值如下。
0 1 1 1 0
1 1 2 2 0
0 1 2 3 1
0 1 2 3 2
0 0 1 2 3

var maximalSquare = function (matrix) {
    if (matrix.length == 0 || matrix[0].length == 0) return 0;
    let maxSide = 0, rows = matrix.length, columns = matrix[0].length;
    let dp = new Array(rows).fill(0).map(() => new Array(columns).fill(0));
    for(let i = 0; i < rows; i++) {
        for(let j = 0; j < columns; j++) {
            if(matrix[i][j] == '0') continue;
            dp[i][j] = Math.min(
                dp[i - 1]?.[j] || 0,
                dp[i][j - 1] || 0,
                dp[i - 1]?.[j - 1] || 0
            ) + 1;
            maxSide = Math.max(maxSide,dp[i][j]);
        }
    }
    return maxSide*maxSide
}

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的
我们采用自下而上的方式进行思考。仍定义F(i) 为组成金额 i 所需最少的硬币数量，假设在计算 F(i) 之前，我们已经计算出 F(0) − F(i−1) 的答案。 则 F(i) 对应的转移方程应为

其中 cj代表的是第 j 枚硬币的面值，即我们枚举最后一枚硬币面额是i-cj这个金额的状态 F(i-cj) 转移过来，再算上枚举的这枚硬币数量 1 的贡献，由于要硬币数量最少，所以F(i) 为前面能转移过来的状态的最小值加上枚举的硬币数量 1 。
例子1：假设
coins = [1, 2, 5], amount = 11
则，当 i==0 时无法用硬币组成，为 0 。当 i<0 时，忽略 F(i)
F(i) 最小硬币数量
F(0) 0 //金额为0不能由硬币组成
F(1) 1 //F(1)=min(F(1-1),F(1-2),F(1-5))+1=1
F(2) 1 //F(2)=min(F(2-1),F(2-2),F(2-5))+1=1
F(3) 2 //F(3)=min(F(3-1),F(3-2),F(3-5))+1=2
F(4) 2 //F(4)=min(F(4-1),F(4-2),F(4-5))+1=2
… …
F(11) 3 //F(11)=min(F(11-1),F(11-2),F(11-5))+1=3
我们可以看到问题的答案是通过子问题的最优解得到的。

const coinChange = (coins, amount) => {
  let dp = new Array(amount + 1).fill(Infinity)
  dp[0] = 0
  for (let coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] = Math.min(dp[i], dp[i - coin] + 1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
方法：动态规划。
思路：假设走到(i,j)的路径数量为f(i,j)，其中i和j的范围分别是[0,m-1]，[0，n-1]。
由于一次只能往右或下走一步，所以要走到(i,j)，要么从(i-1,j)往下，要么从(j,j-1)往右，所以可以写出动态规划转移方程：f(i,j) = f(i-1,j) + f(i,j-1)。（画格子一步一步推算）
注意：如果i=0或j=0，并不是满足要求的状态，为了方便代码编写，我们将所有的f(0,j)和f(i,0)都设置为边界条件，值均为1，因为走到那些格子只有一条路径。
初始条件f(0,0)=1，最终答案即为f(m-1,n-1)。

var uniquePaths = function(m, n) {
    const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
    for(let i = 0; i < m; i++) {
        f[i][0] = 1;
    }
    for(let j = 0; j < n; j++) {
        f[0][j] = 1;
    }
    for(let i = 1; i < m; i++) {
        for(let j = 1; j<n; j++) {
            f[i][j] = f[i-1][j] + f[i][j-1];
        }
    }
    return f[m-1][n-1]
};

// 66.斐波那契数列
function fibonacci(n) {
  if (n <= 2) return 1;
  return fibonacci(n-2) + fibonacci(n-1)
}
// 67.跳台阶
// 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
// 试几个例子发现这是斐波那契数列
// 简单的动态规划问题：把大的问题拆分成多个小的问题
// 首先明确返回能确定的条件：
// 1. number为1时只有一种方案
// 2. number为2时有两种方案，分别为：练跳两个一阶、一次跳一个两阶
// 3. number为3时，可以返回为 jump(1) + jump(2)
// function jump(number) {
//     if (number == 1) return 1
//     if (number == 2) return 2
//     return jump(number - 1) + jump(number - 2)
// }
function jumpFloor(n) {
  const results = [];
  results[1] = 1;
  results[2] = 2;
  if(number>2){
    for(var i=3;i<=number;i++){
      results[i]=results[i-1]+results[i-2];
    }
  }
  return results[number];
}

最长公共子序列(二)

题目主要信息：

• 找到两个字符串的最长公共子序列，子序列不要求位置在原串中连续
• 仅存在一个最长公共子序列，不需要去重
• 最长公共子序列为空需要返回”-1”，而不是空序列，最后要变换

方法一：动态规划+递归获取（推荐使用）
知识点：动态规划
动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果
思路：
题目要求获取最长公共子序列，我们肯定要先知道最长到底是多长，因此肯定要先求最长公共子序列的长度，然后根据这个长度获取这个子序列。（注意：子序列不是子串，子串要求所有字符必须连续，子序列不要求连续，只要求相对位置不变）
具体做法：

• step 1：优先检查特殊情况。
• step 2：获取最长公共子序列的长度可以使用动态规划，我们以dp[i][j]表示在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列长度。
• step 3：遍历两个字符串的所有位置，开始状态转移：若是i位与j位的字符相等，则该问题可以变成1+dp[i−1][j−1]，即到此处为止最长公共子序列长度由前面的结果加1。
• step 4：若是不相等，说明到此处为止的子串，最后一位不可能同时属于最长公共子序列，毕竟它们都不相同，因此我们考虑换成两个子问题，dp[i][j−1]或者dp[i−1][j]，我们取较大的一个就可以了，由此感觉可以用递归解决。
• step 5：但是递归的复杂度过高，重复计算了很多低层次的部分，因此可以用动态规划，从前往后加，由此形成一个表，表从位置1开始往后相加，正好符合动态规划的转移特征。
• step 6：因为最后要返回该序列，而不是长度，所以在构造表的同时要以另一个二维矩阵记录上面状态转移时选择的方向，我们用1表示来自左上方，2表示来自左边，3表示来自上边。
• step 7：获取这个序列的时候，根据从最后一位开始，根据记录的方向，不断递归往前组装字符，只有来自左上的时候才添加本级字符，因为这种情况是动态规划中两个字符相等的情况，字符相等才可用。

图示：

function LCS( s1 ,  s2 ) {
    // write code here
    // 动态规划
    // 状态：f[i][j]表示以text1第i个结尾text2第j个结尾的的公共子串；
    // 状态转移方程: 当text1[i] === text2[j]时：f[i][j] = f[i-1][j-1] + text[i];
    //             当text1[i] !=== text2[j]时；f[i][j] = max{dp[i-1][j], dp[i][j-1]};
    const l1 = s1.length;
    const l2 = s2.length;
    const dp = new Array(l1).fill(0).map(() => new Array(l2).fill(''));
    let max = '';
    for (let i=0; i<l1; i++) {
        for (let j=0; j<l2; j++) {
            if (s1[i] === s2[j]) {
                dp[i][j] = (i===0 || j===0) ? s1[i]: dp[i-1][j-1]+ s1[i];
            } else {
                const tempS1 = i===0 ? '' : dp[i-1][j];
                const tempS2 = j===0 ? '' : dp[i][j-1];
                if (i===1) tempS1
                dp[i][j] = tempS1.length > tempS2.length ? tempS1 : tempS2;
            }
            max = dp[i][j].length > max.length ? dp[i][j] : max
        }
    }
    return max.length ? max : -1;
}

最长公共子串

给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。
具体做法：

• step 1：我们可以用dp[i][j]表示在str1中以第i个字符结尾在str2中以第j个字符结尾时的公共子串长度，
• step 2：遍历两个字符串填充dp数组，转移方程为：如果遍历到的该位两个字符相等，则此时长度等于两个前一位长度+1，dp[i][j]=dp[i−1][j−1]+1，如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。
• step 3：每次更新dp[i][j]后，我们维护最大值，并更新该子串结束位置。
• step 4：最后根据最大值结束位置即可截取出子串。

  function LCS( str1 ,  str2 ) {
    let dp = new Array(str1.length+1).fill(0).map(() => new Array(str2.length+1).fill(0));
    let max = 0;
    const map = new Map()
    for(let i = 1;i<=str1.length;i++){
        for(let j = 1;j<=str2.length;j++){
            if(str1[i-1] === str2[j-1]){
                dp[i][j] = dp[i - 1][j - 1] + 1
                max = Math.max(max,dp[i][j])
                if(!map.has(max)) map.set(max,i)  //避免重复
            }
        }
    }
    let startIndex = map.get(max) - max;
    let endIndex = map.get(max) ;
    return str1.substring(startIndex,endIndex)  //截取字符串
  }

不同路径的数目(一)

一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

假设机器人站在点(i，j)处，其可以从(i-1，j)向下移动一行走到，也可以从(i，j-1)向右移动一步走到。因此到达位置(i，j)出路径的数目等于到达位置(i-1，j)的路径数目 与达到(i，j-1)的路径数目之和。我们假设dp[i,j]表示到达点(i，j)的路径数目，那么dp[i,j] = dp[i-1,j]+dp[i,j-1]。我们新建一个二维表格dp，计算dp里面每一个值，最后返回目标位置的dp即可。
初始化，第一行和第一列的dp值全部为1，这些位置可以确定只有一条路径。表格的其他位置，根据转移方程，进行填充即可。

function uniquePaths(m, n) {
  let dp = new Array(4).fill(0).map(() => {
    return new Array(5).fill('')
  })
  // 第一行初始化，只有一条路径
  for (let i = 0; i < 5; i++) {
    dp[0][i] = 1
  }
  // 第一列初始化，只有一条路径
  for (let i = 0; i < 4; i++) {
    dp[i][0] = 1
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i-1][j] + dp[i][j-1]
    }
  }
  return dp[m-1][n-1]
}

矩阵的最小路径和

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

function minPathSum( matrix ) {
  const n = matrix.length, m = matrix[0].length;
  // dp[i][j] = dp[i-1][j] + dp[i][j-1]
  let dp = new Array(n).fill(0).map(() => { return new Array(m).fill('')} )
  dp[0][0] = matrix[0][0]
  for (let i = 1; i < m; i++) {
    dp[0][i] = dp[0][i-1] + matrix[0][i]
  }
  for (let i = 1; i < n; i++) {
    dp[i][0] = dp[i-1][0] + matrix[i][0]
  }
  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j],dp[i][j-1])
    }
  }
  return dp[n-1][m-1]
}

把数字翻译成字符串

思路：
对于普通数组1-9，译码方式只有一种，但是对于11-19，21-26，译码方式有可选择的两种方案，因此我们使用动态规划将两种方案累计。
具体做法：

• step 1：用辅助数组dp表示前i个数的译码方法有多少种。
• step 2：对于一个数，我们可以直接译码它，也可以将其与前面的1或者2组合起来译码：如果直接译码，则dp[i]=dp[i−1]；如果组合译码，则dp[i]=dp[i−2]。
• step 3：对于只有一种译码方式的，选上种dp[i−1]即可，对于满足两种译码方式（10，20不能）则是dp[i−1]+dp[i−2]

• step 4：依次相加，最后的dp[length]即为所求答案。

  function solve( nums ) {
    // write code here
    let len = nums.length;
    let dp = new Array(len);//dp[i]表示在 当前i位置上有多少种译码的可能。
    dp[0] = 1;
    for(let i = 1;i<len;i++){
        let twoN = parseInt(nums.slice(i-1,i+1));
    if(i === len - 1 && nums[i] == 0 && twoN > 26){
        dp[i] = 0;   
    }else if(nums[i] == 0 || twoN > 26 || nums[i-1] == 0){
            dp[i] = dp[i-1];
        }else{
            dp[i] = i>= 2 ? dp[i-1] + dp[i-2] : dp[i-1] + 1;
        }
    }
    return dp[len - 1];
  }

  兑换零钱(一)

  给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
  如果无解，请返回-1。
  思路：
  这类涉及状态转移的题目，可以考虑动态规划。
  具体做法：

• step 1：可以用dp[i]表示要凑出i元钱需要最小的货币数。

• step 2：一开始都设置为最大值aim+1，因此货币最小1元，即货币数不会超过aim.
• step 3：初始化dp[0]=0。
• step 4：后续遍历1元到aim元，枚举每种面值的货币都可能组成的情况，取每次的最小值即可，转移方程为dp[i]=min(dp[i],dp[i−arr[j]]+1).
• step 5：最后比较dp[aim]的值是否超过aim，如果超过说明无解，否则返回即可。

贪心

剑指 Offer 14- I. 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
方法一：动态规划
我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来
用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积，初始化dp[2] = 1
我们先把绳子剪掉第一段（长度为j），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j (i - j)；如果剪的话长度乘积即为j dp[i - j]。取两者最大值max(j (i - j), j dp[i - j])
第一段长度j可以取的区间为[2,i)，*对所有j不同的情况取最大值，因此最终dp[i]的转移方程为
dp[i] = max(dp[i], max(j (i - j), j dp[i - j]))
最后返回dp[n]即可

let cuttingRope = function(n) {
    let dp = new Array(n + 1).fill(0);
    dp[2] = 1;
    //如果只剪掉长度为1，对最后结果无增益，所以长度为2开始剪
    for(let i = 2; i <= n; i++) {
        for(let j = 1; j < i; j++) {
            //剪了第一段后，剩下i-j长度可以剪或不剪；不剪长度乘积为j*(i-j)；如果剪的话长度乘积即为j * dp[i - j]。取两者最大值
            let bigger = Math.max(j * (i-j), j * dp[i - j]);
            //对于同一个i，内层循环对不同的j都还会拿到一个max，所以每次内循环都要更新max
            dp[i] = Math.max(dp[i],bigger);
        }
    }
    return dp[n];
}

方法二：贪心算法
核心思路是：尽可能把绳子分成 长度为3的小段，这样乘积最大。
步骤如下：
如果 n === 4，返回4
如果 n > 4，分成尽可能多的长度为3的小段，每次循环长度n减去3，乘积res乘以3；最后返回时乘以小于等于4的最后一小段

var cuttingRope = function(n) {
    if(n < 4) return n - 1;
    let result = 1;
    while(n > 4) {
        result *= 3;
        n -=3;
    }
    return result * n;
};

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
方法：贪心
设想一下对于数组中的任意一个位置y，我们如何判断他是否可以到达，根据题目描述，只要存在一个位置x，它本身可以到达，并且它跳跃的最大长度为x+nums[x]，这个值大于等于y，那么y也可以到达。我们可以遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置x，如果他在最远可以已到达的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用x+nums[x]更新最远可以到达的位置。在遍历的过程中，如果最远可以到达的位置大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

//1. 使用一个变量保存当前可到达的最大位置
//2. 时刻更新最大位置
//3. 可达位置大于数组长度返回true
let canJump = function(nums) {
    let n = nums.length;
    let rightmost = 0;
    for(let i = 0; i < n; i++) {
           // 如果i比rightMost大说明中间有位置到不了了
        if(i <= rightmost) { //可以到达的位置
            rightmost = Math.max(rightmost, i + nums[i]);
            if(rightmost >= n-1) {
                return true;
            }
        }
    }
    return false;
}

134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。
思路：首先判断总油量是否小于总油耗，如果是则肯定不能走一圈。如果否，那肯定能跑一圈。接下来就是循环数组，从第一个站开始，计算每一站剩余的油量，如果油量为负了，就以这个站为起点重新计算。如果到达某一个点为负，说明起点到这个点中间的所有站点都不能到达该点，因为到中间的每个站的油量肯定大于等于0，从中间某站开始的话油量初始为0。

let canCompleteCircuit = function(gas,cost) {
    let totalGas = 0;
    let totalCost = 0;
    for(let i = 0; i < gas.length; i++) {
        totalCost += cost[i];
        totalGas += gas[i];
    }
    if(totalGas < totalCost) { return -1};
    let currentGas = 0;
    let start = 0;
    for(let i = 0; i < gas.length; i++) {
        currentGas = currentGas - cost[i] + gas[i];
        //如果到达下一站的时候油量为负数 就以这个站为起点 重新计算
        if(currentGas < 0) {
            currentGas = 0;
            start = i + 1;
        }
    }
    return start;
}

二分查找

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

答案：

// （版本一）左闭右闭区间
var search = function(nums, target) {
    let l = 0, r = nums.length - 1;
    while(l <= r) {
        let mid = Math.floor(l + (r - l) / 2);
        if(nums[mid] == target) return mid;
        if(nums[mid] > target) r = mid - 1;
        if(nums[mid] < target) l = mid + 1
    } 
    return -1
};
// （版本二）左闭右开区间    用l<r的话，r为nums.length，然后就要更新为mid，因为右开区间取不到mid
var search = function(nums, target) {
    let l = 0, r = nums.length;
    // 区间 [l, r）
    while(l < r) {             
        let mid = (l + r) >> 1;
        if(nums[mid] === target) return mid;
        let isSmall = nums[mid] < target;
        l = isSmall ? mid + 1 : l;
        // 所以 mid 不会被取到
        r = isSmall ? r : mid;
    }
    return -1;
};

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            const mid = Math.floor(left + (right - left) / 2); // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    };
};

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

var searchInsert = function(nums, target) {
    let l = 0,r = nums.length - 1
    while(l<=r) {
        let mid = (l+r) >> 1;
        if(target>nums[mid]){
            l = mid + 1;
        } else{
            r = mid -1;
        }
    }
    return l
};

剑指 Offer II 006. 排序数组中两个数字之和

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

var twoSum1 = function(numbers, target) {
    //从数组第一个元素开始，用二分查找函数判断后面的元素是否为target-numbers[i]
    for (let i = 0; i < numbers.length; i++) {
        const x = numbers[i]
        const index = binarySearch(numbers, i + 1, numbers.length - 1, target - x)
        if (index != -1) {
            return [i, index]
        }
    }
    return []
};
//定义二分查找的函数
var binarySearch = function(number, left, right, target) {
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2)
        if (target == number[mid]) {
            return mid;
        } else if (target < number[mid]) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

剑指 Offer II 069. 山峰数组的顶部

符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i ，即山峰顶部。

var peakIndexInMountainArray = function(arr) {
    let l = 0,r = arr.length - 1,ans = Math.max(...arr)
    while(l <= r) {
        let mid = (l + r) >> 1;
        if(arr[mid]==ans) return mid;
        if(arr[mid] < arr[mid+1]) {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return -1
}

也可以用遍历的方法：

var peakIndexInMountainArray = function(arr) {
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] > arr[i+1]) {
            return i
        }
    }
};

374. 猜数字大小

猜数字游戏的规则如下：
每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。

var guessNumber = function(n) {
    let l = 1, r = n;
    while(l <= r) {
        let mid = Math.floor((l + r)/2);
        if(guess(mid) === 0) {
            return mid;
        } else if (guess(mid) === 1){
            l = mid + 1;
        } else {
            r = mid - 1
        }
    }
};

69. x 的平方根

给你一个非负整数x，计算并返回x的平方根 。
由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

var mySqrt = function(x) {
    let l = 1, r= x;
    while(l<=r) {
        let mid = Math.floor((l+r)/2);
        if(mid*mid == x) return mid;
        if(mid*mid > x) {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return l - 1
};

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

var minArray = function(numbers) {
    let left = 0, right = numbers.length-1;
    while(left < right) {
        let mid = Math.floor((left+right)/2);
        if(numbers[mid] === numbers[right]) {
            //因为有可能有重复数字，来缩小范围
            right--
        }
        else if(numbers[mid] < numbers[right]) {
            //mid有可能是最小值
            right = mid
        } else {
            left = mid + 1;
        }
    }
    return numbers[left]
};

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
「归并排序」与「逆序对」是息息相关的。归并排序体现了 “分而治之” 的算法思想，具体为：

• 分： 不断将数组从中点位置划分开（即二分法），将整个数组的排序问题转化为子数组的排序问题；
• 治： 划分到子数组长度为 1 时，开始向上合并，不断将 较短排序数组 合并为 较长排序数组，直至合并至原数组时完成排序；

合并阶段 本质上是 合并两个排序数组 的过程，而每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。

如下图所示，为数组 [7,3,2,6,0,1,5,4] 的归并排序与逆序对统计过程。

var reversePairs = function (nums) {
  let count = 0;
  // 如果数组中只有1个元素或者为空，则不存在逆序对
  if (nums.length < 2) return count;
  const mergeSort = (front, behind) => {
    // 如果前后指针相遇，则归并区间只剩下一个元素了
    if (front == behind) return [nums[front]];
    let mid = front + ((behind - front) >> 1);
    // 规则让左半部分不包含中心元素 右半部分包含中心元素
    let left = mergeSort(front, mid);
    let right = mergeSort(mid + 1, behind);
    let temp = new Array(behind - front + 1).fill(0);
    // 合并有三个指针
    let cur = 0,
      l = 0,
      r = 0;
    while (l < left.length && r < right.length) {
      // 如果右边元素大于左边元素，将左边元素放到结果数组中
      if (right[r] >= left[l]) temp[cur++] = left[l++];
      else {
        temp[cur++] = right[r++];
        // 如果左边元素大于右边元素，那就出现了序列对了
        // 由于左右两边都是有序的，左边当前元素及之后的元素都会跟右边构建逆序对
        count += left.length - l;
      }
    }
    while (l < left.length) temp[cur++] = left[l++];
    while (r < right.length) temp[cur++] = right[r++];
    return temp;
  };
  // 左闭右闭区间
  mergeSort(0, nums.length - 1);
  return count;
};

回溯

什么是回溯法

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯是递归的副产品，只要有递归就会有回溯。

所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。

回溯法的效率

回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

相信大家看着这些之后会发现，每个问题，都不简单！

另外，会有一些同学可能分不清什么是组合，什么是排列？

组合是不强调元素顺序的，排列是强调元素顺序。

例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。

记住组合无序，排列有序，就可以了。

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

这块可能初学者还不太理解，后面的回溯算法解决的所有题目中，我都会强调这一点并画图举相应的例子，现在有一个印象就行。

回溯法模板

• 回溯函数模板返回值以及参数

在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。

回溯算法中函数返回值一般为void。

再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

但后面的回溯题目的讲解中，为了方便大家理解，我在一开始就帮大家把参数确定下来。

回溯函数伪代码如下：

void backtracking(参数)

• 回溯函数终止条件

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

所以回溯函数终止条件伪代码如下：

if (终止条件) { 存放结果; return; }

• 回溯搜索的遍历过程

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

如图：

注意图中，我特意举例集合大小和孩子的数量是相等的！

回溯函数遍历过程伪代码如下：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 }

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

分析完过程，回溯算法模板框架如下：

void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }

这份模板很重要，后面做回溯法的题目都靠它了！

如果从来没有学过回溯算法的录友们，看到这里会有点懵，后面开始讲解具体题目的时候就会好一些了，已经做过回溯法题目的录友，看到这里应该会感同身受了。

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。

那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

有同学问了，什么时候for可以从0开始呢？

求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合，排列问题我们后续的文章就会讲到的。

以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：

从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。

回溯三部曲

• 递归函数参数

全局变量数组path为子集收集元素，二维数组result存放子集组合。

递归函数参数在上面讲到了，需要startIndex。

递归终止条件

从图中可以看出：

剩余集合为空的时候，就是叶子节点。

那么什么时候剩余集合为空呢？

就是startIndex已经大于数组的长度了，就终止了，因为没有元素可取了，代码如下:

if (startIndex >= nums.size()) {
    return;
}

其实可以不需要加终止条件，因为startIndex >= nums.size()，本层for循环本来也结束了。

• 单层搜索逻辑

求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。

代码如下

var subsets = function (nums) {
  let res = [];
  const backtrack = (index, path) => {
    // 把当前路径加入结果r中
    res.push(path.slice());      //用slice是返回新数组
    for (let i = index; i < nums.length; i++) {
      // 选择这个数
      path.push(nums[i]);
      // 基于选这个数，继续递归，传入的是i+1，不是index+1
      backtrack(i + 1, path);
      // 撤销选这个数
      path.pop();
    }
  };
  backtrack(0, []);
  return res;
};

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案

方法一：回溯

思路和算法

回溯三部曲

• 递归函数参数

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1，所以处理排列问题就不用使用startIndex了。

但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:

• 递归终止条件

可以看出叶子节点，就是收割结果的地方。

那么什么时候，算是到达叶子节点呢？

当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

• 单层搜索的逻辑

因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。

而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

var permute = function(nums) {
    const res = [], path = [];
    backtracking(nums, nums.length, []);
    return res;
    function backtracking(n, k, used) {
        if(path.length === k) {
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < k; i++ ) {
            if(used[i]) continue;
            path.push(n[i]);
            used[i] = true; // 同支
            backtracking(n, k, used);
            path.pop();
            used[i] = false;
        }
    }
};

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

• 递归函数参数

这里依旧使用result存放结果集，path存放符合条件的结果。还要定义sum变量统计单一结果path里的总和，其实这个sum也可以不用，用target做相应减法也行，最后target为0就说明找到符合的结果。还需设置startindex来控制for循环的起始位置，对于组合问题，什么时候需要startindex呢，比如一个集合求组和，例如：77.组合，216.组合总和III。如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合。注意以上我只是说求组合的情况，如果是排列问题，又是另一套分析的套路。

• 递归终止条件

从叶子节点可以清晰看到，终止只有两种情况，sum大于target和sum等于target。sum等于target的时候，需要收集结果。

• 单层搜索的逻辑

单层for循环依旧是从startindex开始，搜索cndidates集合。

剪枝优化

对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。

其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

那么可以在for循环的搜索范围上做做文章了。

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。

var combinationSum = function(candidates, target) {
    const res = [], path = [];
    candidates.sort(); // 排序
    backtracking(0, 0);
    return res;
    function backtracking(j, sum) {
        if (sum > target) return;
        if (sum === target) {
            res.push(Array.from(path));
            return;
        }
        for(let i = j; i < candidates.length; i++ ) {
            const n = candidates[i];
            if(n > target - sum) continue;
            path.push(n);
            sum += n;
            backtracking(i, sum);
            path.pop();
            sum -= n;
        }
    }
};

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

• 递归函数参数

全局变量数组path存放切割后回文的子串，二维数组result存放结果集。 （这两个参数可以放到函数参数里）

本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。

• 递归函数终止条件

从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止终止条件。

那么在代码里什么是切割线呢？

在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。

• 单层搜索的逻辑

来看看在递归循环，中如何截取子串呢？

在for (int i = startIndex; i < s.size(); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。

首先判断这个子串是不是回文，如果是回文，就加入在path中，path用来记录切割过的回文子串。注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。

判断回文子串

最后我们看一下回文子串要如何判断了，判断一个字符串是否是回文。

可以使用双指针法，一个指针从前向后，一个指针从后先前，如果前后指针所指向的元素是相等的，就是回文字符串了。

const isPalindrome = (s, l, r) => {
    for (let i = l, j = r; i < j; i++, j--) {
        if(s[i] !== s[j]) return false;
    }
    return true;
}
var partition = function(s) {
    const res = [], path = [], len = s.length;
    backtracking(0);
    return res;
    function backtracking(i) {
        if(i >= len) {
            res.push(Array.from(path));
            return;
        }
        for(let j = i; j < len; j++) {
            if(!isPalindrome(s, i, j)) continue;
            path.push(s.substr(i, j - i + 1));
            backtracking(j + 1);
            path.pop();
        }
    }
};

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

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

思路与算法

设函数check(i, j, k) 表示判断以网格的 (i, j) 位置出发，能否搜索到单词 word[k..]，其中 word[k..] 表示字符串 word 从第 k 个字符开始的后缀子串。如果能搜索到，则返回 true，反之返回 false。函数 check(i,j,k) 的执行步骤如下：

• 如果 board[i][j] != s[k]，当前字符不匹配，直接返回 false。
• 如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 true。
• 否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 word[k+1..]，则返回 true，否则返回 false。

这样，我们对每一个位置 (i,j) 都调用函数 check(i,j,0) 进行检查：只要有一处返回 true，就说明网格中能够找到相应的单词，否则说明不能找到。

为了防止重复遍历相同的位置，需要额外维护一个与 board 等大的 visited 数组，用于标识每个位置是否被访问过。每次遍历相邻位置时，需要跳过已经被访问的位置。

var exist = function(board, word) {
    const h = board.length, w = board[0].length;
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    const visited = new Array(h);
    for (let i = 0; i < visited.length; ++i) {
        visited[i] = new Array(w).fill(false);
    }
    const check = (i, j, s, k) => {
        if (board[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length - 1) {
            return true;
        }
        visited[i][j] = true;
        let result = false;
        for (const [dx, dy] of directions) {
            let newi = i + dx, newj = j + dy;
            if (newi >= 0 && newi < h && newj >= 0 && newj < w) {
                if (!visited[newi][newj]) {
                    const flag = check(newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
    for (let i = 0; i < h; i++) {
        for (let j = 0; j < w; j++) {
            const flag = check(i, j, word, 0);
            if (flag) {
                return true;
            }
        }
    }
    return false;
};