JS算法_知识点精讲

站长

2022年11月05日 10:44 · 阅读数 44

浮躁，是互联网时代的特点

大家好，我是柒八九。

今天，我们继续前端面试的知识点。我们来谈谈关于JS算法的相关知识点。

该系列的文章，大部分都是前面文章的知识点汇总，如果想具体了解相关内容，请移步相关系列，进行探讨。

如果，想了解该系列的文章，可以参考我们已经发布的文章。如下是往期文章。

文章list

好了，天不早了，干点正事哇。 JS算法_知识点精讲

整数

整数除法

题目描述：

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' >提示：

当发生溢出时，返回最大的整数值。假设除数不能为0

只能存储 32 位有符号整数，其数值范围是 [−231, 231−1] 示例：输入： -15和2 输出： -7

分析：

从提示可知，此题中，值的范围是[−231, 231−1],所以，我们可以定义边界值 MIN = -Math.pow(2, 31)/ MAX = Math.pow(2, 31) - 1
当数据发生溢出的时候，返回最大的整数值那就是当 a==MIN,b=-1,return MAX
当被除数和除数中有一个为负数，其商为负数，sign =(a>0)^(b>0) 位运算的异或运算(^)：在两个二进制位不同时返回1，相同时返回0 ,这样有一个好处，就是其实我们不关心，到底是哪个为正哪个为负。
由于负数的相减，会变成两数相加，增加了解题的心智模式，所以利用Math.abs(x)将x变更成正整数
基于减法实现触发，只有当被除数大于除数的时候，我们将其相减，直到不满足条件，然后记录减的次数（count） ==> 而最后的次数，就是所求的商

代码实现

function divide(a, b) {
    const MAX = Math.pow(2, 31) - 1, //最大值
          MIN = -Math.pow(2, 31)    //最小值
    if (a == MIN && b == -1) return MAX;  // 处理边界情况
  
    const sign = (a > 0) ^ (b > 0); // 处理商的正负问题
    a = Math.abs(a), b = Math.abs(b) // 变成正整数之间的相减
    let count = 0
    while(a >= b) {
        a -= b
        count++
    }
    // sign为正，说明，除数和被除数之间 有一个为负数
    return sign ? -count : count; 
};

二进制加法

题目描述：

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。输入为非空字符串且只包含数字 1 和 0 示例：输入 a = "11", b = "10" 输出: "101"

分析：

参考十进制加法来完成二进制加法。在进行十进制加法操作时候，总是将两个数的右端对齐，然后从它们的个位开始从右向左相加同一位置的两个数。如果前一位置有进位，还要加上进位。

从上面分析可知，有几个关键点

从右向左，而我们得到的是字符串，也就是每个串需要一个游标（指针）来记录当前处理位置 (i/j)
存在进位 (carry)
还有一点需要注意，就是给定的字符串可能不是等长的，也就是说，在处理完，它们各自共有长度后，长的那个子串就直接拼接到处理后的子串上
JS中获取字符串中位于index处字符的ASCII码 str.charAt(index)
产生进位的条件 （digitA + digitB + carry)>=2 carry是上一位的残留产物
最高位也需要考虑进位

代码实现

 function addBinary(a, b) {
    let result = ''; // 用于存储结果
    let i = a.length - 1; // 指针i
    let j = b.length -1; // 指针j
    let carry = 0; //  用于存储进位
    while(i>=0 || j>=0){  //只有有数据，就进行数据操作
        // 指定位置的数字(二进制0/1) 
        // 判断位置，以免位置出错 i >=0
        let digitA = i >=0 ? a.charAt(i--) -'0':0;
         // 指定位置的数字(二进制0/1)
         // 判断位置，以免位置出错 j >=0
        let digitB = j >=0 ? b.charAt(j--) -'0':0;
        // 求和处理
        let sum = digitA + digitB + carry;
        // 处理进位
        carry = sum >=2 ? 1 :0;
        // sum可能超过最大当前进度的最大值，
      //例如： 十进制的 7+8 = 15 ==> 指定的个位存 5 (15-10)
        sum = sum >=2 ? sum - 2:sum;
        result = sum + result;
    }
    // 最高位可能会产生进位
    if(carry ==1){
        result = '1' + result;
    }
    return result
};

N进制大数相加

function Nsum(a,b,n){
    let result = '';
    let i = a.length - 1;
    let j = b.length -1;
    let carry = 0;
    while(i>=0 || j>=0){
        let digitA = i >=0 ? a.charAt(i--) -'0':0;
        let digitB = j >=0 ? b.charAt(j--) -'0':0;
        let sum = digitA + digitB + carry;
        carry = sum >=n ? 1 :0;
        sum = sum >=n ? sum - n:sum;
        result = sum + result;
    }
    if(carry ==1){
        result = '1' + result;
    }
    return result;
}

前 n 个数字二进制中 1 的个数

题目描述：

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。输入: n = 2 输出: [0,1,1] 解释: 0 --> 0 1 --> 12 --> 10

分析

我们可以为题目做一个转化，只要我们能求出一个整数i的二进制形式中1的个数，这个问题就迎刃而解。因为，最后的要的数组，无非就是将某一范围内数据的二进制中1的个数做一个统计。

我们能从题目中挖掘的主要信息有：

正整数
0~n之间的数，也就是这些数字是连续的

i&(i-1)

利用i&(i-1)将整数i的最右边的1变成0

整数i减去1,那么它最右边的1变成了0。例如：二进制1100,它减少1的结果是1011。而1100 & 1011 = 1000 。

所以我们可以利用这个特性，对0~n所有的数进行i&(i-1)处理。也就是需要两层循环，第一层循环是遍历整体数据，第二层循环是针对特定数据i。

码上见分晓

function countBits(n){
   // 构建一个长度为n+1 (0~n)，每项都是0的数组
   let result = new Array(n+1).fill(0);
   // 外层循环：处理整体数据
   for(let i=0;i<=n;i++){
        let j =i;
        // 内层循环：对特定数据进行j&(j-1)处理，直到 j里面不含有1，也就是为0
        while(j!=0){
            result[i]++;
            j = j & (j-1)
        }
    }
  return result;
}

优化处理

整数i的二进制形式中1的个数比i&(i-1)的二进制形式中1的个数多1。并且,原来的代码中我们是从i=0开始整体遍历的，然后，根据常识可知，i=0中1的个数为0。根据这些条件，我们可以对上述代码，做一个优化处理，也就是合理利用已经计算出的结果。

function countBits(n){
   // 构建一个长度为n+1 (0~n)，每项都是0的数组
   let result = new Array(n+1).fill(0);
   // 从i=1开始遍历
   for(let i=1;i<=n;i++){
       result[i] = result[i&(i-1)]+1
    }
  return result;
}

这样，少了一层遍历，然后对应的时间复杂度也减少了。

只出现一次的数字

题目描述：

一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次。找出并返回那个只出现了一次的元素。提示：-231 <= nums[i] <= 231 - 1 输入：nums = [2,2,3,2] 输出：3

分析

从提示，我们可以得知，整数是由32个0和1组成的。我们可以将数组中的所有数字的同一位置相加。

将出现3次的数字单独拿出来，那么出现3次的数字的任意第i个数位之和都能被3整除，那么只出现一次的数字的第i个数位一定是0
如果数组中所有数字的第i个数位相加之和被3除余1,那么只出现一次的数字的第i个数位一定是1
在"前 n 个数字二进制中 1 的个数"中我们介绍了，i>>1通过右移动一位的方式，来快速获取 i/2,其实在位运算中，还可以i>>n。也就是将当前位的数右移N位。因为，我们要求数组中所有数字指定位置(i)的二进制位。所以，(num>>(31-i))&1就是某个数字在i的位数。
num<<1 将当前num向右扩大一倍,从二进制角度看，就是将最右边位置补0 例子: 2的二进制位10 2<<1 == 4(二进制位100) 可以通过(4).toSting(2)进行验证

码上见分晓

function singleNumber(nums) {
    // 构建一个用于存储数组所有数字位数之和的数组
    let bitSums = new Array(32).fill(0);
    for(let num of nums){
        for(let i=0;i<32;i++){
         // 求num在i位置的位数，并将其与指定位置的位数相加
         bitSums[i] +=(num>>(31-i)) &1;
        }
    }
    let result =0;
    for(let i=0;i<32;i++){
        //从最地位(0)位开始遍历
        result = (result<<1) + bitSums[i]%3;
    }
    return result;
};

代码中(result<<1) + bitSums[i]%3其实也承载了两种含义

如果bitSums[i]%3 ==0,也就是能被3整除，只出现一次的数字在该位置(i)没出现过
如果bitSums[i]%3 ==1,也就是能被3除余1，只出现一次的数字在该位置(i)出现过

触类旁通

只出现一次之外其他数字都出现两次

题目描述：

一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。输入: [2,2,1]输出: 1

我们将上面的代码，做一个简单的修改。

function singleNumber(nums) {
    // 构建一个用于存储数组所有数字位数之和的数组
    let bitSums = new Array(32).fill(0);
    for(let num of nums){
        for(let i=0;i<32;i++){
         // 求num在i位置的位数，并将其与指定位置的位数相加
         bitSums[i] +=(num>>(31-i)) &1;
        }
    }
    let result =0;
    for(let i=0;i<32;i++){
        //从最地位(0)位开始遍历
        result = (result<<1) + bitSums[i]%2;
    }
    return result;
};

通过对比发现，其实我们就更改了一处地方将(result<<1) + bitSums[i]%3更换为了(result<<1) + bitSums[i]%2仅此而已。

其实，针对该题还有一个更简单的处理方式。是利用了位运算中异或运算（^）:两个二进制位不同时返回1，相同时返回0

 function singleNumber(nums) {
  let result = 0;
  for(let i of nums){
      result ^= i;
  }
  return result
};

result^=i 如果在位置i上存在两个相同的数字，通过异或处理，直接清零。类似于消消乐,他们两个互相抵消了。那么剩下的就是那个只出现一次的数字的位数了。

常规排序算法

由于文章篇幅有限，如果想了解相关内容，请移步到指定文章中。

数组

JS 只支持一维数组，并不支持矩阵(多维数组) 在JS中，我们可以通过很多方式来构建一维数组。

let array = Array('柒','八'，'九'); // new Array / []等

而构建多维数组，就需要借助函数来构建。

const matrix= (x,y) => 
    new Array(x).fill(0)
    .map(
      ()=>new Array(y).fill(0)
    )

通过matrix我们构建了一个，x行，y列且数组中值都为0的二维数组(矩阵)。

双指针

双指针是一种常见的解题思路，使用两个相反方向或者相同方向的指针扫描数组从而达到解题目的。

有两种解题思路: 反向双指针/同向双指针

方向相反的双指针用来求排序数组（升序）中的两个数字之和。
方向相同的双指针用来求正数数组中子数组的和(sum)或者乘积（mult）。

排序数组中的两个数字之和

题目描述：

输入一个递增排序的数组和一个值target,在数组中找出两个和为target的数字并返回它们的下标提示：数组中有且只有一对符合要求同时一个数字不能使用两次示例：输入数组： [1,2,4,6,10],k的值为8 输出[1,3]

分析

看题干，首先一个很关键的点，就是数组已经有序，然后可以采用双指针解法的第一套：反向双指针
按照既定套路， left指向首元素，right指向尾元素
根据 sum VS target 移动对应的指针

代码实现

function twoSum4SortedArray(nums,target){
  let left=0,right= nums.length-1; // 初始化指针left,right 
  while(left<right && nums[left] + nums[right] != target){
    if(nums[left] + nums[right]<target){
      left++;
    }else{
      right--;
    }
  }
  return [left,right]
}

注意：如果大家在刷leetcode等算法网站中，肯定会见过关于数组的两数之和的题。但是，这里的题干和常规的两数之和还有点区别。首先，该题干中，天生有序，所以，可以套用反向双指针的套路。

为了做区分，我们将twoSum的解题代码也直接写出来。它的解题思路是，利用了Map对数据和下标做了转换。

function twoSum(nums,target){
    let valueToIndex = new Map(); // 用于，存储[nums[i],i]之间的关系
    for(let i = 0;i<nums.length;i++){
        let expectValue = target - nums[i];
        // 先从map中找，是否存在指定值
        if(valueToIndex.has(expectValue)){
            // 如果有，直接返回与值相对于的下标
            return [valueToIndex.get(expectValue),i]
        }
        // 存储[nums[i],i]之间的关系
        valueToIndex.set(nums[i],i);
    }
    return null;
}

数组中和为target的3个数字

题目描述：

输入一个数组，找出数组中所有和为target的3个数字的三元组提示：返回值不得包含重复的三元组示例：输入数组： [-1,0,1,2,-1,-4],target的值为0 输出[[-1,0,1],[-1,-1,2]]

分析

如果输入的数组是有序，那就可以先固定一个数，然后在该数后面的数组段中，采用双指针解法的第一套：反向双指针
- 按照既定套路， left指向固定元素的后一个元素，right指向尾元素
- 根据 sum VS target 移动对应的指针
- 该解题思路，其实就是求排序数组中的两个数字之和的升级版
剔除重复三元组的时机，
- 应该是在找到符合要求(三数之和=target)时，在移动指针时，需要跳过所有相同的值
针对整数数组(有正，有负)升序排序利用sort但是需要指定排序函数
- nums.sort((a,b)=>a-b)

代码实现

function threeSum(nums,target){
  let result = [];
  if(nums.length<3) return [];
  
  // 人工对数据进行排序处理
  nums.sort((a,b)=>a-b);
  
  let i =0;
  while(i<nums.length-2){
    twoSum(nums,i,target,result);
    let temp = nums[i];
    // 剔除，重复元祖中第一个数值
    while(i<nums.length && nums[i]==temp) i++;
  }
  return result;
}

我们把排序数组中的两个数字之和的算法，做了一个改造，因为left不在从0开始，所有需要将left的前一个位置i传入，right的逻辑不变，还是数组尾部

left = i + 1
right = nums.length - 1


function twoSum(nums,i,target,result){
  // 初始化指针left,right 
  let left = i + 1, right = nums.length -1;
  
  while(left<right){
    // 求和
    let sum = nums[i] + nums[left] + nums[right];
    // 指针移动过程 (if/else)
    if(sum === target){
      result.push([nums[i],num[left],nums[right]]);
      
      let temp = nums[left];
      // 剔除，重复元祖第二个数值
      while(nums[left] === temp && left < right) left++;
    }else if(sum < 0) {
      left++;
    }else{
      right--;
    }
  }
}

我们来对比下，两个twoSum的共同和不同点。

JS算法_知识点精讲

它们的核心框架是相似的。都是利用方向双指针进行sum与target之间的数据对比。

和大于或等于k的最短子数组

题目描述：

输入一个正整数组成的数组和一个正整数target,找出数组中和大于或等于target的连续子数组的最短长度提示：如果不存在满足条件的子数组，返回0 示例：输入数组： [5,1,4,3],target的值为7 输出2 (和大于或等于7的最短连续子数组是[4,3])

分析

题干出现正整数数组/连续子数组之和，很满足之前介绍的同向双指针解题思路
一个子数组可以用两个指针表示
- left指向子数组的第一个数字
- right指向子数组的最后一个数字
- 子数组就是left/right两指针之间的所有数字的组成
指针left永远不会走到指针right的右边
left/right初始化的时候都指向数组的第一个元素，套用上面的公式
- 1. sum < target: 右移 right（right++）,在子数组右边增加新的数字，子数组长度+1
- 1. sum >= target: 右移left(left++)，删除子数组最左边的数字，子数组长度-1
题目要求，最短长度。而提供的数组为正整数，也就是说，在找到sum>=target时，为了求最短子数组，我们需要移动left进行子数组的瘦身处理 (left++)

代码实现

function minSubArrayLen(nums,target){
  let left=0,right=0; // 同向双指针，默认值
  let sum=0; 
  // 最小的长度
  let minLength = Number.MAX_SAFE_INTEGER;
  
  for(right=0;right<nums.length;right++){
    sum+=nums[right];
    while(left<=right && sum>=target){
      // 更新最小长度
      minLength = Math.min(minLength,right - left + 1);
      // 子数组**瘦身**处理
      sum-= nums[left++]
    }
  }
  return minLength == Number.MAX_SAFE_INTEGER?0:minLength;
}

有几点需要唠叨一下：

针对一些常规的最值的初始值，一般都是反着来。例如：最小值，一般赋合理范围的最大值(Number.MAX_SAFE_INTEGER) 如果已知最大范围，我们也可以给一个定值。例如，100/1000等；那最大值，就是用0等替换
同向双指针 ：right先动,left视情况而动

