破酥 | C4iN
LeetCodeHot100-Hard

LeetCodeHot100-Hard

2024年09月09日 3.9k 字 大概 18 分钟

本文章用于记录刷LeetCodeHot100 hard遇到的知识点和解题思路。

接雨水-双指针

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

解法一：快慢指针

这个是我第一次见到这题的解法，很直观，但是很慢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function trap(height: number[]): number {
    // 快慢指针
    // 快指针遍历慢指针后面的元素，如果nums[slow] > nums[fast]则说明存在水坑
    // 否则说明没有水坑或者水坑结束，此时将慢指针移动到快指针位置
    let result = 0
    let slow = 0
    // 水坑闭合标志
    let isClose = false
    if (height.length < 3) return 0
    while (slow < height.length) {
        let value = 0
        let fastValue = 0
        for (let fast = slow + 1 ; fast < height.length ; fast++) {
            if (height[slow] > height[fast]) {
                isClose = false
                value += height[slow] - height[fast]
                // 存下fast遍历过的最大高度
                fastValue = Math.max(height[fast], fastValue)
                continue
            } else if (height[slow] <= height[fast]){
                isClose = true
                slow = fast - 1
                break
            }
        } 
        // 完成一次水坑寻找后自增
        if (isClose) {
            slow++
            result += value
            continue
        } else {
            // 去掉多余的高度，再寻找一次
            height[slow] = fastValue
            continue
        }
    }

    return result
};

解法二：动态规划

我们定义left[i]表示下标 i 位置及其左边的最高柱子的高度，定义right[i]表示下标 i 位置及其右边的最高柱子的高度。那么下标 i 位置能接的雨水量为min(left[i],right[i])−height[i]。我们遍历数组，计算出left[i]和right[i]，最后答案为 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function trap(height: number[]): number {
    const n = height.length;
    const left: number[] = new Array(n).fill(height[0]);
    const right: number[] = new Array(n).fill(height[n - 1]);
    for (let i = 1; i < n; ++i) {
        left[i] = Math.max(left[i - 1], height[i]);
        right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        ans += Math.min(left[i], right[i]) - height[i];
    }
    return ans;
}

解法三：首尾双指针

我们使用双指针分别从左侧和右侧遍历height，这样我们只需要考虑各个方向由低-高柱子形成的水坑就可以了，最后将左右侧得到的值加到结果数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function trap(height: number[]): number {
    let left = 0
    let result = 0
    let value = 0

    for (let i = 0 ; i < height.length ; i++) {
        // 如果遇到高度大于当前左指针元素高度的，说明形成了一个完整的水坑
        if (height[i] >= height[left]) {
            result += value
            value = 0
            left = i
        } else {
            value += height[left] - height[i]
        }
    }

    value = 0
    let right = height.length - 1
    for (let i = height.length - 1 ; i >= left ; i--) {
        // 如果遇到高度大于当前右指针元素高度的，说明形成了一个完整的水坑
        if (height[i] >= height[right]) {
            result += value
            value = 0
            right = i
        } else {
            value += height[right] - height[i]
        }
    }

    return result
};

滑动窗口最大值-子串

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

解法一-双循环

使用双循环时间复杂度为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function maxSlidingWindow(nums: number[], k: number): number[] {
    let result: number[] = []

    for (let i = 0; i < nums.length - k + 1; i++) {
        let l = i
        let r = l + k - 1
        let currentMax = nums[l]
        while ( r >= l ) {
            currentMax = Math.max(Math.max(nums[l], nums[r]), currentMax)
            l++
            r--
        }
        result.push(currentMax)
    }

    return result
};

我们引入单调队列来降低复杂度。

解法二-单调队列

