❌

普通视图

发现新文章，点击刷新页面。
昨天以前首页

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

✇掘金 前端
作者 少年姜太公
2025年10月30日 01:10

前言

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

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

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交 ：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

 

示例 1：

输入： intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出： Intersected at '8'
解释： 相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

 

示例 2：

输入： intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出： Intersected at '2'
解释： 相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
解法一
思路

如果我们从两个链表的最后一个节点往前遍历，那么相交的这个节点其实就是两个链表最后一个相等的节点，一旦不相等了，说明这个节点的前一个节点就是相交节点，所以我们可以把这两个链表分别放进两个数组里，然后倒序遍历

var getIntersectionNode = function (headA, headB) {
    const list1 = []
    const list2 = []
    while (headA) {
        list1.push(headA)
        headA = headA.next
    }
    while (headB) {
        list2.push(headB)
        headB = headB.next
    }
    let i = list1.length - 1
    let j = list2.length - 1
    let temp
    while (i && j && list1[i] === list2[j]) {
        temp = list1[i]
        i--
        j--
    }
    return temp
};

因为新增了数组，所以这其实并不是最优解，他的时间复杂度和空间复杂度都为O(m+n)，m为headA的长度，n为headB的长度。

解法二
思路

：双指针法，先初始化两个指针p = headA,q = headB，然后不断循环直到p = q，每次循环让p和q各向后走一步，当p为空时，让p为headB，q为空时，q为headA，在循环结束时，如果两个链表相交，那么p和q都会在相交的起始节点处就可以返回p了，如果不相交，那么他们都到空节点了，也可以返回p，即空节点

代码如下:

var getIntersectionNode = function (headA, headB) {
    let p = headA
    let q = headB
    while (p !== q) {
        p = p ? p.next : headB
        q = q ? q.next : headA
    }
    return p
};

这种解法的时间复杂度为O(m+n)，空间复杂度为O(1)

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

示例 1：

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

示例 2：

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

示例 3：

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

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

var lowestCommonAncestor = function (root, p, q) {
    if (!root || root === p || root === q) return root
    let left = lowestCommonAncestor(root.left, p, q)
    let right = lowestCommonAncestor(root.right, p, q)
    if (left && right) return root
    if (left) return left
    if (right) return right
};

234. 回文链表

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

 

示例 1：

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

示例 2：

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

 

提示：

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

 

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

解法一
思路

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

var isPalindrome = function (head) {
    const res = []
    while (head) {
        res.push(head.val)
        head = head.next
    }
    for (let i = 0, j = res.length - 1; i < j; i++, j--) {
        if (res[i] !== res[j]) return false
    }
    return true
};

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

解法二
思路

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

image.png

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

function midNode(head) {
    let slow = head
    let fast = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}
function reverseList(head) {
    let p1 = head
    let p2 = null
    while (p1) {
        let tem = p1.next
        p1.next = p2
        p2 = p1
        p1 = tem
    } return p2
}
var isPalindrome = function (head) {
    const mid = midNode(head)
    let head2 = reverseList(mid)
    while (head2) {
        if (head.val !== head2.val) return false
        head = head.next
        head2 = head2.next
    }
    return true
};

739. 每日温度

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

 

示例 1:

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

示例 2:

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

示例 3:

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

 

提示：

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100
解法一
思路

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

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
    const res = new Array(temperatures.length)
    for (let i = 0; i < temperatures.length; i++) {
        res[i] = 0
        for (let j = i + 1; j < temperatures.length; j++) {
            if (temperatures[j] > temperatures[i]) {
                res[i] = j - i
                break
            }
        }
    }
    return res
};

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

解法二
思路

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

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
    const res = new Array(temperatures.length).fill(0)
    const stack = []
    for (let i = 0; i < temperatures.length; i++) {
        while (stack && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const index = stack.pop()
            res[index] = i - index
        }
        stack.push(i)
    }
    return res
};

226. 翻转二叉树

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

 

示例 1：

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

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

示例 2：

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

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

示例 3：

输入： root = []
输出： []

 

提示：

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

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

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

221. 最大正方形

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

 

示例 1：

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

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

示例 2：

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

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

示例 3：

输入： matrix = [["0"]]
输出： 0

 

提示：

  • 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的正方形

var maximalSquare = function (matrix) {
    let maxSideLen = 0
    let dp = new Array(matrix.length)
    for (let i = 0; i < matrix.length; i++) {
        dp[i] = new Array(matrix[i].length).fill(0)
        for (let j = 0; j < matrix[i].length; j++) {
            if (matrix[i][j] === '1') {
                if (i === 0 || j === 0) {
                    dp[i][j] = 1
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1],dp[i - 1][j - 1]) + 1
                }
                maxSideLen = Math.max(maxSideLen, dp[i][j])
            }
        }
    }
    return maxSideLen * maxSideLen
}

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

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

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

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

 

示例 1:

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

示例 2:

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

 

提示：

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

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

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const n = nums.length;
  return quickSelect(nums, 0, n - 1, n - k); // n-1是数组长度-1，n-k是第k大的元素对应的下标
};

function quickSelect(nums, l, r, k) {
  // l 和 r 是左右边界，k 是要找的第 k 小元素的下标
  if (l === r) return nums[k];
  const x = nums[l];
  let i = l - 1,
    j = r + 1; // 因为下面的do while循环会先自增或自减一次，所以这里要-1和+1
  while (i < j) {
    // i<j 说明还没有扫描完的数组
    do i++;
    while (nums[i] < x);
    do j--;
    while (nums[j] > x);
    if (i < j) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  if (k <= j) {
    return quickSelect(nums, l, j, k);
  } else {
    return quickSelect(nums, j + 1, r, k);
  }
}

208. 实现 Trie (前缀树)

207. 课程表

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

 

示例 1：

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

示例 2：

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

示例 3：

输入： head = []
输出： []
思路

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

var reverseList = function (head) {
    let p1 = head
    let p2 = null
    while (p1) {
        let temp = p1.next
        p1.next = p2
        p2 = p1
        p1 = temp
    }
    return p2
};
❌
❌