前言

本周刷了11道~

okkjoo-leetcodeHot-byJs带你用 JS 刷高频面试算法题~ 每周日更新~ 合集仓库：okkjoo-leetcodeHot-byJs

这是第一周的刷题记录与题解分享，如果你已经按题型分类系统地刷了一遍算法面试题的各个题型，想感受一下面试题的”随机性”的话，欢迎一起~

上题~

3. 无重复字符的最长子串|中等、高频

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

解题思路

无重复+最长子串——看到这两个个关键字你就要想到滑动窗口，那么这道题就是窗口大小无限制的滑动窗口~ 滑动窗口具体控制就是双指针啦

然后需要求得的就是 满足条件（不含重复字符）的窗口中，最大的窗口。

  • 用一个 set 存储窗口内的元素
  • 当窗口内没有重复字符时就不断地向右边扩张
    • 新的右边界字符存入 set
  • 出现重复后就缩小左边的窗口
    • 左边界限向右移动
  • 直到最右边界限

代码

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var lengthOfLongestSubstring = function(s) {
  6.     const set = new Set();//记录窗口内元素是否出现过
  7.     let i = 0, j = 0, res = 0;//左右指针、答案
  8.     if(s.length == 0)return 0;//特殊情况
  9.     while(j < s.length){//右边界小于字符串长度
  10.         if(!set.has(s[j])){//set中没有
  11.             set.add(s[j]);//放入set中
  12.             res = Math.max(res, set.size);//看看答案要不要更新
  13.         }else{//set中已经有了
  14.             while(set.has(s[j])){//右移左边界直到没有重复字符
  15.                 set.delete(s[i]);
  16.                 i++;
  17.             }
  18.             set.add(s[j]);//将右边界字符加入
  19.         }
  20.         j++;//无论如何右边界都是一直走的
  21.     }
  22.     return res
  23. };

20. 有效的括号|简单、高频

题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

解题思路

括号问题，常考的就是栈的运用与操作了~

遍历字符串s，分情况讨论：

  • 拿到左括号：
    • 压入栈中
  • 拿到右括号，分类讨论：
    • 栈不为空：
      • 栈顶为对应的左括号：取出栈顶，继续遍历
      • 栈顶不是对应的左括号，return false
    • 栈为空: 直接return false

遍历完之后，如果栈中还有括号，就说明有左括号没有右括号来与之配对，return false

扩展：

也可以通过设置计数器变量存储左右括号出现次数来进行判断

pps：只有一种括号类型的时候才可以使用计数器这个方法:（（）），如果不止一种括号，可能就会有些样例过不了，所以这个方法是无效的，例如这种示例4([)]'，没有以正确的顺序闭合。

⭐：

  • 栈的操作
  • JS中的数组中的push、popAPI 就可以模拟栈

代码

  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  */
  5. var isValid = function(s) {
  6.     const stk = [] //数组模拟栈
  7.     const mp = new Map()////对应括号映射
  8.     mp['(']=')'
  9.     mp['{']='}'
  10.     mp['[']=']'
  11.     for(let c of s){
  12.         //拿到左括号
  13.         // if(['(','[','{'].indexOf(c) != -1){
  14.         if(c in mp){
  15.             stk.push(c)
  16.         }else {
  17.             const top = stk.pop()
  18.             if(c !== mp[top]) return false //栈顶不是对应的左括号或者为undefined
  19.         }
  20.     }
  21.     if(stk.length)return false
  22.     return true//一切都恰当
  23. };

4. 寻找两个正序数组的中位数|困难、低频

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

解题思路

不完全暴力

双指针分别从两个数组A、B起始位开始

  1. 如果 A[i] <= B[j] , 则把 A[i] 放入新的数组中,i 往后移一位,即 i++ .
  2. 如果A[i] > B[j], 则把 B[j] 放入新的数组中,j 往后移一位, 即 j++ .
  3. 计数器cnt，每次任意指针时都
  4. 重复，直到 cnt == (n+1)/2，即到达中位数之地

虽然比起完全合并优化了一些，小于O(n+m)，但没有达到O(log(n+m))的要求

二分查找

⭐：

  1. 两个有序数组合并后，一个数组中本身的相对位置并不会变
  2. 有序——二分查找
  3. 对小的那个数组进行二分，确定一个 i，自然就能得到 j，因为最后的找到中位数的情况就是 (i+1) + (j+1) == (m + n + 1) / 2

其中m、n分别两个数组的大小

