👨‍💻必会数据结构

# 👨‍💻必会数据结构

# 01 数组

# 【1】刷题必掌握的数组API

这里直接看MDN文档 (opens new window)即可~讲得很详细

另外《学习JS数据结构与算法》这本书中提到了一些高频方法，如下

数组切片常用方法 slice() 返回一个新的数组对象，这一对
象是一个由 begin 和 end 决定的原数组的浅拷贝（包括 begin，不包括end）。原始数组不会被改变。

# 【2】数组必会题目

这部分题目为前端er必会的数组相关题目，都很有代表性！

掘金文章链接（排版更好看一些~） (opens new window)

单纯针对数组来考察的题目，总体来说，都不算太难——数组题目要想往难了出，基本都要结合排序、二分和动态规划这些相对复杂的算法思想才行。

本部分记录那些“不那么难，但是面试中很高频且可以考验你数组掌握程度”的题目

不那么难，指的是这种题不需要用到困难的“解题技巧”，排序、二分思想、动态规划
面试中高频，字面意思，面试经常考嘛（虽说感觉前端er的面试中链表会问的比较多？）
考验数组掌握程度，这一点很重要，决定了面试官对你的看法——
- 你是个不求甚解所有题目都暴力求解的选手
- 还是会不断优化，充分利用数组API与一些简单技巧（例如双指针、哈希表）进行求解的选手？

# 1. 两数之和 (opens new window)

哈希表

几乎所有求和问题，都可以转化为求差问题，不知道i如何优化？试着想想求差~

暴力解——嵌套循环这个就不用写了，大家都会的~ 写两个for循环然后逐个比对咯

借助哈希表一趟遍历解题

新建一个空对象模拟哈希表

var twoSum = function(nums, target) {
  const map = {};
  for(let i = 0; i < nums.length; i++) {
    if (map[target - nums[i]] >= 0) {
      return [map[target - nums[i]], i];
    } else {
      map[nums[i]] = i;
    }
  }
};

或者使用Map这个数据类型

var twoSum = function(nums, target){
  const map = new Map();
  for(let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [i, map.get(target - nums[i])]
    } else{
      map.set(nums[i], i);
    }
  }
}

# 88. 合并两个有序数组 (opens new window)

同向正序双指针，同向倒序双指针

笨拙的暴力法

// 纯属是为了提高数组相关API的熟练度XD，时间复杂度太高 不符合要求
// 看看就好 面试可别这么写~
var merge = function(nums1, m, nums2, n) {
  nums1.splice(m); // 先把nums1后面的m个0清除掉
  for(let j = 0; j < n; j++){
    for(let i = 0; i < m + n; i++){
      if(nums2[j] <= nums1[i]) {
        nums1.splice(i, 0, nums2[j]);
        break;
      }

      // nums2中的值全都比nums1大的话 直接推到nums1里就可以了
      if(nums2[j] > Math.max(...nums1)) {
        nums1.push(...nums2.slice(j)) 
        return nums1
      }
    }
  }
};

玩儿赖皮法一股脑合并

var merge = function(nums1, m, nums2, n) {
  nums1.splice(m, nums1.length - m, ...nums2);
  nums1.sort((a,b) => a - b);
}

开辟新空间，常规同向双指针寻值

var merge = function(nums1, m, nums2, n) {
  let p1 = 0, p2 = 0;
  let temp = [];

  while(p1 < m || p2 < n){
    // 如果nums1/nums2已经遍历完了，那么只能操作另外一个数组了~
    if(p1 === m) {
      temp.push(nums2[p2++]);
    } else if(p2 === n) {
      temp.push(nums1[p1++]);
    } else if(nums1[p1] < nums2[p2]) {
      // 较小的元素插入temp中（常规思路了这里~）
      temp.push(nums1[p1++]);
    } else if (nums1[p1] >= nums2[p2]){
      temp.push(nums2[p2++]);
    }
  }

  for (let i = 0; i < m + n; i++) {
    nums1[i] = temp[i];
  }
};

不必开辟新空间，巧妙逆向双指针！

ppt过程模拟看这里 (opens new window)

面试能答出来这么个倒序双指针，不得起飞咯😎（好吧这其实是基操。）

var merge = function(nums1, m, nums2, n) {
  let p1 = m - 1, p2 = n - 1;
  let tail = m + n - 1; // 从尾部开始插入 大->小
  let cur; // 设置cur记录每次要进行插入操作的值

  while (p1 >= 0 || p2 >= 0) {
    if(p1 === -1) {
      cur = nums2[p2--];
    } else if(p2 === -1) {
      cur = nums1[p1--];
    } else if (nums1[p1] >= nums2[p2]) {
      cur = nums1[p1--];
    } else if (nums1[p1] < nums2[p2]) {
      cur = nums2[p2--];
    }

    nums1[tail--] = cur;
  }
};

# 15. 三数之和 (opens new window)

反向对撞双指针

核心方法：对撞（反向）双指针 + 定指针分别挪动 & 保证获得的三个数不能重复（使用特殊判断跳过重复的值）

这里写了个题解【JavaScript】对撞双指针 + 定指针注释齐全 (opens new window)

var threeSum = function(nums) {
  nums.sort((a, b) => a - b);
  const ans = [];
  for (let i = 0; i < nums.length - 2; i++) {
    // 如果重复 则跳过本次循环 直接返回for语句
    if (i >= 1 && nums[i - 1] === nums[i]) {
      continue;
    }

    // 每轮不断地动p1 p2来找答案
    let p1 = i + 1;
    let p2 = nums.length - 1;
    while (p1 < p2) {
      let sum = nums[i] + nums[p1] + nums[p2];
      if (sum === 0) {
        ans.push([nums[i], nums[p1], nums[p2]]);

        // p1指针后移之后，要保证当前值和上一个不同，下面的p2同理
        p1++;
        while (nums[p1] === nums[p1 - 1]) {
          p1++;
        }
        p2--;
        while (nums[p2] === nums[p2 + 1]) {
          p2--;
        }
      } else if (sum < 0) {
        p1++;
        while (nums[p1] === nums[p1 - 1]) {
          p1++;
        }
      } else if (sum > 0) {
        p2--;
        while (nums[p2] === nums[p2 + 1]) {
          p2--;
        }
      }
    }
  }
  return ans;
};

# 【3】数组高频面试题

这部分内容为汇总的一些前端面试高频算法题~

# 找出排序数组中只出现一次的数字&延伸题目

# 540. 有序数组中的单一元素 (opens new window)

同剑指 Offer II 070. 排序数组中只出现一次的数字 (opens new window) 一样

我的题解——[JavaScript]异或、二分搜索（全体二分查找乱序数组&偶数二分查找有序数组）注释齐全 (opens new window)

# 异或快捷解决

540题中英文版有规定：Your solution must run in O(log n) time and O(1) space. 所以这个方法仅供了解

主要考察二分法！

var singleNonDuplicate = function(nums) {
    let res;
    for(let i = 0; i < nums.length; i++) {
        res ^= nums[i];
    }
    return res;
};

# 再优化，二分法（面试重点）

这里的第一个关键点是先把四种情况列出来！

参考官方题解

例子 1：中间元素的同一元素在右边，且被 mid 分成两半的数组为偶数。

我们将右子数组的第一个元素移除后，则右子数组元素个数变成奇数，我们应将 lo 设置为 mid + 2。

例子 2：中间元素的同一元素在右边，且被 mid 分成两半的数组为奇数。

我们将右子数组的第一个元素移除后，则右子数组的元素个数变为偶数，我们应将 hi 设置为 mid - 1。

例子 3：中间元素的同一元素在左边，且被 mid 分成两半的数组为偶数。

我们将左子数组的最后一个元素移除后，则左子数组的元素个数变为奇数，我们应将 hi 设置为 mid - 2。

例子 4：中间元素的同一元素在左边，且被 mid 分成两半的数组为奇数。

我们将左子数组的最后一个元素移除后，则左子数组的元素个数变为偶数，我们应将 lo 设置为 mid + 1。

然后就常规二分法做就行了~注意分情况讨论的细则即可！

var singleNonDuplicate = function(nums) {
    // 定义双指针
    let i = 0, j = nums.length - 1;
    while(i < j) {
        // let mid = (i + j) >> 1;
        // 为了防止大数溢出 建议这么写
        let mid = i + (j - i >> 1);
        // 此方法的关键——判断哪边为奇数的变量 要设置好
        let isEven = (j - mid) % 2 == 0;
        // 如果j-mid为偶数 则去除中间两个值相同的元素并跳过它们之后，两指针（包括两指针）之间有奇数个元素，
        // 也就是单个的元素一定在这之间
        if(nums[mid] === nums[mid - 1]) {
            if(isEven) {
                // 在左边
                j = mid - 2;
            } else {
                i = mid + 1;
            }
        } else if(nums[mid] === nums[mid + 1]){
            if(isEven) {
                // 在右边
                i = mid + 2;
            } else{
                j = mid - 1;
            }
        } else{
            return nums[mid];
        }
    }
    return nums[i];
};

怎么说呢，双指针的题，多画图就完事了！

时间复杂度 O(logn)，相比于暴力循环（包括异或），每次迭代将搜索空间缩减了一半！

# 进一步优化，仅对偶数索引进行二分搜索

最佳实践

var singleNonDuplicate = function(nums) {
    let i = 0, j = nums.length - 1;// 数组长度必为奇数，所以一前一后两个元素下标为偶数
    while(i < j) {
        let mid = i + ((j - i) >> 1);
        if(mid % 2 === 1) {
            // mid为奇数则-1变为偶数 则mid现在必为“边缘” 不必再分四种情况来讨论
            // 这就是仅对偶数索引进行二分搜索！
            mid--;
        } if(nums[mid + 1] === nums[mid]) {
            // 去除mid那一对数之后，左侧数必为偶数，右侧数必为奇数，继续去紧挨着那对数的右边1个找
            i = mid + 2;
        } else {
            // 去除mid那一对数之后，左侧数为奇数，右侧数必为偶数，继续去紧挨着那对数的左边1个找
            j = mid;// 此时mid已经在原基础上左移一位了 所以j直接放在mid这个位置即可
        }
    }
    return nums[i];
};

时间复杂度：O(log n/2) = O(logn)。我们仅对元素的一半进行二分搜索。

# 剑指 Offer 56 - I. 数组中数字出现的次数 (opens new window)

# 位运算-分组异或

这个分组的方法就很灵性。

var singleNumbers = function(nums) {
    let n = 0;
    // 01 n 为 两个单独数a b的乘积
    // 接下来(02中)使用与运算
        // 与运算特点 二进制中只有6&6 = 6 6&0 = 0&0 =0
    for(let num of nums){
        n ^= num;
    }
    // 02 m可以保证这个数组中单身的两个数a b中的一个可以不被它抵消掉 
    // 也就是 m&a = 0 m&b != 0
    let m = 1;
    while((n & m) === 0){
        // 只要n&m不为0 就一直让m左移，直到m可以抵消掉a与b中的一个
        m <<= 1;
    }
    // 03 接下来使用m把两个单独的数分在两堆 并分组
    let x = 0, y = 0;
    for(let num of nums){
        if((num & m) === 0){
            x ^= num;
        }
        else{
            y ^= num;
        }
    }
    return [x, y];
};

看不懂我这个解释（或者觉得太大白话）可以看看 K神的题解 (opens new window)

# 137. 只出现一次的数字 II (opens new window)

同剑指 Offer 56 - II. 数组中数字出现的次数 II (opens new window)一样

# 暴力哈希解

