Leetcode热门100题刷题笔记(JavaScript实现)

LeetCode
算法
发布日期:   2022-07-07
更新日期:   2022-08-24
文章字数:   4.9k
阅读时长:   20 分
阅读次数:  

Leetcode热门100题刷题笔记

二叉树

96. 不同的二叉搜索树

题解：

  1. 递归
  2. 动态规划

【提示】

（1）递归：将数组在节点i处划分为两部分low and high，数组中不同的数都可以作为根节点。不同BST的个数= count(low, i - 1) * count(i + 1, high);

==递归函数写在主函数内会超时，暂时没弄清楚怎么回事，写在外面可以。==

const count = (low, high) => {
  	// 退出条件，空节点也算一种情况
    if (low > high) {
      return 1;
    }

    let res = 0;
		
    // 穷举
    for (let i = low; i <= high; i++) {
      let left = count(low, i - 1);
      let right = count(i + 1, high);
      res += left * right;
    }
    return res;
  }

（2）动态规划：

dp: n 个节点存在二叉排序树的个数是 dp[n]，令 f(i) 为以 i 为根的二叉搜索树的个数，则

$G(n)=f(1)+f(2)+f(3)+f(4)+…+f(n)$

$f(i) = f(i -1) * f(n - i)$

dp数组要初始化为0

var numTrees = function(n) {
  const dp = new Array(n + 1).fill(0); 
  dp[0] = 1;
  dp[1] = 1;

  for (let i = 2; i < n + 1; i++) {
    for (let j = 1; j < i + 1; j++) {
      dp[i] += dp[j - 1] * dp[i - j]; 
    }
  }

  // console.log(dp)

  return dp[n];
};

98. 验证二叉搜索树

leetcode

【提示】BST的中序遍历时按升序排列的；中序遍历递归比较前一个数与当前数的大小，当前节点的左右子树也要是BST。

if (maxVal < root.val) {
  maxVal = root.val;
} else {
  return false;
}

101. 对称二叉树

leetcode

【提示】两种思路：递归和迭代。

（1）递归

将整棵树分为左右两侧的子树，比较每个节点的外侧和内侧节点是否相同。前序位置递归，处理每一个节点然后接着往下递归。退出条件是：

if (leftNode === null && rightNode !== null) {
  return false;
} else if (leftNode !== null && rightNode === null) {
  return false;
} else if (leftNode === null && rightNode === null) {
  return true;
} else if (leftNode.val !== rightNode.val) {
  return false;
}

（2）迭代（暂时未实现，没有思路）

栈或队列都可以，一层一层的对比两侧子树的外侧节点和内侧节点

while (stack.length) {
  // 取出栈顶的两个节点
  let leftNode = stack.pop();
  let rightNode = stack.pop();

  // 如果这两个节点都为null，说明这一侧的节点都是对称的
  if (leftNode === null && rightNode === null) {
    continue;
  }
  // 如果这两个节点其中一个为null而另一个不为null或者这两个节点的值不相等，则不对称
  if ((leftNode === null && rightNode !== null) || (leftNode !== null && rightNode === null) || (leftNode.val !== rightNode.val)) {
    return false;
  }

  // 外侧的节点
  stack.push(leftNode.left);
  stack.push(rightNode.right);
  // 内侧的节点
  stack.push(leftNode.right);
  stack.push(rightNode.left);
}

102. 二叉树的层序遍历

leetcode

【提示】两层循环

while(queue,length) {
  let size = queue.length;
  let perLevel = [];
  
  // 遍历一层的节点
  while (size--) {
    ...
  }
}

104. 二叉树的最大深度

leetcode

【提示】（前序遍历-递归、层序遍历-迭代）当root不为null时，初始的深度为1。其实，如果初始深度为0的话，求的是节点的高度，根节点的高度就是最大深度。

节点深度与高度的区别

  • 二叉树节点的深度：从根节点到该节点的最长简单路径边的条数。

  • 二叉树节点的高度：从该节点到叶子结点的最长简单路径边的条数。