具体来说，就是最后的情况满足len(Aleft)+len(Bleft)=(m+n+1)/2，并且满足(maxLeftA <= minRightB && maxLeftB <=minRightA)，也就是最终为下图这样的形式：

带你JS 刷高频面试算法题|第一周|okkjoo-leetcodeHot-byJs - 图1

那么要怎么到达这样的形式呢

对小的那一个数组进行二分查找，不满足就调整，具体怎么调整看代码，直到调整到满足条件

最终复杂度为O(min(m,n))

带你JS 刷高频面试算法题|第一周|okkjoo-leetcodeHot-byJs - 图2

代码

  1. /**
  2.  * @param {number[]} nums1
  3.  * @param {number[]} nums2
  4.  * @return {number}
  5.  */
  6. var findMedianSortedArrays = function(nums1, nums2) {
  7.     //对数组长度较短的那个进行二分查找操作
  8.     nums1.length > nums2.length && ([nums1, nums2] = [nums2, nums1])
  9.     const m = nums1.length, 
  10.           n = nums2.length
  11.     let low = 0, high = m 
  12.     //二分
  13.     while(low <= high){
  14.         const i = low + Math.floor((high - low) / 2), //i:数组A中 minRightA 的下标
  15.               j = Math.floor((m + n + 1) / 2) - i     //j:数组B中 minRightB 的下标  
  16.         //这里注意特判，在边界的时候为了满足下面的条件，left的就是负无穷，right那头就是正无穷
  17.         const maxLeftA = i === 0 ? -Infinity : nums1[i-1],
  18.               minRightA = i === m ? Infinity : nums1[i]     
  19.         const maxLeftB = j === 0 ? -Infinity : nums2[j - 1],
  20.               minRightB = j === n ? Infinity : nums2[j]     
  21.         //进行判断
  22.         if(maxLeftA <= minRightB && maxLeftB <= minRightA){
  23.             return (m + n) & 1 //m+n 的奇偶情况分量讨论
  24.                 ? Math.max(maxLeftA, maxLeftB)
  25.                 : (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB))/2
  26.         }//不满足的话就要根据情况调整 low / high 指针
  27.         else if(maxLeftA > minRightB){
  28.             high = i - 1
  29.         }else {
  30.             low = low + 1
  31.         }
  32.     }
  33. };

1. 两数之和|简单、高频

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

解题思路

暴力

最容易想到的就是两层for来遍历，得到满足条件的两个整数
没什么好说的，也当然是必须优化的
时间O(n^2)，空间O(1)

Map

用 Map 记录遍历过的值以及对应下标，同时当前遍历到的值为 value，判断（ target - value） 是否记录过在Map 中

⭐：

  • 求和 —> 求差
  • Map 记录值与下标的映射
  • 空间换时间

时间O(1),空间O(n)

代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number[]}
  5.  */
  6. var twoSum = function (nums, target) {
  7.     const mp = new Map();
  8.     for (let i = 0; i < nums.length; i++) {
  9.         const v = nums[i];
  10.         const diff = target - v;
  11.         if (mp.has(diff)) return [mp.get(diff), i];
  12.         mp.set(v, i);
  13.     }
  14. };

88. 合并两个有序数组|简单、高频

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n

解题思路

暴力

没做过的第一个想法肯定是将num2放到num1后面，然后再一起进行排序

但这显然就用不到两个数组一开始就是有序的特征了

归并排序

复习一下归并排序的步骤：

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  4. 重复步骤 3 直到某一指针达到序列尾；
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

关键在于第三步~
比较两个数组头元素然后将较小的推至最终数组，并将其从原数组中吐出去，不断循环，直到两个数组都为空

但值得注意的是 题目要求 不返回一个新数组，而是存储再数组num1中，也就是要求原地修改，不能申请多的空间~ 为此，题目里说了 num1 的初始长度为 m+n，后n个元素为0

那么我们可以从后往前比较，从后面插入即可，用三个指针模拟

  • cur：记录当前到那个位置
  • m：记录 num1 数组处理到哪里
  • n：记录 num2 数组处理到哪里

时间复杂度O(n) 空间复杂度O(1)