var singleNumber = function(nums) {
    let map = new Map();
    for(let num of nums){
        if(map.get(num) > 0){
            let count = map.get(num);
            count++;
            map.set(num, count);
        }
        else{
            map.set(num, 1);
        }
    }
    for(let [num,count] of map.entries()){
        if(count === 1){
            return num;
        }
    }
};

其他方法 (opens new window)太恶心了饶了我吧…我真不想做位运算了😢😢😢😢😢😢

# 【4】数组经典面试题

这部分题目由leetcode官网的“学习计划”提供，都是经典习题~

# 217. 存在重复元素 (opens new window)

经典的数组查重问题！

【1】利用判重API indexOf构建去重辅助数组

var containsDuplicate = function(nums) {
    let newArr = []
    for(let i = 0; i < nums.length; i++) {
        if(newArr.indexOf(nums[i]) === -1) {
            newArr.push(nums[i])
        }
    }
    return newArr.length !== nums.length
};

执行用时较高！想必是indexOf方法的锅咯~

【2】利用数据结构Set 构造只有单一元素的Set对象,判断Set对象与原数组长度是否相同

var containsDuplicate = function(nums) {
    let newArr = new Set(nums)
    return newArr.size !== nums.length
};

同理使用哈希表记录出现的次数也可以~

这里用Set其实更好哈~主要上面刚用过换个口儿😄

var containsDuplicate = function(nums) {
    let map = new Map()
    for(let i = 0; i < nums.length; i++) {
        if(map.has(nums[i])) {
            return true
        }
        else{
            map.set(nums[i], 1)
        }
    }
    return false
};

时间复杂度O(N)

空间复杂度O(N)

【3】排序后冒泡比较

这里可以拓展炫技手写个排序出来？😏

var containsDuplicate = function(nums) {
    nums.sort((a, b) => a - b)
    for(let i = 0; i < nums.length - 1; i++) {
        if(nums[i] === nums[i + 1]) {
            return true
        }
    }
    return false
};

时间复杂度O(N*log~N~)

空间复杂度O(log~N~) 在这里应当考虑排序时递归调用栈的深度。

V8 引擎 sort 函数只给出了两种排序 InsertionSort 和 QuickSort，

数量小于10的数组使用 InsertionSort-插入排序

比10大的数组则使用 QuickSort-快速排序

详情见V8 引擎array源码 (opens new window) 710行开始快排在760行处

【4】说干就干！来手写个快排！参考之前写过的一篇Java题解 (opens new window)（写得贼详细每一步都拆分开来说了！），这篇文章是参考的leetcode主站的一篇优秀图解 by 袁厨 (opens new window)~（好家伙连环参考）

快排分以下几步

1.选出基准值

2.使用填坑法 (opens new window)，写一个partition函数将数组分为小于基准值和大于基准值两部分

3.递归完成快排！

下面代码里这个注释很清楚了吧！

另外还写了个题解 (opens new window) 搭配图看着更舒服哈~

var sortArray = function(nums) {
    quicksort(nums, 0, nums.length - 1)// 调用快排方法
    return nums
};
var quicksort = function(nums, low, high) {
    if(low < high) {
        let index = partition(nums, low, high)// 得到用来将数组分成两部分（左面全小于index 右面全大于index）的索引
        quicksort(nums, low, index - 1)// 以第一轮得出的index为基准划分出左半区和右半区 对数组的左半区进行递归 将其全部变为有序
        quicksort(nums, index + 1, high)// 同理左半区
    }
}
var partition = function(arr, low, high) {
    let pivot = arr[low]// 选定第一个元素为基准值 把它拿出来 即为“挖坑”
    while(low < high) {
        // 【1】 挖了坑就需要填坑~从high指针开始向左找 
        while(low < high && arr[high] >= pivot) {
            high--
        }
        arr[low] = arr[high]// 一旦找到比坑对应值pivot小的 就扔到low那侧的坑里
        // 【2】 同【1】从low指针开始向右找填坑值
        while(low < high && arr[low] < pivot) {
            low++
        }
        arr[high] = arr[low]// 一旦找到比坑对应值pivot大的 就扔到high那侧的坑里
        //（刚刚这侧有一个值去填low那侧的坑了 所以出现了一个坑位~）
    }
    // 经过上面【1】【2】的不断迭代 low===high 此时这个位置即为基准位置
    arr[low] = pivot
    return low// 分区成功！返回定海神针~（此时low=high哦~）
}

再拓展补充下~

不稳定的四种排序方法 快选希堆

最快的排序方法是归并排序 还有一个不常见的堆排序！时间复杂度为 n×log~n~

快速排序的平均时间复杂度是n×log~n~

归并排序 (opens new window)和快速排序的区别：

归并是先拆开从底下往上面排

快排是每次都打乱一下从上往下排

# 53. 最大子数组和 (opens new window)

字节日常实习二面遇到的一题

【1】贪心思想找到关键点解决问题

关键是：维护一个当前遍历到的元素之和sum 只要sum<0 那么就丢弃上一组元素让sum=当前元素

var maxSubArray = function(nums) {
    let max = nums[0]
    let sum = nums[0]
    let n = nums.length
    for(let i = 1; i < n; i++) {
        if(sum < 0) {
            sum = nums[i]
        }
        else {
            sum += nums[i]
        }
        max = max > sum ? max : sum
    }
    return max
};

【2】动态规划

本题是超级经典的动态规划题型~

对dp几乎一窍不通的我向weiwei哥学习了一下 (opens new window)~

*需要我们掌握动态规划问题设计状态的技巧（无后效性）

*我们需要知道如何推导状态转移方程

运用动态规划解题过程如下：

1.定义状态 dp[i]：表示以 nums[i]（也就是第i个元素）结尾的连续子数组的最大和。

2.写出状态转移方程（描述子问题之间的联系）

这也是所有dp问题的关键

在本题中我们研究一个连续求和的问题——

如果 dp[i - 1] > 0，那么可以把 nums[i] 直接接在 dp[i - 1] 表示的那个数组的后面，得到和更大的连续子数组；
如果 dp[i - 1] <= 0，那么 nums[i] 加上前面的数 dp[i - 1] 以后值不会变大。（这里其实和贪心思想是一致的！）于是 dp[i] 「另起炉灶」，此时单独的一个 nums[i] 的值，就是 dp[i]。

以上两种情况的最大值就是 dp[i] 的值，写出如下状态转移方程：（上下两个状态转移方程同理嗷~）

3.思考初始值

dp[0] 根据定义，只有 1 个数，一定以 nums[0] 结尾，因此 dp[0] = nums[0]。

根据「状态转移方程」，dp[i] 的值只和 dp[i - 1] 有关，因此可以使用「滚动变量」的方式将代码进行优化。

【1】不进行空间优化的dp解

（也是看起来比较像动态规划的解法hhh）

var maxSubArray = function(nums) {
    let n = nums.length
    let dp = new Array(n)// dp[i]表示以nums[i]结尾的连续子数组的最大和
    dp[0] = nums[0]
    let max = dp[0]// 记录最大子数组和
    for(let i = 1; i < n; i++) {
        // 根据状态转移方程计算dp[i]的值
        if(dp[i - 1] > 0) {
            dp[i] = dp[i - 1] + nums[i]
        }
        else {
            dp[i] = nums[i]
        }
        max = max > dp[i] ? max : dp[i]// 不断更新最大值
    }
    return max
};

【2】进行空间优化的dp解

与贪心算法非常类似！本方法中pre+num就相当于贪心法中的sum 比较sum与num选取更大的一方

而贪心法是只有sum小于0时才选取下一个

相比之下我认为这个动态规划的思想要更加出色与容易理解！

var maxSubArray = function(nums) {
    let pre = 0
    let max = nums[0]
    for(let num of nums) {
        // 因为本题中 dp[i] 的值只和 dp[i - 1] 有关 
        // 所以可以使用这种滚动变量的方法（也可以说是 归并法~比较像reduce方法的感觉~）
        // 使用变量pre代替dp[i-1]
        pre = Math.max(pre + num, num)
        max = Math.max(max, pre)
    }
    return max
};

这里weiwei哥对空间优化补充了一下~

最后评论区里再学习一波

感谢weiwei哥详尽的分享！

# 1. 两数之和 (opens new window)

一些简单题是很可以考察思维的~可以思考下本题除了暴力破解还可以有什么好方法呢？

【1】暴力双层遍历

var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length - 1; i++) {
        for(let j = i + 1; j < nums.length; j++) {
            if(nums[i] + nums[j] === target) {
            	return [i, j]
            }
        }
    }
};

【2】哈希表＋变加法为减法——一趟遍历解决问题

// 借助数据结构Map
var twoSum = function(nums, target) {
    let map = new Map()
    for(let i = 0; i < nums.length; i++) {
        let t = target - nums[i]// 将问题变为减法，t是通过减法获得的要找的那个值
        if(map.has(t)) {
            return [i, map.get(t)]
        }
        else { 
            map.set(nums[i], i)// 为避免返回重复的值 先判断map中是否有值再进行填充
        }
    }
};

【还可以使用更高效的数组来直接模拟哈希表

var twoSum = function(nums, target) {
    let n = nums.length
    let map = new Array(n)
    for(let i = 0; i < n; i++) {
        let t = target - nums[i]// 要找的那个值
        if(map[t] >= 0) {
            return [i, map[t]]
        }
        else { 
            map[nums[i]] = i// 为避免返回重复的值 先判断map中是否有值再进行填充
        }
    }
};

# 88. 合并两个有序数组 (opens new window)

【1】取巧-暴力插入后全体排序

var merge = function(nums1, m, nums2, n) {
    for(let i = 0; i < n; i++) {
        nums1[i + m] = nums2[i]
    }
    nums1.sort((a, b) => a - b)
};

面试官：“啥？没有优化了么？哦这样，好的，今天的面试就到这里了你还有什么想问我的麽”

【2】利用辅助数组和同向双指针

抄一下官方题解的动图很形象~

var merge = function(nums1, m, nums2, n) {
    let ans = []
    let i = 0, j = 0
    while(i < m || j < n) {
        // 如果双指针任意一个到达了边界 则将另一个数组中的值加入结果数组
        if (i === m) {
            ans.push(nums2[j++])
        }
        else if (j === n) {
            ans.push(nums1[i++])
        }
        // 将较小的值加入结果数组
        else if (nums1[i] < nums2[j]) {
            ans.push(nums1[i++])
        }
        else if (nums1[i] >= nums2[j]){
            ans.push(nums2[j++])
        }
    }
    // 因为最后要返回nums1 所以要把结果数组中的内容加入nums1中
    for(let i = 0; i < ans.length; i++) {
        nums1[i] = ans[i]
    }
};

【3】不需要辅助空间+反向双指针原地完成

var merge = function(nums1, m, nums2, n) {
    let i = m - 1, j = n - 1
    let tail = m + n - 1
    let cur;
    while(i >= 0 || j >= 0) {
        // 遍历完一个数组则拿另一个数组中的值
        if (i === -1) {
            cur = nums2[j--]
        }
        else if (j === -1) {
            cur = nums1[i--]
        }
        // 拿到较大的值 放到尾部
        else if (nums1[i] < nums2[j]) {
            cur = nums2[j--]
        }
        else if (nums1[i] >= nums2[j]) {
            cur = nums1[i--]
        }
        nums1[tail--] = cur
    }
};

# 121. 买卖股票的最佳时机 (opens new window)

一趟循环——贪心法

贪心地在日价格prices[i]更低的时候记录一下~

