力扣热题100(前10道题目)

前言

算法题几乎是面试必考的，许多同学一看到算法题就是一个头两个大，所以笔者这次准备把力扣热题100写成文章与jym一起学习，估计会分为10篇文章来写。在这个过程中会分享一些自己刷题的想法和思路，让大家能够轻松看懂，这些题目我会采用js来写，有看不懂js的同学可以看个思路然后换成自己熟悉的语言去写🔥 LeetCode 热题 HOT 100

在每道题目之前我都会把对应的题目链接贴出来，方便大家可以看完我的解法再去力扣上刷题，而且这些题目我会尽可能多种解法去写，大家可以参考一下。

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

示例 1：

1输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
2输出： 3
3解释： 节点 5 和节点 1 的最近公共祖先是节点 3 。
4

示例 2：

1输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
2输出： 5
3解释： 节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
4

示例 3：

1输入： root = [1,2], p = 1, q = 2
2输出： 1
3

思路

如果当前节点是空节点，就返回当前节点，如果当前节点是p或者q也就返回当前节点，当左右子树都能找到时，他们的公共祖先也就是当前节点，只有左子树能找到就返回左子树递归的结果，只有右子树能找到就返回右子树递归的结果。

1var lowestCommonAncestor = function (root, p, q) {
2    if (!root || root === p || root === q) return root
3    let left = lowestCommonAncestor(root.left, p, q)
4    let right = lowestCommonAncestor(root.right, p, q)
5    if (left && right) return root
6    if (left) return left
7    if (right) return right
8};
9
10

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

1输入： head = [1,2,2,1]
2输出： true
3

示例 2：

1输入： head = [1,2]
2输出： false
3

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解法一

思路

将链表的每个值都存进数组里，然后使用双指针来比较前后两端的元素，一个指针从起点向中间移动看，另一个指针从终点向中间移动。

1var isPalindrome = function (head) {
2    const res = []
3    while (head) {
4        res.push(head.val)
5        head = head.next
6    }
7    for (let i = 0, j = res.length - 1; i < j; i++, j--) {
8        if (res[i] !== res[j]) return false
9    }
10    return true
11};
12

由于要逐个访问n个元素，所以他的时间复杂度和空间复杂度都是O(n),来看下面的这个解法，就能让他的空间复杂度变成O(1)。

解法二

思路

找到中间节点并反转链表，如果链表有奇数个节点，就找他正中间的节点，如果链表有偶数个节点，就找他正中间右边的节点。

找到中间节点后把中间节点到链表末尾反转如上图所示，把他的头节点记为head2，然后从head2开始，依次遍历原链表的最后一个节点、倒数第二个节点...，最后同时遍历head和head2，循环比较两个值是否相等，相等就返回true，不等就返回false，循环结束后如果没有返回false，就说明链表是回文的。用这个解法前可以先刷下这两道题目876. 链表的中间结点和206. 反转链表

1function midNode(head) {
2    let slow = head
3    let fast = head
4    while (fast && fast.next) {
5        slow = slow.next
6        fast = fast.next.next
7    }
8    return slow
9}
10function reverseList(head) {
11    let p1 = head
12    let p2 = null
13    while (p1) {
14        let tem = p1.next
15        p1.next = p2
16        p2 = p1
17        p1 = tem
18    } return p2
19}
20var isPalindrome = function (head) {
21    const mid = midNode(head)
22    let head2 = reverseList(mid)
23    while (head2) {
24        if (head.val !== head2.val) return false
25        head = head.next
26        head2 = head2.next
27    }
28    return true
29};
30

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1输入: temperatures = [73,74,75,71,69,72,76,73]
2输出: [1,1,4,2,1,1,0,0]
3

示例 2:

1输入: temperatures = [30,40,50,60]
2输出: [1,1,1,0]
3

示例 3:

1输入: temperatures = [30,60,90]
2输出: [1,1,0]
3

提示：

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

解法一

思路

直接暴力解法，对于每个温度，向后遍历查找第一个比他高的温度，然后计算间隔天数，用一个数组来存放0，对于比他高的温度后者-前者就是这个天数

1/**
2 * @param {number[]} temperatures
3 * @return {number[]}
4 */
5var dailyTemperatures = function (temperatures) {
6    const res = new Array(temperatures.length)
7    for (let i = 0; i < temperatures.length; i++) {
8        res[i] = 0
9        for (let j = i + 1; j < temperatures.length; j++) {
10            if (temperatures[j] > temperatures[i]) {
11                res[i] = j - i
12                break
13            }
14        }
15    }
16    return res
17};
18

这种解法是最直观的，但是这种解法在力扣上提交会超时，因为他的时间复杂度是O(n²)，而力扣上的测试用例包含长度高达10⁵的数组，在最坏情况下要执行10¹⁰次比较操作，所以会超时

解法二

思路

单调栈，不主动寻找每个温度后面的第一个高温，当遇到高温时，回头解决之前没有解决的低温问题，用栈来存储温度索引，保持栈中的温度值单调递增。