114. 二叉树展开为链表

leetcode

【提示】后序遍历，在根节点处的操作：

  1. 获取flatten后的左子树；
  2. 获取flatten后的右子树；
  3. root.left = null; /* 根节点的左子树置为null */
  4. root.right = left; /* 根节点的右子树设为flatten后的左子树 */
  5. 找到root的右子树的叶子结点，然后将flatten后的右子树接上去。
var flatten = function(root) {
    if (root === null) {
        return null;
    }
		
  	/* 后序遍历 */
    flatten(root.left);
    flatten(root.right);
		
  	/* 根节点处的操作 */
    let left = root.left; // 对应步骤1
    let right = root.right; // 步骤2
    
    root.left = null; // 步骤3
    root.right = left; // 步骤4
		
  
  	// 步骤5
    let p = root; // 指向根节点的指针，后面会迭代赋值，直到找到叶子结点
    while (p.right !== null) {
        p = p.right;
    }
    p.right = right;
};

105. 从前序与中序遍历序列构造二叉树

leetcode

【提示】设根节点在中序遍历中的索引为rootIndex，则前序遍历的左子树范围和右子树范围，中序遍历的左子树范围和左子树范围就可以确定了，分别是：

前序和中序构建二叉树 
preStart: 前序遍历的开始位置；
preEnd: 前序遍历的结束位置；
inStart: 中序遍历的开始位置；
inEnd: 中序遍历的结束位置；

preLeftStart: 前序遍历中，左子树的开始位置索引；
preLeftEnd: 前序遍历中，左子树的结束位置索引；
inLeftStart: 中序遍历中，左子树的开始位置索引；
inLeftEnd: 中序遍历中，左子树的结束位置索引；

preRightStart: 前序遍历中，右子树的开始位置索引；
preRightEnd: 前序遍历中，右子树的结束位置索引；
inRightStart: 中序遍历中，右子树的开始位置索引；
inRightEnd: 中序遍历中，右子树的结束位置索引；

let preLeftStart = preStart + 1;
let inLeftStart = inStart;
let inLeftEnd = rootIndex - 1;
let preLeftEnd = preLeftStart + inLeftEnd - inLeftStart;

let inRightStart = rootIndex + 1;
let inRightEnd = inEnd;
let preRightStart = preLeftEnd + 1;
let preRightEnd = preEnd;

226. 翻转二叉树

leetcode

【提示】两种解法：

  1. 深度优先遍历（前序递归）

    在每个节点处交换该节点的左右子节点。

  2. 宽度优先遍历（层序遍历）

注意

不要跟对称二叉树弄混了，对称二叉树才需要对比内侧和外侧。

538. 把二叉搜索树转换为累加树

leetcode

题解

【提示】BST 的中序遍历是有序的。将 BST 看成一个递增的有序数组，要让有序数组的每个元素是比它大的元素的累加和，则从后往前遍历这个数组即可。类比数组的遍历，BST 的中序遍历是递增的，那么将中序遍历倒置，即先遍历右子树再遍历左子树，在”倒中序遍历位置“累加和。

543. 二叉树的直径

leetcode

题解

【提示】按递归三要素来分析：

  1. 递归函数的参数：节点 node；
  2. 每个节点的处理逻辑：全局设置一个数 maxPath。后序遍历位置，分别得到当前节点左右子树的深度 L 和 R，则当前节点的直径为 max(maxPath, L + R - 1)；
  3. 返回值：节点的深度 max(L, R) + 1；
var diameterOfBinaryTree = function(root) {
  let maxPath = 0;

  const traverse = (node) => {
    if (node === null) {
      return 0;
    }

    let L = traverse(node.left);
    let R = traverse(node.right);

    maxPath = Math.max(maxPath, L + R + 1);

    return Math.max(L, R) + 1;
  }

  traverse(root);

  return maxPath - 1;
};

617. 合并二叉树

leetcode

题解