乘积大于或等于k的最短子数组

题目描述：

输入一个正整数组成的数组和一个正整数target,找出数组中乘积小于target的连续子数组的所有组合的个数示例：输入数组： [10,5,2,6],target的值为100 输出 8 （[10],[5],[2],[6],[10,5],[5,2],[2,6],[5,2,6]）

分析

题干出现正整数数组/连续子数组乘积，很满足之前介绍的同向双指针解题思路，两个指针之间的数字组成一个子数组。
指针left永远不会走到指针right的右边 (left<=right)
两个指针初始化都指向数组的第一个数字
指针移动逻辑
- 1. mult < target: 右移 right（right++）,在子数组右边增加新的数字，子数组长度+1 (mult变大)
- 1. mult >= target: 右移left(left++)，删除子数组最左边的数字，子数组长度-1(mult变小)
一旦向右移动指针left到某个位置时子数组的乘积小于target,就不需要移动left。只要right保持不动，[left,right]区间的所有的子数组的乘积都一定小于target。也就说说，两个指针之间有多少个数字，就有多少个满足条件的子数组

代码实现

function numSubarrayMultLessThanTarget(nums,target){
  let mult = 1; 
  let left =0,right=0; // 初始化指针
  let count = 0;
  
  for(right=0;right<nums.length;right++){
    mult *=nums[right];
    // 指针left永远不会走到指针right的右边
    while(left<=right && mult >= target){
      mult /=nums[left++];
    }
    count += right>=left?right - left +1 :0;
  }
  return count;
}

虽然，在求正整数数组和或者乘积之间，有些具体逻辑不大相同，但是总体的思路都是利用同向双指针对数据进行处理。

累加数组数字求子数组之和（Si）

使用双指针解决子数组之和有一个前提条件：数组中的所有数字都是正数。所有，双指针的在解决非正数的数组时，是不满足条件的。

针对非正数的数组，我们换一个思路来求子数组之和。

假设整个数组的长度为n,它的某个子数组的第一个数字的下标是i;最后一个数字的下标是j。我们做一个预处理，计算从数组下标为0的数字开始到以每个数字为结尾的子数组之和。预处理只需要从头到尾扫描一次，就能求出从下标0开始到下标0结束的子数组之和 S0 ,以此类推，S1,S2,Sn-1因此，从下标为i开始到下标为j结束的子数组的和就是 Sj-Si-1

例如：在数组[1,2,3,4,5]中，从S2的子数组[1,2,3]之和是6，S4的子数组[1,2,3,4,5]之和是15，那么从下标3开始到下标4结束的子数组之和[4,5]之和是9，也就是 S4 - S2 即： 15 - 9 = 6

和为target的子数组

题目描述：

输入一个整数组成的数组和一个整数target,找出数组中数字之和等于target的连续子数组的个数示例：输入数组： [1,1,1],target的值为2 输出 2

分析

求连续子数组之和，但是数组不是正整数，所以同向双指针作废
双指针作废，那我们就采用前i个数字之和的处理方式
- 从头到尾扫描数组时，求前i个数字之和，并将和保存下来
- 将数组的前i个数字之和记为x
- 如果存在一个j (j<i) 即，j在x前面，且数组的前j个数字之和为x-target（很重要）
- 那么数组中从第j+1个数字开始到第i个数字结束的子数组之和为target
此题中需要计算和为target的子数组的个数。当扫描到数组第i个数字并求得前i个数字之和是x时，需要知道在i之前存在多少个j并且前j个数字之和等于x-target
- 所以，对于每个i,不但要保存前i个数字之和，还要保存每个和出现的次数
- 所以，我们用一个Map（哈希表）的键(key)保存前i个数字之和，值(value)保存每个和出现的次数

代码实现

function subarraySum(nums,target){
  // 构建哈希表，并初始化[0,1]
  let sumToCount = new Map();
  sumToCount.set(0,1);
  
  let sum = 0;
  let count =0;
  for(let num of nums){
    sum += num;
    // 统计 在当前数值下的 x-target的值
    count += sumToCount.get(sum - target) // 前面已经存在
             || 0; // 首次出现
    sumToCount.set(
        sum,
        (sumToCount.get(sum)||0)+1
      )
  }
  return count;
}

0和1个数相同的子数组

题目描述：

输入一个只包含0和1的数组，求0和1的个数相同的最长连续子数组的长度示例：输入数组： [0,1,0] 输出 2 （两个子数组分别是[0,1]和[1,0]）

分析

如果把数组中所有的0换成-1,做一个转化处理，求0/1个数相同的子数组，就变成了，求子数组之和为0。那就变成和为target的子数组的进阶版，只不过，需要求子数组中长度最长的子数组的长度
那就还是采用和为target的子数组的解题思路：前i个数字之和
扫描数组时累加扫描过的数字之和，如果数组中前i个数字之和为m,前j个数字(j<i)之和也为m,那么从j+1到第i个数字的子数组之和为0，长度为i - j
利用一个Map来存储对应的下标，键(key)是从第一个数字开始累加到当前扫描到的数字之和，而值(value)是当前扫描的数字的下标

代码实现

function findMaxLength(nums){
  let sumToIndex = new Map();
  sumtoIndex.set(0,-1);
  let sum = 0;
  let maxLength =0;
  
  for(let i=0;i<nums.length;i++){
    // 数据转化
    sum+=nums[i]==0?-1:1;
    if(sumToIndex.has(sum)){
      maxLength = Math.max(maxLength,i-sumToIndex.get(sum));
    }else{
      // 存储关系
      sumToIndex.set(sum,i)
    }
  }
  return maxLength;
}

我们可以看到，在和为target的子数组和0和1个数相同的子数组中，虽然有些细节是不一样的，但是总体框架还是一致的。

前i个数字之和求出sum
利用Map 来存储sum与对应所求的(count/index)直接的关系
满足条件更新结果

左右两边子数组的和相等

题目描述：

输入一个整数数组，如果一个数字左边的子数组的数字之和等于右边子数组的数字之和，返回该数字的下标示例：输入数组： [1,7,3,6,2,9] 输出 3 （对应的值为6），下标为3的数字(值为6)的左边3个数1,7,3的和与右边两个数字2,9的和相等

分析

当扫描到第i个数字时
- 它左边的子数组的数字之和就是从第一个数字开始累加到第i-1个数字的和
- 它右边的子数组的数字之和就是从第i+1个数字开始累加到最后一个数字的和,这个和等于数组中所有数字之和减去从第一个数字累加到第i个数字的和

代码实现

function pivotIndex(nums){
  let total =0;
  total =nums.reduce((pre,cur)=>pre+cur);
  
  let sum = 0;
  for(let i=0;i<nums.length;i++){
    sum+=nums[i];
    if(sum - nums[i] == total - sum){
      return i
    }
  }
  return -1;
}

总结

数组算法千千万，sum套路就那般
类型不同路不同，正整数双指针，其余尝试用Si
正整数分两类，同向/反向双指针
1. 数据有序反向针，left为首right为尾(求两数之和)
2. 子数组同向针，区域之和或乘积
非正整数用Si(前i个数据和)
1. Sj-Si-1 为所求
2. 找次数、长度 Map(sum,count/index)来辅助

字符串

在JS中，字符串可以被视为字符数组

str.charAt(i)用于获取str在i位置的字符

在JS中，字符之间是无法之间相减

'b' - 'a' // NAN

其实，这里面的深层次的原因是，JS中针对 '-'操作符，没兼容字符。而-操作符要的预期就是返回数值，因为，字符没被兼容，所以结果返回了一个NAN。

作为替换方案，str.charAt(i).charCodeAt()(获取str在i位置的字符ASCLL码值 )就肩负起，字符之间相减的操作

str = 'ba';
str.charAt(1).charCodeAt() - str.charAt(0).charCodeAt()
// 结果为1  b的ascll 为98，a的ascll为97 即：98 -97

双指针

字符串可以被视为字符数组，那么也可以用双指针的技巧来处理字符串的一些问题。

由于在处理字符串时，很多都与统计字母出现的次数有关，所以我们可以借用哈希表(map)来存储每个元素出现的次数。

Map 在信息存储方面还是很有用的。在讲数组算法中，在非正整数用Si时，就用 Map进行key 和value的信息存储

字符串中的变位词

题目描述：

输入字符串s1和s2,判断s2中是否包含s1的某个变位词提示：如果s2中包含s1的某个变位词，则s1至少有一个变位词是s2的子字符串 假设两个字符串中只包含英文小写字母示例：s1 为“ac”, s2为“dgcaf” ,由于s2包含s1的变位词"ca", 结果为true

分析

变位词是指组成各个单词的字母及每个字母出现的次数完全相同，只是字母的排列顺序不同
变位词有几个特点
- 一组变位词长度相同
- 组成变位词的字母集合相同
- 每个字母出现的次数也相同
变位词与字母及字母出现的次数有关，那么统计字符串中包含的字母及每个字母出现的次数。
- 哈希表的键是字母
- 值对应的是字母出现的次数
题中，说只含有小写英文，所以我们可以用数组模拟一个哈希表
- 数组下标表示字母，即下标为0 对应字母a, 下标为1对应字母b
- 数组中的值表示对应字母出现的次数
首先，扫描s1,每扫描到一个字符，就找到它在哈希表中的位置，并把它对应+1
判断s2的子字符串是否包含s1的变位词
- 假设s1长度为n
- 逐一判断s2中长度为n的子字符串是不是s1的变位词
- 扫描子字符串中的每个字母，把该字母在哈希表中对应的值-1
- 如果哈希表中所有值都是0，那么该子字符串就是s1的变位词

代码实现

function checkInclusion(s1,s2){
  let s1l = s1.length,s2l = s2.length;
  
  if(s2l<s1l) return false;
  
  // 构建 字符 => 个数 数组
  let counts = new Array(26).fill(0);
  
  // 遍历s1,并对s1中字符进行数据收集 (++)
  // 针对已收集的s1数据信息，与s2进行匹配(--)
  for(let i =0;i<s1l;i++){
    counts[s1.charAt(i).charCodeAt() - 97]++;
    counts[s2.charAt(i).charCodeAt() - 97]--;
  }
  
  //判断，是否全为0，如果是，刚才已经满足情况了，直接返回true
  if(areaAllZero(counts)) return true;
  
  //从s1l的位置出发，先匹配，后收集(类似同向双指针)
  for(let i = s1l;i<s2l;i++){
    counts[s2.charAt(i).charCodeAt() - 97]--;
    counts[s2.charAt(i - s1l).charCodeAt() -97]++;
    if(areaAllZero(counts)) return true;
  }
  return false
}

辅助函数，用于判断，数值中值是否都为0

function areaAllZero(counts){
  for(let count  of counts) {
    if(count >0) return false
  }
  return true;
}

在上面的函数中，

第一个指针指向下标为i-s1l的位置
第二个for循环中的下标i相当于第二个指针，指向子字符串的最后一个字符
两个指针之间的子字符串的长度一直是字符串s1的长度

字符串中所有变位词

题目描述：

输入字符串s1和s2,找出s1的所有变位词在s2中的起始下标提示：假设两个字符串中只包含英文小写字母示例：s1 为“abc”, s2为“cbadabacg” ,s1的两个变位词"cba"/"bac"是s2中的子字符串，输出在s2中的起始下标为0和5

分析

和找字符串中的变位词的思路是一样的

变位词与字母及字母出现的次数有关，那么统计字符串中包含的字母及每个字母出现的次数。
- 哈希表的键是字母
- 值对应的是字母出现的次数
题中，说只含有小写英文，所以我们可以用数组模拟一个哈希表
- 数组下标表示字母，即下标为0 对应字母a, 下标为1对应字母b
- 数组中的值表示对应字母出现的次数
首先，扫描s1,每扫描到一个字符，就找到它在哈希表中的位置，并把它对应+1
判断s2的子字符串是否包含s1的变位词
- 假设s1长度为n
- 逐一判断s2中长度为n的子字符串是不是s1的变位词
- 扫描子字符串中的每个字母，把该字母在哈希表中对应的值-1
- 如果哈希表中所有值都是0，那么该子字符串就是s1的变位词（进行下标的记录处理）

代码实现

function findAnagrams(s1,s2){
  let result = [];
  
  let s1l = s1.length,s2l = s2.length;
  if(s2l<s1l) return result;
  
  let counts = new Array(26).fill(0);
  
  for(let i= 0;i<s1l;i++){
    counts[s1.charAt(i).charCodeAt() - 97]++;
    counts[s2.charAt(i).charCodeAt() - 97]--;
  }
  
  if(areaAllZero(counts)) result.push(0);
  
  for(let i= s1l;i<s2l;i++){
    counts[s2.charAt(i).charCodeAt()-97]--;
    counts[s2.charAt(i-s1l).charCodeAt()-97]++;
    // 在满足情况下，对应的开始下标为`i-s1l+1`
    if(areaAllZero(counts)) result.push(i - s1l+1);
  }
  return result
}

辅助函数，用于判断，数值中值是否都为0

function areaAllZero(counts){
  for(let count  of counts) {
    if(count >0) return false
  }
  return true;
}

针对字符串中的变位词还是字符串中所有变位词中用到的思路，都是利用数组来模拟哈希表(map)然后，针对特定的场景进行数据的处理。然后，针对双指针的定义，在第二个for循环中，第一个指针为i-s1l对应的位置，第二个指针，为i对应的位置，而两者恰好相差(s1l)的长度。

不含重复字符的最长子字符串

题目描述：

输入一个字符串，求该字符串中不含重复字符的最长子字符串 示例: 输入"babcca",其最长的不含重复字符的子字符串为“abc”，长度为3

分析

此处用哈希表(map)统计子字符串中字符出现的次数
如果一个字符串中不含重复的字符，那么每个字符都是只出现一次，即哈希表中对应的值为1
我们还是采用用数组来模拟哈希表，由于题目中，没限制字符为小写英文字母，所以我们需要对字符做一个简单限制，只处理ascll的字符，即：new Array(256).fill(0)
仍用两个指针来定位一个子字符串
- 第一个指针指向子字符串的第一个字符
- 第二个指针指向子字符串的最后一个字符
如果两个指针之间的子字符串不包含重复的字符，为了找出最长的子字符串，向右移动第二个指针，然后判断是否出现重复字符
如果两个指针之间的子字符串中包含重复的字符，向右移动第一个指针

代码实现

function lengthOfLongestSubstring(s){
  let sl = s.length;
  if(sl==0) return 0;
  
  let counts = new Array(256).fill(0);
  let longest = 0;
  let j= -1; // 左指针
  // i 为右指针
  for(let i=0;i<sl;i++){
    counts[s.charAt(i).charCodeAt()]++;
    while(hasGreaterThan1(counts)){
      j++
      counts[s.charAt(j).charCodeAt()]--;
    }
    // 更新最长子串的长度
    longest = Math.max(i-j,longest);
  }
  return longest;
}

辅助函数，用于判断数组中是否有含有大于1的数

function hasGreaterThan1(counts){
  for(let count of counts){
    if(count>1) return true
  }
  return false;
}

在上面代码中，其实难点就是双指针的定义和赋值

左指针 1. 默认值为-12. 在hasGreaterThan1为true时，j++,且counts指定位置counts[s.charAt(j).charCodeAt()]--
右指针 1. 默认值为0 2. 通过循环控制右指针移动

回文字符串

回文是一类特殊的字符串。不管从前往后，还是从后往前，得到的字符信息都是一样的。

有效回文

题目描述：

输入一个字符串，判断它是不是回文提示：只考虑字母和数字字符，忽略大小写示例: 输入字符串“abba”返回true, 输入“abc”返回false

分析

判断字符串是否为回文，既定套路反向双指针
- 一个指针从第一个字符开始，从前往后移动
- 另一个指针从最后一个字符开始，从后往前移动
针对非数字和字母的字符，进行跳过处理
大小写需要转换

代码实现

function isPalindrome(s){
  let left =0,right = s.length -1;
  
  while(left<right){
    // 获取指定位置的字符
    let cl = s.charAt(left);
    let cr = s.charAt(right);
    
    // 跳过非数字和字母的字符 (!isLetterOrDigit(x))
    if(!isLetterOrDigit(cl)){
      left++;
    }else if(!isLetterOrDigit(cr)){
      right--;
    }else {
      // 大小写不敏感
      cl = cl.toLocaleLowerCase();
      cr = cr.toLocaleLowerCase();
      // 不一样，跳出循环
      if(cl!=cr) return false
      
      // 指针移动
      left++;
      right--;
    }
  }
  return true;
}