代码

  1. /**
  2.  * @param {number[]} nums1
  3.  * @param {number} m
  4.  * @param {number[]} nums2
  5.  * @param {number} n
  6.  * @return {void} Do not return anything, modify nums1 in-place instead.
  7.  */
  8. var merge = function(nums1, m, nums2, n) {
  9.     let cur = m + n - 1 //从nums1尾部开始
  10.     while(cur >= 0){
  11.         if(n===0)return //num2已经全部放入num1中了
  12.         if(m < 1){//num1指针先走完了
  13.             nums1[cur--] = nums2[--n]
  14.             continue
  15.         }
  16.         if(n < 1){//num2指针先走完了
  17.             nums1[cur--] = nums1[--m]
  18.             continue
  19.         }
  20.         //取较大的插入 nums1 的末尾、更新对应的指针
  21.         if(nums1[m - 1] > nums2[n - 1]){
  22.             nums1[cur--] = nums1[--m]
  23.         }else {
  24.             nums1[cur--] = nums2[--n]
  25.         }
  26.     }
  27. };

415. 字符串相加|简单、高频

题目描述

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

解题思路

直接模拟

对两个非负整数进行 竖式计算 的模拟即可
将相同数位对齐，从低到高逐位相加，如果当前位和超过 1010，则向高位进一位
双指针从数的末尾即最低位开始，逐位相加，记录进位到 add 变量中
较少位的那一个数就在前面补零

⭐：

  • num1.charAt(i) - '0'将一个数字字符转为数字
  • 最后要reverse才是正确顺序的结果
  • 再用join将数组转为字符串

时间复杂度O(n)，空间复杂度O(1)

代码

  1. /**
  2.  * @param {string} num1
  3.  * @param {string} num2
  4.  * @return {string}
  5.  */
  6. var addStrings = function(num1, num2) {
  7.     let i = num1.length - 1, 
  8.         j = num2.length - 1
  9.         add = 0
  10.     const ans = []
  11.     while(i >= 0 || j >= 0 || add > 0){
  12.         const a = i >= 0 ? num1[i].charAt() - '0' : 0,
  13.               b = j >= 0 ? num2[j].charAt() - '0' : 0
  14.         const res = a + b + add
  15.         ans.push(res % 10)
  16.         add = Math.floor(res / 10)
  17.         i--,j--
  18.     }
  19.     return ans.reverse().join('')
  20. };

165. 比较版本号|中等、高频

题目描述

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 ‘.’ 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。

返回规则如下：

如果 version1 > version2 返回 1，
如果 version1 < version2 返回 -1，
除此之外返回 0。

解题思路

最方便的字符串切割

利用 split('.')将版本号字符串切割为数组，从下标为0开始依次比对：

时间复杂度O(n)，空间复杂度O(n)

  1. /**
  2.  * @param {string} version1
  3.  * @param {string} version2
  4.  * @return {number}
  5.  */
  6. var compareVersion = function(version1, version2) {
  7.     const v1 = version1.split('.')
  8.           v2 = version2.split('.')
  9.      for (let i = 0; i < v1.length || i < v2.length; ++i) {
  10.         let x = 0, y = 0;
  11.         if (i < v1.length) x = parseInt(v1[i]);   
  12.         if (i < v2.length) y = parseInt(v2[i]);  
  13.         if (x !== y)return x > y ? 1 : -1;
  14.     }
  15.     return 0;
  16. };

空间优化

我们可以不降其切割后放入数组再进行逐一比对，而是在切割时就进行逐一比对

代码

  1. /**
  2.  * @param {string} version1
  3.  * @param {string} version2
  4.  * @return {number}
  5.  */
  6. var compareVersion = function (version1, version2) {
  7.     const n = version1.length,
  8.         m = version2.length;
  9.     let i = 0,
  10.         j = 0; //双指针
  11.     while (i < n || j < m) {
  12.         let a = 0, b = 0; //同一下标下的两个修订号
  13.         for (; i < n && version1[i] !== "."; ++i) {
  14.             a = a * 10 + version1[i] - "0";
  15.         }
  16.         ++i; // 跳过点号
  17.         for (; j < m && version2[j] !== "."; ++j) {
  18.             b = b * 10 + version2[j] - "0";
  19.         }
  20.         ++j; // 跳过点号
  21.         if (a !== b) return a > b ? 1 : -1;
  22.     }
  23.     return 0;
  24. };

70. 爬楼梯|简单、中频

题目描述

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

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

解题思路

动态规划

f(x) 表示爬到第x级阶梯的方案数，由每次可走一步或两步可知

  • 转移条件为：f(x)=f(x-1)+f(x-2)
  • 初始化：f(0)=1、f(1)=1，到第0级和第1级的方案数都是1