var maxProfit = function(prices) {
    let maxProfit = 0// 如果无法盈利则返回0
    let lowPrice = prices[0]
    for(let i = 0; i < prices.length; i++) {
        lowPrice = lowPrice < prices[i] ? lowPrice : prices[i]// 每轮更新最低买入价格
        let profit = prices[i] - lowPrice
        maxProfit = profit > maxProfit ? profit : maxProfit// mei
    }
    return maxProfit
};

# 350. 两个数组的交集 II (opens new window)

双层比对暴力解

纯粹为了练练编码速度~

var intersect = function(nums1, nums2) {
    // 首先尝试下暴力大法 练练熟练度
    let m = nums1.length
    let n = nums2.length
    // 找出来数组长度较短的那一个-nums1 算是效率较高的暴力解吧~
    if(m < n){  
        return intersect(nums2, nums1)
    }
    let res = []
    for(let i = 0; i < nums1.length; i++) {
        for(let j = 0; j < nums2.length; j++) {
            if(nums1[i] === nums2[j]) {
                res.push(nums1[i])
                nums2.splice(j, 1)// 及时删去较长数组中的元素
                break
            }
        }
    }
    return res
};

排序＋双指针

比对两个数组使用的常客——双指针~~

var intersect = function(nums1, nums2) {
    // 先将二者升序排列
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);
    let l1 = 0, l2 = 0;// 给出同向双指针
    let res = [];
    // 双指针法熟悉的while循环
    while(l1 < nums1.length && l2 < nums2.length){
        if(nums1[l1] === nums2[l2]){
            // 找到元素则双指针都往后走一位
            res.push(nums1[l1]);
            l1++;
            l2++;
        }
        else if(nums1[l1] > nums2[l2]){
            l2++;
        }
        else{
            l1++
        }
    }
    return res;
};

哈希表

很容易想到的哈希表方法

感觉涉及到“元素在序列中出现的次数符合xxx要求”的问题都可以用哈希表记录一个状态，有点像人工智能研究中的一个思维方式——“咋让机器（有）学习（能力）？整几个表记录学习过程中的状态，智能体下一步的策略根据这个表来进行！”（啥你问我为啥刷题时候能想到机器学习？前段时间实验做多了的缘故吧！）

var intersect = function(nums1, nums2) {
    // 本题 哈希表中存储的形式为 {num: count}
    let map = new Map();
    let res = [];
    if(nums1.length > nums2.length){
        // 将较短的数组存入哈希表中 降低空间复杂度 一天一个优化小技巧~
        return intersect(nums2, nums1);
    }
    // 将较短的数组存入哈希表中
    for(let x of nums1){
        let count = map.get(x);//根据数组的元素 获得“值”
        if(count > 0){//判断这个值是否已经插入过哈希表
            count++;
            map.set(x, count);
        }
        else{
            map.set(x, 1)
        }
    }
    for(let x of nums2){
        // 开始进行比对
        let count = map.get(x);//如果哈希表中有x这个键 那么获取它对应的count
        if(count > 0){
            res.push(x);
            count--;
            map.set(x, count);
        }
    }
    return res;
};

# 566. 重塑矩阵 (opens new window)

先将老数组mat扁平化再赋值给新数组

直接使用一个一维数组进行过渡

var matrixReshape = function(mat, r, c) {
    let m = mat.length
    let n = mat[0].length
    // reshape操作不合理则输出原始矩阵
    if(m * n !== r * c) {
        return mat
    }
    let queue = mat.flat()// 数组扁平化获得一维数组 存在队列中 FIFO
    let ans = []// 最终答案数组
    console.log(queue)
    for(let i = 0; i < r; i++) {
        let temp = []// 共有r个temp最终需要存到ans中
        for(let j = 0; j < c; j++) {
            temp.push(queue.shift())
        }
        ans.push(temp)
    }
    return ans
};

将二维数组映射成为一维数组不用借助flat函数拍平！

直接从二维数组 nums 得到 r 行 c 列的重塑矩阵

var matrixReshape = function(mat, r, c) {
    let m = mat.length
    let n = mat[0].length
    if(m * n !== r * c) {
        return mat
    }
    let ans = new Array(r).fill(0).map(() => new Array(c).fill(0))
    for(let i = 0; i < m * n; i++) {
        ans[Math.floor(i / c)][i % c] = mat[Math.floor(i / n)][i % n]
    }
    return ans
};

时间复杂度：O(rc)

空间复杂度：O(1)

# 118. 杨辉三角 (opens new window)

暴力找规律(数学)法

var generate = function(numRows) {
    // 比较暴力的找规律法——根据上一行的两个值算出本行的值
    let ans = []
    for(let i = 0; i < numRows; i++) {
        let temp = new Array(i + 1).fill(1)
        for(let j = 1; j < i; j++) {
            temp[j] = ans[i - 1][j - 1] + ans[i - 1][j] 
        }
        ans.push(temp)
    }
    return ans
};

# 179. 最大数 (opens new window)

巧妙排序

var largestNumber = function(nums) {
    let sorted = nums.sort((a, b) => {
        if (`${a}${b}` > `${b}${a}`) {
            return -1
        }
        else {
            return 1
        }
    })
    // 存在[0,0] [0,0,0]这种特殊情况 会出现00这种奇怪的答案，所以要删去多余的0
    for (let i = 0; i < sorted.length - 1; i++) {
        if (sorted[i] === 0) {
            sorted.splice(i, 1)
            i--// 防止删除数组中某个元素之后造成的数组塌陷
        }
        else {
            break
        }
    }
    return sorted.join("")
};

知识点：V8中sort函数的实现机制

sort() 方法用原地算法 (opens new window)对数组的元素进行排序，并返回数组。默认排序顺序是在将元素转换为字符串，然后比较它们的UTF-16代码单元值序列时构建的

— MDN

关于 Array.prototype.sort() ，ES 规范并没有指定具体的算法，在 V8 引擎中， 7.0 版本之前 ，数组长度小于10时， Array.prototype.sort() 使用的是插入排序，否则用快速排序。

在 V8 引擎 7.0 版本之后 就舍弃了快速排序，因为它不是稳定的排序算法，在最坏情况下，时间复杂度会降级到 O(n2)。

于是采用了一种混合排序的算法：TimSort 。

这种功能算法最初用于Python语言中，严格地说它不属于以上10种排序算法中的任何一种，属于一种混合排序算法：

在数据量小的子数组中使用插入排序，然后再使用归并排序将有序的子数组进行合并排序，时间复杂度为 O(nlogn) 。

作者：an_371e 链接：https://www.jianshu.com/p/a557e9006186 来源：简书著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 02 字符串

# 【1】刷题必掌握的API

# `String.prototype.substring()` (opens new window)

substring()方法返回一个字符串在开始索引到结束索引之间的一个子集, 或从开始索引直到字符串的末尾的一个子集。
str.substring(indexStart[, indexEnd])
indexStart

需要截取的第一个字符的索引，该索引位置的字符作为返回的字符串的首字母。

indexEnd

可选。一个 0 到字符串长度之间的整数，以该数字为索引的字符不包含在截取的字符串内。

var anyString = "bill";// 输出"bil" console.log(anyString.substring(0,3));// 下面这些神奇的用法同样可以输出索引 0 1 2 的字符console.log(anyString.substring(3,0));console.log(anyString.substring(3,-3));console.log(anyString.substring(3,NaN));console.log(anyString.substring(-2,3));console.log(anyString.substring(NaN,3));// 比较好用的一个取数技巧var test = "xbill";// 获取字符串bill 剔除前面的字符test.substring(1);// "bill" 比较实用~

# `String.prototype.replace()/split()`删除str0中的str1

删除字符串的一段内容——使用replace

JS去掉字符串中的一段字符串 - 两种基础方法&简单正则 (opens new window)

JS删除String里某个字符的方法（指定某个字符进行删除） - 正则方法 (opens new window)

同理想全局/局部去除某串字符也可以方便快速地使用正则方法

也可以用 new RegExp('a', 'g') 或者 /a/g 创建正则，

第一个参数“a”指定了正则表达式的模式或其他正则表达式。

后一个参数是一个可选的字符串，包含属性 "g"、"i" 和 "m"，分别用于指定全局匹配、区分大小写的匹配和多行匹配。ECMAScript 标准化之前，不支持 m 属性。如果 pattern 是正则表达式，而不是字符串，则必须省略该参数。

# 【2】字符串必会题型

字符串在算法面试中，单独考察的机会并不多，同样倾向于和一些经典算法（后面会讲的）结合来体现区分度。本节我们先解决只需要数据结构知识做基础就可以解决的字符串问题。

两个字符串相关的基本算法技能

反转字符串

判断是否为回文字符串

这两个技能偶尔也会单独命题，但整体来看在综合性题目中的考察频率较高，需要大家着重熟悉、反复练习和记忆，确保真正做题时万无一失。（链表的题里面这二位也是经典得不行勒！）

# 反转字符串

直接调用API即可（还有其他的方法，比较体现技巧，一些公司一面为了试水，有时会单独考这个操作）

let str = "bytedance";
let res = str.split("").reverse().join("");// "ecnadetyb"

这里的核心主要是数组的API reverse()

# 344. 反转字符串 (opens new window)

代码随想录题解 (opens new window)

双指针

var reverseString = function(s) {
    let i = 0, j = s.length - 1;
    while(i < j){
        [s[i], s[j]] = [s[j], s[i]];// 解构赋值快速交换两个数的位置~
        i++;
        j--;
    }
    // return s;这里的字符串没有被改变，依旧是原来的顺序，不理解的可以在下一题试一试，看看还能不能这么反转
    // 题目中每组[s[i],s[j]]的顺组改变了，最终返回一个反转好的字符数组
};

# 541. 反转字符串 II (opens new window)

与344的反转字符串容易搞混的点在于：

344中测试代码接收的结果为[s[s.length-1],...s[1],s[0]]——是一个字符数组

而本题要求返回字符串，需要对数组&字符串的转换很熟悉！

var reverseStr = function(s, k) {
    let loop = Math.ceil(s.length / (2*k));// 需要进行对撞双指针遍历的轮数loop
    let arr = s.split("");// 将字符串拆成数组，方便最后返回结果arr.join(""),不然交换元素不能改变字符串本身
    for(let m = 0; m < loop; m++){
        // 每轮双指针的位置如下：（也是本题的关键）
        let i = m*2*k;
        let j = (s.length - i) < k ? s.length - 1 : i + k - 1;// 若剩余字符<k 则j指针位于字符串的末尾（将剩余字符全部反转）
        while(i < j){
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
            j--;
        }
    }
    return arr.join("");
};

# 回文字符串

判断一个字符串是否回文是必备技能！

回文字符串例子

let str = "gooddoog"

【1】使用额外的空间存一个新字符串，看看与最开始的是否是同一个

最简单的想法，但是空间复杂度为 O(N)

let newStr = str.split('').reverse().join('');
return newStr === str;

【重要】【2】利用字符串以中间为轴的对称性，使用双指针

for(let i = 0; i < str.length; i++){
    // 遍历字符串的前半部分，如果与后半部分相同，则满足对称性
    if(str[i] !== str[str.length - i]){
        return false;
    }
}
return true;

# 125. 验证回文串 (opens new window)

这题一个比较重要的点是要做数据预处理，把空格、逗号、冒号啥的都去除XD

s = "I:am:bill, llib ma I";// 这个字符串回文的必要条件是剔除掉空格、特殊符号们

使用正则表达式进行数据预处理

这种方法一劳永逸，一次性去除特殊字符

let newS = s.toLowerCase().match(/[a-z0-9]+/g);
console.log(newS);// ['i','am', 'bill', 'llib', 'ma', ]
// 使用match方法在字符串内索引指定值/找到一个或多个正则表达式的匹配
// 查找从大写A到小写z的字符，并返回匹配值