辅助函数

const isLetterOrDigit = str =>  /^[A-Za-z0-9]+$/.test(str)

最多删除一个字符得到回文

题目描述：

输入一个字符串，判断最多从字符串中删除一个字符能不能得到一个回文字符串示例: 输入字符串“abca”, 删除字符b或者c能得到一个回文字符串，因此输出true

分析

判断字符串是否为回文，既定套路反向双指针
- 一个指针从第一个字符开始，从前往后移动
- 另一个指针从最后一个字符开始，从后往前移动
题目中说，最多删除一个字符
- 不删除：本身就是回文串
- 删除：可能是前半部分，也可能是后半部分

代码实现

function validPalindrome(s){
  let left =0,right = s.length -1;
  
  let middlePosition = s.length>>1;
  
  // 移动指针，并比较字符是否相等
  for(;left<middlePosition;left++,right--){
    if(s.charAt(left)!=s.charAt(right)) break;
  }
  // 这里有两类情况 
  // 1: 字符串本身是回文 (left == middlePosition)
  // 2. 需要对字符串进行字符剔除 （isPalindrome）
  return left == middlePosition 
        || isPalindrome(s,left,right-1)
        || isPalindrome(s,left+1,right)
}

辅助函数，用于判断字符串是否是回文

function isPalindrome(s,left,right){
  while(left<right){
    if(s.charAt(left)!= s.charAt(right)) break;
    
    left++;
    right--;
  }
  return left>=right;
}

这里有一个比较重要的点，就是最多可以删除一个字符。放到代码中其实就是在validPalindrome中return那里体现

不删除字符：本身就是回文，那就意味着在validPalindrome中for循环没阻断，即：left == middlePositon
删除字符：意味着在validPalindrome中的for发生了阻断(break)
- 在阻断处，删除后半部分的字符isPalindrome(s,left,right-1)
- 在阻断处，删除前半部分的字符isPalindrome(s,left+1,right)

回文子字符串的个数

题目描述：

输入一个字符串，求字符串中有多少个回文连续子字符串？示例: 输入字符串“abc”有3个回文子字符串，分别是"a"/"b"/"c"

分析

判断字符串是否为回文，既定套路反向双指针
- 从两边向中间移动(比较常见)
- 从中间向两边扩散
回文的长度既可以是奇数，也可以是偶数
- 长度为奇数的回文的对称中心只有一个字符
- 长度为偶数的回文的对称中心有两个字符

代码实现

function countSubstrings(s){
  if(s==null || s.length==0) return 0; //处理边界
  
  let count = 0;
  for(let i=0;i<s.length;i++){
    // 字符串下标为i。
    // 既作为奇数回文的中心
    // 又可以和i+1一同作为偶数回文的中心
    count+=countPalindrome(s,i,i);
    count+=countPalindrome(s,i,i+1);
  }
  return count;
}

辅助函数，

function countPalindrome(s,left,right){
  let count = 0;
  while(left>=0&&right<s.length
        && s.charAt(left)==s.charAt(right)){
          count++;
          left--;
          right++;
        }
  return count;
}

这个题，最主要的就是需要明白：

第i个字符本身可以成为长度为奇数的回文字符串的对称中心
- 所以，在下标i的位置 countPalindrome(s,i,i);
第i个字符和第i+1个字符可以成为长度为偶数的回文字符串的对称中心
- 所以，在下标i的位置 countPalindrome(s,i,i+1);

总结

字符串算法有很多，变位词、回文串来报道
变位词要数数，哈希表来撑场面
- 哈希表可变通，counts = new Array(x).fill(0)
- 下标对应ascll字符，s.charAt(i).charCodeAt()
- 值对应字符梳理, counts[x]++或--
- 反向双指针，第一指针，始终为i-s1l,第二指针i
回文串有特点，前后字符都一样
- 反向双指针花样多
- 两边向中间,left=0/right= s.length-1
- 中间向两边, i可为奇数中心，i与i+1可为偶数中心

链表

构造链表节点单向链表的节点代码

class ListNode {
      val: number
      next: ListNode | null
      constructor(val?: number, next?: ListNode | null) {
          this.val = (val===undefined ? 0 : val)
          this.next = (next===undefined ? null : next)
      }
  }

链表基础算法

其实，针对链表存在一些常规的工具方法。一些比较复杂的算法，都是各种工具方法的组合。

而下面的这些方法，是需要熟记的。

1. 链表反转

关键点解释：

需要三个指针
- 各自初始值如下：
- perv = null
- cur = head
- next = cur.next
遍历的时候
- 先存后续(next= cur.next)
- 在修改引用(cur.next = prev)
- 暂存当前节点(prev= cur)
- 后移指针(cur=next)

function reverseList(head){
  // 初始化prev/cur指针
  let prev = null;
  let cur = head;
  // 开始遍历链表
  while(cur!=null){
    // 暂存后继节点
    let next = cur.next;
    // 修改引用指向
    cur.next = prev;
    // 暂存当前节点
    prev = cur;
    // 移动指针
    cur = next;
  }
  return prev;
};

2. 判断链表是否有环

关键点解释：

快慢指针
遍历的条件
- while(fast && fast.next)

function hasCycle(head){
  let fast = head;
  let slow = head;
  
  while(fast && fast.next){
    fast = fast.next.next;
    slow = slow.next;
    if(fast == slow) return true;
  }
  return false;
}

3. 合并链表

关键点解释：

为了规避，边界情况(l1/l2可能初始为空)，采用dumy节点
- dumy = new ListNode(0)
- 定义一个临时指针node = dumy
处理l1/l2相同位置的节点信息
- while(l1 && l2)
- 根据特定的规则，对链表进行合并处理
- node.next = lx (x=1/2)
- 移动处理后的链表 lx = lx.next
处理l1/l2溢出部分的节点信息
- if(lx) node.next = lx;
返回整合后的首节点
- dumy.next

function mergeList(l1,l2){
  let dumy = new ListNode(0);
  let node = dumy;
  while(l1 && l2){
    node.next = l1;
    l1 = l1.next;
    
    node.next = l2;
    l2 = l2.next;
  }
  // 由于l1/l2长度一致
  if(l1) node.next = l1;
  if(l2) node.next = l2;
  return dumy.next;
}

4. 找中点

关键点解释：

利用快慢指针
- 初始值
- slow = head
- fast = head
循环条件为
- fast && fast.next非空
指针移动距离
- fast每次移动两步 fast = fast.next.next
- slow每次移动一步 slow = slow.next
处理链表节点为偶数的情况
- 跳出循环后，也就是fast.next ==null,但是，fast可能不为空
- 如果fast不为空，slow还需要移动一步 slow = slow.next (奇数情况)
最后，slow所在的节点就是链表的中间节点

function middleNode(head){
        let slow = head;
        let fast = head;
        // 遍历链表节点
        while (fast && fast.next) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 处理链表节点为偶数的情况
        if(fast){
          slow = slow.next;
        }
        return slow;
    }

哨兵节点

哨兵节点是为了简化处理链表边界条件而引入的附加链表节点

哨兵节点通常位于链表的头部，它的值没有任何意义。在一个有哨兵节点的链表中，从第二个节点开始才真正的保存有意义的信息。

简化链表插入操作

哨兵节点，在链表尾部添加元素

function append(head,value) {
  // 哨兵节点 
  let dumy = new ListNode(0);
  dumy.next = head;
  
  // 遍历链表，直到链表尾部
  let node = dumy;
  while(node.next!=null){
    node = node.next;
  }

  node.next = new ListNode(value);
  return dumy.next;
}

在遍历链表的时候，并不是直接对dumy进行处理，而是用了一个临时游标节点(node)。这样做的好处就是，在append操作完成以后，还可以通过dumy节点来，直接返回链表的头节点dumy.next。因为,dumy一直没参与遍历过程。

简化链表删除操作

为了删除一个节点，需要找到被删除节点的前一个节点，然后把该节点的next指针指向它下一个节点的下一个节点。

哨兵节点，在删除指定节点

function delete(head ,value){
  let dumy = new ListNode(0);
  dumy.next = head;
  
  let node = dumy;
  while(node.next!=null){
    if(node.next.value==value){
      node.next = node.next.next;
      barek;
    }
    node = node.next;
  }
  return dumy.next;
}

通过哨兵节点(dumy)直接将链表为空和被删除节点是头节点的两种特殊情况，直接囊括了。用最少的代码，处理最多的情况。

使用哨兵节点可以简化创建或删除链表头节点的操作代码

双指针

在链表中，双指针思路又可以根据两个指针的不同移动方式分为两种不同的方法。

前后双指针：即一个指针在链表中提前朝着指向下一个节点的指针移动若干步，然后移动第二个指针。

应用：查找链表中倒数第k个节点

快慢双指针：即两个指针在链表中移动的速度不一样，通常是快的指针朝着指向下一个节点的指针一次移动两步，慢的指针一次只移动一步。

特征：在一个没有环的链表中，当快的指针到达链表尾节点的时候，慢的指针正好指向链表的中间节点

删除倒数第`k`个节点

题目描述：

给定一个链表，删除链表中倒数第k个节点提示：假设链表中节点的总数为n且 1≤ k ≤ n 只能遍历一次链表 示例：链表为 1->2->3->4->5,删除倒数第2个节点后链表为1->2->3->5，删除了4所在的节点

分析

题目要求只能遍历一次链表，我们可以定义两个指针
- 第1个指针 front从链表的头节点开始向前走k步的过程中，第2个指针back保持不动
- 从第k+1步开始，back也从链表的头节点开始和front以相同的速度遍历
- 由于两个指针的距离始终保持为k,当指针front指向链表的尾节点时（如果存在dumy节点的话，就是front指向尾节点的下一个节点），指针back正好指向倒数第k+1个节点
我们要删除倒数第k个节点，而利用快慢双指针，我们可以找到倒数第k+1个节点,即倒数k节点的前一个节点，那更新倒数k+1节点的next指针，就可以将倒数k个节点删除
当k等于链表的节点总数时，被删除的节点为原始链表的头节点，我们可以通过dumy节点来简化对此处的处理
而由于dumy节点的出现，由于存在front/back两个指针，就需要对其进行初始化处理。
- back：由于存在③的情况（删除原始链表头节点），所以back初始化必须是back=dumy（back指向dumy）
- front：初始指向原始链表的头节点(front=head)

代码实现

function removeNthFromEnd(head,k){
  let dumy = new ListNode(0);
  dumy.next = head;
  
  let front = head; //指向原始链表头节点
  let back = dumy; // 指向dumy节点
  
  // front 向前移动了k个节点
  for(let i =0; i<k; i++){
    front = front.next;
  }
  // 同步移动
  while(front!=null){
    front = front.next;
    back = back.next;
  }
  // 删除第k个节点
  back.next = back.next.next;
  return dumy.next;
}

在同步移动的过程中，只有front移动到尾节点的下一个节点，即：null时，此时back节点才到了倒数k+1的位置

链表中环的入口节点

题目描述：

如果一个链表包含环，找出环的入口节点！示例：输入：head = [3,2,0,-4], 输出： pos = 1 返回索引为 1 的链表节点

分析

判断一个链表是否有环：
- 定义两个指针并同时从链表的头节点出发(不涉及append/delete，可以不用dumy节点)
- 一个指针一次走一步，另外一个指针一次走两步
- 如果有环，走的快的指针在绕了n圈之后将会追上走的慢的指针
在①的基础上，快慢指针在某处进行相遇了，此时调整快慢指针的指向，将fast指针指向链表头部，slow指针保持不变。并且，slow/fast以相同的速度(每次移动一个节点)，在slow/fast再次相遇时，就是环的入口节点
- 根据快慢指针移动速度之间的关系，并且假设在快指针移动n后相遇，我们可以有1. a + n(b+c) + b = a+(n+1)b+nc （快指针移动的距离）2. (a+b) (慢指针移动的距离) 3. a+(n+1)b+nc=2(a+b)(快指针比慢指针多移动一倍的距离)4. a=c+(n−1)(b+c)可以得出，如果有两个指针分别从头节点和相遇节点以相同的速度进行移动。在经过n-1圈后，他们会在环的入口处相遇

代码实现

判断一个链表是否有环

function hasCycle(head){
  let fast = head;
  let slow = head;
  
  while(fast && fast.next){
    fast = fast.next.next;
    slow = slow.next;
    if(fast == slow) return true;
  }
  return false;
}

找到环的入口节点

function detectCycle(head){
  let fast = head;
  let slow = head;
  while(fast && fast.next){
    fast = fast.next.next;
    slow = slow.next;
    if(fast ==slow){
      fast = head;
      while(fast!=slow){
        fast = fast.next;
        slow = slow.next;
      }
      return slow
    }
  }
  return null;
}

通过对比我们发现，利用双指针查找链表中环的入口节点，其实就是在判断链表是否有环的基础上进行额外的处理。

两个链表的第一个重合节点

题目描述：

输入两个单向链表，找出它们的第一个重合节点示例：链表A:1->2->3->4->5->6 链表B: 7->8->4->5->6 输出两个链表的第1个重合节点的值是4

分析

如果两个单向链表有重合节点，那么这些重合的节点一定只出现在链表的尾部。并且从某个节点开始这两个链表的next指针都指向同一个节点。
由于涉及到两个链表，此时它们各自的长度会不一样，而根据①中我们得知，两个链表相同的节点，都位于各自链表的尾部。
- 可以利用两个指针分别指向两个链表的头结点
- 分别遍历对应的链表，计算出对应链表的节点数量（count1/count2）
- 在第二次遍历的时候，节点数多的链表先向前移动distance = Math.abs(count1-count2)个节点
- 在移动distance个节点后，此时两个链表中所剩节点数相同，也就是说，从接下来，可以认为在两个相同长度的单向链表中寻找第一个重合节点

代码实现

计算链表中有多少个节点

function countList(head){
  let count = 0;
  while(head!=null){
    count++;
    head = head.next;
  }
  return count;
}

查找第一个重合节点

function getIntersectionNode(headA, headB) {
  // 计算各自节点数量
  let count1 = countList(headA);
  let count2 = countList(headB);
  
  // 相差节点数
  let distance = Math.abs(count1-count2);
  
  // 找出最长/最短 链表
  let longer  = count1 > count2 ? headA : headB;
  let shorter = count1 > count2 ? headB : headA;
  
  // 定义指向 longer链表的指针
  let node1 = longer;
  // 优先移动distance个节点
  for(let i =0 ;i<distance;i++){
    node1 = node1.next;
  }
  // 定义指向 shorter 链表的指针
  let node2 = shorter;
  // 判断处理
  while(node1!=node2){
    node2 = node2.next;
    node1 = node1.next;
  }
  return node1;
};

反转链表

单向链表最大的特点就是其单向性--即只能顺着指向下一个节点的指针方向从头到尾遍历。

而有些情况，从链表尾部开始遍历到头节点更容易理解。所以，就需要对链表进行反转处理。

反转链表

题目描述：

将指定的链表反转，并输出反转后链表的头节点示例：链表:1->2->3->4->5 反转后的链表为5->4->3->2->1, 头节点为5所在的节点

代码实现

function reverseList(head){
  // 初始化prev/cur指针
  let prev = null;
  let cur = head;
  // 开始遍历链表
  while(cur!=null){
    // 暂存后继节点
    let next = cur.next;
    // 修改引用指向
    cur.next = prev;
    // 暂存当前节点
    prev = cur;
    // 移动指针
    cur = next;
  }
  return prev;
};

重排链表

题目描述：

给一个链表，链表中节点的顺序是l0->l1->l2->(...)->l(n-1)->ln。对链表进行重排处理，使节点顺序变成l0->ln->l1->l(n-1)->l2->l(n-2)->(...) 示例：链表:1->2->3->4->5->6 重排后的链表为1->6->2->5->3->4

分析

通过观察可知，在原链表经过如下处理，即可拼接出重排后链表
1. 链表一分为二 第一部分：1->2->3 第二部分：4->5->6
2. 对①的第二部链表，进行反转处理 4->5->6-->6->5->4
3. 在②的基础上，从前半段链表和后半段的头节点开始，逐个把它们节点连接起来最后的节点顺序为： 1->6->2->5->3->4
使用双指针来寻找链表的中间节点
- 一快一慢两个指针同时从链表的头节点出发
- 快指针一次顺着next指针方向向前走两步
- 慢指针一次走一步
- 当快指针走到链表的尾节点时候，慢指针刚好走到链表的中间节点