那么我们对f[]数组从2开始的遍历即可

  1. for(let i = 2; i <=n; i++){
  2.     f[i] = f[i-1] + f[i-2];
  3. }
  4. return f[n]

这样的时间复杂度和空间复杂度都是O(n)

我们发现，f(x)只与f(x-1)和f(x-2)有关，也就是与f(x-2)之前的东西再无瓜葛，最后要求的结果也只是f(x)再利用滚动数组思想优化一下：直接用三个变量存储关键的东西就行了

  1. var climbStairs = function(n) {
  2.     let p = 0, q = 0, r = 1;
  3.     for (let i = 1; i <= n; ++i) {
  4.         p = q;
  5.         q = r;
  6.         r = p + q;
  7.     }
  8.     return r;
  9. };

现在时间复杂度为O(n)，空间复杂度为O(1)

但这种dp的入门题，还用dp就有点low了（卷，就嗯卷）

矩阵快速幂

用这个方法需要对线性代数有了解，但如果只是想看懂我的题解的话，也不需要特别多

  • 矩阵乘法：一句话总结，就是矩阵C 内第1行第1列的元素 = 矩阵A第一行元素 与 矩阵 B第一列元素对应各项相乘再累加后得到的

也算有关于数论吧

快速幂

  1. //a^n
  2. while(n>0)
  3. {
  4.     if(n&1) res*=a;
  5.     n>>=1;
  6.     a=a*a;
  7. }

对于n次幂，对n二进制话，二进制位上位1 的话就相乘，然后一直将n右移

什么时候可以用矩阵快速幂

矩阵快速幂的使用相较于dp可能没那么好看出来——也可能只是我相比这个来说dp比较熟悉

  • 问题可转换为求解矩阵的n次方
    • 结合快速幂优化效率
  • 递归式形如齐次线性递推式
    • 就可以构造出矩阵n次方再乘一个列向量a得到一个列向量b，且列向量b中包含我们需要的f(x)
  • 递归式可以转换为齐次线性递推式

这道题目中的转移条件f(x)=f(x-1)+f(x-2)就是上面的第二种情况：递归式形如其次线性递归式

这个方法的时间复杂度为O(logn)

如果你觉得难的话，其实只学dp也行，这个方法讲个思路应该也不错了…

代码

最终代码如下：

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var climbStairs = function(n) {
  6.     const q = [[1, 1], [1, 0]];
  7.     const res = pow(q, n);
  8.     return res[0][0];
  9. };
  11. const pow = (a, n) => {
  12.     let ret = [[1, 0], [0, 1]];
  13.     while (n > 0) {
  14.         if ((n & 1) === 1) {
  15.             ret = multiply(ret, a);
  16.         }
  17.         n >>= 1;
  18.         a = multiply(a, a);
  19.     }
  20.     return ret;
  21. }
  23. const multiply = (a, b) => {
  24.     const c = new Array(2).fill(0).map(() => new Array(2).fill(0));
  25.     for (let i = 0; i < 2; i++) {
  26.         for (let j = 0; j < 2; j++) {
  27.             c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
  28.         }
  29.     }
  30.     return c;
  31. }

46. 全排列|中等、高频

题目描述

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

解题思路

求全排列问题需要的前置知识：回溯~

以[1,2,3]为例

  1. 从中选一个数a
  2. 再选一个数，且该数不能为选过的数
  3. 重复，直到选完所有的数

那么关键就在于 怎么判定该数选没选过，如果用多一个 map 专门判断，判断的时间复杂度为O(1)，但是要用到额外的空间O(n)，但是本来就需要用到 tmpList 存储临时结果，所以直接用自带的 includes 线性查找判断就好了

总体的时间复杂度还是O(n)，空间复杂度O(n)

代码

  1. // 回溯函数
  2. function backtrack(lists, tmpList, nums){
  3.     if(tmpList.length === nums.length) return lists.push([...tmpList])
  4.     for(let i = 0; i < nums.length; i++){
  5.         if(tmpList.includes(nums[i])) continue
  6.         tmpList.push(nums[i])
  7.         backtrack(lists, tmpList, nums)
  8.         tmpList.pop() //回溯
  9.     }    
  11. }
  12. /**
  13.  * @param {number[]} nums
  14.  * @return {number[][]}
  15.  */
  16. var permute = function(nums) {
  17.     const lists = []
  18.     backtrack(lists, [], nums)
  19.     return lists
  20. };

53. 最大子序和|简单、高频

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

解题思路

暴力