对于窗口里的元素{2, 3, 5, 1 ,4}，单调队列里只维护{5, 4} 就够了，保持单调队列里单调递减，此时队列出口元素就是窗口里最大元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
function maxSlidingWindow(nums: number[], k: number): number[] {
    let result: number[] = []

    // 单调递减队列
    class MonoQueue {
        private queue: number[]
        constructor() {
            this.queue = []
        }

        // 入队，value如果大于队尾元素，则将队尾元素删除，
        // 直至队尾元素大于value，或者队列为空
        public enqueue(value: number) {
            let bottom = this.queue[this.queue.length - 1]
            while (bottom !== undefined && bottom < value) {
                this.queue.pop()
                bottom = this.queue[this.queue.length - 1]
            }
            this.queue.push(value)
        }
        // 出队，只有当队头元素等于value，才出队
        public dequeue(value: number) {
            let top = this.top()
            if (top !== undefined && top === value) {
                console.log("dequeue top ", this.queue[0])
                this.queue.shift()
            }
        }
        // 获取栈顶元素，即当前滑动窗口最大值
        public top() {
            return this.queue[0]
        }
    }
    
    const numsQueue: MonoQueue = new MonoQueue()

    let l = 0
    let r = 0

    // 创建滑动窗口
    while (r < k) {
        numsQueue.enqueue(nums[r++])
    }

    result.push(numsQueue.top())

    // 获得滑动窗口最大值
    for ( ; r < nums.length ; l++, r++) {
        numsQueue.enqueue(nums[r])
        numsQueue.dequeue(nums[l])
        result.push(numsQueue.top())
    }

    return result
};

我们创建一个单调队列对象，封装需要的方法，具体的解释看代码的注释。这里需要注意的是，当我们创建完滑动窗口时，应立即把当前窗口最大值存入结果中，否则会出现遗漏。

接下来我们来看一个优化后的解法，相对于上面的解法比较抽象：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function maxSlidingWindow(nums: number[], k: number): number[] {
    let result: number[] = []
    // 单调队列，存储元素对应索引
    let queue: number[] = []
    
    // 获得滑动窗口最大值
    for (let i = 0 ; i < nums.length ; i++) {
        // 当前值
        let value = nums[i]
        // 入队，value如果大于队尾元素，则将队尾元素删除
        // 直至直至队尾元素大于value，或者队列为空
        while (queue.length && nums[queue[queue.length - 1]] <= value) {
            queue.pop()
        }
        // 将当前值value的索引加入队尾
        queue.push(i)

        // 出队，只有当前元素索引i与队首元素索引差值为窗口大小
        // 即是一个完整滑动窗口时，将队首元素索引出队
        if (i - queue[0] + 1 > k) {
            queue.shift()
        }

        // 保存滑动窗口最大值
        if ( i >= k - 1) {
            result.push(nums[queue[0]])
        }
    }

    return result
};

思路类似，也是用单调队列的思想来解决这道题。不同的是我们不封装队列对象，直接通过数组来完成单调队列。同时我们不直接创建滑动窗口，而是根据遍历时索引大小与k的关系来确定是否是一个完成的滑动窗口，并仅当完成一个窗口时，才弹出队首元素。

最小覆盖字串-子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function minWindow(s: string, t: string): string {
    let result = ""

    // 存储t中出现的字母a-zA-Z以及出现次数
    let hash = Array(52).fill(0)
    // 存储当前子串中字母a-zA-Z出现的次数
    let map = Array(52).fill(0)
    // 出现的字符种类
    let tLen = 0
    for (let i = 0; i < t.length; i++) {
        if (++hash[getIndex(t[i])] === 1) tLen++
    }

    for (let l = 0, r = 0 ; r < s.length ; r++) {
        const rightIndex = getIndex(s[r])

        if (++map[rightIndex] === hash[rightIndex]) tLen--
        
        while (l < r) {
            const leftIndex = getIndex(s[l])

            // 如果map中左侧指针对应元素的个数大于需要的个数，说明不是最短字符串，移动
            if (map[leftIndex] > hash[leftIndex] && --map[leftIndex] >= 0) {
                l++
            } else break

        }
        
        if (tLen === 0 && (!result || result.length > r - l + 1)) result = s.substring(l, r+1)

    }
    
    return result
};

// 获取字母对应索引
function getIndex(value: string): number {
    return value >= 'A' && value <= 'Z' ? value.charCodeAt(0) - 'A'.charCodeAt(0) + 26 : value.charCodeAt(0) - 'a'.charCodeAt(0);
}