代码实现

找到链表的中间节点（使用快慢指针）

function middleNode(head){
        let slow = head;
        let fast = head;
        // 遍历链表节点
        while (fast && fast.next) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 处理链表节点为偶数的情况
        if(fast){
          slow = slow.next;
        }
        return slow;
    }

合并两个链表

function mergeList(l1,l2){
  let dumy = new ListNode(0);
  let node = dumy;
  while(l1 && l2){
    node.next = l1;
    l1 = l1.next;
    
    node.next = l2;
    l2 = l2.next;
  }
  // 由于l1/l2长度一致
  if(l1) node.next = l1;
  if(l2) node.next = l2;
  return dumy.next;
}

重排链表

function reorderList(head){
  if(head==null) return head;
  
  //找到链表的中间节点
  let mid = middleNode(head);
  // 前半部分链表
  let l1 = head;
  // 后半部分链表
  let l2 = mid.next;
  // 将原链表一分为二
  mid.next = null;
  // 后半部分链表反转
  l2 = reverseList(l2);
  // 合并处理
  mergeList(l1, l2);
}

回文链表

题目描述：

判断一个链表是回文链表要求：时间复杂度为O(n),空间复杂度为O(1) 示例：链表:1->2->3->3->2->1 该链表为回文链表

分析

题目对时间复杂度和空间复杂度都有很高的要求。也就是需要对链表遍历一次，就需要判断链表是否为回文链表
而根据回文的特性可知，从数据的中间一刀两断，对某一部分链表进行反转，此时反转后的链表和另外的部分是相同的
- 找到链表中间节点(一分为二)
- 反转某一部分链表
- 两个链表挨个对比

代码实现

还是熟悉的味道

找到链表的中间节点 (前文有介绍，这里不再赘述)

反转某部分链表 (前文有介绍，这里不再赘述)

那么，现在就剩下对两个链表进行对比判断了

function equails(head1,head2){
  while(head1 && head2){
    //相应位置的val不同，两个链表不同
    if(head1.val!=head2.val){
      return faslse;
    }
    head1 = head1.next;
    head2 = head2.next;
  }
  // 如果head1/head2长度不同，也返回false
  return head1 ==null && head2==null;
}

判断是否为回文

function isPalindrome(head) {
   
    let left = head;
    // 找到链表的中间节点
    let slow = middleNode(head)
    // 反转链表
    let right = reverse(slow);
    // 比较链表
    return equals(left,right)
};

总结

链表算法多又杂，既定工具来报道
简化创建/删除头节点，dumy节点来相助
双指针又来到，解决问题不能少
- 前后双指针-> 倒数第k个节点
- 快慢双指针 -> 找中点/判断环/找环入口
反转链表，三板斧，prev/cur/next
- 先存后续(next= cur.next)
- 在修改引用(cur.next = prev)
- 暂存当前节点(prev= cur)
- 后移指针(cur=next)
常用工具要记牢，遇到问题化繁为简，拼就完事

栈

JS版本的Stack

我们就自己实现一个比较功能完备的stack。它有如下的功能点

push(element(s)):添加一个（或几个）新元素到栈顶
pop():移除栈顶的元素，同时返回被移除的元素
peek(): 返回栈顶的元素，不对栈做任何修改
isEmpty():如果栈里没有任何元素就返回true,否则返回false
size(): 返回栈里的元素个数
clear(): 移除栈里所有的元素

class Stack {
 constructor() {
   this.items = []; 
 }
 // 添加element到栈顶
 push(element) {
   this.items.push(element);
 }
 // 移除栈顶的元素,同时返回被移除的元素
 pop() {
   return this.items.pop();
 }
 // 返回栈顶的元素，不对栈做任何修改
 peek() {
   return this.items[this.items.length - 1];
 }
 // 如果栈里没有任何元素就返回`true`,否则返回`false`
 isEmpty() {
   return this.items.length === 0;
 }
 // 返回栈里的元素个数
 size() {
   return this.items.length;
 } 
 // 移除栈里所有的元素
 clear() {
   this.items = [];
 } 
}

虽然，我们实现了一个功能完备的stack结构，但是仔细一看，其实就是对array中push/pop等api进行了一次包装。但是，经过包装后，使得针对stack结构的各种操作，变得更具有封装性，而不会产生很多样板代码。

后缀表达式

题目描述：

后缀表达式是一种算术表达式，也叫逆波兰式（RPN）,它的操作符在操作数的后面。要求输入一个用字符串数组表示的后缀表达式，请输出该后缀表达式的计算结果。示例：后缀表达式["2","1","3","*","+"]对应的表达式是2 + 1 * 3,因此输出的计算结果为5

分析

以["2","1","3","*","+"]为例子分析。
- 从左往右扫描数组，首先遇到的操作数2,由于后缀表达式的特点，操作符还在后面，在操作符未知的情况下，是无法进行计算处理。所以，需要将当前的操作数进行暂存处理。
- 继续扫描数组，接下来的两个数据都是操作数，（1/3）还是没有操作符的出现，继续将对应的操作数进行暂存处理
- 继续扫描，直到遇到操作符（*）。按照后缀表达式的规则，此操作符对应的操作数是刚刚被暂存的一对操作数1/3
- 存储操作数的容器，是根据数据存入的时间顺序而排序。1/3明显位于容器的尾部。也就是说，需要从容器的尾部将一对数据取出，并做运算处理。
- 根据数据存入和取出的特点，我们可以利用stack来作为存储操作数的容器
一对操作数在操作符的作用下，合并成一个值，而这个值可能还会和未被处理的操作数进行计算，所以需要将其存入容器中
在容器中仅存唯一的数值，并且操作符也全部被消费了，此时容器中的数据就是后缀表达式最终的结果

代码实现

function evalRPN(tokens){
  let stack = new Stack();
  for(let token of tokens){
    switch(token){
        // 处理操作符
        case "+":
        case "-":
        case "*":
        case "/": 
            // 在源数据中，靠后的操作数
            let back = stack.pop(); 
            // 在源数据中，靠前的操作数
            let prev = stack.pop();
            // 计算操作数，并将其入栈处理
            stack.push(
                calculate(prev,back,token)
                );
            break;
        default:
            // 处理操作数，直接入栈
            stack.push(parseInt(token));
      }
    }
    // 操作符都处理完，且栈中只有一个数据
    return stack.pop();
}

辅助函数，用于处理两个操作数之间的算术问题。(有一点需要注意，就是操作数之间的顺序问题)

fucntion calculate(prev,back,operator){
    switch(operator){
        case "+":
            return prev + back;
        case "-":
            return prev - back;
        case "*":
            return prev * back;
        case "/":
            return (prev/back)>>0; // 数据取整
        default:
            return 0;
    }
}

小行星碰撞

输入一个表示小行星的数组

数组中每个数字的绝对值表示小行星的大小

数字的正负表示小行星运动的方向，正号表示向右飞行，负号表现向左飞行。

如果两个小行星相撞，体积小的小行星会消失，体积大的不受影响

如果相撞的小行星大小相等，两个都会消失

飞行方向相同的小行星永远不会相撞示例：有6颗小行星[4,5,-6,4,8,-5],它们相撞之后最终剩下3颗小行星[-6,4,8]

分析

拿例子中的数据来分析，存在6颗小行星[4,5,-6,4,8,-5]
- 第一颗是向右飞行大小为4的行星，此时不知道是否会和后面行星碰撞，先将其保存到某个数据容器中。(因为它位于第一位置，所以不需要考虑前面)
- 第二颗还是向右飞行大小为5的行星，它与现存且已知的行星方向相同，所以与其不会碰撞。但是，不知道是否与后面的行星是否发生碰撞，所以也是先将其存入到数据容器中。
- 第三颗是向左飞行大小为6的行星。由于它与现存且已知的行星方向相反，一定会相撞，大小为5的行星离它近，因此两个行星率先相遇。
- 由前面分析我们得知，我们先后往数据容器中依次存入了4/5，而在遇到方向不同的行星时，是率先取最近一次加入到数据容器的数据。也就是说，针对数据容器中的数据的存取，满足后进先出的规则。我们可以考虑用栈来具象化该数据结构。
在①中我们规定，针对向右飞行的行星，是采取了直接存入到数据容器中(stack)
- 如果当前元素是向左飞行时，此时就会发生碰撞，且他们直接遵循大值原则即谁大谁能存活。
- 并且向左飞行的元素秉持着，不撞南墙不回头的态度，只要栈里面还有额外的数据，它就要和stack中的数据battle一下，哪怕身败名裂
- 只有存活下来的元素，才配进入栈中

代码实现

function asteroidCollision(asteroids){
  let stack = new Stack();
  for(let as of asteroids){
        // 当前元素向左飞行，并且该元素的绝对值比栈顶元素大
        while(!stack.empty() 
              && stack.peek()>0
              && stack.peek()<-as
              ){
                stack.pop();
              }
        
        // 当前元素向左飞行,当前元素和栈顶元素体积一样 (需要互相抵消)   
        if(stack.length 
           && as<0
           && stack.peek()==-as
           ){
            stack.pop();
        }else if(
                as >0  //当前元素向右飞行
                || stack.isEmpty() // 栈为空 （初始化）
                // 当前元素向左飞行(在经过对比后，还是无法消除) 
                || stack.peek()<0
                ){
                  stack.push(as)
                }
    }
    return stack;
}

判断括号的正确性

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。示例：输入：s = "()[]{}" 输出：true 输入：s = "(]" 输出：false

分析

当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合，但是，我们此时还用不到该左括号，所以，将其存入数据容器中
由于，题目中还需指定，必须以指定的顺序，此时，就需要考虑左括号的存入顺序了，后存入的先处理。即：后进先出的规则 ==> 那数据容器可以选为栈

代码实现

function isValid (s) {
    let stack = new Stack();
    // 遍历 字符串
    for(let c of s){
        // 遇到左括号，将与其匹配的右括号入栈处理
        if(c==='('){
            stack.push(')')
        }else if(c==='['){
            stack.push(']')
        }else if(c==='{'){
            stack.push('}')
        // 遇到右括号
        // 1. 判断栈内是否有括号，如果没有，那说明此时匹配不了
        // 2. 满足①的情况下，判断此时字符是否和栈顶元素匹配
        }else if(stack.isEmpty() || stack.pop()!==c){
            return false;
        }
    }
    // 最后再验证一下，栈是否为空，如果不为空，说明还有未匹配的括号
    return stack.isEmpty();
};

每日温度

输入一个数组，每个数字都是某天的温度。计算每天需要等几天才会出现更高的温度示例：输入数组[35,31,33,36,34],输出结果为[3,1,1,0,0]

第一天温度为35°，要等3天才会出现更高的温度36°

第四天的文档是36°，后面没有更高的温度，与其对应的输出是0

分析

每次从数组中读出某一天的温度，并且都将其与之前的温度（保存在数据容器中的温度）相比较。
从离它较近的温度开始比较，也就是后存入数据容器中的温度先拿出来比较，满足后进先出的原则 ---> 我们选Stack作为数据容器
题目中，需要计算出现更高温度的等待天数，存入栈中的数据应该是温度在数组中的下标。
- 等待的天数就是两个温度在数组中的下标之差。

代码实现

function dailyTemperatures(temperatures){
   // 定义一个与源数组相同的数组，用于存储最后结果
  let result = new Array(temperatures.length);
  let stack = new Stack();
  for(let i = 0;i<temperatures.length;i++){
    // stack 非空，且当前的温度大于栈顶温度
    while(!stack.empty()
          && temperatures[i]>temperatures[stack.peek()]){
          // 取出，存于stack中的满足条件的温度的下标
          let prev = stack.pop();
          // 计算等待天数 并将其存入result[prev]中
          result[prev] = i - prev;
    }
    // 将当前下标存入stack中
    stack.push(i)
  }
  return result;
}

额外提醒

只有在 stack 非空，且当前的温度大于栈顶温度，才会从stack中取出栈顶元素
在满足条件的时候，是已经存入到stack中的数据，找到了它对应的需要等待的天数i - prev

直方图最大面积

输入一个由非负数组成的数组，数组中的数字是直方图中柱子的高，求直方图中最大矩形的面积假设直方图中柱子的宽度为1 示例：输入数组[2,1,5,6,2,3],直方图中最大矩形的面积为10（2*5）

分析 - 双指针法

如果直方图中一个矩形从下标为i的柱子开始，到下标为j的柱子结束，那么两根柱子之间的矩形（含两端的柱子）的宽度是j-i+1，矩形的高度就是两根柱子之间的所有柱子最矮的高度
如果能逐一找出直方图中所有矩形并比较它们的面积，就能得到最大的矩形面积
定义两个指针i/j :i表示靠前的柱子下标，j表示靠后的柱子下标

代码实现 - 双指针法

function largestRectangleArea(heights){
  let maxArae = 0;
  for(let i=0;i<heights.length;i++){
    let min = heights[i];
    for(let j=i;j<heights.length;j++){
      min = Math.min(min,heights[j]);
      let area = min * (j -i +1);
      maxArea = Math.max(maxArea,area)
    }
  }
  return maxArea;
}

想到maxX是不是联想到选择排序 (最主要的特点就是找极值的序号(minIndex/largestIndex))

我们来简单的再重温一下，选择排序的大体思路。

function selectionSort(arr){
  let len = arr.length;
  if(len<2) return arr; // 处理边界值
  
  let i,j,minIndex;
  // 外层循环: 控制迭代轮次
  for(i=0;i<len-1;i++){
    minIndex = i;
    // 内层循环：从内层循环中找到最小值的位置
    for(j=i+1;j<len;j++){
      // 在未排区域寻找最小的数，并记录其位置j
      if(arr[j]<arr[minIndex]) minIndex = j;
    }
    // 内层循环完毕，最小值确定，和已排区间最后一位交互位置
    swap(arr,i,minIndex);
  }
  return arr;
}

这两个算法之间有很多相似的地方

双层循序
通过对极值的判断，对数据进行处理

由于采用了双层循环，所以该方法的时间复杂度为O(n²)，不够优雅。我们可以采用更加优雅的处理方式。

队列

JS版本的Queue

自己实现一个比较功能完备的queue。它有如下的功能点

enqueue(element(s))：向队列尾部添加一个（或多个）新的项。
dequeue()：移除队列的第一项（即排在队列最前面的项）并返回被移除的元素。
peek()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与 Stack 类的 peek 方法非常类似）。
isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false。
size()：返回队列包含的元素个数，与数组的 length 属性类似。

数组版本

class Queue {
   constructor() {
     this.items = []; 
   }
   // 入队
   enqueue(element) {
     this.items.push(element);
  } 
  // 出队，并返回队首元素
  dequeue() {
    return this.items.shift();
  } 
  // 查看，队首元素
  peek() {
    return this.items[0]
  } 
  // 如果队列里没有任何元素就返回`true`,否则返回`false`
  isEmpty() {
   return this.items.length === 0;
  }
  // 返回队列的元素个数
  size() {
   return this.items.length;
  }
  // 移除队列里所有的元素
  clear() {
   this.items = [];
  }
}

滑动窗口

在数组中某一个长度的子数组可以看成数组的一个窗口。若给定数组[1,2,3,4,5,6],那么子数组[2,3,4]就是其中一个大小为3的窗口。窗口向右滑动一个数字，那么窗口就包含数字[3,4,5]。

也就是向右滑动窗口，每向右滑动一个数字，都在窗口的最右边插入一个数字，同时把最左边的数字删除。即满足队列 先进先出的特性。

滑动窗口的平均值

题目描述：

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。

该类型的构造函数的参数确定滑动窗口的大小

每次调用next函数，会在滑动窗口中添加一个整数，并返回滑动窗口的所有数字的平均值

分析

在窗口中添加数字，当窗口中的数字的数目超过限制时，还可以从窗口中删除数字。
- 例如，当窗口的大小为3,在添加第四个数字时，就需要从窗口中删除最早添加进来的数字。
- 这是一种先进先出的顺序，对应的数据容器为队列
每次在窗口中添加数字之后，需要判断是否超出窗口的大小限制。如果超出限制，从队列中删除一个数字
利用sum实时记录，窗口中现存数据的和

代码实现

class MovingAverage {
    constructor(size) {
      this.nums = new Queue();
      this.capacity = size;
      this.sum = 0;
    }