1/**
2 * @param {number[]} temperatures
3 * @return {number[]}
4 */
5var dailyTemperatures = function (temperatures) {
6    const res = new Array(temperatures.length).fill(0)
7    const stack = []
8    for (let i = 0; i < temperatures.length; i++) {
9        while (stack && temperatures[i] > temperatures[stack[stack.length - 1]]) {
10            const index = stack.pop()
11            res[index] = i - index
12        }
13        stack.push(i)
14    }
15    return res
16};
17

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

转存失败，建议直接上传图片文件

1输入： root = [4,2,7,1,3,6,9]
2输出： [4,7,2,9,6,3,1]
3

示例 2：

转存失败，建议直接上传图片文件

1输入： root = [2,1,3]
2输出： [2,3,1]
3

示例 3：

1输入： root = []
2输出： []
3

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

思路

用深度优先搜索(DFS)递归的交换每个节点的左右子节点，核心就是利用分治思想将大问题分解为小问题，然后递归的解决每个子问题

1var invertTree = function (root) {
2    if (!root) return null
3    return {
4        val: root.val,
5        left: invertTree(root.right),
6        right: invertTree(root.left)
7    }
8};
9
10

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

转存失败，建议直接上传图片文件

1输入： matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
2输出： 4
3

示例 2：

转存失败，建议直接上传图片文件

1输入： matrix = [["0","1"],["1","0"]]
2输出： 1
3

示例 3：

1输入： matrix = [["0"]]
2输出： 0
3

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'

思路

用动态规划来解决，以每个位置为右下角，计算能形成的最大正方形的边长，用dp[i][j]来表示以(i,j)为右下角顶点的，只包含'1'的最大正方形的边长，其状态转移方程为dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，比如说要形成一个边长为k的正方形，就必须满足上方能形成变成为k-1的正方形，左方能形成边长为k-1的正方形，左上方能形成边长为k-1的正方形，只有这三个条件都满足时，才能在当前位置扩展成边长为k的正方形

1var maximalSquare = function (matrix) {
2    let maxSideLen = 0
3    let dp = new Array(matrix.length)
4    for (let i = 0; i < matrix.length; i++) {
5        dp[i] = new Array(matrix[i].length).fill(0)
6        for (let j = 0; j < matrix[i].length; j++) {
7            if (matrix[i][j] === '1') {
8                if (i === 0 || j === 0) {
9                    dp[i][j] = 1
10                } else {
11                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1],dp[i - 1][j - 1]) + 1
12                }
13                maxSideLen = Math.max(maxSideLen, dp[i][j])
14            }
15        }
16    }
17    return maxSideLen * maxSideLen
18}
19
20

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

1输入: [3,2,1,5,6,4], k = 2
2输出: 5
3

示例 2:

1输入: [3,2,3,1,2,4,5,5,6], k = 4
2输出: 4
3

提示：

1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

思路

可以使用快速选择的思想来解决，要找第k个最大元素，其实就相当于找第(n-k)小的元素，我们可以先选中一个基准值，然后使用双指针从数组两端向中间扫描，将小于基准值的元素移到左边，大于基准值的元素移到右边，完成一次分区操作后，再根据目标元素应该所在区域来决定继续在左半部分还是右半部分进行递归搜索，这样的话每次都能排除掉一部分元素而不需要处理整个数组

1/**
2 * @param {number[]} nums
3 * @param {number} k
4 * @return {number}
5 */
6var findKthLargest = function (nums, k) {
7  const n = nums.length;
8  return quickSelect(nums, 0, n - 1, n - k); // n-1是数组长度-1，n-k是第k大的元素对应的下标
9};
10
11function quickSelect(nums, l, r, k) {
12  // l 和 r 是左右边界，k 是要找的第 k 小元素的下标
13  if (l === r) return nums[k];
14  const x = nums[l];
15  let i = l - 1,
16    j = r + 1; // 因为下面的do while循环会先自增或自减一次，所以这里要-1和+1
17  while (i < j) {
18    // i<j 说明还没有扫描完的数组
19    do i++;
20    while (nums[i] < x);
21    do j--;
22    while (nums[j] > x);
23    if (i < j) {
24      [nums[i], nums[j]] = [nums[j], nums[i]];
25    }
26  }
27  if (k <= j) {
28    return quickSelect(nums, l, j, k);
29  } else {
30    return quickSelect(nums, j + 1, r, k);
31  }
32}
33
34

1输入： head = [1,2,3,4,5]
2输出： [5,4,3,2,1]
3

示例 2：

1输入： head = [1,2]
2输出： [2,1]
3

示例 3：

1输入： head = []
2输出： []
3

思路

迭代法，先创建一个空链表，然后用头插法依次把节点插入到这个新链表的头部，就得到了反转后的链表

1var reverseList = function (head) {
2    let p1 = head
3    let p2 = null
4    while (p1) {
5        let temp = p1.next
6        p1.next = p2
7        p2 = p1
8        p1 = temp
9    }
10    return p2
11};
12

《力扣热题100(前10道题目)》是转载文章，点击查看原文。

力扣热题100(前10道题目)

前言

160. 相交链表

解法一

思路

解法二

思路

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

思路

234. 回文链表

解法一

思路

解法二

思路

739. 每日温度

解法一

思路

解法二

思路

226. 翻转二叉树

思路

221. 最大正方形

思路

215. 数组中的第K个最大元素

思路

208. 实现 Trie (前缀树)

207. 课程表

206. 反转链表

思路