思路：首先先存储匹配字符串t的字符信息，用字母表hash保存各个字母出现的次数tLen，并统计共有几种字母。另建一个字母表用于存储当前右指针扫描过的字母以及出现次数，如果某一字母出现次数与hash中对应字母相同，则说明完成一种字母的匹配，此时tLen自减。对于左指针，如果左指针对应的字母出现次数大于hash中的次数，则说明不是最短字符串，此时左指针移动。依此类推，当tLen == 0且当前结果值长度大于新的字符串，则替换结果字符串。

缺失的第一个正数-普通数组

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

解法一：暴力解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function firstMissingPositive(nums: number[]): number {
    let result: number = 1

    // 升序排序
    nums.sort((a,b) => a-b)

    // 去除非正整数
    let test = 0
    while(nums[test] <= 0) {
        nums.shift()
    }
    if (nums[0] !== 1) return result

    for (let i = 0; i < nums.length; i++) {
        // 跳过相同数字
        if (nums[i] === nums[i+1]) {
            continue
        }
        if (nums[i] + 1 !== nums[i+1]) {
            result = nums[i] + 1
            break
        }
    }

    return result
};

思路：排序，去除负数，然后遍历判断即可。

解法二：哈希表

我们可以考虑将给定的数组设计成哈希表。若不存在没出现过的最小正整数，则数组中必定存在从1到nums.length的正整数。由于我们要找的是没有出现过的最小正整数，所以我们可以利用数组的下标来表示是否存在该正整数，关系为index = num - 1。具体实现过程详见代码注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function firstMissingPositive(nums: number[]): number {
    let result: number = 1
    let n = nums.length
    // 判断是否含有1
    let oned = false

    for (let i = 0 ; i < n ; i++) {
        if (nums[i] === 1) {
            oned = true
        
        } else if (nums[i] < 1 || nums[i] > n) {
            // 将所有非正整数设置为1
            nums[i] = 1;
        }
    }
    
    // 不含直接返回1
    if (!oned) {
        return result
    }

    // 遍历，将正整数对应的索引的元素设置为相反数作为存在该正整数的标记
    for (let i = 0; i < n; i++) {
        let num = nums[i]
        let index = Math.abs(num) - 1
        if (nums[index] > 0) {
            nums[index] = -nums[index]
        }
    }

    // 再次遍历，当遇到第一个正数说明该索引对应的数字为缺失的第一个整数
    for (let i = 0; i < n; i++) {
        if(nums[i] > 0) {
            return i+1
        }
    }

    return n+1

}

解法三：置换

我们还可以使用置换的方法，将给定的数组「恢复」成下面的形式：

  • 如果数组中包含 ，那么恢复后，数组的第 个元素为 。

对数组进行一次遍历，对于遍历到的数x=nums[i]，如果 ，我们就知道 x 应当出现在数组中的 的位置，因此交换nums[i]和nums[x−1]，这样 就出现在了正确的位置。在完成交换后，新的nums[i]可能还在 的范围内，我们需要继续进行交换操作，直到 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
export function firstMissingPositive(nums: number[]): number {
    // 置换法
    let n = nums.length
    let result = n + 1

    for (let i = 0; i < n; ++i) {
        while (nums[i] > 0 && nums[i] < n+1 && nums[i] !== nums[nums[i]-1]) {
            const temp = nums[nums[i] - 1]，如果是nums[i]，下面改变将会引起
            // temp得是nums[nums[i] - 1]
            // 如果是nums[i]，nums[i]改变将会影响后续nums[nums[i] - 1]
            // 在交换过程中，nums[i] 和 nums[nums[i] - 1] 会不断地交换彼此的值，导致无限循环
            nums[nums[i] - 1] = nums[i]
            nums[i] = temp

        }
        
    }

    for (let i = 0 ; i < n ; i++) {
        if (nums[i] != i+1) {
            return i+1
        }
    }

    return result
}