【提示】同时遍历两棵树，用 root1.left 和 root1.right “接住”递归返回的节点。

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function(root1, root2) {
  if (root1 === null || root2 === null) {
    return root1 === null ? root2 : root1;
  }
  if (root1 !== null && root2 !== null) {
    root1.val += root2.val; 
  }

  root1.left = mergeTrees(root1.left, root2.left);
  root1.right = mergeTrees(root1.right, root2.right);

  return root1;
};

437. 路径总和 III

leetcode

题解

【提示】两种解法：深度优先搜索和前缀和。

（1）深度优先搜索

计算每个节点作为路径起点时的路径和，计算量大，耗时。

  1. 递归函数的参数：节点 root，路径总和 target；
  2. 返回值：路径总和满足 target 的路径数量；
  3. 退出条件：递归到空节点，返回 0；
  4. 单层逻辑：当前节点的值是否等于 target（target 在每次递归时减去当前路径起点的 val）；

注意

主函数中也有递归的逻辑，遍历每个节点，以每个节点作为路径起点计算满足路径和为 target 的路径数量。

/* 主函数 */
var pathSum = function(root, targetSum) {
    if (root === null) {
        return 0;
    }

    let res = rootSum(root, targetSum); // 以 root 为路径起点
    res +=  pathSum(root.left, targetSum); // root 的左子树每个节点作为路径起点
    res += pathSum(root.right, targetSum); // root 的右子树每个节点作为路径起点

    return res;
};

/* 以某个节点作为路径起点时，计算满足路径总和的路径数量 */
function rootSum(root, targetSum) {
    if (root === null) {
        return 0;
    }
		
  	// 前序遍历位置
    let res = 0;

    if (root.val === targetSum) {
        res++;
    }

    res += rootSum(root.left, targetSum - root.val);
    res += rootSum(root.right, targetSum - root.val);

    return res;
}

（2）前缀和

也是递归，计算每个并存储每个节点的前缀和。

  1. 递归参数：节点 node，前缀和 prefix（hash表），当前节点的前缀和 curSum，路径总和 targetSum。
  2. 返回值：满足 targetSum 的路径数量；
  3. 退出条件：递归到空节点，返回 0；
  4. 单层逻辑：计算当前节点的前缀和，从前缀和中获取前缀和为 (curSum - targetSum) 的值，这个值就是满足条件的路径数量。将当前节点的前缀和存储起来，分别递归当前节点的左右子树，回溯时将相应的前缀和 -1。
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
var pathSum = function(root, targetSum) {
    if (root === null) {
        return 0;
    }

    const prefix = new Map();
    prefix.set(0, 1); // 初始化前缀和

    let res = dfs(root, prefix, 0, targetSum);

    return res;
};

function dfs(node, prefix, curSum, targetSum) {
    if (node === null) {
        return 0;
    }

    let res = 0;

    curSum += node.val;
    res = prefix.get(curSum - targetSum) || 0;
    prefix.set(curSum, (prefix.get(curSum) || 0) + 1);

    res += dfs(node.left, prefix, curSum, targetSum);
    res += dfs(node.right, prefix, curSum, targetSum);

    prefix.set(curSum, (prefix.get(curSum) || 0) - 1);
    
    return res;
}

124. 二叉树中的最大路径和

leetcode

题解

【提示】分析最大路径和为：当前节点+左子树+右子树。

  • 左子树的贡献值（左子树的最大路径和）；
  • 右子树的贡献值（右子树的最大路径和）；

