浮躁，是互联网时代的

大家好，我是柒八九。

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

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

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

文章list

好了，天不早了，干点正事哇。

整数

整数除法

题目描述：

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' >
提示：
当发生溢出时，返回最大的整数值。假设除数不能为0
只能存储 32 位有符号整数，其数值范围是 [−2³¹, 2³¹−1]

示例：输入： -15和2 输出： -7

分析：

从提示可知，此题中，值的范围是[−2³¹, 2³¹−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 --> 1
2 --> 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 ，除某个元素仅出现一次外，其余每个元素都恰出现三次。找出并返回那个只出现了一次的元素。
提示：-2³¹ <= nums[i] <= 2³¹ - 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的共同和不同点。

它们的核心框架是相似的。都是利用方向双指针进行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. 1. sum < target: 右移 right（right++）,在子数组右边增加新的数字，子数组长度+1
  2. 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. 1. mult < target: 右移 right（right++）,在子数组右边增加新的数字，子数组长度+1 (mult变大)
  2. 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;
}
复制代码

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

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

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

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

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

例如：在数组[1,2,3,4,5]中，从S₂的子数组[1,2,3]之和是6，S₄的子数组[1,2,3,4,5]之和是15，那么从下标3开始到下标4结束的子数组之和[4,5]之和是9，也就是 S₄ - S₂ 即： 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套路就那般
类型不同路不同，正整数双指针，其余尝试用S_i
正整数分两类，同向/反向双指针

1. 数据有序反向针，left为首right为尾(求两数之和)
2. 子数组同向针，区域之和或乘积

非正整数用S_i(前i个数据和)

1. S_j-S_i-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 在信息存储方面还是很有用的。在讲数组算法中，在非正整数用S_i时，就用 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. 默认值为-1
2. 在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)
  }

JS算法_知识点精讲

文章list

整数

整数除法

分析：

代码实现

二进制加法

分析：

代码实现

N进制大数相加

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

分析

i&(i-1)

码上见分晓

优化处理

只出现一次的数字

分析

码上见分晓

触类旁通

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

常规排序算法

数组

双指针

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

分析

代码实现

数组中和为target的3个数字

分析

代码实现

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

分析

代码实现

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

分析

代码实现

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

和为target的子数组

分析

代码实现

0和1个数相同的子数组

分析

代码实现

左右两边子数组的和相等

分析

代码实现

总结

字符串

双指针

字符串中的变位词

分析

代码实现

字符串中所有变位词

分析

代码实现

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

分析

代码实现

回文字符串

有效回文

分析

代码实现

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

分析

代码实现

回文子字符串的个数

分析

代码实现

总结

链表

链表基础算法

1. 链表反转

2. 判断链表是否有环

3. 合并链表

4. 找中点

哨兵节点

简化链表插入操作

简化链表删除操作

双指针

删除倒数第k个节点

分析

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

删除倒数第`k`个节点