计算所有[i...j]和，留最大的max作为答案。

时间复杂度 O(n^2)，空间复杂度O(1)

代码就不写了，就是二重循环

动态规划 dp

想办法把他拆解为规模小一点的子问题~

用dp[i]表示末尾下标为i子序列中最大之和。

  • 最后答案就是{dp[i]|i∈[0,1,2,n-1]}中最大值，这个在遍历dp[i]的时候就可以存下来
  • 那么已知dp[i-1]要怎么推出dp[i]呢
    • dp[i] = dp[i-1] + nums[i]
    • 但是注意：有可能dp[i-1]是一个复数，那还不如不加呢。所以也可能是dp[i] = nums[i]

现在时间复杂度O(n)，空间复杂度O(n)。我们还能优化一下，不新建dp[]数组，直接在传入的nums[]上操作，空间复杂度为O(1)

动态规划代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var maxSubArray = function(nums) {
  6.     const len = nums.length
  7.     let mx = nums[0]
  8.     for(let i = 1; i < len; i++){
  9.         nums[i] = Math.max(0, nums[i-1]) + nums[i]
  10.         if(nums[i] > mx)mx = nums[i]
  11.     }
  12.     return mx
  13. };

前缀和

前缀和，一种降低查询操作复杂度的预处理手段，一句话概述的话就是这样：让s[i]记录下标从0到i的和，那么[i, j]的和就等于s[j] - s[i-1]

那么在这里该怎么结合在一起？

当s[i]是s[0],s[1],...s[j-1]最小值的时候，s[j]-s[i]就是以 j 为下标的子序列之和的最大值了

我们这里只需要临时存储s[i] 就好了，所以直接用sum 变量就行

时间复杂度为O(n)，空间复杂度为O(1)

前缀和代码

  1. /**前缀和
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var maxSubArray = function(nums) {
  6.   const len = nums.length
  7.     let mx = nums[0], mn = 0, sum = 0
  8.     for(let i = 0;i < len; i++){
  9.         sum += nums[i]
  10.         if(sum - mn > mx) mx = sum - mn
  11.         if(sum < mn) mn = sum
  12.     }
  13.     return mx
  14. };

112. 路径总和|容易、高频

题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

解题思路

这题形式上有点像两数之和有没有

看到这样的一个二叉树，我们可以想到使用深度优先搜索 dfs，来做这道题目。这里前中后序都无所谓

那么 dfs 递归函数的参数就应该是

  • 二叉树的节点
  • 一个用于判断是否达到目标和的计数器
    • 如果用加法就比较麻烦，每一处都需要传入 targetSum 来在函数体内判断，我们可以用减法，第一次调用传入的是 targetSum ，后面判断是否为0就ok了

因为只需要搜索其中一条符合条件的路径，那么递归函数就需要一个返回值，当遇到合适的路径就及时返回，不要再继续搜索了

⭐：

  • 节点的值可以为负，所以也不能剪枝，必须遍历完一整条路径

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @param {number} targetSum
  12.  * @return {boolean}
  13.  */
  14. // var hasPathSum = function(root, targetSum) {
  15. //     const traversal = (node, cnt) =>{
  16. //         if(cnt === 0 && !node.left && !node.right) return true // 找到符合题意的叶子节点
  17. //         if(!node.left && !node.right) return false //不合适的叶子节点就直接返回
  18. //         // 往左右子节点找(如果子节点不为空的话)
  19. //         if(node.left && traversal(node.left, cnt - node.left.val)) return true
  20. //         if(node.right && traversal(node.right, cnt - node.right.val)) return true
  21. //         return false //都没找到合适的就 false
  22. //     }
  23. //     if(!root) return false //空树
  24. //     return traversal(root, targetSum - root.val)
  25. // };
  26. //将上面的 traversal 融合进来，简化代码
  27. var hasPathSum = function(root, targetSum) {
  28.     if(!root) return false
  29.     if(!root.left && !root.right && targetSum === root.val) return true
  30.    return (
  31.         hasPathSum(root.left, targetSum - root.val) ||
  32.         hasPathSum(root.right, targetSum - root.val)
  33.     );
  34. };

在最后

好了这就是本周的刷题记录与题解分享了，如果你已经按题型分类系统地刷了一遍算法面试题的各个题型，想感受一下面试题的”随机性”的话，欢迎一起~

合集仓库：okkjoo-leetcodeHot-byJs

🌊如果有所帮助，欢迎点赞关注，一起进步⛵