递归四部曲：

  1. 递归参数：节点 node；
  2. 返回值：每个节点的最大贡献值，即 node.val + max(leftPathSum, rightPathSum)；
  3. 退出条件：递归到空节点，返回贡献值 0。
  4. 单层逻辑：后序遍历位置，先递归得到左右子树的最大贡献值，然后计算最大路径和 node.val + leftPathSum + rightPathSum，在每个节点处比较得到 maxPathSum。
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function(root) {
    let maxPathSum = -Infinity;

    function traverse(node) {
        if (node === null) {
            return 0;
        }
        let leftPathSum = Math.max(traverse(node.left), 0);
        let rightPathSum = Math.max(traverse(node.right), 0);
      
				// 后序遍历位置
        let pathSum = node.val + leftPathSum + rightPathSum; // 计算最大路径和
        maxPathSum = Math.max(maxPathSum, pathSum); // 比较
        return node.val + Math.max(leftPathSum, rightPathSum); // 返回当前节点的最大贡献值
    }

    traverse(root);
    return maxPathSum;
};

动态规划

01背包

53. 最大子数组和

leetcode

题解

【提示】目前只实现了暴力双循环和贪心的解法，还有动态规划和分治法两种解法。

（1）贪心

如果连续和小于等于0，那么此时的子数组和对最大子数组和没有贡献，将子数组和重置为0，从下一个数继续加。

（2）动态规划

  • dp[i]: 表示以nums[i]结尾的最大子数组和；
  • 递推公式：dp[i] = max(dp[i - 1] = nums[i], nums[i]);
  • 初始化：dp[0] = nums[0];

（3）分治法

分情况讨论：

  1. 最大子数组和在中间位置的两边；
  2. 最大子数组和跨越中间位置；

分别求出上面两种情况的子数组和，最大的就是最大子数组和；

// 二分法，递归求中间位置两边的子数组和，并与跨越中间位置的最大子数组和比较
function maxSubArrayHelper(nums, left, right) {
  if (left === right) {
    return nums[left];
  }

  let mid = Math.floor((left + right) / 2);
  let leftSum = maxSubArrayHelper(nums, left, mid);
  let rightSum = maxSubArrayHelper(nums, mid + 1, right);
  let midSum = findMaxCrossingSubArray(nums, left, mid, right);
  return Math.max(leftSum, rightSum, midSum);
}

/* 求跨越中间位置的最大子数组和 */
function findMaxCrossingSubArray(nums, left, mid, right) {
  // 虽然求左右两边的最大子数组和用的贪心，但是与贪心解法又有差异，sum没有在循环中置为0
  let leftSum = -Infinity;
  let sum = 0;
  for (let i = mid; i >= left; i--) {
    sum += nums[i];
    leftSum = Math.max(leftSum, sum);
  }

  let rightSum = -Infinity;
  sum = 0;

  for (let i = mid + 1; i <= right; i++) {
    sum += nums[i];
    rightSum = Math.max(rightSum, sum);
  }
  return (leftSum + rightSum);
}

5. 最长回文子串

leetcode

题解

【提示】中心向两边扩散（双指针），使用动态规划优化（空间换时间）

中心向两边扩散，定义 left 和 right 指针，分别指向当前字符的左右字符；

  1. 如果 left 处的字符与当前字符相同，则 left–，直到不相等；
  2. 如果 right 处的字符与当前字符相同，则 right++，直到不相等；
  3. 如果 left 和 right 指向的字符相同，则同时分别向左右移动，left–, right++，直到不相等；

需要注意边界：left >= 0, right < s.length；

动态规划优化：定义 dp 数组为 dp[i][j]，表示 i 到 j 范围内的子串是否为回文子串；

递推公式：如果 dp[i + 1][j - 1] = true 并且 i 和 j 指向的字符相同，则 dp[i][j] = true。