    next(val) {
      this.nums.enqueue(val);
      this.sum+=val;
      if(this.nums.size()>this.capacity){
        this.sum -=this.nums.dequeue();
      }
      return this.sum / this.nums.size()
    }
}

二叉树的广度优先搜索（BFS）

二叉树的广度优先搜索是从上到下按层遍历二叉树，从二叉树的根节点开始，先遍历二叉树的第一层，再遍历第二层，以此类推。

通常基于队列来实现二叉树的广度优先搜索。

从二叉树的根节点开始，先把根节点放入到一个队列中，然后每次从队列中取出一个节点遍历。
如果该节点有左右子节点，则分别将它们添加到队列中。（先左后右）
以此类推，直到所有节点都被遍历

二叉树节点

  class TreeNode {
      val: number
      left: TreeNode | null
      right: TreeNode | null
      constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
          this.val = (val===undefined ? 0 : val)
          this.left = (left===undefined ? null : left)
          this.right = (right===undefined ? null : right)
      }
  }

利用queue实现二叉树广度优先遍历

function bfs(root){
  let queue = new Queue();
  if(root!=null) {
    queue.enqueue(root);
  }
  
  let result = [];
  while(!queue.isEmpty()){
    let node = queue.dequeue();
    result.push(node.val)
    
    if(node.left!=null){
      queue.enqueue(node.left);
    }
    
    if(node.right!=null){
      queue.enqueue(node.right);
    }
  }
  return result;
}

由于queue的先进先出特性，二叉树的某一层节点按照从左到右的顺序插入队列中。因此，这些节点一定会按照从左到右的顺序遍历到。用广度优先(BFS)的顺序遍历二叉树，很容易知道

每层最左边或者最右边的节点
每层的最大值或者最小值

也就是说，关于二叉树的题目如果出现层的概念，尝试用广度优先来解决问题。

二叉树中每层的最大值

题目描述：

输入一课二叉树，请找出二叉树中每层的最大值。示例：输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9] ![](files.mdnice.com/user/24720/… =40%x)

用两个队列实现二叉树的广度优先搜索

分析

将不同层树的节点，存入不同的队列中。
- queue1只放当前遍历层的节点
- queue2只放下一层的节点
最开始时，把二叉树的根节点放入队列queue1中。
- 接下来，每次从队列中取出一个节点遍历
- 队列queue1用来存放当前遍历层的节点，总是从队列queue1中取出节点来遍历
- 如果当前遍历的节点有子节点，并且子节点位于下一层，则把子节点放入队列queue2
当队列queue1被清空时，此时能够获取到当前层的最大值
在开始遍历下一层之前，
- 把队列queue1指向queue2
- 将队列queue2重新初始化为空队列

代码实现

function largestValues(root) {
  
  let q1 = new Queue();
  let q2 = new Queue();
  let result = [];
  if(root!=null){
    q1.enqueue(root);
  }
  let max = Number.MIN_SAFE_INTEGER;
  while(!q1.isEmpty()){
    let node = q1.dequeue();
    max = Math.max(max,node.val);
    
    if(node.left!=null){
      q2.enqueue(node.left);
    }
    
    if(node.right !=null){
      q2.enqueue(node.right);
    }
    
    if(q1.isEmpty()){
      result.push(max);
      max = Number.MIN_SAFE_INTEGER;
      q1 = q2;
      q2 = new Queue();
    }
  }
  return result;
}

二叉树最底层最左边的值

题目描述：

输入一课二叉树，找出它最底层最左边节点的值。示例：输入: root = [1,2,3,4,null,5,6,null,null,7] 输出: 7 ![](files.mdnice.com/user/24720/… =60%x)

分析

题目越短，越需要咬文嚼字。
- 二叉树
- 最底层
根据①所得，我们可以使用二叉树的广度优先遍历(BFS)来进行层级的处理。
最底层最左边的节点就是最后一层的第一个节点
可以使用一个bottomLeft来保存每层最左边的节点的值。每当新的层级出现时候，将bottomLeft的值变更为第一个节点的值。
需要区分不同的层，我们采用两个队列的方式来实现

代码实现

function findBottomLeftValue(root){
  let q1 = new Queue();
  let q2 = new Queue();
  
  q1.enqueue(root);
  let bottomLeft = root.val;
  
  while(!q1.isEmpty()){
    let node = q1.dequeue();
    if(node.left !=null){
      q2.enqueue(node.left)
    }
    
    if(node.right !=null){
      q2.enqueue(node.right)
    }
    
    if(q1.isEmpty()){
      q1 = q2;
      q2 = new Queue();
      // 当q1为空时，开始遍历下一层，如果下一层还有节点，则更新bottomLeft
      if(!q1.isEmpty()){
        bottomLeft = q1.peek().val;
      }
    }
  }
  return bottomLeft
}

二叉树的右侧视图

题目描述：

输入一课二叉树，站在该二叉树的右侧，从上到下看到的节点构成二叉树的右侧视图。示例：输入: root = [1,2,3,null,5,null,4] 输出: [1,3,4]

分析

题目越怪，越需要向已知套路靠
根据右侧视图的概念和示例的结果分析，其实它就是想要每层最右边的一个节点，因此二叉树的右侧视图其实就是从上到下每层最右边的节点
有几个关键节点
- 二叉树
- 区分不同的层
- 最右边的节点
直接二叉树bfs安排上

代码实现

function rightSideView(root){
  let result = [];
  if(root==null) return result;
  
  let q1 = new Queue();
  let q2 = new Queue();
  q1.enqueue(root);
  while(!q1.isEmpty()){
    let node = q1.dequeue();
    if(node.left!=null){
      q2.enqueue(node.left)
    }
    
    if(node.right !=null){
      q2.enqueue(node.right)
    }
    
    if(q1.isEmpty()){
      result.push(node.val); //此时node是当前层的最后一个节点
      q1= q2;
      q2 = new Queue();
    }
  }
  return result;
}

回溯法

回溯法可以看做暴力法的升级版,它在解决问题时的每一步都尝试所有可能的选项，最终找出所有可行的解决方案。

回溯法非常适合解决由多个步骤组成的问题，并且每个步骤都有多个选项。

用回溯法解决问题的过程可以形象的用一个树形结构表示，求解问题的每个步骤可以看作树中的一个节点。如果在某一步有n个可能的选项，那每个选项是树中的一条边，经过这些边就可以到达该节点的n个子节点。

在采用回溯法解决问题时，

如果到达树形结构的叶节点，就找到了问题的一个解。
如果希望找到更多的解，可以回溯到当前节点的父节点，再尝试父节点其他的选项
如果父节点所有可能的选项都已经试过，那么再回溯到父节点的父节点，继续尝试其他选项，这样逐层回溯到树的根节点。

因此，采用回溯法解决问题的过程实质上是在树形结构中从根节点开始进行深度优先遍历

通常，回溯法的深度优先遍历用递归代码实现。

如果在前往某个节点时对问题的解的状态进行了修改，那么在回溯到它的父节点时，要清除相应的修改。

集合的组合、排列

从一个包含m个元素的集合中挑选出n个元素（0≤n≤m）形成一个{子集|Subset}。一个子集又称为一个组合。如果两个子集（组合）的元素完全相同只是顺序不同，那么它们可以看作同一个子集（组合）。

从一个包含m个元素的集合中挑选出n个元素（0≤n≤m）并按照某种顺序形成一个排列。 m等于n的排列有称为全排列。如果两个排列的元素完全相同只是顺序不同，那么它们就是两个不同的排列。 排列与元素的顺序相关。

所有子集

题目描述：

输入一个不含重复数字的数据集合，请找出它的所有子集输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

分析

子集就是从一个集合中选出若干元素。
- 如果集合中包含n个元素，那么生成子集可以分为n步
每一步从集合中取出一个数字，此时面临两个选择
1. 将该数字添加到子集中
2. 不将该数字添加到子集中
生成一个子集可以分成若干步，并且每一步都面临若干选择 -- 回溯法

代码实现

function subsets(nums){
  let result = [];
  if(nums.length == 0) return result;
  
  (function helper(nums,index,subset,result){
    if(index === nums.length){ // 基线条件
      result.push([...subset])
    }else if(index < nums.length){
      helper(nums,index + 1, subset,result); // 不将数字添加到子集
      
      subset.push(nums[index]); // 将数字添加到子集中
      helper(nums,index + 1,subset,result);
      subset.pop();
    }
  })(nums,0,[],result)
  return result;
}

代码解释

递归函数helper有四个参数
1. nums 是数组nums,包含输入集合的所有数字。可以逐一从集合中取出一个数字并选择是否将数字添加到子集中。
2. index是当前取出的数字在数组nums中下标
3. subset是当前子集
4. result是所有已经生成的子集
每当从数组nums中取出一个下标为index的数字时，都要考虑是否将该数字添加到子集subset中。
1. 不将数字添加到子集的情形。不对子集进行任何操作，只需要调用递归函数helper处理数组nums中的下一个数字(下标增加1)
- helper(nums,index + 1,subset,result)
1. 将下标为index的数字添加到子集subset中。
- 在将该数字添加到子集之后
- subset.push(nums[index])
- 接下来调用递归函数处理数组nums下一个数字(下标增加1)
- helper(nums,index + 1, subset, result)
- 等递归函数执行完成之后，函数helper也执行完成，接下来将回溯到前一个数字的函数调用处继续执行。
- 在回溯到父节点之前，应该清除已经对子集状态进行的修改。
- subset.pop()
当index等于数组nums的长度时候，表示数组中的所有数字都已经处理过，因此可以生成一个子集。将子集subset添加到result中
- 在此处加入的是subset的副本，因为接下来还需要修改subset用以获得其他的子集
- result.push([...subset])

包含k个元素的组合

题目描述：

输入n和k，请输入从1到n中选取k个数字组成的所有组合。输入：n = 3, k = 2 输出：[[1,2],[1,3],[2,3]]

分析

集合的组合也是一个子集，求集合的组合的过程和求子集的过程是一样的。
此题增加了一个限制条件，只找包含k个数字的组合
在上一个题目所有子集增加一些限定条件，就可以处理该题。

代码实现

function combine(n,k){
 let result = [];
 (function helper(n,k,index,subset,result){
   if(subset.length === k){ // 基线条件
     result.push([...subset])
   }else if(index <= n){
     helper(n,k, index + 1, subset,result); // 不将数字添加到子集
     
     subset.push(index); // 将数字添加到子集中
     helper(n,k,index + 1,subset,result); 
     subset.pop();
   }
 })(n,k,1,[],result)
 return result;
}

代码解释

递归函数helper有五个参数
1. n 是数组范围1~n
2. k是组合的长度
3. index是当前取出的数字
4. subset是当前子集
5. result是所有已经生成的子集
当subset.length等于k时，进行子集的收集处理
- result.push([...subset])
还有一点 index是从1开始的。

允许重复选择元素的组合

题目描述：

给定一个没有重复数字的正整数集合，请找出所有元素之和等于某个给定值(target)的所有组合。同一个数字可以在组合中重复任意次。输入：candidates = [2,3,6,7], target = 7 输出：[[7],[2,2,3]]

分析

关于组合的相关题目，使用回溯法解决
用回溯法解决的问题都能够分成若干步来解决，每一步都面临着若干选择
对于从集合中选取数字组成组合的问题而言，集合中有多少个数字，解决这个问题就需要多少步。
每一步从集合中取出一个下标为i的数字,此时，面临两个选择。
1. 什么都不做 --选择跳过这个数字不将该数字添加到组合中，接下来处理下标为i + 1的数字。
2. 将数字添加到组合中 -- 由于一个数字可以重复在组合中重复出现，也就是下一步可能再次选择同一个数字，因此下一步仍然处理下标为i的数字。

代码实现

function combinationSum(nums,target){
  let result = [];
  (function helper(nums,target,index,subset,result){
    if(target ==0){ //基线条件
      result.push([...subset])
    }else if(target > 0 && index < nums.length){
      helper(nums,target,index + 1,subset,result); // 不将数字添加到子集
      
      subset.push(nums[index]); // 将数字添加到子集中
      helper(nums,target - nums[index],index,subset,result);
      subset.pop();
    }
  })(nums,target,0,[],result)
  return result;
}

代码解释

由于nums[index]可能在组合中重复出现，因此在index处，选择了将数字添加到组合的选择，递归调用helper时，index是不需要+1的。
每当选择了一个数据后，需要更新target
- target - nums[index]
当某次遍历的时候，target为0时，说明现在子集已经满足情况。
- result.push([...subset])
由于题干中，数据都是正整数，在操作过程中，target只能少，不能多，所以可以判断target与0的关系，来进行剪枝处理。
- if(target>0 && index < nums.length)

举一反三

上面的几个题目都是关于数学上的组合、集合，其实这些模型可以应用到很多其他问题中。

例如，当客人走近餐厅准备吃饭，一种点菜的方法就是生成一个符合条件的组合。

如果每道菜只点一份，那么就是找出所有符合条件的组合
如果总共只能点k道菜，那么就是找出包含k个元素的所有符合条件的组合
如果每道菜可以点任意多份，那么就是找出允许选择重复元素的符合条件的组合

包含重复元素集合的组合

题目描述：

给定一个可能包含重复数字的整数集合，请找出所有元素之和等于某个给定值（target）的所有组合。输出中不得包含重复的组合。输入：candidates = [2,5,2,1,2], target = 5 输出：[[1,2,2],[5]]

分析

如果输入的集合中有重复的数字，不经过特殊处理将产生重复的组合。
避免重复的组合的方法是当在某一步决定跳过某个值为m的数字时，跳过所有值为m的数字。
为了方便跳过后面所有值相同的数字，可以将集合中的所有数字排序，把相同的数字放在一起，这样方便比较数字。
- 当决定跳过某个值时，可以按顺序扫描后面的数字，直到找到不同的值为止。

代码实现

function combinationSum(nums,target){
  nums.sort((a,b) => a -b);
  
  let result = [];
  (function helper(nums,target,index,subset,result){
    if(target == 0){ // 基线条件
      result.push([...subset]);
    }else if(target > 0 && index < nums.length){
      // 选择跳过某批值相同的数字
      helper(nums,target,getNext(nums,index),subset,result); 
      
      subset.push(nums[index]);
      helper(nums,target - nums[index], index + 1,subset,result);
      subset.pop();
    }
  })(nums,target,0,[],result)
  return result;
}

辅助函数

function getNext(nums,index){
  let next = index;
  while(next < nums.length && nums[next] == nums[index]){
    next++;
  }
  return next;
}

代码解释

排序是为了方便跳过相同的数字。
- 这个处理方式和在数组中处理三数之和的道理是一样的
利用getNext找到与当前index值不同的下标

没有重复元素集合的全排列

题目描述：

给定一个没有重复数字的集合，请找出它的所有全排列。输入：nums = [0,1] 输出：[[0,1],[1,0]]

分析

排列和组合(子集)不同，排列与元素的顺序相关，交互数字能够得到不同的排列。
生成全排列的过程，就是交换输入集合中元素的顺序以得到不同的排列。
如果输入的集合有n个元素，
- 那么生成一个全排列需要n步
- 当生成排列的第一个数字时，面临着n个选项
- 当生成排列的第二个数字时，面临着n-1个选项
解决问题可以分成n步，每一步面临着若干选项 -- 回溯法

代码实现

function permute(nums){
  let result = [];
  (function helper(nums,index,result){
    if(index == nums.length){
      result.push([...nums]) // 基线条件
    }else {
      for(let j = index;j<nums.length;j++){
        swap(nums,index,j); // 数字替换位置
        helper(nums,index + 1,result);
        swap(nums,index,j); // 清除对排列状态的修改
      }
    }
  })(nums,0,result)
  return result;
}

辅助函数

const swap = (nums,i,j) => [nums[i],nums[j]] = [nums[j],nums[i]];

代码解释

在函数执行过程总数组nums保存着当前排列的状态
当函数helper生成排列的下标为index的数字时，
- 下标从0到index-1的数字都已经选定，
- 但数组nums中下标从index到n-1的数字(假设数组的长度为n)都有可能放到排列的下标为index的位置
- 因此函数helper中有一个for循环逐一用下标为index的数字交互它后面的数字。
- for循环包含下标为index的数字本身，因为它自己也能放在排列下标为index的位置
- swap(nums,index,j)
交互之后接着调用递归函数生成排列中下标为index + 1的数字
- helper(nums,index + 1, result)
在函数退出之前需要清除对排列状态的修改
- swap(nums,index,j)

包含重复元素集合的全排列

题目描述：