K个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  const dummy = new ListNode();
  dummy.next = head; 

  let pre = dummy; //pre记录 被翻转链表 的上一个节点

  while (true) {
    let start = pre.next; //start从头节点开始

    let end = pre; //end要在dummy开始走k步
    let count = k;

    while (count > 0 && end != null) {
      end = end.next;
      count--;
    }
    if (end == null) {
      break; //在这里结束
    }

    let next = end.next; //next记录 被翻转链表 的下一个节点

    reverseList(start, k); //翻转从start数起，长度为k的部分链表

    //翻转后end节点到前面去了，start节点到后面去了
    pre.next = end; //pre 接上头
    start.next = next; // start 接上尾

    pre = start; // pre重新指向next的上一个节点也就是start，开始新一轮
  }

  return dummy.next;
}

思路：创建虚表头，找到翻转区间的开始节点和结束节点，以及区间的前置节点和后置节点，完成翻转后，移动整个区间，将前结束节点作为新的区间的前置节点，然后找到其余节点对应的位置，再次进行翻转即可。

合并 k 个升序链表 - 链表 （hard）

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

解法一：递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    let n = lists.length
    if (n === 2) {
        return mergeTwoLists(lists[0], lists[1])
    } else if (n === 1) {
        return lists[0]
    } else if (n === 0) {
        return null
    }

    let mid = Math.floor(n / 2)
    let l = 0
    let r = mid + 1

    let left = mergeKLists(lists.slice(l, mid))
    let right = mergeKLists(lists.slice(mid, n))


    return mergeTwoLists(left, right)
};

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    let p1 = list1
    let p2 = list2
    let result: ListNode = new ListNode(), cur = result
    

    while (list1 && list2) {
        if (list1.val <= list2.val) {
            cur.next = list1
            list1 = list1.next
        } else if (list1.val > list2.val) {
            cur.next = list2
            list2 = list2.next
        }

        
        cur = cur.next as ListNode
    
        
    }

    // 补充剩下的节点
    cur.next = list1 ?? list2


    return result.next
};

思路：使用分治法，将原链表组不停的对半分开，用之前实现的合并排序两个升序链表的思路处理每对链表。这里需要注意链表组长度为0，1，2时结束递归。

解法二：迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if (lists.length === 0) {
        return null;
    }

    while (lists.length > 1) {
        let mergedLists: Array<ListNode | null> = [];

        for (let i = 0; i < lists.length; i += 2) {
            let l1 = lists[i];
            let l2 = i + 1 < lists.length ? lists[i + 1] : null;
            mergedLists.push(mergeTwoLists(l1, l2));
        }

        lists = mergedLists;
    }

    return lists[0];
}

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    let dummy: ListNode = new ListNode(0);
    let cur = dummy;

    while (list1 !== null && list2 !== null) {
        if (list1.val <= list2.val) {
            cur.next = list1;
            list1 = list1.next;
        } else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }

    // Append the remaining nodes
    cur.next = list1 !== null ? list1 : list2;

    return dummy.next;
}

思路：将链表两两合并排序，然后将合并后的链表组作为下一轮处理的链表组，最后会得到完整的排序链表。

二叉树中最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function maxPathSum(root: TreeNode | null): number {
    let result: number = -10000

    // 每个节点都寻找一次最大和
    function dfs(node: TreeNode | null) {
        if (!node) return 0

        // 计算每个节点的最大贡献值，即该节点树的最大路径值，值不为负数
        let left = Math.max(dfs(node.left), 0)
        let right = Math.max(dfs(node.right), 0)

        // 当前节点的最大路径值
        let max = node.val + left + right

        result = Math.max(result, max)

        return node.val + Math.max(left, right)
    }

    
    dfs(root)

    return result
};

思路：遍历时对当前节点计算最大贡献值（对应节点左右子树各自的最大路径和），左右子树的最大路径值加上当前节点的值即为该节点的最大路径和。

Author：破酥 | C4iN
Link：https://c4in1.github.io/2024/09/09/算法/LeetCodeHot100-Hard/
版权声明：本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
leetcode刷题