写一个判断遍历到的字母是否位于 a-z / 0-9 之间 的函数进行数据预处理

这种方法要求进行遍历，并在遍历过程中进行调用函数，判断对应字符是否符合要求

另外注意：在JS中进行字符串的比较大小实际上就是比较它们的ASCII码值的大小~如下：

建议搭配双指针使用

function isValid(str){
    return str >= 'a' && str <= 'z' || str >= '0' && str <= '9';
}
// 如果遍历到的字母

将数据预处理好了之后，有三种经典的解决方法

是的，就是reverse、双指针、栈三种方法

【1】正则匹配 + reverse法

reverse法非常适合与正则表达式搭配对题目进行秒杀

var isPalindrome = function(s) {
    let valid = s.toLowerCase().match(/[a-z0-9]+/g);// valid为进行正则匹配后筛选出来的数组
    if(!valid){
        return true;
    }
    let str = valid.join("");// 数据预处理(正则匹配)后得到的字符串
    let comp = str.split("").reverse().join("");// 将字符串翻转
    return comp === str;
};

【2】特殊字符处理函数 + 双指针

var isPalindrome = function(s) {
    var str = s.toLowerCase();
    // 定义好一头一尾的双指针
    let i = 0;
    let j = str.length - 1;

    while(i < j){
        // i/j不符合下面的isValid就推动左/右指针 并结束本轮迭代
        if(!isValid(str[i])){
            i++;
            continue;
        }
        if(!isValid(str[j])){
            j--;
            continue;
        }
        if(str[i] !== str[j]){
            return false;
        }
        i++;
        j--;
    }
    return true;
};
var isValid = function(str){
    return (str >= 'a' && str <= 'z') || (str >= '0' && str <= '9');
}

【3】正则匹配 + 栈

var isPalindrome = function(s) {
    let valid = s.toLowerCase().match(/[a-z0-9]+/g);
    if(!valid){
        return true;
    }
    let str = valid.join("");// 正则匹配过后获得的字符串
    let stack = [];
    
    let mid = str.length >> 1;// 设置中间的位置，入栈至str[mid - 1]再遍历后续内容 并与栈中内容一一比对
    for(let i = 0; i < mid; i++){
        stack.push(str[i]);
    }
    // 入栈完毕，接下来进行比对
    // 额外注意：如果字符串长度为奇数，应该跳过中间的字符进行比对
    if(str.length % 2){
        mid++;
    }
    for(let i = mid; i < str.length; i++){
        let comp = stack.pop();// 将元素一一出栈
        if(comp !== str[i]){
            return false;
        }
    }
    return true;
};

# 680. 验证回文字符串 Ⅱ (opens new window)

经典衍生问题

本质思想依旧是利用回文字符串的对称性——自然而然地想到了双指针~

要记住！

对称性

双指针

可以解决大部分回文字符串相关问题！

另外本体需要我们头脑清晰地创建一个工具方法——isPalindrome(s, i, j) 判断字符串s从i到j是否局部回文！

var validPalindrome = function(s) {
    let i = 0;
    let j = s.length - 1;
    while(i < j){
        if(s[i] !== s[j]){
            return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
        }
        i++;
        j--;
    }
    return true;
};
// 判断从i到j的s是否回文！跳过某一项之后局部回文，则整体回文！
// eg: cuppucu 
    // 先判断 uppucu 发现不回文 
    // 再判断 cuppuc 发现回文
var isPalindrome = function(s, i, j){
    while(i < j){
        if(s[i] !== s[j]){
            return false;
        }
        i++;
        j--;
    }
    return true;
}

# 实用技巧-正则表达式

暂时跳过了，正则表达式回头根据情况学一下咯！

# 【medium】211. 添加与搜索单词 - 数据结构设计 (opens new window)

设计题

RegExp+哈希表记录对应长度数组

var WordDictionary = function() {
  this.map = new Map();
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
  if(this.map.has(word.length)) {
    this.map.set(word.length, [...this.map.get(word.length), word]);
  } else {
    this.map.set(word.length, [word])
  }
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
  const len = word.length;
  if(!this.map.has(len)) {
    return false;
  }
  if (!word.includes('.')) {
    return this.map.get(len).includes(word);
  }

  // 如果search传入了包含 '.' 的字符串 则创建正则表达式对象 使用test API进行匹配
  const reg = new RegExp(word);

  // 对应数组长度中有一个匹配正则表达式的字符串 即返回true
  return this.map.get(len).some((item) => {
    return reg.test(item)
  })
};

# 【medium】8. 字符串转换整数 (atoi) (opens new window)

# 【3】字符串高频面试题

这部分内容为汇总的一些前端面试高频算法题~

# 【4】字符串好题

记录下来做完有感悟的字符串好题~

# 415. 字符串相加 (opens new window)

charAt()+模拟题
- 【不要用parseInt做字符串->整数用charAt！】
- 用错方法卡了四十多分钟最后还整数越界了。。

var addStrings = function(num1, num2) {
  let ans = [];
  let add =0;// 进位数
  let i = num1.length - 1, j = num2.length - 1;
  while (i >= 0 || j >= 0 || add !== 0) {
    // 如果某一个字符串走到头则返回0 加上三元表达式避免报错
    const x = i >= 0 ? num1.charAt(i) - '0' : 0;
    const y = j >= 0 ? num2.charAt(j) - '0' : 0;
    // 计算每一位数
    let count = x + y + add;
    add = Math.floor(count / 10);// 满十进一
    ans.push(count % 10);
    i--;
    j--;
  }
  return ans.reverse().join("");
};

# 387. 字符串中的第一个唯一字符 (opens new window)

利用哈希表存储数频

var firstUniqChar = function(s) {
  let map = new Map()
  for(let str of s) {
    // 快速创建记录数频的哈希表
    map.set(str, map.has(str) ? map.get(str) + 1 : 1);
  }
  for(let i = 0; i < s.length; i++) {
    if(map.get(s[i]) === 1) {
        return i
    }
  }
  return -1
};

# 383. 赎金信 (opens new window)

用哈希表（利用map数据结构）存储杂志的字符串出现次数，与信上一一比对

可以用来熟练下Map数据结构的使用，但是在碰到需要哈希表记录出现频率的场景使用一维数组比使用Map数据结构要优秀！

var canConstruct = function(ransomNote, magazine) {
  let mapMag = new Map()
  // 用哈希表存储杂志的字符串出现次数
  for(let str of magazine) {
    mapMag.set(str, mapMag.has(str) ? mapMag.get(str) + 1 : 1);
  }
  // 进行比对
  for(let str of ransomNote) {
    if(!mapMag.has(str) || mapMag.get(str) <= 0) {
      return false
    }
    else {
      // 发现相同字符则将哈希表中记录的频率-1
      let count = mapMag.get(str) - 1
      mapMag.set(str, count)
    }
  }
  return true
};

更高效的哈希表方法——用长度为26的一维数组模拟哈希表

所有涉及到字符出现频率的哈希表问题都建议用这个方法！构造简单，效率高🤤

var canConstruct = function(ransomNote, magazine) {
    let mapMag = new Array(26).fill(0)
    // 用哈希表存储杂志的字符串出现次数
    for(let str of magazine) {
        mapMag[str.charCodeAt() - 'a'.charCodeAt()]++
    }
    // 进行比对
    for(let str of ransomNote) {
        // 发现相同字符则将哈希表中记录的频率-1
        mapMag[str.charCodeAt() - 'a'.charCodeAt()]--
        if(mapMag[str.charCodeAt() - 'a'.charCodeAt()] < 0) {
            return false
        }  
    }
    return true
};

另外可以在最开始优化一下

if(ransomNote.length > magazine.length) {
    // 随手一写的特殊情况排除 显示出考虑的全面性~~
    return false
}

# 242. 有效的字母异位词 (opens new window)

使用哈希表记录字符串出现频率并进行比对

var isAnagram = function(s, t) {
    if(s.length !== t.length) {
        return false// 特殊条件判断下~
    }
    let map = new Array(26).fill(0)
    // 创建哈希表记录字符串t的字符串频率
    for(let str of t) {
        map[str.charCodeAt() - 'a'.charCodeAt()]++
    }  
    // 与字符串s进行比对
    for(let str of s) {
        // 防止s中字符比t中多——如果发现t中没有s中的字符，则返回false
        if(map[str.charCodeAt() - 'a'.charCodeAt()] <= 0) {
            return false
        }
        else {
            map[str.charCodeAt() - 'a'.charCodeAt()]--
        }
    }
    // 防止t中字符比s中多——最后要保证哈希表中记录的字符串出现频率为空
    return !map.includes(1)
};

排序之后一一比对

一行了事~

另外字符串和数组来回倒腾的方法也要非常熟练~

var isAnagram = function(s, t) {
    // 因为是小写字母的排序，所以直接调用sort排序就好~
    // 如果大小写都有则需要在sort里面用toLowerCase()全转化成小写再进行比较
    return s.length === t.length && [...s].sort().join('') === Array.from(t).sort().join('')
};

# 5980. 将字符串拆分为若干长度为 k 的组 (opens new window)

简单模拟

很简单也很棒的字符串题目~

之前做字符串的题总是先将其转变为数组再去思考，就很复杂！这样子多简单！

var divideString = function(s, k, fill) {
    const ans = []
    let str = ""
    for (const word of s) {
        str += word
        if (str.length === k) {
            ans.push(str)
            str = ''
        }
    }
    if (str.length > 0 && str.length < k) {
        while (str.length < k) {
            str += fill
        }
        ans.push(str)
    }
    return ans
};

# 03 链表

# 【1】链表基础

# 链表结点的构造函数

function ListNode(val, next){
    this.val = val;
    this.next = next;
}
// 创建结点node时，传入数据域对应的值val；指定next-下一个链表结点
let head = new ListNode(1);// 头结点，值为1
head.next = new ListNode(2);// 头结点指向的结点，值为2
let dummyHead = new ListNode(0, head);// 虚拟头结点，指向头结点head

# 【2】链表基础操作【刷题】

数组、字符串若想往难了出，那一定是要结合一些超越数据结构本身的东西——比如排序算法、二分思想、动态规划思想等等

但是链表可不一样了。如果说在命题时，数组和字符串的角色往往是“算法思想的载体”，那么链表本身就可以被认为是“命题的目的”。

结合实际面试中的命题规律，我把这些题目分为以下三类：

链表的处理
合并

删除（重点！）

链表的反转以及衍生题目

链表成环问题以及衍生题目

->快速上手——从0到1掌握算法面试需要的数据结构（二）-栈、队列、链表 (opens new window)

->链表的应用——真题归纳与解读 (opens new window)

# {1}链表的合并

# 21. 合并两个有序链表 (opens new window)（递归法重要！）

这俩题一样哈——剑指 Offer 25. 合并两个排序的链表 (opens new window)

# 迭代法