给定一个包含重复数据的集合，请找出它的所有全排列输入：nums = [1,1,2] 输出：[[1,1,2],[1,2,1],[2,1,1]]

分析

如果集合中有重复的数字，那么交换集合中重复的数字得到的全排列是同一个全排列
当处理到全排列的第i个数字时，如果已经将某个值为m的数字交换为排列的第i个数字，那么再遇到其他值为m的数字就跳过

代码实现

function permuteUnique(nums){
  let result = [];
  (function helper(nums,index,result){
    if(index === nums.length){
      result.push([...nums]); // 基线条件
    }else {
      let map = {};
      for(let j = index;j<nums.length;j++){
        if(!map[nums[j]]){
          map[nums[j]] = true;
          
          swap(nums,index,j);
          helper(nums,index + 1,result);
          swap(nums,index,j);
        }
      }
    }
  })(nums,0,result)
  return result;
}

辅助函数

const swap = (nums,i,j) => [nums[i],nums[j]] = [nums[j],nums[i]];

代码解释

用一个对象map，来保存已经交换到排列下标为index的位置的所有值。
只有当一个数值之前没有被交换到第index位时才做交换，否则直接跳过
- 在for循环中多一层判断
- if(!map[nums[j]])

解决其他问题

除了可以解决与集合排列、组合相关的问题，回溯法还能解决很多问题。

如果解决一个问题需要若干步骤，并且每一步都面临若干选择，当在某一步做了某个选择之后，前往下一步仍然面临若干选项。那么可以考虑用回溯法

通常，回溯法可以用递归代码实现。

生成匹配的括号

题目描述：

输入一个正整数n,请输出所有包含n个左括号和n个右括号的组合，要求每个组合的左括号和右括号匹配。输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

分析

输入n，生成的括号组合包含n个左括号和n个右括号。
- 因此，生成这样的组合需要2n步，每一步生成一个括号
- 每一步都面临着两个选项，既可能生成左括号也可能生成右括号
- 回溯法解决
生成括号组合时，需要注意每一步都需要满足两个限制条件
1. 左括号或右括号的数目不能超过n个
2. 括号匹配原则：即在任意步骤中已经生成的右括号的数目不能超过左括号的数目

代码实现

function generateParenthesis(n){
  let result = [];
  (function helper(left,right,subset,result){
    if(left == 0 && right ==0){
      result.push(subset); //基线条件
      return ;
    }
    // 已经生成的左括号的数目少于`n`个
    if(left > 0){ 
      helper(left -1,right,subset + "(",result)
    }
    // 已经生成的右括号的数目少于已经生成的左括号的数目
    if(left < right){ 
      helper(left,right -1,subset + ")",restule)
    }
  })(n,n,"",result)
  return result;
}

代码解释

参数left:表示还需要生成的左括号的数目
参数right：表示还需要生成右括号的数目。
每生成一个左括号，参数left-1;每生成一个右括号，参数right -1;当left/right都等于0，一个完整的括号组合生成
- result.push(subset);
在生成一个括号时
- 只要已经生成的左括号的数目少于n个(left>0)就能生成一个左括号
- 只要已经生成的右括号的数目少于已经生成的左括号的数目（left < right）就能生成一个右括号

分割回文字符串

题目描述：

输入一个字符串，要求将它分割成若干子字符串，使每个字符串都是回文。输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]

分析

当处理到字符串中的某个字符串时候，如果包括该字符在内后面还有n个字符，那么面临n个选项
- 分割出长度为1的字符串（只包含该字符）
- 分割出长度为2的字符串（包含该字符及它后面的一个字符）
- 分割出长度为x的字符串 (x<n)
- 分割出长度为n的字符串
解决这个问题需要很多步，每一步分割出一个回文字符串。

代码实现

function partition(str){
  let result = [];
  (function heler(str,start,subset,result){
    if(start == str.length){
      result.push([...subset]); // 基线条件
    }else {
      for(let i = start;i<str.length;i++){
        if(isPalinadrome(str,start,i)){
          subset.push(str.substring(start,i+1));
          helper(str,i + 1,subset,result);
          subset.pop();
        }
      }
    }
  })(str,0,[],result)
  return result;
}

辅助函数

function isPalinadrome(str,start,end){
  while(start < end){
    if(str[start++]!=str[end--]) return false;
  }
  return true
}

代码解释

当处理到下标为start的字符串时，用一个for循环逐一判断从下标start开始到i结束的每个子字符串是否会回文
- i从下标start开始，到字符串s的最后一个字符结束
如果是回文，就分割出一个符合条件的子字符串，添加到subset中
- subset.push(str.substring(start,i+1)) （substring它的第一个参数表示子字符串的开始位置，第二个位置表示结束位置--返回结果不含该位置）
- 接着处理下标从i+1开始的剩余字符串。

小结

如果解决一个问题需要若干步骤，并且在每一步都面临着若干选项，那么可以尝试用回溯法解决问题。

应用回溯法能够解决集合的排列、组合的很多问题。

回溯法都可以使用递归的代码实现。递归代码需要先确定递归退出的边界条件(基线条件)，然后逐个处理集合中的元素。

对于组合类问题，每个数字都面临两个选项

添加当前数字到组合中
不添加当前数字到组合中

对于排列类问题，一个数字如果后面有n个数字，那么面临n+1个选择，即可以将数字和后面的数字(包括它自身)交换。

动态规划

运用动态规划解决问题的第一步是识别哪些问题适合运用动态规划。和运用回溯法的问题类似，使用动态规划的问题都存在若干步骤，并且每个步骤都面临若干选择。

如果要求列举出所有的解决，那选择用回溯法解决
如果求一个问题的最优解(最大值或者最小值)，或者求问题的数目，那选择动态规划

在采用动态规划时，总是用递归的思路分析问题，即把大问题分成小问题，再把小问题的解合起来形成大问题的解。

找出描述大问题的解和小问题的解之间递归关系的状态转移方程是采用动态规划解决问题的关键所在。

如果将大问题分解成若干小问题之后，小问题相互重叠，那么直接用递归的代码实现就会存在大量重复计算。小问题之间存在重叠的部分，这是可以运用动态规划求解问题的另一个显著特点。

在用代码实现动态规划时，有两种方式

采用递归的代码按照从上往下的顺序求解，那么每求出一个小问题的解就缓存下来，这样下次再遇到相同的小问题就不用重复计算。

按照从下往上的顺序，从解决最小的问题开始，并把已经解决的小问题的解存储下来（大部分都是存储在一维数组或者二维数组中），然后把小问题的解组合起来逐步解决大问题。

爬楼梯的最小成本

题目描述：

一个数组cost的所有数字都是正数，它的第i个数字表示在一个楼梯的第i级台阶往上爬的成本，在支付了成本cost[i]之后可以从i级台阶往上爬1级或2级。假设台阶至少有2级，既可以从第0级台阶出发，也可以从第1级台阶出发。请计算爬上该楼梯的最少成本。输入：cost = [10, 15, 20] 输出：15 --> 最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

分析

爬上一个有多级台阶的楼梯需要若干步，每一步有两个选择，
- 既可以往上爬1级台阶，
- 也可以爬2级台阶
计算爬上楼梯最少成本，而不是所有的解 -- 抛弃回溯法，选择动态规划

确定状态转移方程

用f(i)表示从楼梯的第i级台阶再往上爬的最少成本。如果一个楼梯有n级台阶(台阶从0开始计数，从第0级一直到第n-1级)，由于一次可以爬1级或2级台阶，因此可以从第n-2级台阶或第n-1级台阶爬到楼梯的顶部，即f(n-1)和f(n-2)的最小值就是这个问题的最优解。

应用动态规划的第1步是找出动态转移方程，即用一个等式表示其中某一步的最优解和前面若干步的最优解的关系。(反向推理)

根据题目要求，可以一次爬1级或2级台阶，

既可以从第i-1级台阶爬上第i级台阶，
也可以从第i-2级台阶爬上第i级台阶。

因此，从第i级台阶往上爬的最少成本应该是从第i-1级台阶往上爬的最少成本和从第i-2级台阶往上爬的最少成本的较小值再加上爬第i级台阶的成本。

用状态转移方程表示为f(i) = Math.min(f(i-1),f(i-2)) + cost[i]

上面的状态转移方程有一个隐含条件，即i大于或等于2。

如果i等于0,可以直接从第0级台阶往上爬 -> f(0) = cost[0]
如果i等于1，可以直接从第1级台阶往上爬 -> f(1) = cost[1]

代码实现

递归代码

状态转移方程其实是一个递归的表达式，可以很方便的将它转换成递归代码。

function minCost(cost){
  let len = cost.length;
  return Math.min(helper(cost,len -2),helper(cost,len -1));
}

辅助函数

function helper(cost,i){
  if(i<2){ // 基线条件
    return cost[i]
  }
  return Math.min(helper(cost,i-2),helper(cost,i-1)) + cost[i];
}

代码解释

递归函数helper和状态转移方程相对应
求解f(i)这个问题的解，依赖于求解f(i-1)和f(i-2)这两个子问题的解，由于求解f(i-1)和f(i-2)这两个子问题有重叠的部分。如果只是简单的将状态转移方程转换成递归的代码就会带来严重的效率问题。

使用缓存的递归代码

为了避免重复计算，一个常用的解决办法就是将已经求解过的问题的结果保存下来。

在每次求解一个问题之前，应先检查该问题的求解结果是否已经存在。如果问题的求解过程已经存在，则不需要重复计算，只需要从缓存中读取之前的求解结果即可。

function minCost(cost){
  let len = cost.length;
  if(len<=2){
    return Math.min(cost[0],cost[1])
  }
  //初始化都为 0 计算之后应该是大于 0 的结果
  let dp = new Array(len).fill(0); 
  //从最上层的台阶往下走 从上到下进入递归
  helper(cost,len -1,dp);
  return Math.min(dp[len-2],dp[len-1]);
}

辅助函数

function helper(cost,i,dp){
  if(i<2){ //基线条件
    dp[i] = cost[i]
  }else if(dp[i]==0){
    helper(cost,i-2,dp);
    helper(cost,i-1,dp);
    dp[i] = Math.min(dp[i-2],dp[i-1]) + cost[i]
  }
  
}

代码解释

数组dp用来保存求解每个问题结果的缓存
- dp[i]用来保存f(i)的计算结果
- 该数组的每个元素都初始化为0 -> new Array(len).fill(0)
由于从每级台阶往上爬的成本都是正数，如果某个问题f(i)之前已经求解过，那么dp[i]的缓存的结果将是一个大于0的数值。
- 只有当dp[i]等于0时，它对应的f(i)之前还没有被求解过
有了缓存dp，就能确保每个问题f(i)只需要求解一次。
在辅助函数中，针对i<2的情况，是直接返回dp[i] = cost[i],但是，没有处理比较特殊的情况
- 当cost.length ≤2时，需要做一次特殊处理。
- 直接返回它们的最小值即可 Maht.min(cost[0],cost[1])

空间复杂度为O(n)的迭代代码

也可以自下而上的解决这个过程，也就是从子问题入手，根据两个子问题f(i-1)和f(i-2)的解求出f(i)的结果。

通常用迭代的代码实现自下而上的求解过程。

function minCost(cost){
  let len = cost.length;
  let dp = new Array(len).fill(0);
  dp[0] = cost[0];
  dp[1] = cost[1];
  
  for(let i =2;i<len;i++){
    dp[i] = Math.min(dp[i-2],dp[i-1]) + cost[i]
  }
  return Math.min(dp[len-2],dp[len-1])
}

代码解释

先求得f(0)和f(1)的结果并保存到数组dp的前两个位置
- dp[0] = cost[0];
- dp[1] = cost[1];
用一个for循环根据状态转移方程逐一求解f(2)到f(n-1)
时间复杂度和空间复杂度都是O(n)

空间复杂度为O(1)的迭代代码

用一个长度为n的数组将所有f(i)的结果都保存下来。但是，在求解f(i)时只需要f(i-1)和f(i-2)的结果。从f(0)到f(i-3)的结果其实在求解f(i)并没有任何作用。

也就是说，在求每个f(i)的时候，需要保存之前的f(i-1)和f(i-2)的结果，因此只需要一个长度为2的数组即可

function minCost(cost){
  let len = cost.length;
  let dp = [cost[0],cost[1]];
  
  fort(let i =2;i<len;i++){
    dp[i&1] = Math.min(dp[0],dp[1])+cost[i]
  }
  return Math.min(dp[0],dp[1]);
}

代码解释

dp的长度是2，求解的f(i)的结果保存在数组下标为i&1的位置。
可以根据f(i-1)和f(i-2)的结果计算出f(i)的结果，并将f(i)的结果写入之前保存f(i-2)的位置。
- 用f(i)的结果覆盖f(i-2)的结果并不会带来任何问题
- 因为，接下来求解f(i+1)只需要f(i)的结果和f(i-1)的结果
- 不需要f(i-2)的结果

比较4种解法

第一种解法在找出状态转移方程之后直接将其准换成递归代码，由于计算过程中存在大量的重复计算，时间复杂度很大
第二种解法在第一种解法的基础上添加了一个一位数组，用来缓存已经求解的结果。
- 有了这个长度O(n)的数据，缓存之后就能够确保每个子问题值需要计算一次
- 时间复杂度为O(n)
第三种解法时间复杂度和空间复杂度都是O(n)。和第二种解法有两方面的不同
1. 求解顺序不同：第二种解法从大的子问题出发，采用自上而下的顺序求解；而第三种解法从子问题出发，采用自下而上的顺序求解。
2. 代码实现思路不同：第二种采用递归方式实现；而第三种采用迭代方式实现。
第四种解法在第三种解法的基础上进一步优化空间效率，使空间下来变成O(1)。

单序列问题

解决单序列问题，需要若干步骤，并且每个步骤都面临若干选择，需要计算解的数目或最优解。

这类题目的输入通常是一个序列，如一个一维数组或字符串。

应用动态规划解决单序列问题的关键是每一步在序列中{增加}一个元素，根据题目的特点找出该元素对应的最优解（或解的数目）和前面若干元素（通常是一个或两个）的最优解（或解的数目）的关系，并以此找出相应的状态转移方程。

一旦找出了状态转移方程，只要注意避免不必要的重复计算，就能解决问题。

房屋偷盗

题目描述：

输入一个数组表示某条街道上的一排房屋内的财产的数量。如果这条街道上相邻的两栋房屋被盗就会自动触发报警系统。请计算小偷在这条街道上最多能偷取到多少财产输入：nums = [1,2,3,1] 输出：4 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

分析

应用动态规划解决问题的关键就是在于找出转移方程。
用动态规划解决单序列的问题的关键在于找到序列中一个元素对应的解和前面若干元素对应的解的关系，并用状态转移方程表示。
假设街道上有n幢房屋（分别用0~n-1标号），小偷从标号为0的房屋开始偷东西。
- 用f(i)表示小偷从标号为0的房屋开始标号为i的房屋为止最多能偷取到的财物最大值
- f(n-1)的值是小偷从n幢房屋中能偷取的最多财物的数量。
小偷在标号为i的房屋前有两个选择
1. 选择进去偷东西 - 由于有报警系统，因此他不能进入相邻的标号为i-1的房屋内，之前他最多能偷取的财物的最大值是f(i-2),因此，如果进入标号为i的房屋并进行偷盗，他最多能偷的f(i-2)+nums[i]
2. 不进入标号为i的房屋 - 那么他可以进入标号为i-1的房屋，因为此时他最多能偷取的财物数量为f(i-1)
在到达标号为i的房屋时，他能偷取的财物的最大值就是两个选项的最大值
- f(i) = max(f(i-2)+nums[i],f(i-1))
状态转移方程还有一个隐含条件，即i大于或等于2
- 当i等于0时，f(0) = nums[0]
- 当i等于1时，f(1)= max(nums[0],nums[1])

带缓存的递归代码

状态转移方程是一个递归的表达式。可以创建一个数组dp,它的第i个元素dp[i]用来保存f(i)的结果。

如果f(i)之前已经计算出结果，那么只需要从数组dp中读取dp[i]的值，不用在重复计算。

function rot(nums){
  if(nums.length==0) return 0;
  
  let dp = new Array(nums.length).fill(-1);
  (function helper(nums,i,dp){
    if(i ==0){
      dp[i] = nums[0]
    }else if(i ==1){
      dp[i] = Math.max(nums[0],nums[1])
    }else if(dp[i]<0){
      helper(nums,i -2,dp);
      helper(nums,i -1,dp);
      dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])
    }
  })(nums,nums.length-1,dp);
  return dp[nums.length-1]
}