for (let r = 1; r < s.length; r++) {
  for (let l = 0; l < r; l++) {
    if (s.charAt(l) === s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
      // r - l <= 2 表示 r 和 l 之间的距离不超过 2,
      dp[l][r] = true;
      len = r - l + 1;
      if (len > maxLen) {
        maxLen = len;
        maxStart = l;
        maxEnd = r;
      }
    }
  }

416. 分割等和子集

leetcode

题解

【提示】抽象问题为01背包问题。

  • 背包容量为数组和的一半，即sum / 2；
  • 如果dp[sum/2]===sum/2，则return true，否则return false；

494. 目标和

leetcode

题解

【提示】将问题抽象为01背包。target不能直接作为背包容量，因为此时物品的价值有两种状态。由于nums数组中的数字有正负两种情况，那么构成的表达式可以分成三部分：正数和+负数和=target，而正数和-负数和=sum（数组和）。于是问题转换为求背包容量为正数和时，装满背包有多少种情况。公式化：

由 $positive+negetive=target, positive-negetive=sum$，有：

$positive = (sum+target)/2$

这里注意，可能positive<0，此时positive=-positive（转换成正数和，因为数组中都是正整数）

完全背包

零钱兑换

leetcode

题解

【提示】抽象问题为完全背包，amount为背包容量，求最小的个数。

递推公式：dp[j] = min(dp[j], dp[j - coins[i]] + 1)；

初始化：dp[0] = 0，其他的dp[j] = Infinity；

279. 完全平方数

leetcode

题解

【提示】抽象为完全背包问题，求最小个数。

递推公式：dp[j] = min(dp[j], dp[j - i * i] + 1)；

初始化：dp[0] = 0，其他dp[j] = Infinity；

注意

这里的物品应该抽象为i * i，即完全平方数，因为背包里面只能装完全平方数。

打家劫舍

198. 打家劫舍

leetcode

【提示】难点在确定 dp 数组的含义。

  1. dp 数组的含义：dp[i] 表示偷 下标 i 以内的房间，能够偷到的最高金额。
  2. 递推公式：max(dp[i - 1], dp[i - 2] + nums[i])
    • 不偷房间 i : dp[i - 1]；
    • 偷房间 i : dp[i - 2] = nums[i]；
  3. 初始化：从递推公式看出需要初始化 dp[0] 和 dp[1]；
    • dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])；

337. 打家劫舍 III

leetcode

题解

【提示】房屋分布在一颗二叉树上，此时需要遍历这棵树。两种解法：递归和动态规划；

（1）递归（JavaScript 超时）

后序遍历，利用返回值求解。得到偷当前节点和不偷当前节点时的最大金额，然后取两者的最大值。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    const umap = new Map();

    const traverse = (root) => {
        if (root === null) {
            return 0;
        }
        if (root.left === null && root.right === null) {
            return root.val;
        }
				
      	// 记忆化递归，利用 Map 将遍历过的节点的返回值保存起来，再次遍历到该节点直接返回
        if (umap.get(root)) {
            return map.get(root);
        }

        let val1 = root.val;
      	// 偷当前节点
        if (root.left) {
            val1 += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right) {
            val1 += rob(root.right.left) + rob(root.right.right)
        }
				
      	// 不偷当前节点
        let val2 = rob(root.left) + rob(root.right);

        umap.set(root, Math.max(val1, val2)); // 保存当前节点的值
        return Math.max(val1, val2);
    }

    return traverse(root);
};

（2）动态规划（树形 DP）

利用数组记忆节点的状态。这里利用长度为 2 的数组记录偷当前节点和不偷当前节点时的状态，下标 0 表示不偷当前节点，1 表示偷。

dp 数组的含义：dp[0] 表示不偷当前节点的最大金额， dp[1] 表示偷当前节点时的最大金额。

var rob = function(root) {
  const traverse = (cur) => {
    if (cur === null) {
      return [0, 0];
    }

    let left = traverse(cur.left);
    let right = traverse(cur.right);

    let val1 = cur.val + left[0] + right[0]; // 投当前节点
    let val2 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // 不偷当前节点

    return [val2, val1]; // 注意这里的返回值与 dp 数组的定义一致
  }

  const res = traverse(root);
  return Math.max(res[0], res[1]);
};

深度优先搜索（回溯）

200. 岛屿数量

leetcode

题解1-通用解法

题解2-本题解法

【提示】岛屿问题是一类在网格中的深度搜索问题，类似于二叉树和一般的一维数组的搜索（N叉树），只是网格深度搜索需要特别注意标记已遍历过的节点，并且搜索的方向有4个。求岛屿的数量，在宽度遍历中count++。