var mergeTwoLists = function(l1, l2) {
    let dummyHead = new ListNode(0, l1);
    let cur = dummyHead;
    while(l1 !== null && l2 !== null){
        if(l1.val < l2.val){
            cur.next = l1;
            l1 = l1.next;
        }
        else{
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = l1 === null ? l2 : l1;
    return dummyHead.next;
};

OJ中链表以数组形式展示，打印出来就一目了然了~

var mergeTwoLists = function(list1, list2) {
    let preHead = new ListNode(0)
    let cur = preHead
    while(list1 !== null && list2 !== null) {
        if(list1.val <= list2.val) {
            // console.log(list1, cur, preHead)
            cur.next = list1
            list1 = list1.next
        }
        else {
            // console.log(list2, cur, dummyHead)
            cur.next = list2
            list2 = list2.next
        }
        cur = cur.next
    }
    cur.next = list1 === null ? list2 : list1
    // console.log(cur, preHead)
    return preHead.next
};

可以清晰地看出来 cur就像是前序结点preHead的打工人一样，不断前进并把list2中的内容按照升序加入preHead中。

最终返回preHead.next即可得到最终结果

# 递归

要了解递归调用栈的原理！

着重思考最内层（【2】）（递归调用栈栈顶的函数）即可（也就是达成边界条件的那一步）！

var mergeTwoLists = function(list1, list2) {
  if (list1 === null) {
    // 👇【2】抵达最内层-递归调用栈栈顶函数返回值-递结束 开始归
    return list2;
  }
  if (list2 === null) {
    return list1;
  }
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    // list2.next=返回值
    return list1;
  } else {
    // 👇【1】递的过程——将对应函数放入递归调用栈
    list2.next = mergeTwoLists(list1, list2.next);
    // 👇【3】归的过程——按序从递归调用栈出栈并执行函数
    // list1.next=返回值
    return list2;
  }
};

下面的图参考——递归法图解 (opens new window)

递归就思考第一层第二层最好

每层不要忘了返回当层结果（执行这一次递归函数返回的结果）！

以原始用例 [1,2] [1,3,4]

【1】开始“递” 一直到最里面那一层

l1小的时候 l1指向再里层一些的那个递归函数mergeTwoLists()别忘了l1要往前挪动一位 mergeTwoLists(l1.next, l2)
l2小的时候同理

【2】return l2 执行时

这里结束了“递”

最里面那层的mergeTwoLists()执行完了

开始“归” —— 逐步执行外层的mergeTwoLists()函数

【3】最外面一层函数执行完

就可以返回最终结果了~

还有点懵？问题不大按顺序打印一下每一步的状态——

var mergeTwoLists = function(list1, list2) {
    if(list1 === null) {
        console.log("list1为空，递结束，开始归，list1.next=", list2)
        return list2// 递归第一步——
        // 边界条件：碰到一个链表走到null 就结束递（将函数放入递归调用栈）开始归（根据递归调用栈顺序开始调用对应函数）
    }
    else if(list2 === null) {
        return list1
    }
    else if(list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2)// 递归第二步——
        // 逐步将内层函数放入递归调用栈中
        console.log("list2.next=", list1)
        return list1
    }
    else {
        list2.next = mergeTwoLists(list1, list2.next)
        console.log("list1.next=", list2)
        return list2
    }
};

结果如下

# {2}链表的删除

要点：找要删除的结点的前一个结点

# 203. 移除链表元素 (opens new window)

超经典链表删除题！

var removeElements = function(head, val) {
    let dummyHead = new ListNode(0, head)
    let pre = dummyHead// 使用虚拟头结点避免在用例需要删除头结点时删不掉头结点
    while(pre !== null && pre.next !== null) {
        if(pre.next.val === val) {
            // 删除关键操作~
            pre.next = pre.next.next
        } else {
            pre = pre.next
        }
    }
    return dummyHead.next
};

如果不用虚拟头结点就会在需要删除头结点的用例中出错~

以身试法😑

想不用虚拟头结点就得先循环把头结点删了

嘿！这才算是把虚拟头结点理解透了嘛！

var removeElements = function(head, val) {
    // 先跳过所有头结点
    while (head !== null && head.val === val) {
        head = head.next
    }
    if(head === null) {
        return head
    }
    let pre = head
    // 之后正常遍历即可~
    while(pre !== null && pre.next !== null) {
        if(pre.next.val === val) {
            pre.next = pre.next.next
        } else {
            pre = pre.next
        }
    }
    return head
};

# 83. 删除排序链表中的重复元素 (opens new window)

与上题略有一些不同~要删除重复元素而不是指定元素

因为第一个结点不会被删掉所以不需要使用dummyHead~

var deleteDuplicates = function(head) {
    let cur = head
    while(cur !== null && cur.next !== null) {
        if(cur.val === cur.next.val) {
            // 当前值与下一个值相同则 通过修改链表结点指向跳过这个值
            cur.next = cur.next.next
        } else {
            // 当前值与下一个值不相同则 结点继续移动 检查接下来的结点
            cur = cur.next
        }
    }
    return head
};

# {3}链表删除的延伸（变式）

# 82. 删除排序链表中的重复元素 II (opens new window)

但是现在，咱们要做的事情变成了把前驱和后继一起删掉，前面两个值为1的结点要一起狗带才行，起始结点直接变成了第三个：

如果继续沿用刚才的思路，我们会发现完全走不通。因为我们的 cur 指针就是从图中第一个结点出发开始遍历的，无法定位到第一个结点的前驱结点，删除便无法完成。

虚拟头结点应用场景：

其实在链表题中，经常会遇到这样的问题：链表的第一个结点，因为没有前驱结点，导致我们面对它无从下手。这时我们就可以用一个 dummy 结点来解决这个问题。

本题思路

如果想要删除两个连续重复的值为 1 的结点，我们只需要把 dummy 结点的 next 指针直接指向 2：

如此一来，就大功告成啦~

注意：由于重复的结点可能不止一个两个，我们这里需要用一个 while 循环来反复地进行重复结点的判断和删除操作。

const deleteDuplicates = function(head) {
    // 极端情况：0个或1个结点，则不会重复，直接返回
    if(!head || !head.next) {
        return head
    }
    // dummy 登场
    let dummy = new ListNode() 
    // dummy 永远指向头结点
    dummy.next = head   
    // cur 从 dummy 开始遍历
    let cur = dummy 
    // 当 cur 的后面有至少两个结点时
    while(cur.next && cur.next.next) {
        // 对 cur 后面的两个结点进行比较
        if(cur.next.val === cur.next.next.val) {
            // 若值重复，则记下这个值
            let val = cur.next.val
            // 反复地排查后面的元素是否存在多次重复该值的情况
            while(cur.next && cur.next.val===val) {
                // 若有，则删除
                cur.next = cur.next.next 
            }
        } else {
            // 若不重复，则正常遍历
            cur = cur.next
        }
    }
    // 返回链表的起始结点
    return dummy.next;
};

# 237. 删除链表中的结点 (opens new window)

很有趣的一道题！你真的很熟悉链表的删除嘛？来试一试~

var deleteNode = function(node) {
    // 本题关键：无法要删除“node”，没关系！把node.next赋值给node，再删掉node.next即可！
    let nodeNext = node.next;// 暂存下一个结点
    node.val = nodeNext.val;// 把node.next赋值给node
    node.next = nodeNext.next;// 再删掉node.next
};

评论区热评——

很贴切有木有！！

# 【4】双指针的妙用

# 【medium】29.删除链表的倒数第 N 个结点 (opens new window)

两个要点——

虚拟头结点
双指针（快指针先走一步~）

var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode(0, head);
    let slow = dummy;
    let fast = dummy;
    for(let i = 0; i < n; i++){
        fast = fast.next;
    }
    while(fast !== null && fast.next !== null){
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
};

# 206.反转链表 (opens new window)

双指针法

这题的双指针写法相当经典！

在很多其他题型的解决方案种也有体现！（比如回文链表）