代码解释

函数helper就是将状态转移方程f(i)= max(f(i-2)+nums[i],f(i-1))翻译成js的代码。
状态转移方程要求i大于或等于2，因此函数helper单独处理了i分别等于0和1的特殊情况

空间复杂度为O(n)的迭代代码

递归代码是采用自上而下的处理方式，我们也可以选择使用自下而上的迭代代码。

先求出f(0)和f(1)的值，

然后用f(0)和f(1)的值求出f(2)
用f(1)和f(2)的值求出f(3)
依次类推，直至求出f(n-1)

function rob(nums){
  if(nums.length==0) return 0;
  
  let dp = new Array(nums.length).fill(0);
  dp[0] = nums[0];
  if(nums.length>1){
    dp[1] = Math.max(nums[0],nums[1])
  }
  
  for(let i=2;i<nums.length;i++){
    dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])
  }
  return dp[nums.length-1]
}

空间复杂度为O(1)的迭代代码

在空间复杂度为O(n)的迭代代码中发现，计算dp[i]时，只需要用到dp[i-1]和dp[i-2]两个值，也就是说，只需要缓存两个值就足够了，并不需要一个长度为n的数组。

function rob(nums){
  if(nums.length==0) return 0;
  let dp = new Array(2).fill(0);
  dp[0] = nums[0];
  
  if(nums.length>1){
    dp[1] = Math.max(nums[0],nums[1])
  }
  
  for(let i=2;i<nums.length;i++){
    dp[i&1] = Math.max(dp[(i-1)&1],dp[(i-2)&1]+nums[i])
  }
  return dp[(nums.length-1)&1]
}

代码解释

数组dp的长度为2，将f(i)的计算结果保存在数组下标为dp[i&1]的位置
- f(i)和f(i-2)将保存到数组的同一个位置
根据f(i-1)和f(i-2)的结果计算出f(i),然后用f(i)的结果写入数组原来保存f(i-2)的位置。
接下来用f(-1)和f(i)的结果计算出f(i+1)

环形房屋偷盗

题目描述：

一条环形街道上有若干房屋。输入一个数组表示该条街道上的房屋内财产的数量。如果这条街道上相邻的两幢房屋被盗就会自动触发报警系统。计算小偷在这条街道上最多能偷取的财产的数量输入：nums = [1,2,3,1] 输出：4 先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

分析

线性街道上的房屋和环形街道上的房屋存在不同之处
如果n幢房屋围成一个首尾相接的环形，那么标号为0的房屋和标号为n-1的房屋相邻。如果小偷进入这两幢房屋内偷东西就会触发报警系统。
这个问题和线性街道的区别在于小偷不能同时到标号为0和n-1的两幢房屋内偷东西
因此将这个问题分解成两个子问题
1. 求从标号为0开始到标号为n-2结束的房屋内偷得的最多财物的数量
2. 求从标号为1开始到标号为n-1结束的房屋内偷得的最多财物的数量

代码实现

在线性街道的代码基础上做一点修改

function rob(nums){
  if(nums.length ==0) return 0;
  if(nums.length ==1) return nums[0];
  
  let result1 = helper(nums,0,nums.length -2);
  let result2 = helper(nums,1,nums.length -1);
  return Math.max(result1,result2)
}

辅助函数helper

function helper(nums,start,end){
  let dp = new Array(2).fill(0);
  dp[0] = nums[start];
  if(start<end){
    dp[1] = Math.max(nums[start],nums[start+1])
  }
  // 注意i的取值
  for(let i= start+2;i<=end;i++){
    let j = i - start; //这里是关键
    dp[j&1] = Math.max(dp[(j-1)&1],dp[(j-2)&1]+nums[i])
  }
  // 最后取值
  return dp[(end- start)&1]
}

双序列问题

双序列问题的输入有两个或更多的序列，通常是两个字符串或数组。

由于输入的是两个序列，因此状态转移方程通常有两个参数，

即f(i,j)

定义第一个序列中下标从0到i的子序列

和第二个序列中下标从0到j的子序列

的最优解或解的个数

一旦找到了f(i,j)与

f(i-1,j-1)
f(i-1,j)
f(i,j-1)

的关系，问题就会迎刃而解。 JS算法_知识点精讲

双序列的状态转移方程有两个参数，因此通常需要使用一个二维数组来保存状态转移方程的计算结果。

最长公共子序列

题目描述：

输入两个字符串，请求出它们的最长公共子序列的长度。如果从字符串s1中删除若干字符之后能得到字符串s2，那么字符串s2就是字符串s1的一个子序列输入：s1 = "abcde", s2 = "ace" 输出：3 最长公共子序列是 "ace" ，它的长度为 3。

分析确定状态转移方程

应用动态规划解决问题的关键在于确定状态转移方程。
由于输入有两个字符串，因此状态转移方程有两个参数。
- 用函数f(i,j)表示
- 第1个字符串中下标从0到i的字符串(记为s1[0..i])
- 第2个字符串中下标从0到j的字符串(记为s2[0..j])
- 的最长公共序列的长度
如果第1个字符串的长度是m，第2个字符串的长度是n，那么f(m-1,n-1)就是问题的解
如果第1个字符串中下标为i的字符(记为s1[i])与第2个字符串中下标为j(记为s2[j])的字符相同，
- 那么f(i,j)相当于在s1[0..i-1]和s2[0..j-1]的最长公共子序列的后面添加一个公共字符。
- 也就是f(i,j) = f(i-1,j-1)+1
如果字符s1[i]与字符s2[j]不相同，则这两个字符不可能同时出现在s1[0..i]和s2[0..j]的公共子序列中。此时s1[0..i]和s2[0..j]的最长公共子序列，
- 要么是s1[0..i-1]和s2[0..j]的最长公共子序列
- 要么是s1[0..i]和s2[0..j-1]的最长公共子序列
- 也就是，此时f(i,j)是f(i-1,j)和f(i,j-1)的最大值
那么状态转移方程为
- 当s1[i]==s2[j], f(i,j) = f(i-1,j-1)+1
- 当s1[i]!=s2[j], f(i,j) = max(f(i-1,j),f(i,j-1))
上述状态转移方程的i或者j等于0时，即求f(0,j)或f(i,0)时可能需要的f(-1,j)或f(i,-1)的值。
- f(0,j)的含义是s1[0..0]和s2[0..j]这两个字符串的最长公共子序列的长度
- 即第1个字符串只包含一个下标为0的字符，那么f(-1,j)对应的第1个子字符串再减少一个字符
- 所以第1个字符串是空字符串。
- 任意空字符串和另一个字符串的公共子序列的长度都是0,所以f(-1,j)的值等于0

根据状态转移方程写代码

状态转移方程可以用递归的代码实现，但由于存在重叠的子问题,因此需要用一个二维数组缓存计算结果，以确保不必要的重复计算。

也可以用自下而上的方法来计算状态转移方程，这个方程可以看成一个表格的填充过程，可以用一个表格来保存f(i,j)的计算结果。

先将表格中i等于-1对应的行和j等于-1对应的列都初始化为0
然后按照从上到下、从左到右的顺序填充表格中的其他位置

先用一个二维数组实现这个表格，然后用一个二重循环实现从上到下、从左到右的填充顺序。

function longestCommonSubsequence(s1,s2){
  let l1 = s1.length;
  let l2 = s2.length;
  // 注意行、列的长度  （l1+1/l2+1）
  let dp = new Array(l1+1).fill(0)
              .map(()=>
                new Array(l2+1).fill(0)
               )
  
  for(let i=0;i<l1;i++){
    for(let j=0;j<l2;j++){
      if(s1[i]==s2[j]){
        dp[i+1][j+1]= dp[i][j]+1
      }else {
        dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j])
      }
    }
  }
  return dp[l1][l2];
}

代码解释

由于表格中有i等于-1对应的行和j等于-1对应的列，因此如果输入字符串的长度分别为m、n，那么代码中的二维数组dp的行数和列数分别是m+1和n+1
- f(i,j)的值保存在dp[i+1][j+1]中

优化空间效率，只保存表格的两行

f(i,j)的值依赖于表格中

左上角f(i-1,j-1)的值、
正上方f(i-1,j)的值
同一行左边f(i,j-1)的值

由于计算f(i,j)的值只需要使用上方一行的值和同一行左边的值，因此实际上只需要保存表格中两行就可以。

function longestCommonSubsequence(s1,s2){
  let l1 = s1.length;
  let l2 = s2.length;
  if(l1<l2){
    return longestCommonSubsequence(s2,s1)
  }
  //行数为2
  let dp = new Array(2).fill(0)
            .map(()=>
              new Array(l2+1).fill(0)
              )
  
  for(let i=0;i<l1;i++){
    for(let j=0;j<l2;j++){
      if(s1[i]==s2[j]){
        // 处理行数
        dp[(i+1)&1][j+1]= dp[i&1][j]+1;
      }else {
        // 处理行数
        dp[(i+1)&1][j+1] = Math.max(
                              dp[i&1][j+1],
                              dp[(i+1)&1][j]
                            )
      }
    }
  }
  return dp[l1&1][l2]
}

代码解释

二维数组dp只有两行，f(i,j)的值保存在dp[(i+1)&1][j+1]中。
由于数组dp的行数是一个常数，因此此时的空间复杂度是O(min(m,n))

进一步优化空间效率，只需要一个一维数组

只需要用一个一维数组就能保存所有计算所需要的信息。这个一维数组的长度是表格的列数。（即输入字符串s2的长度+1）。

为了让一个一维数组保存表格的两行信息。

一维数组的每个位置需要保存原来表格中上下两格的信息
即f(i,j)和f(i-1,j)都保存在数组dp下标j+1的位置。

在计算f(i,j)之前，dp[j+1]中保存的是f(i-1,j)的值；在完成f(i,j)的计算之后，dp[j+1]被f(i,j)的值替换。

在计算f(i,j+1)时，可能还需要f(i-1,j)的值，因此在计算f(i,j)之后，不能直接用f(i,j)的值替换dp[j+1]中的f(i-1,j)的值。

可以在用f(i,j)的值替换dp[j+1]中f(i-1,j)的值之前先将f(i-1,j)的值临时保存起来。这样在下一步在计算f(i,j+1)时还能得到f(i-1,j)的值。

function longestCommonSubsequence(s1,s2){
  let l1 = s1.length;
  let l2 = s2.length;
  if(l1<l2){
    return longestCommonSubsequence(s2,s1)
  }
  
  let dp = new Array(l2+1).fill(0);
  for(let i=0;i<l1;i++){
    let prev = dp[0];
    for(let j = 0;j<l2;j++){
      let cur ;
      if(s1[i]==s2[j]){
        cur = prev +1;
      }else {
        cur = Math.max(dp[j],dp[j+1])
      }
      prev = dp[j+1];
      dp[j+1]= cur;
    }
  }
  return dp[l2]
}

代码解释

变量prev用来保存数组中被替换的值。
- 在计算f(i,j)之前，变量prev保存的是f(i-1,j-1)的值。
- 在计算f(i,j)（代码中变量cur）之后，将它保存到dp[j+1]中。
在保存f(i,j)之前，将保存在dp[j+1]中的值(即f(i-1,j))临时保存到变量prev中
下一步计算f(i,j+1)时可以从变量prev中得到f(i-1,j)
在代码cur = Math.max(dp[j],dp[j+1])中
- dp[j]对应的是f(i,j-1)
- dp[j+1]对应的是f(i-1,j)
由于是按照从上而下、从左到右的顺序填充表格，因此在计算f(i,j)之前，f(i,j-1)的值已经计算出来并保存到dp[j]的位置
- 此时f(i,j)的值还没有计算出来，因此保存在dp[j+1]中的还是f(i-1,j)的值

矩阵路径问题

这类问题通常输入是一个二维的格子，一个机器人按照一定的规则从格子的某个位置走到另一个位置，要求计算路径的条数或找出最优路径。

矩阵路径相关问题的状态转移方程通常有两个参数，即f(i,j)的两个参数i、j通常是机器人当前到达的坐标。

需要根据路径的特点找出到达坐标(i,j)之前的位置，通常是

左上角f(i-1,j-1)的值、
正上方f(i-1,j)的值
同一行左边f(i,j-1)的值

中的一个或多个。相应地，状态转移方程就是找出f(i,j)与f(i-1,j-1)、f(i-1,j)、f(i,j-1)的关系。

可以根据状态转移方程写出递归代码，但是一定要将f(i,j)的计算结果用一个二维数组缓存，以避免不必要的重复计算。也可以将计算所有f(i,j)看成填充二维表格的过程

路径的数目

题目描述：

一个机器人从m×n的格子的左上角出发，它每步要么向下要么向右，直到抵达格子的右下角。请计算机器人从左上角到达右下角的路径的数目输入：m = 3, n = 2 输出：3 从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向下 -> 向下

向下 -> 向下 -> 向右

向下 -> 向右 -> 向下

分析

机器人每走一步都有两个选择，

要么向下走，
要么向右走。

一个任务需要多个步骤才能完成，每步面临若干选择。题目要求计算路径的数目，而不是具体路径，选择动态规划解决该问题。

分析确定状态转移方程

用函数f(i,j)表示从格子的左上角坐标为(0,0)的位置出发到达坐标为(i,j)的位置的路径数目。
- 如果格子的大小为m×n,那么f(m-1,n-1)就是问题的解
当i等于0时，机器人位于格子最上面的一行，机器人不可能从某个位置向下走一步到达一个行号i等于0的位置。
- 因此，f(0,j)等于1
- 即机器人只有一种方法可以到达坐标为f(0,j)的位置
- 即从f(0,j-1)的位置向右走一步
当j等于0时，机器人位于格子最左边的一列，机器人不可能从某个位置向右走一步到达一个列号j为0的位置。
- 因此，f(i,0)等于1
- 即机器人只有一种方法可以到达坐标为(i,0)的位置
- 即从(i-1,0)的位置向下走一步
当行号i、列号j都大于0时，机器人有两种方法可以到达坐标为(i,j)的位置。
- 可以从坐标为(i-1,j)的位置向下走一步
- 可以从坐标为(i,j-1)的位置向右走一步
- 因此，f(i,j)= f(i-1,j)+f(i,j-1)

根据状态转移方程写递归代码

function uniquePaths(m,n){
  let dp = new Array(m).fill(0)
              .map(()=>
                  new Array(n).fill(0)
                )
  return (function helper(i,j,dp){
    if(dp[i][j]==0){
      if(i==0||j==0){
        dp[i][j] =1;
      }else {
        dp[i][j] = helper(i-1,j,dp) + helper(i,j-1,dp)
      }
    }
    return dp[i][j]
  })(m-1,n-1,dp)
}

代码解释

为了避免不必要的重复计算，需要用一个二维数组缓存f(i,j)的结果。
f(i,j)保存在dp[i][j]中

迭代代码

如果将二维数组dp看成一个表格，在初始化表格的第1行(行号为0)和第1列(列号0)之后，可以按照从左到右、从上到下的顺序填充表格的其他位置。

f(0,j)和f(i,0)的值都等于1，将表格的第1行和第1列的值都设为1
计算第2行(行号为1)剩下的位置的值。
- 按照状态转移方程,f(1,1)等于f(0,1)与f(1,0)之和
- f(1,2)等于f(1,1)和f(0,2)之和
依次类推，计算剩余行数

function uniquePaths(m,n){
 let dp = new Array(m).fill(0).map((item,index)=>{
        if(index == 0){
            // 初始化f(0,j) 
            return new Array(n).fill(1)
        }else {
            return new Array(n).fill(0)
        }
  });
  
  for(let i=1;i<m;i++){
    dp[i][0] =1
  }
  
  for(let i=1;i<m;i++){
    for(let j=1;j<n;j++){
      dp[i][j] = dp[i][j-1]+dp[i-1][j]
    }
  }
  return dp[m-1][n-1]
}

优化空间效率

在计算f(i,j)时，只需要计算用到f(i-1,j)和f(i,j-1)的值，因此只需要保存标号分别为i-1和i的两行就可以。

创建一个只有两行的二维数组dp，将f(i,j)保存在dp[i&1][j]中，那么将空间复杂度到O(n)。

还可以进一步优化空间效率，只需要创建一个一维数组dp就可以，在计算f(i,j)时需要用到f(i-1,j)和f(i,j-1)的值。接下来在计算f(i,j+1)时需要用到f(i-1,j+1)和f(i,j)的值。在计算完f(i,j)之后，就不再需要f(i-1,j)的值。（正上方的值）