岛屿问题的通用框架：

  • '0'表示海洋；
  • '1'表示陆地（还没遍历过）；
  • '2'表示陆地（已经遍历过）；
const row = grid.length;
const column = grid[0].length;

/* 宽度遍历 */
for (let i = 0; i < row; i++) {
  for (let j = 0; j < column; j++) {
    if (grid[i][j] === '1') {
      dfs(grid, i, j);
      具体操作(求岛屿数量)
    }
  }
}

/* 深度遍历 --- 是否有返回值根据题目要求定 */
function dfs(grid, myRow, myColumn) {
  // base case---退出递归的条件
  if (!inArea(grid, myRow, myColumn)) {
    return ;
  }
  
  grid[myRow][myColumn] = '2'; // 标记已遍历过的陆地，防止重复遍历
  
  // 分四个方向分别深度搜索
  dfs(grid, myRow - 1, myColumn);
  dfs(grid, myRow + 1, myColumn);
  dfs(grid, myRow, myColumn - 1);
  dfs(grid, myRow, myColumn + 1);
}

/* 判断这个位置是否在网格上 */
function inArea(grid, myRow, myColumn) {
  const row = grid.length;
  const column = grid[0].length;

  return (myRow >= 0 && myRow < row) && (myColumn >= 0 && myColumn < column);
}

463. 岛屿的周长

leetcode

题解

【提示】其实求岛屿的周长就是求与边界相邻的岛屿的边缘和与海洋相邻的岛屿的边缘，如图所示

将岛屿周长中的边分为两类

当dfs即遇到上图两种情况时返回1，即周长加1。

236. 二叉树的最近公共祖先

leetcode

【提示】后序遍历，把整棵树分为三部分：左子树、根节点、右子树。

  • 递归参数：root, p, q；返回值：root（最近公共祖先）；

  • 退出条件：

    if (root === p || root === q || root === null) {
  return root;
}

  • 后序遍历，分别得到左右子树递归的结果，然后判断左右子树值的情况；

    • left和right都不为空，则返回root；
    • left为空，right不为空，则返回right；
    • left不为空，right为空，则返回left；
    • left和right都为空，则返回null；

数组

两数之和

leetcode

题解

【提示】num1+num2=target，那么 num2=target-num1，即 num1 和 num2 之间存在映射关系。用 HashMap 来存储 key: nums[i], value: i。在一次遍历 nums 的过程中，找 map 中是否有 target-nums[i]，如果存在就返回结果；不存在就把 nums[i] 存到 map 里面。

三数之和

leetcode

题解

【提示】找到数组 nums 中 a+b+c=0 的序列。用回溯法（组合+去重）超时了。用双指针，先对数组排序，然后用两个指针 left 和 right 分别指向当前元素的后一个和数组的最后一位，随后 while 循环移动双指针找到符合条件的序列。注意移动指针的过程需要去重。

for (let i = 0; i < nums.length; i++) {
  // 当前的数大于 0，三个数之和肯定大于 0
  if (nums[i] > 0) {
    break;
  }
  // 去重
  if (i > 0 && nums[i] === nums[i - 1]) {
    continue;
  }
  left = i + 1;
  right = nums.length - 1;
  // 双指针移动
  while (left < right) {
    let sum = nums[i] + nums[left] + nums[right];
    if (sum < 0) {
      left++;
    } else if (sum > 0) {
      right--;
    } else {
      res.push([nums[i], nums[left], [nums[right]]]);
      while (left < right && nums[left] === nums[left + 1]) left++; // 去重
      while (left < right && nums[right] === nums[right - 1]) right--; // 去重
      left++;
      right--;
    }
  }
}
文章作者: elegantlee
文章链接: https://elegantlee.github.io/2022/07/07/suan-fa/leetcode-re-men-100-ti/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 elegantlee !
LeetCode
赏
评论
  目录