var reverseList = function(head) {
    let pre = null;
    let cur = head;
    while(cur !== null){
        let temp = cur.next;
        // 下面三步让局部的两个结点指向反转&各自前进一个结点
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
};

分享一篇GIF图解 (opens new window)，当初我就是看着这篇的GIF明白的😄

递归法速解

还可以使用递归的方法秒杀本题~

var reverseList = function(head) {
    // “递”的过程 一直递到链表的最后一个结点 即为反转后的头结点
    if(head === null || head.next === null){
        return head;
    }
    let newHead = reverseList(head.next);// 把head.next这个子问题传进去 递归调用栈将调用函数reverseList入栈
    // “归”的过程——递归调用栈开始弹栈
    head.next.next = head;// 让下一个结点head.next的next指针指向当前结点head
    head.next = null;// 让当前结点head本来指向head.next的指针指向NULL
    // 至此 一次局部反转完成
    return newHead;
};

递归这里的动图看这篇 (opens new window)~ 清楚！另外刚才那篇题解的递归图解也是不错的！

# 【medium】92.反转链表 II (opens new window)

好题！局部反转！

要点：保存断开连接的边缘，用于连接反转过后得到的头结点

var reverseBetween = function(head, left, right) {
    let dummy = new ListNode(0,head);
    let p = dummy;// 用于遍历
    for(let i = 0; i < left - 1; i++){
        p = p.next;
    }
    let leftHead = p;// 保存断开的边缘
    let start = leftHead.next;// 保存开始反转的边界
    // 设置双指针
    let pre = start;
    let cur = pre.next;
    for(let j = left; j < right; j++){
        // 反转局部链表
        let temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    leftHead.next = pre;// 连接最开始(断链的边缘)和局部反转链表反转过后得到的头结点
    start.next = cur;// 连接反转后的链表和后面那段链表
    return dummy.next;
};

# 【5】经典环形链表问题

# 141. 环形链表 (opens new window)

快慢指针的经典（也是很简单的一个）实践~

只要有环二者必定可以相遇

比较简洁的双指针实现方式如下：

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

二刷的时候用了这个代码A的

可见思考问题还是不够全面！

var hasCycle = function(head) {
    if(head === null || head.next === null) {
        return false
    }
    let slow = head
    let fast = head
    while(true) {
        fast = fast.next.next
        slow = slow.next
        // 这里就可以如上面一样简化咯！还不用写特例判断了！
        if(fast === null || fast.next === null) {
            return false
        }
        if(fast === slow) {
            return true
        }
    }
};

# 【medium】142. 环形链表 II (opens new window)

超级经典的面试题，尽量对其中的数学原理多了解些！面试时候可以说出点东西最好！

我写的题解 (opens new window)

推荐看的图文并茂的题解 (opens new window)（当时我就是看这个懂的！）

简单说一下这题的数学原理——

首先设链表长度为 a + b(环内结点个数)

【1】slow指针a+nb步之后一定会到入口；
【2】二者第一次相遇时慢指针已经走了nb步；
- 数学推导得来——fast走了2*slow 且第一次相遇时fast比slow快了 b*n 步联立一下:
- fast = 2 * slow ; fast = slow + n*b; —— slow = n*b

所以要让slow在第一次与fast相遇后再走a步停下来（满足刚好走完一整圈链表的长度）

这里建议看一下大佬们的图解XD 就很好理解了！

var detectCycle = function(head) {
    let slow = head;
    let fast = head;
    // 01 让两个指针第一次相交 此时slow指针走了n*b步
    while (true) {
        if(fast === null || fast.next === null){
            return null;
        }
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast){
            break;
        }
    }
    // 02 换新的结点从头结点开始丈量a步 保证slow指针一共走了a+n*b步
    let newFast = head;
    while (slow !== newFast) {
        newFast = newFast.next;
        slow = slow.next;
    }
    // 03 返回slow指向的结点 一定刚好走完一整圈
    return slow;
}

# 04 二叉树

[ ] DFS&BFS思想~
- [ ] 这个用得很深的题很多鸭感觉还是只掌握了皮毛
[x] 基本的递归操作
[ ] 回溯思想的运用
[x] 二叉搜索树
- [x] 简单的查找、插入操作
- [ ] 二叉搜索树的删除-这个有一丢丢麻烦的说
[ ] 平衡二叉树
[ ] 简单的堆问题-堆的建立&堆排序

另外感觉二叉树的简单递归是有很多有趣的模板的~

遍历
计算深度

单纯遍历
二叉树的经典前、中、后序遍历 (opens new window)（同理的）

对节点进行操作
插入

交换顺序

比较两个二叉树
100. 相同的树 (opens new window)

101. 对称二叉树 (opens new window)

# 【1】二叉树的遍历-递归/迭代

# 144. 二叉树的前序遍历 (opens new window)

递归

很简单的DFS思想(深度优先搜索的核心思想，是试图穷举所有的完整路径)，设置好退出条件、递归式两个重要元素就解题完成了，不用费心思去想栈的事儿~

节点遍历顺序：

根节点-左子树-右子树

var preorderTraversal = function(root) {
    const res = []
    function dfs(root) {
        if(root === null) {
            return;
        }
        res.push(root.val)
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    return res
};

DFS迭代

var preorderTraversal = function(root) {
    const res = []  
    const stack = [] 
    if(!root) {
        return res
    } 
    stack.push(root)  
    while(stack.length) {
        const cur = stack.pop() 
        // 当前结点就是当前子树的根结点，把这个结点放在结果数组的尾部
        res.push(cur.val)
        // 右子树先入栈 这样下一次遍历先遍历到的就是左子树了
        if(cur.right) {
            stack.push(cur.right)
        }
        if(cur.left) {
            stack.push(cur.left)
        }
    }
    return res
};

# 94. 二叉树的中序遍历 (opens new window)

DFS递归

很简单的DFS思想，设置好退出条件、递归式两个重要元素就解题完成了，不用费心思去想栈的事儿~

节点遍历顺序：

左子树-根节点-右子树

var inorderTraversal = function(root) {
    const res = []
    function dfs(root) {
        if(root === null) {
            return;
        }
        dfs(root.left)
        res.push(root.val)
        dfs(root.right)
    }
    dfs(root)
    return res
};

DFS迭代

借助栈的骚操作两个关键点——

外层while循环循环整体内层while找左节点
途径过的每一个节点，我们都要视情况地及时把它入栈。这样当最深处的叶子结点出栈时，第一个回溯（是的~这里利用到了栈来进行回溯）到的就是它的父结点：

var inorderTraversal = function(root) {
    const stack = []
    const res = []
    while(stack.length || root !== null) {
        // 1.内存循环用来DFS找左节点
        while(root !== null) {
            stack.push(root)
            // 先DFS到最深层
            root = root.left
        }
        // 2.根据当前节点的情况确定下一个操作是否要入栈
        	// 如果root为 叶子节点 root.right为null 自然不用入栈 继续进行出栈操作即可
        	// 如果root有子节点 将root.right加入栈中 继续深搜
        root = stack.pop()
        res.push(root.val)
        root = root.right
    }
    return res
};

# 145. 二叉树的后序遍历 (opens new window)

递归

很简单的DFS思想，设置好退出条件、递归式两个重要元素就解题完成了，不用费心思去想栈的事儿~

节点遍历顺序

左子树 -> 右子树 -> 根结点

var postorderTraversal = function(root) {
    const res = []
    function dfs(root) {
        if(root === null) {
            return;
        }
        dfs(root.left)
        dfs(root.right)
        res.push(root.val)
    }
    dfs(root)
    return res
};

DFS迭代

const postorderTraversal = function(root) {
  const res = []  
  if(!root) {
      return res
  }
  const stack = [] 
  stack.push(root)  
  while(stack.length) {
      const cur = stack.pop() 
      // 把这个结点放在结果数组的头部 先放进来的必定是排在最后的（跟先序遍历正好反过来！）
      res.unshift(cur.val)
      // 谁排在前面 谁就先入栈
      if(cur.left) {
        stack.push(cur.left)
      }  
      if(cur.right) {
        stack.push(cur.right)
      }
  }
  return res
};

# 102. 二叉树的层序遍历 (opens new window)

BFS 借助队列先进先出的特性，迭代实现

广度优先搜索的套路是——访问下一层之前要扫描下一层的可达点（扫描队头元素的可达点），将其入队（并将队头元素出队并按需求打印）

（图出处 (opens new window))

本题中BFS的关键是：在while 循环的每一轮中，都是将当前层的所有结点出队列（关键：使用for循环），再将下一层的所有结点入队列（关键：使用辅助队列），这样就实现了层序遍历。

另外BFS还可以应用在最短路径问题中（最近人工智能还学习了A*算法，可以更高效（智能）地解决最短路径问题）

var levelOrder = function(root) {
    const res = [];
    const queue = [];
    queue.push(root);
    if(!root) {
        return []; // 特殊情况要处理下，不然root为null，进入循环时搜索null.left会报错的！
    }
    while(queue.length !== 0) {
        const temp = []; // 记录每层的元素
        const len = queue.length; // 得到本层元素个数，确定这一轮要放几个元素进到temp中
        for(let i = 0; i < len; i++) {
            const top = queue.shift(); // 取出队头元素，并对下一层进行扫描（广度优先搜索）
            if(top.left) {
                // 搜到左节点后面还有元素，则将其入队
                queue.push(top.left);
            }
            if(top.right) {
                // 搜到右节点后面还有元素，则将其入队
                queue.push(top.right);
            }
            // 将本层内容加入结果数组
            temp.push(top.val);
        }
        res.push(temp);
    }
    return res;
};

做完上面这题再来一道简单一些的BFS经典面试题增强下自信心！

# 剑指 Offer 32 - I. 从上到下打印二叉树 (opens new window)

经典BFS法的应用

var levelOrder = function(root) {
    if(!root) {
        return []
    }
    const queue = []
    const res = []
    queue.push(root)
    while(queue.length) {
        const top = queue.shift()
        if(top.left !== null) {
            queue.push(top.left)
        }
        if(top.right !== null) {
            queue.push(top.right)
        }
        res.push(top.val)
    }
    return res
};

# 104. 二叉树的最大深度 (opens new window)

DFS 自下向上的递归

先用深搜思想找到叶子节点，再将深度不断返回给上一层

var maxDepth = function(root) {
    function dfs(root) {
        if(root === null) {
            return 0;
        }
        let leftDepth = dfs(root.left)
        let rightDepth = dfs(root.right)
        return Math.max(leftDepth, rightDepth) + 1
    }
    return dfs(root)
};

一行快速解题

上面写了一个dfs函数是为了让代码看起来更易懂，封装了一个深搜的函数

其实本题直接一行就能搞定

var maxDepth = function(root) {
    return root === null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};

递归是用来简化我们解决问题的复杂度的！要学会让电脑帮我们完成一些事儿（我们要做的就是把边界条件、递归式、return的值这些想清楚）

自上向下的DFS递归法

核心思想：递归到叶节点则计算这一条深度搜索路径的深度，并更新最大深度

var maxDepth = function(root) {
    let ans = 1// 用来记录深度，第一层的深度为1，所以如果一次递归都不发生的话就返回1
    function dfs(root, depth) {
        if(root === null) {
            // 避免root为空的情况
            return 0;
        }
        if(root.left === null && root.right === null) {
            // 递归到叶节点则计算这一条深度搜索路径的深度，并更新最大深度
            ans = Math.max(ans, depth)
        }
        dfs(root.left, depth + 1)
        dfs(root.right, depth + 1)
        return ans
    }
    return dfs(root, 1)// 因为第一层深度为1 所以传进去的depth=1
};

# 112. 路径总和 (opens new window)

BFS迭代

本题中 BFS的思路比较容易想到

维护一个队列记录当前节点，并根据当前节点搜索下一层

维护一个队列记录路径和temp，并时刻更新（将下一层的节点值计算进去，并时刻判断是否为叶子节点，如果是叶子节点则将temp与targetSum进行比较）

var hasPathSum = function(root, targetSum) {
    if(!root) {
        return false
    }
    // BFS法 创建两个数组 一个记录所有节点 一个记录路径和
    const queue = []
    const res = []
    queue.push(root)
    res.push(root.val)
    // 进入BFS
    while(queue.length) {
        const top = queue.pop()
        const temp = res.pop()
        // 如果遍历到叶子节点处时 路径和=targetSum 则返回true
        if(top.left === null && top.right === null) {
            if(temp === targetSum) return true
        }
        // 如层序遍历一般更新queue与路径和数组
        if(top.left) {
            queue.push(top.left)
            res.push(temp + top.left.val)
        }
        if(top.right) {
            queue.push(top.right)
            res.push(temp + top.right.val)
        }
    }
    return false
};

与广度优先使用计算路径和的思路反了过来

深搜使用的思想是，每层计算都进行targetSum-root.val 如果到叶子节点时 targetSum === root.val说明路径和符合要求了

var hasPathSum = function(root, targetSum) {
    if(root === null) {
        return false
    }
    // 搜到叶子节点，则判断当前节点值是否等于目标值
    if(root.left === null && root.right === null) {
        return root.val === targetSum
    }
    // 还没搜到叶子节点，则进行 目标值-当前节点值，并继续往下搜
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
};

# 【2】N叉树的遍历-递归/迭代

# 【3】对二叉树节点进行操作

用这道超级经典的题目练习深度优先搜索（递归）与广度优先搜素（迭代），并理解二者之间的差别

极好！

# 226. 翻转二叉树 (opens new window)

DFS深搜——递归

这种方法不用写很复杂的递归式，每层递归函数干的事儿就是把当前这层的两个子节点换个位置

如上图，所以写成代码也相当简单

var invertTree = function(root) {
    if(root === null) {
        return null// 到达最底部时需要返回null-意味着空节点
    }
    // 将当前遍历到的root的左右孩子换位置
    [root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
    return root
};

代码写详细一些就是这样~

另外，我们打印每一次调用的root

var invertTree = function(root) {
    if(root === null) {
        return null// 到达最底部时需要返回null-意味着空节点
    }
    let left = invertTree(root.left)
    let right = invertTree(root.right)
    root.left = right// invertTree(root.right)被调用 进入深搜模式~
    root.right = left// invertTree(root.left)被调用
    console.log(root)
    return root
};

简单分析下就是如下这样

BFS广度优先搜索——迭代

昨天刚刚学习过BFS实现层序遍历 (opens new window)，再来看看本题，同样是层序遍历+简单的交换左右孩子的操作~

var invertTree = function(root) {
  if (!root) {
    return null;
  }
  const queue = [];
  queue.push(root);
  while (queue.length) {
    const top = queue.shift();
    [top.left, top.right] = [top.right, top.left];
    if (top.left) {
      queue.push(top.left);
    }
    if (top.right) {
      queue.push(top.right);
    }
  }
  return root;
};

BFS广度优先搜索（从根节点开始翻转）与DFS深度优先搜索（递归到最底部的叶子节点才进行翻转）是相反滴~

来自上而下地打印每个节点看看，一、目、了、然

# 【4】比较两棵二叉树/一棵二叉树的两个分支

100与101都是要对树与树之间进行比对

# 101. 对称二叉树 (opens new window)

这题开始想着用中序遍历获得元素按照对称顺序排布的数组（并把null也加进去）

后来发现一次前/中/后序遍历无法还原一棵二叉树😢

选对方法，找对套路很重要啊！

本题正解：

DFS的题目思路都很相似完成核心思路的设计——递归式剩下的交给递归（搜索到底）完成就ok

var isSymmetric = function(root) {
    // 先dfs深搜到最下面，验证局部对称性
    function dfs(left, right) {
        // 遍历到叶节点，返回true
        if(left === null && right === null) {
            return true
        }
        // 遍历到只有一个子节点的节点，返回false
        if(left === null || right === null) {
            return false
        }
        // 遍历到两个不相等的节点，返回false
        if(left.val !== right.val) {
            return false
        }
        // 递归比较左节点的左孩子和右节点的右孩子&&左节点的右孩子和右节点的左孩子
        // 这一步 将递归函数dfs不断加入递归调用栈，进行局部对称性的验证
        return dfs(left.left, right.right) && dfs(left.right, right.left)
    }
    return dfs(root.left, root.right)
};

# 100. 相同的树 (opens new window)

做过上面的101，建议再做一下这道题，几乎一模一样的思路，但是又有一些细小的不同点，比对着理解了两题，这类“比较两棵二叉树的不同点”的问题就能轻松解决了！

var isSameTree = function(p, q) {
    if(p === null && q === null) {
        return true
    }
    if(p === null || q === null) {
        return false
    }
    if(p.val !== q.val) {
        return false
    }
    // 唯一的区别，上一题要求对称，这一题要求完全一样~所以return中的内容略有不同
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

# 【5】二叉搜索树

利用二叉搜索树的定义解决二叉搜索树相关的一些问题
验证

搜索、插入、删除操作

二叉搜索树定义：

空树√

二叉搜索树上的每一棵子树，都应该满足 左孩子 <= 根结点 <= 右孩子 这样的大小关系√

对于同一个遍历序列来说，平衡二叉树比非平衡二叉树（图上的结构可以称为链式二叉树）的查找效率更高，因为它把“二分”这种思想以数据结构的形式表达了出来

# 700. 二叉搜索树中的搜索 (opens new window)

了解了定义这样就很容易做题了

递归

var searchBST = function(root, val) {
    if(!root) {
        return null
    }
    if(root.val === val) {
        return root
    }
    return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val)
};

迭代

因为递归并不是深搜DFS（而是从根节点往下一个岔路口进行一个判断）所以迭代法写法同样简洁~

var searchBST = function(root, val) {
    while(root) {
        if(root.val === val) {
            return root
        }
        root = root.val > val ? root.left : root.right
    }
    return null
};

# 701. 二叉搜索树中的插入操作 (opens new window)

递归法

了解了二叉搜索树的性质，这种方法很好想到的~

注释很清晰了

var insertIntoBST = function(root, val) {
    // 遍历到空节点，创造值为val的节点并将其返回给上一个递归函数，插入成功~
    if(root === null) {
        return new TreeNode(val)
    }
    // val更小 所以插到二叉搜索树的左子树
    if(root.val > val) {
        root.left = insertIntoBST(root.left, val)
    }
    // val更大 所以插到二叉搜索树的右子树
    else {
        root.right = insertIntoBST(root.right, val)
    }
    return root
};

迭代法

跟递归法一个意思的,这个也是官方给出的正解“模拟法”

也很简单就是了！

var insertIntoBST = function(root, val) {
    // 空树的特殊情况要单独拿出来
    if(root === null) {
        return new TreeNode(val)
    }
    let cur = root// 拷贝一下根节点(的地址) cur改变root也会改变~
    while(cur) {
        if(cur.val > val) {
            if(cur.left === null) {
                cur.left = new TreeNode(val)
                break
            }
            cur = cur.left
        }
        if(cur.val < val) {
            if(cur.right === null) {
                cur.right = new TreeNode(val)
                break
            }
            cur = cur.right
        }
    }
    return root
};

# 98. 验证二叉搜索树 (opens new window)

重要结论：正确二叉搜索树的中序遍历结果应该是递增的

玩赖暴力法-将整个树中序遍历然后比对排序前排序后是不行的，因为有相同节点的用例

DFS思想在中序遍历过程中一点点比对前一个值与现在的值

var isValidBST = function(root) {
    let pre = -Infinity
    function inorder(root) {
        // 深搜到底则返回上一级
        if(root === null) {
            return true
        }
        // 1.对左子树进行中序遍历，如果2中出现false的情况则返回false；否则左子树满足二叉搜索树，继续检查右子树
        if(inorder(root.left) === false) {
            return false
        }
        // 2.判断现在节点的值是否比上一个节点小
        if(pre >= root.val) {
            return false
        }
        pre = root.val
        // 3.检查右子树是否为二叉搜索树 检查无误则返回true
        return inorder(root.right)
    }
    return inorder(root)
};

DFS思想非递归写法

上面的递归有点难懂？问题不大，看下非递归的写法就更清晰了！

通过非递归的写法(嘶~貌似非递归的DFS更难蛤注释尽量写全了已经😂跟着用例多走几遍就理解了~)

var isValidBST = function(root) {
    let stack = []
    let pre = -Infinity
    while(stack.length || root !== null) {
        // 按中序遍历的“左节点优先”准则将节点压入栈中，回头出栈的顺序即为中序遍历的顺序
        while(root !== null) {
            stack.push(root)
            root = root.left
        }
        // DFS到最底层的左孩子被拿出来
        root = stack.pop()
        // 比较是否满足二叉搜索树
        if(root.val >= pre) {
            return false
        }
        // 更新pre值
        pre = root.val
        // 当前节点有右孩子的话 就把右孩子压入栈中 作为中序遍历到的下一个节点（左、根、右的顺序~）
        root = root.right
    }
    return inorder(root)
};

# 653. 两数之和 IV - 输入 BST (opens new window)

【0】22/3/21的更新 DFS递归直接求解

function findTarget(root: TreeNode | null, k: number): boolean {
  const set = new Set();
  const dfs = (root) => {
    if (!root) {
      return false;
    }
    if (set.has(k - root.val)) {
      return true;
    }
    set.add(root.val);
    return dfs(root.left) || dfs(root.right);
  }
  return dfs(root);
};

【1】中序遍历转换成递增数组 转换问题为167. 两数之和 II - 输入有序数组 (opens new window) —— 双指针
- 如果是对普通树进行遍历后（得到无序数组）则转换问题为经典问题 1. 两数之和 (opens new window) —— 暴力解/哈希表
先进行熟练的中序遍历XD

let ans = []
function dfs(root) {
    if(root === null) {
        return
    }
    dfs(root.left)
    ans.push(root.val)
    dfs(root.right)
}
dfs(root)

得到递增序列 ans

可以简单无脑地使用嵌套循环把题先A掉

for(let i = 0; i < ans.length - 1; i++) {
    for(let j = i + 1; j < ans.length; j++) {
        if(ans[i] + ans[j] === k) {
            return true
        }
    }
}
return false

【2】可以使用双指针寻找递增序列 ans 中的target
- 使用对撞双指针

var findTarget = function(root, k) {
    let ans = []
    function dfs(root) {
        if(root === null) {
            return
        }
        dfs(root.left)
        ans.push(root.val)
        dfs(root.right)
    }
    // 中序遍历得到递增的序列ans
    dfs(root)
    let i = 0, j = ans.length - 1
    while(i < j) {
        // 双指针相向而行
        let sum = ans[i] + ans[j]
        if(sum === k) {
            return true
        }
        if(sum < k) {
            i++
        } else {
            j--
        }
    }
    return false
};

# 235. 二叉搜索树的最近公共祖先 (opens new window)

做这题要充分利用二叉搜索树的性质！

左孩子小于根节点&右孩子大于根节点

理解BST的特性之后使用递归轻松解决问题

定住一个根节点，一共就三种情况——同侧（左/右）/异侧

关键是要找到那个离二者最近的根节点——递归咯~

var lowestCommonAncestor = function(root, p, q) {
    // 同侧的情况
    if((root.val - p.val) * (root.val - q.val) > 0) {
        if(root.val > p.val) {
            // 1.二者在当前根节点root左侧，则继续遍历右子树root.left
            return lowestCommonAncestor(root.left, p, q)
        }
        else {
            // 2.二者在当前根节点root右侧，则继续遍历右子树root.right
            return lowestCommonAncestor(root.right, p, q)
        }
    }
    // 3.二者在根节点的两侧，那就好办咯~最近公共祖先肯定是根节点
    else {
        return root
    }
};

# 【6】平衡二叉树

平衡二叉树的判定

平衡二叉树的构造

# 剑指 Offer 55 - II. 平衡二叉树 (opens new window)

判断是否是平衡二叉树

其实就是判断左右两个子树深度是否满足差<=1

树的深度 = 1（根节点深度）+ max(左子树深度，右子树深度)——递归求解其每个节点的深度，最后返回到根节点

DFS无脑递归

var isBalanced = function(root) {
    let flag = true
    function dfs(root) {
        if(root === null){
            return 0
        }
        let left = dfs(root.left)
        let right = dfs(root.right)
        if(Math.abs(left - right) > 1) {
            flag = false
        }
        return Math.max(left, right) + 1
    }
    dfs(root)
    return flag
};

# 1382. 将二叉搜索树变平衡 (opens new window)——平衡二叉树的构造

# 05 栈与队列

[x] 经典：用栈实现队列
[x] 辅助栈的思想（关键是是理解栈这个数据结构入栈、出栈的规则并灵活使用）
- [x] 经典-有效的括号
- [x] 递归调用栈的思想
[ ] 单调栈（很多难题的解决方案）
[ ] 一些骚操作待学习…

# 【1】栈的设计

# 155. 最小栈 (opens new window)

其实这题主要难点在于获取栈中最小值的功能实现，这一点上我们可以优化~

所以我们使用两个方案解决这个问题~

# 一趟遍历法（O(N)的时间复杂度）

最好想的点——一趟遍历法

// 初始化栈结构
var MinStack = function() {
    this.stack = [];
};
// 入栈操作
MinStack.prototype.push = function(val) {
    this.stack.push(val);
};

// 出栈操作
MinStack.prototype.pop = function() {
    this.stack.pop();
};

// 获取栈顶元素
MinStack.prototype.top = function() {
    if(this.stack === null || this.stack.length === 0){
        // 熟练地完成边界条件判断可能不是必要地，但在不少时候可能会救你一命XD
        return;
    }
    return this.stack[this.stack.length - 1];
};

// 获取栈中最小值
MinStack.prototype.getMin = function() {
    const {stack} = this;// 小秀一手解构赋值
    let min = stack[0];
    for(let i = 1; i < stack.length; i++){
        min = stack[i] > min ? min : stack[i];
    }
    return min;
};

# 辅助栈法（O(1)的时间复杂度）

经典空间换时间哈~

这里使用的辅助栈下面739.每日温度也会用到！

==单调栈==——创建一个单调栈用于辅助，栈顶元素为最小，最后getMin的时候直接对辅助栈出栈即可~

// 初始化栈结构
var MinStack = function() {
    this.stack = [];
    this.stack2 = [];// 辅助栈
};
// 入栈操作
MinStack.prototype.push = function(val) {
    this.stack.push(val);
    // 本方法的关键——如何维护辅助栈！
        // 当辅助栈为空时入栈val & val比辅助栈栈顶元素小时入栈
    if(this.stack2.length === 0 || val <= this.stack2[this.stack2.length - 1]){
        this.stack2.push(val);
    }
};

// 出栈操作
MinStack.prototype.pop = function() {
    if(this.stack.pop() === this.stack2[this.stack2.length - 1]){
        // 若出栈元素和目前辅助栈栈顶元素相同则将其从辅助栈出栈
        this.stack2.pop();
    }
};

// 获取栈顶元素
// 这里没变化~
MinStack.prototype.top = function() {
    if(this.stack === null || this.stack.length === 0){
        // 熟练地完成边界条件判断可能不是必要地，但在不少时候可能会救你一命XD
        return;
    }
    return this.stack[this.stack.length - 1];
};

// 获取栈中最小值
MinStack.prototype.getMin = function() {
    return this.stack2[this.stack2.length - 1];// 直接取栈顶元素即可！
};

# 225. 用队列实现栈 (opens new window)

# 【2】使用到栈的经典题型

# 20. 有效的括号 (opens new window)

很经典(且面试高频)的题！重点是要联想到使用栈辅助解题！

var isValid = function(s) {
  // 利用Map对象创建哈希表~
  const map = new Map([        
    ["(", ")"],
    ["{", "}"],
    ["[", "]"],
  ]);

  let stack = [];
  // 遍历fi'fu'c并 对栈进行填充 + 将没资格入栈的元素与栈顶元素比较（别忘了出栈~）
  for(let str of s) {
    if(map.has(str)) {
      stack.push(str);
    } else if(map.get(stack.pop()) !== str) {
      return false;
    }
  }
  return !stack.length;
  // 只要栈里没有元素了 可以返回true，
  // 但别忘了如果栈中还有元素说明右侧的括号并没有成功匹配哦！
};

# 【medium】739. 每日温度 (opens new window)

本题可以用暴力两层循环去写，但是这样写会造成重复操作

栈结构可以帮我们避免重复操作。

及时将不必要的数据出栈，避免它对我们后续的遍历产生干扰即可！

单调栈的思想！单调栈的特点如下：
- 存储下标
- 从栈底到栈顶的下标对应着的温度依次降低！
  - 一旦出现一个不符合这个规律的（temperatures[i] > temperatures[stack[stack.length - 1]]）就将下标出栈并得到答案！

// 入参是温度数组
const dailyTemperatures = function(T) {
    const len = T.length // 缓存数组的长度 
    const stack = [] // 初始化一个栈   
    const res = (new Array(len)).fill(0) //  初始化结果数组，注意数组定长，占位为0
    for(let i=0;i<len;i++) {
      // 若栈不为0，且存在打破递减趋势的温度值
      while(stack.length && T[i] > T[stack[stack.length-1]]) {
        // 将栈顶温度值对应的索引出栈
        const top = stack.pop()  
        // 计算 当前栈顶温度值与第一个高于它的温度值 的索引差值
        res[top] = i - top 
      }
      // 注意栈里存的不是温度值，而是索引值，这是为了后面方便计算
      stack.push(i)
    }
    // 返回结果数组
    return res 
};

# 【3】使用栈实现队列

# 剑指 Offer 09. 用两个栈实现队列 (opens new window)

入队
出队（如果无法出队则返回-1）

本题为面试高频题目，务必很熟练！

而且在很多题目中需要用到辅助栈的思路，请掌握！

栈的方法没法实现队列的需求？

没关系！用辅助栈！

// 初始化两个辅助栈
var CQueue = function() {
    this.stack1 = [];
    this.stack2 = [];
};

// 在队列尾部添加数据 
CQueue.prototype.appendTail = function(value) {
    this.stack1.push(value);
};

// 删除队列头部数据
CQueue.prototype.deleteHead = function() {
    if(this.stack2.length === 0){
        while(this.stack1.length !== 0){
            this.stack2.push(this.stack1.pop());
        }
    }
    // 将stack1中内容移到stack2中之后，如果stack2中再没有（说明stack1也是空的，没有值被移到stack2）就不对了！
    if(this.stack2.length === 0){
        return -1;
    }
    else{
        return this.stack2.pop();
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

# 232. 用栈实现队列 (opens new window)

入队
出队
返回队头
判断队列是否为空

比上面那道题多了俩功能

因为栈是先进后出

队列是先进先出

所以想只用栈的入栈、出栈方法来实现队列，必须要使用两个栈按照一定规则将元素插入、弹出

举个例子，把这个过程想象成银行叫号

用A B两个“罐子”（也就是两个栈）模拟银行叫号的“先排队的先办业务”

这个过程如下所示：

【1】push方法发给每个人一个取号牌，拿到取号牌的人就放到A罐中

【2】MyQueue.prototype.pop方法就好比叫号，怎么根据栈的pop方法来让1号牌子出栈呢，人家是第一个排队的嘛

那么我们就要用到B罐子——调用pop方法时，把A罐子中的所有牌子依次出栈放到B中

while(this.stack1.length !== 0) {
    this.stack2.push(this.stack1.pop())
}
return stack2.pop()

【3】这里要注意，并不是每一次pop操作都要把A罐子中的内容放到B中！

B罐子中都是正在排队的老用户，A罐子的新人怎么能插队呢！

所以只有B罐子（stack2）中为空时，才会把A罐子中的等号牌放进B罐子中

if(this.stack2.length === 0) {
    while(this.stack1.length !== 0) {
        this.stack2.push(this.stack1.pop())
    }
}

【4】简单总结下

此类辅助栈的思想在很多题型中都可以用得到，一定要很熟悉栈这个数据结构！

var MyQueue = function() {
    this.stack1 = []
    this.stack2 = []
};

// 入队
MyQueue.prototype.push = function(x) {
    this.stack1.push(x)
};

// 出队
MyQueue.prototype.pop = function() {
    if(this.stack2.length === 0) {
        while(this.stack1.length !== 0) {
            this.stack2.push(this.stack1.pop())
        }
    }
    return this.stack2.pop()
};

// 查看队头 元素
MyQueue.prototype.peek = function() {
    // 复用上面的pop方法 先把队头元素弹出 再把它放进去，位置不会变~
    let top = this.pop()
    this.stack2.push(top)
    return top
};
// 判断队列是否为空
MyQueue.prototype.empty = function() {
    return !this.stack2.length && !this.stack1.length
};

# 【4】双端队列用途

可用于检查回文字符串

先添加到双端队列（用数组模拟即可）中

再用依次比对(其实与双指针同理，只不过这个看起来更有数据结构的思维hh)

顺带着还练了下字符串的操作XD

var isPalindrome = function(s) {
    let queue = []
    s = s.toLowerCase()
    // 获取符合要求的队列
    for(let str of s) {
        if(!isValid(str)) continue
        queue.push(isValid(str))
    }
    // 使用双端队列
    while(queue.length > 1) {
        if(queue.shift() !== queue.pop()) {
            return false
        }
    }
    return true
};
// 去除 小写字母&数字 以外的字符
function isValid(s) {
    if((s >= 'a' && s <= 'z') || (s >= '0' && s <= '9')) {
        return s
    }
}

双端队列衍生出的滑窗问题

# 剑指 Offer 59 - I. 滑动窗口的最大值 (opens new window)

和主站的 239. 滑动窗口最大值 (opens new window)一样

借鉴的修言大佬的思路 (opens new window)~

const maxSlidingWindow = function(nums, k) {
  // 缓存数组的长度
  const len = nums.length;
  // 初始化结果数组
  const res = [];
  // 初始化双端队列
  const deque = [];
  // 开始遍历数组
  for (let i = 0; i < len; i++) {
    // 当队尾元素小于当前元素时
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
      // 将队尾元素（索引）不断出队，直至队尾元素大于等于当前元素
      deque.pop();
    }
    // 入队当前元素索引（注意是索引）
    deque.push(i);
    // 当队头元素的索引已经被排除在滑动窗口之外时
    while (deque.length && deque[0] <= i - k) {
      // 将队头元素索引出队
      deque.shift();
    }
    // 判断滑动窗口的状态，只有在被遍历的元素个数大于 k 的时候，才更新结果数组
    if (i >= k - 1) {
      res.push(nums[deque[0]]);
    }
  }
  // 返回结果数组
  return res;
};

自己理解了一下~

var maxSlidingWindow = function(nums, k) {
    // 将暴力双重循环O(n*k)变为O(n) 在窗口发生移动时，只根据发生变化的元素对最大值进行更新
    // 达到这个效果的核心方法是使用递减队列（目的：确保队头元素始终是当前窗口的最大值）
    // 随着滑窗前进，不断检查被抛弃的那个数是不是最大值-如果是（和当前队头比较即可）则出队，不是就不用管
    // 另外别忘了特值-保证遍历到的元素个数是大于滑动窗口长度的（考虑要全面哦~）
    const len = nums.length;
    const res = [];
    const deque = [];// 本题关键-维护双端队列
    for(let i = 0; i < len; i++){
        // 双端队列中有元素 且 队尾元素小于当前元素的话，不符合递减队列，出队~一直出队到碰到比当前元素大的！
        while(deque.length && nums[deque[deque.length - 1]] < nums[i]){
            deque.pop();
        }
        // 当前元素是最大/仅次于最大的那个了~，入队当前元素的索引(回头在滑窗滑过它的时候需要把它出队！通过索引判断~)
        deque.push(i);
        // 队头元素的索引已经被排除在滑窗之外时，把它出队(从队头)，新王准备登基
        if(deque.length && deque[0] <= i - k){
            deque.shift();
        }
        if(i >= k - 1){
            // 特殊情况的判断-保证遍历到的元素个数是大于滑动窗口长度的
            res.push(nums[deque[0]]);
        }
    }
    return res;
};

回头刷剑指的时候我们还会再见面的~

# 06 设计题

# 【1】数组相关

# 384. 打乱数组 (opens new window)

medium

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

Solution(int[] nums) 使用整数数组 nums 初始化对象
int[] reset() 重设数组到它的初始状态并返回
int[] shuffle() 返回数组随机打乱后的结果

随机选数+及时删除

var Solution = function(nums) {
    this.nums = nums
    this.copy = nums.slice()
};

Solution.prototype.reset = function() {
    this.nums = this.copy.slice()
    return this.nums
};

Solution.prototype.shuffle = function() {
    let list = []
    let shuffled = new Array(this.nums.length).fill(0)
    let list = this.copy.slice()// 复制一个原数组的副本下来 边随机插入结果数组shuffled 边进行删除
    for(let i = 0; i < this.nums.length; i++){
        let len = list.length
        let index = Math.random()*len
        shuffled[i] = list[Math.floor(index)]
        list.splice(index, 1)
    }
    this.nums = shuffled.slice()
    return this.nums
};
// 下面是官方的暴力解 但是效率奇低 不知道为啥。。
// var Solution = function(nums) {
//     this.nums = nums
//     this.copy = nums.slice()
// };

// Solution.prototype.reset = function() {
//     this.nums = this.copy.slice()
//     return this.nums
// };

// Solution.prototype.shuffle = function() {
//     let shuffled = new Array(this.nums.length).fill(0)
//     let list = this.nums.slice()
//     for(let i = 0; i < this.nums.length; i++){
//         let index = Math.random()*list.length
//         console.log(index)
//         shuffled[i] = list.splice(index, 1)[0];
//     }
//     this.nums = shuffled.slice()
//     return this.nums
// };

Fisher–Yates shuffle 洗牌算法

非常有趣的思路与解法！

是解决随机打乱问题的最优方法！

【1】先从数组末尾开始，选取最后一个元素，与数组中随机一个位置的元素交换位置

【2】然后在已经排好的最后一个元素以外的位置中，随机产生一个位置，让该位置元素与倒数第二个元素进行交换

以此类推，打乱整个数组的顺序

var Solution = function(nums) {
    this.nums = nums;
    this.original = this.nums.slice();
};

Solution.prototype.reset = function() {
    this.nums = this.original.slice();
    return this.nums;
};

Solution.prototype.shuffle = function() {
    for (let i = 0; i < this.nums.length; ++i) {
        const j = Math.floor(Math.random() * (this.nums.length - i)) + i;
        const temp = this.nums[i];
        this.nums[i] = this.nums[j];
        this.nums[j] = temp;
    }
    return this.nums;
};

# 519. 随机翻转矩阵 (opens new window)