在二维表格中，f(i,j)和f(i-1,j)是上下相邻的位置。由于f(i-1,j)计算出f(i,j)就不再需要，因此可以只用一个位置来保存f(i-1,j)和f(i,j)的值。

这个位置在计算f(i,j)之前保存的是f(i-1,j)的值
计算f(i,j)之后，保存的是f(i,j)的值

由于每个位置能够用来保存两个值，因此只需要一个一维数组就能保存表格中的两行。

function uniquePaths(m,n){
  // 数组长度为列数
  let dp = new Array(n).fill(1);
  
  for(let i=1;i<m;i++){
    for(let j=1;j<n;j++){
      dp[j] += dp[j-1]
    }
  }
  return dp[n-1]
}

代码解释：

dp是一个一维数组，f(i-1,j)和f(i,j)都保存在dp[j]中。
仍然用一个二重循环按照状态转移方程计算
循环体内的dp[j]+=dp[j-1]可以看成dp[j]= dp[j]+dp[j-1]
- 在赋值运算符的右边 dp[j]保存的是f(i-1,j)，dp[j-1]中保存的是f(i,j-1)
- 在计算f(i,j)之前，按照从左到右的顺序f(i,j-1)的值已经计算出来并保存在dp[j-1]中
- 用f(i-1,j)和f(i,j-1)的值计算出f(i,j)之后将结果保存到dp[j]中
虽然之前保存在dp[j]中的f(i-1,j)的值被覆盖，但这个值不在需要，因此覆盖这个值并不会出现任何问题

最小路径之和

题目描述：

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 因为路径 1→3→1→1→1 的总和最小。

分析

机器人每走一步都有两个选择，

要么向下走，
要么向右走。

一个任务需要多个步骤才能完成，每步面临若干选择。题目要求计算路径的数目，而不是具体路径，选择动态规划解决该问题。

分析确定状态转移方程

用函数f(i,j)表示从格子的左上角坐标为(0,0)的位置(用grid[0][0]表示)出发到达坐标为(i,j)的位置(用grid[i][j]表示)的路径的数字之和的最小值。
如果格子的大小为m x n,那么f(m-1,n-1)就是问题的解
当i等于0时，机器人位于格子的最上面的一行，机器人不可能从某个位置向下走一步到达一个行号i等于0的位置。
- 此时只有一条从左到右的路径，因此f(0,j)为最上面一行从grid[0][0]开始到grid[0][j]为止所有格子的值之和
当j等于0时，机器人位于格子的最左边的一列，机器人不可能从某个位置向右走一步到达一个列号j等于0的位置。
- 此时只有一条从上到下的路径，因此f(i,0)为最左边一列从grid[0][0]开始到grid[i][0]为止所有格子的值之和
当行号i、列号j都大于0时，机器人有两种方法可以到达坐标为(i,j)的位置
1. 从坐标(i-1,j)的位置向下走一步
2. 从坐标(i,j-1)的位置向右走一步
3. 因此f(i,j)= min(f(i-1,j)+f(i,j-1))+grid[i][j]

根据状态转移方程写代码

function minPathSum(grid){
  const m = grid.length, n = grid[0].length

  // 状态定义：dp[i][j] 表示从 [0,0] 到 [i,j] 的最小路径和
  const dp = new Array(m).fill(0)
            .map(() => 
                  new Array(n).fill(0)
                )

  // 状态初始化
  dp[0][0] = grid[0][0]
  // 状态转移
  for (let i = 0; i < m ; i++) {
      for (let j = 0; j < n ; j++) {
          if (i == 0 && j != 0) {
              dp[i][j] = grid[i][j] + dp[i][j - 1]
          } else if (i != 0 && j == 0) {
              dp[i][j] = grid[i][j] + dp[i - 1][j]
          } else if (i != 0 && j != 0) {
              dp[i][j] = grid[i][j] + 
                        Math.min(
                          dp[i - 1][j], 
                          dp[i][j - 1]
                          )
          }
      }
  }
  return dp[m-1][n-1]
}

优化空间效率

在计算f(i,j)时只需要用到它上面一行的f(i-1,j)，因此实际上只需要保留两行就可以。也就是说，创建一个只有两行的数组dp，将f(i,j)保存到dp[i&1][j]中即可。

还可以进一步优化空间，即只需要一个一维数组dp。在计算f(i,j)时，需要f(i-1,j)的值。

将f(i-1,j)和f(i,j)保存到同一个数组dp的同一个位置dp[j]中
在计算f(i,j)之前，dp[j]保存的是f(i-1,j)的值
用f(i-1,j)的值，计算f(i,j)之后，将f(i,j)的值保存到dp[j]中

function minPathSum(grid){
  let dp = new Array(grid[0].length).fill(0);
  dp[0] = grid[0][0];
  
  for(let j=1;j<grid[0].length;j++){
    dp[j] = grid[0][j] + dp[j-1]
  }
  
  for(let i=1;i<grid.length;i++){
    dp[0] +=grid[i][0];
    for(let j=1;j<grid[0].length;j++){
      dp[j] = grid[i][j] + Math.min(dp[j],dp[j-1])
    }
  }
  return dp[grid[0].length-1]
}

背包问题

背包问题基本描述如下：给定一组物品，每组物品都有重量和价格，在限定的总重量内如何选择才能使物品的总价格最高。

根据物品的特点，背包问题还可以进一步细分。如果每种物品只有一个，可以选择将之放入或不放入背包，那么可以将这类问题成为0-1背包问题。0-1背包问题是最基本的背包问题，其他背包问题通常可以转化为0-1背包问题

如果第i种物品最多有Mi个，也就是每种物品的数量都是有限的，那么这类背包问题称为有界背包问题（也可以称为多重背包问题）。
如果每种物品的数量都是无限的，那么这类背包问题称为无界背包问题（也可以称为完全背包问题）。

分割等和子集

题目描述：

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分输入：nums = [1,5,11,5] 输出：true nums 可以分割成 [1, 5, 5] 和 [11] 。

分析

如果能够将数组中的数字分成和相等的两部分，那么数组中所有数字的和(记sum)应该是一个偶数。

如果将数组中的每个数字看成物品的重量，也可以这样描述这个问题：能否选择若干物品，使它们刚好放满一个容量为t的背包？由于每个物品(数字)最多只能选择一次，因此这是一个0-1背包问题。

如果有n个物品，每步判断一个物品是否要放入背包，也就是说解决这个问题需要n步，并且每步都面临着放入或者不放入两个选择，看起来是一个能用回溯法解决的问题，但是题目中没有要求列出所有可能的方法。只要求判断是否存在放满背包的方法，所以选择用动态规划解决该问题。

分析确定状态转移方程

用f(i,j)表示能否从前i个物品（物品标号分别为0，1...i-1）中选择若干物品放满容量为j的背包。
- 如果总共有n个物品，背包的容量为t，那么f(n,t)就是问题的解
当判断能否从前i个物品中选择若干物品放满容量为j的背包时，对标号为i-1的物品有两个选择
1. 将标号为i-1的物品放入背包中，如果能从前i-1个物品(物品标号分别为0,1,...i-2)中选择若干物品放满容量为j-nums[i-1]的背包（即f(i-1,j-nums[i-1])为true）,那么f(i,j)就为true
2. 不将标号为i-1的物品放入背包，如果从前i-1个物品中选择若干物品放满容量为j的背包（即f(i-1,j)为true）,那么f(i,j)也为true
当j等于0时，即背包的容量为0,不论有多少物品，只要什么物品都不选择，就能使选中的物品总重量为0,
- 因此f(i,0)都为true
当i等于0时，即物品的数量为0,肯定无法用0个物品来放满容量大于0的背包，
- 因此当j大于0时，f(0,j)都为false

根据状态转移方程写递归代码

function canPartition(nums){
  let sum =nums.reduce((acc,cur)=>acc+cur,0);
  if(sum&1==1) return false;
  return subsetSum(nums,sum/2)
}

辅助函数

function subsetSum(nums,target){
  // 初始化为null
  let dp = new Array(nums.length+1).fill(0)
              .map(()=>new Array(target+1).fill(null));
  return (function helper(nums,dp,i,j){
    if(dp[i][j]===null){
      if(j==0){
        dp[i][j]= true;
      }else if(i==0){
        dp[i][j] = false
      }else {
        // 不选择放入
        dp[i][j]= helper(nums,dp,i-1,j);
        // 选择放入
        if(!dp[i][j]&&j>=nums[i-1]){
          dp[i][j] = helper(nums,dp,i-1,j-nums[i-1])
        }
      }
    }
    return dp[i][j]
  })(nums,dp,nums.length,target)
}

代码解释

先求出数组nums中所有数字之和sum,然后调用函数subsetSum判断能否从数组中选出若干数字使它们的和等于target(target为sum的一半)
为了避免不必要的重复计算，用二维数组dp保存f(i,j)的计算结果。
如果某个dp[i][j]等于null，则表示该位置对应的f(i,j)还没有计算过

根据状态转移方程写递归代码

如果将二维数组dp看成一个表格，就可以用迭代的代码进行填充。根据状态转移方程，表格的

第1列(j等于0)的所有格子都标为true
第1行的其他格子(i等于0并且j大于0)都标为false
接下来从第2行(i等于1)开始从上到下、从左到右填充表格中每个格子。

按nums = [1,5,11,5]进行数据分析：

第2行的第2个格子对应f(1,1),它表示能否从数组的前一个数字（即1）中选出若干数字使和等于1.

如果不选择1，那么f(1,1)的值等于f(0,1)的值，而f(0,1)的为false
如果选择1，此时f(1,1)等于f(0,0)，而f(0,0)为true,因此f(1,1)为true

第2行的第3个格子对应f(1,2)，它表示能否从数组的前一个数字（即1）中选出若干数字使和等于2.

如果不选择1，那么f(1,2)的值等于f(0,2)的值，而f(0,2)的为false
如果选择1，此时f(1,1)等于f(0,1)，而f(0,0)为false,因此f(1,2)为false

function subsetSum(nums,target){
  let m = nums.length;
  let n = target;
  let dp = new Array(m+1).fill(0)
          .map(()=>
              new Array(n+1).fill(false)
            );
  
  for(let i=0;i<=m;i++){
    dp[i][0] = true;
  }
  
  for(let i=1;i<=m;i++){
    for(let j=1;j<=n;j++){
      dp[i][j] = dp[i-1][j];
      if(!dp[i][j]&& j>=nums[i-1]){
        dp[i][j] = dp[i-1][j-nums[i-1]]
      }
    }
  }
  return dp[m][n]
}

最少的硬币数量

题目描述：

给定正整数数组conis表示硬币的面额和一个目标总额t,请计算凑出总额t至少需要的硬币数目。每种硬币可以使用任意多枚 输入：coins = [1, 2, 5], t = 11 输出：3 11 = 5 + 5 + 1 。

分析

将每种面额的硬币看成一种物品，而将目标总额看成背包的容量，那么这个问题可以等价于求将背包放满时物品的最少件数。这里每种面额的硬币可以使用任意多次，因此这个问题不是0-1背包问题，而是一个无界背包问题（也叫完全背包问题）

分析确定状态转移方程

分析和解决完全背包问题的思路与0-1背包问题的思路类似
用函数f(i,j)表示用前i种硬币（coins[0...i-1]）凑出总额为j需要的硬币的最少数目。
- 当使用0枚标号为i-1的硬币时，f(i,j)等于f(i-1,j)（用前i-1种硬币凑出总额j需要的最少硬币数目，再加上0枚标号为i-1的硬币）
- 当使用1枚标号为i-1的硬币时，f(i,j)=f(i-1,j-coins[i-1])+1(用前i-1种硬币凑出总额j-coins[i-1]需要的最少硬币数目，再加上1枚标号为i-1的硬币)
- 以此类推，当使用k枚标号为i-1的硬币时，f(i,j) = f(i-1,j-k × coins[i-1]) + k（用前i-1种硬币凑出总额j - k × coins[i-1]需要的最少硬币数目，再加上k枚标号为i-1的硬币）
状态转移方程为

f(i,j)=min(f(i-1,j - k × conis[i-1])+k)
(k × conis[i-1]≤j)

如果硬币有n种，目标总额为t，那么f(n,t)就是问题的解
当j等于0（即总额等于0）时，f(i,0)等于0，即从前i种硬币中选出0个硬币，使总额等于0
当i等于0且j大于0时，即用0种硬币凑出大于0的总额，这是不可能的

根据状态转移方程写代码

可以用不同的方法实现状态转移方程

转换成递归代码
将计算f(i,j)看成填充一个表格并用二重循环实现
在②的基础上，优化空间复杂度，只使用一个一维数组就能保存所有需要的信息

function coinChane(conis,target){
  let dp = new Array(target+1).fill(target+1);
  dp[0]= 0;
  for(let coin of coins){
    for(let j = target;j>=-1;j--){
      for(let k=1;k*coin <= j;k++){
        dp[j] = Math.min(dp[j],dp[j-k*coin]+k)
      }
    }
  }
  return dp[tareget] > target 
          ?-1
          :dp[target]
}

代码解释：

硬币的面额是正整数，每种硬币的面额一定大于或等于1。如果能用硬币凑出总额target，那么硬币的数目一定小于或等于target
- 用target+1表示某个面额不能用输入的硬币凑出

另外一种思路

用函数f(i)表示凑出总额为i的硬币需要的最少数目。这个函数只有一个参数，表示硬币的总额。如果目标总额为t，那么f(t)就是整个问题的解。

为了凑出总额为i的解，有如下选择

在总额为i-conis[0]的硬币中添加1枚标号为0的硬币，此时f(i)=f(i-coins[0])+1（在凑出总额为i-coins[0]的最少硬币数的基础上加1枚标号为0的硬币）
在总额为i-coins[1]的硬币中添加1枚标号为1的硬币，此时f(i)=f(i-coins[1])+1
依次类推，在总额为i-coins[n-1]的硬币中添加1枚标号为n-1的硬币，此时f(i)等于f(i-coins[n-1])+1

状态转移方程表示为

f(i) = min(f(i-coins[j])+1)
(coins[j]≤i)

由于状态转移方程只有1个参数，因此只需要一个一维数组就可以保存所有f(i)的计算结果

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

总结

通过记住一些事情来节省时间，这就是动态规划的精髓。具体来说，如果一个问题的子问题会被我们重复利用，我们则可以考虑使用动态规划

一般来说，动态规划使用一个一维数组或者二维数组来保存状态

动态规划做题步骤

① 明确 dp(i) 应该表示什么（二维情况：dp(i)(j)）；
② 根据 dp(i)和 dp(i-1) 的关系得出状态转移方程；
③ 确定初始条件，如 dp(0)

分为几步

找到“状态”和“选择”

明确dp数组/函数定义

寻找“状态”之间的关系

运用数学归纳思想解决问题

后记

分享是一种态度。

参考资料：剑指offer/leetcode官网/学习JavaScript数据结构与算法第3版

全文完，既然看到这里了，如果觉得不错，随手点个赞和“在看”吧。

JS算法_知识点精讲

JS算法_知识点精讲

文章list

整数

整数除法

分析：

代码实现

二进制加法

分析：

代码实现

N进制大数相加

前 n 个数字二进制中 1 的个数

分析

i&(i-1)

码上见分晓

优化处理

只出现一次的数字

分析

码上见分晓

触类旁通

只出现一次之外其他数字都出现两次

常规排序算法

数组

双指针

排序数组中的两个数字之和

分析

代码实现

数组中和为target的3个数字

分析

代码实现

和大于或等于k的最短子数组

分析

代码实现

乘积大于或等于k的最短子数组

分析

代码实现

累加数组数字求子数组之和 （Si）

和为target的子数组

分析

代码实现

0和1个数相同的子数组

分析

代码实现

左右两边子数组的和相等

分析

代码实现

总结

字符串

双指针

字符串中的变位词

分析

代码实现

字符串中所有变位词

分析

代码实现

不含重复字符的最长子字符串

分析

代码实现

回文字符串

有效回文

分析

代码实现

最多删除一个字符得到回文

分析

代码实现

回文子字符串的个数

分析

代码实现

总结

链表

链表基础算法

1. 链表反转

2. 判断链表是否有环

3. 合并链表

4. 找中点

哨兵节点

简化链表插入操作

简化链表删除操作

双指针

删除倒数第k个节点

分析

累加数组数字求子数组之和（Si）

删除倒数第`k`个节点