返回
Featured image of post CodeTop - Top 10
又携书剑路茫茫

CodeTop - Top 10

睁眼一看，都是我的血泪史啊

题目 简述、方案、死人坑
无重复字符的最长子串 这里我们用双指针加哈希表或集合，遇到就循环移除
反转链表 迭代法：nxt->cur.next->nxt.next->pre.next->nxt
递归法：双终止->递归下一个->头下下->头下
LRU 缓存 哈希表加上双向链表，理论不难但是特别容易出错。我的想法是把只实现两个辅助函数，一个add一个remove，其中每一个函数要封装到一起，不要把功能拆出去。哈希表用的是del hash[key]。
数组中的第K个最大元素 快选法：分治，分成大于和小于pivot点的两部分
分割pivot用的是l和r指针，终止后j指针指向左侧边界（包含）
最大堆：建立一个堆，需要实现以下几个函数，down+pop+bigger+swap+son+parent+序列建堆，另外up和push可以不用
K 个一组翻转链表 迭代法：nxt->cur.next->nxt.next->pre.next->nxt，先遍历一遍找到group组数
三数之和 先排序，再双指针，中间记得去重
对i去重，我们只要第一个不同的i，其他的全部略过
对j和k去重，我们如果命中，则j和k都要更新到不同的下一个
最大子数组和 Kadane算法，用short和long来遍历
short = max(num, num + short)
long = max(long, short)
手撕快排 循环完要分治递归啊！！！ 血泪教训，l->j和 j+1->r
合并两个有序链表 罕见的简单题
最长回文子串 扩展法：最容易错的是指针方向，这两个是往外走，l, r = l - 1, r + 1
动态规划：也可以，但是和扩展法的复杂度是一样的

无重复字符的最长子串

3. 无重复字符的最长子串

题目描述

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

方案一：双指针+哈希集合

这道题可以使用 滑动窗口 的思想来解决。滑动窗口是一种常见的用于解决数组/字符串子串问题的技巧。我们维护一个窗口，窗口的左右边界分别是 left 和 right，表示当前子串的起始和结束位置。我们使用一个哈希集合（set）来记录当前窗口内的字符。

  1. 初始化：left 和 right 都从 0 开始，表示窗口的初始位置。max_len 用于记录最大子串的长度。
  2. 移动右边界：将 s[right] 加入哈希集合，并向右移动 right。
  3. 处理重复字符：如果 s[right] 已经在哈希集合中，说明遇到了重复字符，此时需要移动 left 指针，直到将重复字符移出窗口。
  4. 更新最大长度：在每一步移动 right 后，更新 max_len。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        # 记录一个集合统计窗口内的数字
        char_set = set()
        left = 0
        max_len = 0

        # 遍历整个字符串
        for right in range(0, len(s)):

            # 重合则移除直到单一
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1
            
            # 无条件添加元素并计算
            char_set.add(s[right])
            max_len = max(max_len, right-left+1)

        return max_len

方案二：双指针 + 哈希映射

思路：使用哈希映射（字典）来记录字符最后一次出现的位置。当遇到重复字符时，left 指针可以直接跳转到重复字符的下一个位置，而不需要逐步移动。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        # 使用字典来记录字符最后出现的位置
        char_map = {}
        left = 0
        max_len = 0

        # 遍历整个字符串
        for right in range(0, len(s)):
            if s[right] in char_map and char_map[s[right]] >= left:
                # 如果字符在字典中且在当前窗口内，移动左指针
                left = char_map[s[right]] + 1
            
            # 更新字符的最新位置
            char_map[s[right]] = right
            
            # 更新最大长度
            max_len = max(max_len, right - left + 1)

        return max_len

时空复杂度分析

  • 时间复杂度: O(n)，其中 n 是字符串的长度。left 和 right 指针最多各移动 n 次。
  • 空间复杂度: O(min(m, n))，其中 m 是字符集的大小。在最坏情况下，哈希集合或哈希表的大小为 min(m, n)。

LRU缓存

146. LRU 缓存

题目描述

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

方案：哈希表+双向链表

为了实现 O(1) 时间复杂度的 get 和 put 操作，我们需要结合 哈希表（快速查找）和 双向链表（维护数据顺序）来实现 LRU 缓存。具体思路如下：

  1. 双向链表：

    • 链表中的节点按访问时间排序，最近访问的节点放在链表头部，最近最少使用的节点放在链表尾部。
    • 链表的插入和删除操作时间复杂度为 O(1)。

  2. 哈希表：

    • 哈希表存储键和对应的链表节点的指针，便于快速查找和更新。

  3. 操作逻辑：

    • get(key)：如果键存在，通过哈希表找到节点，将其移动到链表头部（表示最近使用），并返回值；如果键不存在，返回 -1。
    • put(key, value)：如果键存在，更新节点的值，并将其移动到链表头部；如果键不存在，创建新节点并插入链表头部，同时检查容量是否超过限制，如果超过则删除链表尾部的节点。
 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

class Node:
    def __init__(self, key=0, value=0):
        """
        双向链表节点类。
        :param key: 节点的键，默认为 0。
        :param value: 节点的值，默认为 0。
        """
        self.key = key  # 节点的键
        self.value = value  # 节点的值
        self.prev = None  # 前驱节点，指向前一个节点
        self.next = None  # 后继节点，指向下一个节点


class LRUCache:
    def __init__(self, capacity: int):
        """
        初始化 LRU Cache。
        :param capacity: 缓存容量。
        """
        self.capacity = capacity  # 缓存的最大容量
        self.cache = {}  # 缓存字典，用于存储键值对
        self.head = Node()  # 双向链表的虚拟头节点
        self.tail = Node()  # 双向链表的虚拟尾节点
        self.head.next = self.tail  # 初始化链表，头节点指向尾节点
        self.tail.prev = self.head  # 尾节点指向头节点

    def remove(self, node):
        """
        从双向链表和缓存字典中移除指定节点。
        :param node: 要移除的节点。
        """
        node.prev.next = node.next  # 修改前驱节点的后继指针
        node.next.prev = node.prev  # 修改后继节点的前驱指针
        del self.cache[node.key]  # 从缓存字典中移除该节点的键值对

    def add(self, node):
        """
        将节点添加到双向链表的头部，并加入缓存字典。
        :param node: 要添加的节点。
        """
        node.next = self.head.next  # 新节点的后继指针指向原链表的第一个节点
        node.prev = self.head  # 新节点的前驱指针指向虚拟头节点
        self.head.next.prev = node  # 原链表的第一个节点的前驱指针指向新节点
        self.head.next = node  # 虚拟头节点的后继指针指向新节点
        self.cache[node.key] = node  # 将节点加入缓存字典

    def get(self, key: int) -> int:
        """
        获取缓存中指定键对应的值，并将该节点移动到链表头部（表示最近使用）。
        :param key: 要查找的键。
        :return: 如果键存在，返回对应的值；否则返回 -1。
        """
        if key in self.cache:
            node = self.cache[key]  # 从缓存字典中获取节点
            self.remove(node)  # 从链表中移除该节点
            self.add(node)  # 将该节点添加到链表头部
            return node.value  # 返回节点的值
        else:
            return -1  # 键不存在，返回 -1

    def put(self, key: int, value: int) -> None:
        """
        插入或更新缓存中的键值对。如果缓存已满，则移除最久未使用的节点。
        :param key: 要插入或更新的键。
        :param value: 要插入或更新的值。
        """
        if key in self.cache:
            node = self.cache[key]  # 从缓存字典中获取节点
            self.remove(node)  # 从链表中移除该节点
            node.value = value  # 更新节点的值
            self.add(node)  # 将节点添加到链表头部
        else:
            node = Node(key, value)  # 创建新节点
            self.add(node)  # 将节点添加到链表头部
            if len(self.cache) > self.capacity:  # 如果缓存超出容量
                self.remove(self.tail.prev)  # 移除链表的最后一个节点

时空复杂度分析

  • 时间复杂度：
    • get 和 put 操作的时间复杂度均为 O(1)，因为哈希表的查找、插入和删除操作均为 O(1)，双向链表的插入和删除操作也为 O(1)。
  • 空间复杂度: O(capacity)，其中 capacity 是缓存的容量。哈希表和双向链表的空间复杂度均为 O(capacity)。

易错点

  1. 哈希表与链表的同步更新：别他妈忘了这两个要同步更新
  2. 哈希表的删除和添加：这个贼容易错，我之前就错过

反转链表

206. 反转链表

题目描述

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

方法一：当前不动，后移动到前 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 如果链表为空，直接返回
        if not head:
            return head 
      
        # 创建一个哑节点(dummy)，用于简化操作
        dummy = ListNode(-1, head)
        # cur指向当前节点，prv指向当前节点的前一个节点
        cur, prv = head, dummy 
      
        # 遍历链表，反转节点
        while cur.next:
            nxt = cur.next  # 保存当前节点的下一个节点
            cur.next = nxt.next  # 将当前节点的next指向nxt的下一个节点
            nxt.next = prv.next  # 将nxt的next指向prv的next节点
            prv.next = nxt  # 将prv的next指向nxt
      
        # 返回反转后的链表头节点
        return dummy.next

时空复杂度

  • 时间复杂度: O(n)，其中 n 是链表的长度。我们需要遍历链表中的每个节点一次。
  • 空间复杂度: O(1)，我们只使用了常数个额外的指针，没有使用额外的空间。

易错点

  • 边界条件处理：如果链表为空，直接返回 head。
  • 指针操作顺序：在反转节点时，指针的操作顺序非常重要，错误的顺序可能导致链表断裂或死循环。
  • 返回值：最终返回的是 dummy.next，而不是 prv 或 cur。

方法二：递归法 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 递归终止条件：如果链表为空，或者链表只有一个节点，直接返回 head
        if not head or not head.next:
            return head
        
        # 递归调用，反转从 head.next 开始的链表
        # p 是反转后的新链表的头节点
        p = self.reverseList(head.next)
        
        # 将当前节点的下一个节点的 next 指向当前节点，实现反转
        head.next.next = head
        
        # 将当前节点的 next 置为 None，避免链表成环
        head.next = None
        
        # 返回反转后的链表的头节点
        return p

举例说明

假设链表为 1 -> 2 -> 3 -> 4 -> 5，递归过程如下：

  1. 递归到 5，满足终止条件，返回 5。
  2. 回溯到 4：
    • 4.next.next = 4，即 5.next = 4。
    • 4.next = None。 链表变为：5 -> 4。
  3. 回溯到 3：
    • 3.next.next = 3，即 4.next = 3。
    • 3.next = None。 链表变为：5 -> 4 -> 3。
  4. 依此类推，最终链表变为：5 -> 4 -> 3 -> 2 -> 1。

时空复杂度

  • 时间复杂度: O(n)，其中 n 是链表的长度。递归会遍历链表中的每个节点一次。
  • 空间复杂度: O(n)，递归调用栈的深度与链表长度成正比。

易错点

  1. 递归终止条件：必须判断 if not head or not head.next，否则会导致空指针异常或无限递归。
  2. 链表成环：在反转指针后，一定要将当前节点的 next 置为 None，否则链表会成环。
  3. 返回值的理解：返回值是反转后的新链表的头节点（即原链表的最后一个节点），而不是当前节点。

数组中的第K个最大元素

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

题目描述

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

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

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

方法1：快速选择

  1. 快速选择算法：通过选择一个基准值（pivot），将数组分为两部分，左边部分的元素都大于等于基准值，右边部分的元素都小于等于基准值。然后根据 k 的值决定在哪个分区继续查找。
  2. 分区操作：使用双指针法进行分区操作，确保左边分区的元素都大于等于基准值，右边分区的元素都小于等于基准值。
  3. 递归调用：根据 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
34
35
36
37
38
39
40

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        # 定义快速选择函数
        def quickSelect(left, right, k) -> int:
            
            # 如果区间只有一个元素，直接返回该元素
            if left == right:
                return nums[left]
            
            # 选择数组中间位置的元素作为基准值（pivot）
            pivot = nums[(left+right)//2]
            i, j = left, right 
            
            # 使用双指针进行分区操作
            while True:
                # 从左向右找到第一个小于等于 pivot 的元素
                while nums[i] > pivot:
                    i += 1
                # 从右向左找到第一个大于等于 pivot 的元素
                while nums[j] < pivot:
                    j -= 1
                # 如果指针相遇或交叉，结束循环
                if i >= j:
                    break 
                # 交换两个元素的位置
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i + 1, j - 1
            
            # 计算左边分区的元素数量
            cnt = j - left + 1
            # 如果 k 小于等于左边分区的元素数量，则在左边分区继续查找
            if k <= cnt:
                return quickSelect(left, j, k)
            # 否则在右边分区继续查找，同时更新 k 的值
            else:
                return quickSelect(j+1, right, k-cnt)

        # 调用快速选择函数，返回第 k 大的元素
        return quickSelect(0, len(nums)-1, k)

时间复杂度分析

  • 平均情况：O(n)，其中 n 是数组的长度。快速选择算法在平均情况下每次能将问题规模减半，因此时间复杂度为线性。
  • 最坏情况：O(n^2)，如果每次选择的基准值都是最小或最大值，导致每次分区只能减少一个元素。

空间复杂度分析

  • 空间复杂度：O(1)，除了递归调用栈外，算法没有使用额外的空间。

易错点

  1. 是严格小于，而不是小于等于：会影响分区结果。如果全是pivot，这会让指针越界
  2. 分区（Partition）：将数组分为两部分：
    • 左侧部分：所有元素 小于 基准值。
    • 右侧部分：所有元素 大于 基准值。
    • 基准值本身位于正确的位置。
  3. cnt和k：
    • k是从1开始计数的，不要弄错
    • k大于cnt意味着前面没罩住，往后找
    • k小于等于cnt意味着结果在前面，缩小尾巴

方法2：最大堆

最大堆是一种树形数据结构，其中每个节点的值都大于或等于其子节点的值。我们可以通过构建一个最大堆来找到第k个最大元素。具体步骤如下：

  1. 构建最大堆：将整个数组构建成一个最大堆。
  2. 移除堆顶元素：从堆中移除堆顶元素（最大值），重复k-1次。
  3. 返回堆顶元素：最后堆顶的元素就是第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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

class Heap:
    def __init__(self, arr=[]):
        self.heap = arr
        if len(arr) > 0:
            for i in range(len(arr)//2-1, -1, -1):
                self.heapify_down(i)
    
    def parent(self, i):
        return (i-1)//2
    
    def left_son(self, i):
        return 2*i+1
    
    def right_son(self, i):
        return 2*i+2
    
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def size(self):
        return len(self.heap)
    
    def heapify_up(self, i):
        while i > 0 and self.heap[i] > self.heap[self.parent(i)]:
            self.swap(i, self.parent(i))
            i = self.parent(i)
    
    def heapify_down(self, i):
        index = i 
        left = self.left_son(i)
        right = self.right_son(i)

        if left < self.size() and self.heap[left] > self.heap[index]:
            index = left 
        if right < self.size() and self.heap[right] > self.heap[index]:
            index = right 

        if index != i:
            self.swap(index, i)
            self.heapify_down(index)
    
    def push(self, num):
        self.heap.append(num)
        self.heapify_up(self.size()-1)

    def pop(self):
        res = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify_down(0)
        return res 

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = Heap(nums)
        for i in range(k-1):
            heap.pop()
        return heap.pop()

时间复杂度分析

返回堆顶元素的时间复杂度为 O(1)

每次移除堆顶元素的时间复杂度为 O(log n)

  1. 从空堆逐个插入建堆：
    • 每次插入的时间复杂度是 O(log n)。
    • 总时间复杂度是 O(n log n)。
  2. 从数组自下而上建堆：
    • 使用 heapify_down 操作，总时间复杂度是 O(n)。

为啥从下而上建堆是O(n)

  1. 常见误解：
    • 通常我们会认为建堆的时间复杂度是 O(n log n)，因为每个元素插入堆的时间是 O(log n)，总共有 n 个元素，所以总的复杂度是 O(n log n)。
    • 但实际上，建堆的时间复杂度是 O(n)，而不是 O(n log n)。
  2. 为什么是 O(n)：
    • 在常规的从空堆插入元素的情况下，每次插入需要 O(log n)，所以总复杂度是 O(n log n)。
    • 但是，当我们从一个已有的数组（arr）构建堆时，采用的是自下而上的 heapify 操作，而不是从空堆逐个插入。
    • 具体来说，建堆的过程是从数组的中间位置开始（即从 n//2 - 1 到 0），对每个节点进行 heapify_down 操作。
    • heapify_down 的时间复杂度取决于当前节点的高度，而不是树的高度。对于第 i 层的节点，heapify_down 的时间复杂度是 O(h-i)，其中 h 是树的高度。
    • 通过数学计算，可以发现建堆的总时间复杂度是 O(n)。
  3. 数学证明
    • 假设树的高度为 h，第 i 层有 2^i 个节点，每个节点的 heapify_down 操作的时间复杂度为 O(h-i)。
    • 总时间复杂度的计算如下： $$ T(n) = \sum_{i=0}^{h} 2^i \cdot (h - i) $$
    • 这个求和结果可以证明是 O(n)

空间复杂度分析

  • 构建堆需要额外的空间来存储堆结构，空间复杂度为 O(n)。

易错点

  1. 堆的构建：在初始化堆时，需要从数组的中间位置开始进行 heapify_down 操作，而不是从头开始，这会影响建堆的复杂度，从O(nlogn)降低到O(n)
  2. 堆的维护：在 pop 操作后，需要正确地维护堆的性质，即调用 heapify_down。
  3. 边界条件：当 k=1 时，直接返回堆顶元素即可，不需要进行移除操作。

K 个一组翻转链表

25. K 个一组翻转链表

题目描述

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

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

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

方法：双指针翻转

  1. 统计链表长度：首先统计链表的长度，确定需要翻转的组数。
  2. 分组翻转：对每一组的 k 个节点进行翻转，翻转过程中需要维护前驱节点和当前节点的关系。
  3. 更新指针：翻转完一组后，更新前驱节点和当前节点，继续处理下一组节点。
  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

class Solution:  
    def reverseKGroup(self, head, k) -> Optional[ListNode]:  
        # 初始化计数器 cnt、当前节点 cur 和虚拟头节点 dummy  
        cnt, cur, dummy = 0, head, ListNode(-1, head)   
        
        # 统计链表长度  
        while cur is not None:  
            cnt, cur = cnt+1, cur.next   
        
        # 计算需要翻转的组数  
        n = cnt // k   
        
        # 初始化前驱节点 prv 和当前节点 cur  
        prv, cur =  dummy, head   
        
        # 遍历每一组节点进行翻转  
        for _ in range(n):  
            # 每组需要翻转 k-1 次  
            for _ in range(k - 1):  
                nxt = cur.next  # 保存当前节点的下一个节点  
                cur.next = nxt.next  # 当前节点指向下下个节点  
                nxt.next = prv.next  # 下一个节点指向当前组的新头节点  
                prv.next = nxt  # 前驱节点指向新的头节点  
            # 更新前驱节点和当前节点到下一组  
            prv, cur = cur, cur.next  
​  
        # 返回修改后的链表  
        return dummy.next

复杂度分析

  1. 时间复杂度：
    • 统计链表长度：O(n)，其中 n 是链表长度。
    • 翻转链表组：外层循环遍历 n//k 组，每组需要翻转 k 个节点，时间复杂度为 O(n)。
    • 总时间复杂度为 O(n)。
  2. 空间复杂度：
    • 只使用了常数级别的额外空间（几个指针），空间复杂度为 O(1)。

三数之和

15. 三数之和

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0。请你找出所有和为 0 且不重复的三元组。

方法1：排序 + 双指针

  1. 排序：首先将数组排序，这样可以利用双指针的技巧来减少时间复杂度。
  2. 固定一个数：遍历数组，固定一个数 nums[i]，然后使用双指针在剩下的数组中寻找其他两个数，使得这三个数的和为 0。
  3. 双指针：使用两个指针 j 和 k，分别指向 i+1 和 len(nums)-1。根据三数之和与 0 的关系，移动指针来逼近目标。
  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

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # 首先对数组进行排序
        res = []  # 用于存储结果的三元组
      
        # 遍历数组，固定一个数
        for i in range(0, len(nums)-2):
            # 如果当前数和前一个数相同，跳过以避免重复
            if i > 0 and nums[i] == nums[i-1]:
                continue
              
            j, k = i+1, len(nums)-1  # 初始化双指针
            while j < k:
                total = nums[i] + nums[j] + nums[k]  # 计算三数之和
              
                if total == 0:
                    # 如果和为0，加入到结果中
                    res.append([nums[i], nums[j], nums[k]])
                    # 跳过重复的元素
                    while j < k and nums[j] == nums[j+1]:
                        j += 1
                    while j < k and nums[k] == nums[k-1]:
                        k -= 1
                    # 移动双指针
                    j, k = j+1, k-1
                elif total > 0:
                    # 如果和大于0，移动右指针
                    k -= 1
                else:
                    # 如果和小于0，移动左指针
                    j += 1
      
        return res  # 返回结果

时间复杂度分析

  1. 排序：O(n log n)，其中 n 是数组的长度。排序是算法中最耗时的部分。
  2. 双指针遍历：O(n^2)，外层循环遍历每个元素，内层循环使用双指针遍历剩余的元素。
  3. 总时间复杂度：O(n log n + n^2)，在大多数情况下，O(n^2) 是主要部分。

空间复杂度分析

  1. 排序：O(log n)，排序算法的空间复杂度。
  2. 结果存储：O(n)，最坏情况下需要存储 O(n) 个三元组。
  3. 总空间复杂度：O(n)，主要用于存储结果。

易错点

  1. 去重：在固定一个数和移动指针时，必须跳过相同的元素，否则会导致重复的三元组。
  2. 边界条件：在处理数组边界时，确保索引不会越界。
  3. 排序：在开始双指针之前，必须对数组进行排序，否则无法保证双指针的有效性。

最大子数组和

53. 最大子数组和

题目描述

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

方法：动态规划（Kadane’s Algorithm）

  1. 核心思路：

    • 状态定义：cur_sum 表示以当前元素结尾的子数组的最大和。
    • 状态转移：对于每个元素，我们有两个选择：要么将其加入到当前子数组中，要么以当前元素为起点重新开始一个新的子数组。我们选择两者中较大的一个，即 cur_sum = max(cur_sum + num, num)。
    • 边界条件：初始时，cur_sum 和 max_sum 都设置为负无穷大，以确保数组中的任何元素都能成为新的起点。
    • 最终结果：在整个遍历过程中，我们始终维护一个 max_sum，它记录了到目前为止的最大子数组和。

  2. 算法步骤：

    • 初始化 cur_sum 和 max_sum 为 -float('inf')。
    • 遍历数组中的每个元素：
      • 更新 cur_sum 为 max(cur_sum + num, num)。
      • 更新 max_sum 为 max(max_sum, cur_sum)。
    • 返回 max_sum。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 初始化当前子数组和与最大子数组和
        cur_sum, max_sum = -float('inf'), -float('inf')
        # 遍历数组中的每个元素
        for num in nums:
            # 更新当前子数组和，选择加入当前元素或重新开始
            cur_sum = max(cur_sum + num, num)
            # 更新最大子数组和
            max_sum = max(max_sum, cur_sum)
        # 返回最大子数组和
        return max_sum

时间复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组的长度。我们只需遍历一次数组，每个元素的操作都是常数时间。
  • 空间复杂度：O(1)，只使用了常数个额外空间来存储 cur_sum 和 max_sum。

易错点

  1. 初始化值：cur_sum 和 max_sum 应初始化为 -float('inf')，而不是 0，因为数组可能包含负数，我们需要确保任何单个元素都能成为起点。
  2. 状态转移：在更新 cur_sum 时，一定要选择 max(cur_sum + num, num)，而不是直接加上当前元素，否则可能会错过更优的子数组。

快速排序

912. 排序数组

题目描述

这是一道快速排序的经典实现题目。给定一个整数数组 nums，要求将数组升序排序。

方法：快速排序

  1. 核心思路：

    • 分治法：快速排序是一种基于分治法的排序算法。它的基本思想是通过选择一个基准值（pivot），将数组分为两部分：一部分小于等于基准值，另一部分大于等于基准值。
    • 递归排序：对每一部分递归地进行快速排序，最终实现整个数组的排序。
    • 基准值选择：通常选择数组中间位置的元素作为基准值，这样可以避免最坏情况（如已排序数组）的发生。
    • 分区操作：使用双指针法进行分区操作，确保左边分区的元素都小于等于基准值，右边分区的元素都大于等于基准值。

  2. 算法步骤：

    • 终止条件：如果 left >= right，当前数组已经有序，直接返回。
    • 基准值选择：选择数组中间位置的元素作为基准值（pivot）。
    • 分区操作：使用双指针 i 和 j 进行分区操作：
      • 从左向右找到第一个大于等于 pivot 的元素。
      • 从右向左找到第一个小于等于 pivot 的元素。
      • 如果 i >= j，分区结束。
      • 否则，交换 nums[i] 和 nums[j]，并移动指针。
    • 递归排序：对左右两部分分别进行递归排序。
 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

class Solution:
    def quickSort(self, nums, left, right):
        # 终止条件：如果区间长度小于等于 1，直接返回
        if left >= right:
            return 
      
        # 选择基准值：数组中间位置的元素
        pivot = nums[(left + right) // 2]
        i, j = left, right
      
        # 分区操作
        while True:
            # 从左向右找到第一个大于等于 pivot 的元素
            while nums[i] < pivot:
                i += 1
            # 从右向左找到第一个小于等于 pivot 的元素
            while nums[j] > pivot:
                j -= 1
            # 如果指针相遇或交叉，结束分区
            if i >= j:
                break
            # 交换两个元素的位置
            nums[i], nums[j] = nums[j], nums[i]
            # 移动指针
            i, j = i + 1, j - 1
      
        # 递归排序左半部分
        self.quickSort(nums, left, j)
        # 递归排序右半部分
        self.quickSort(nums, j + 1, right)

    def sortArray(self, nums: List[int]) -> List[int]:
        # 调用快速排序函数，对整个数组进行排序
        self.quickSort(nums, 0, len(nums) - 1)
        # 返回排序后的数组
        return nums

时间复杂度分析

  • 平均情况：O(n log n)，其中 n 是数组的长度。快速排序每次将数组分为两部分，理想情况下每次分区都能将问题规模减半。
  • 最坏情况：O(n^2)，如果每次选择的基准值都是最小或最大值，导致每次分区只能减少一个元素。

空间复杂度分析

  • 空间复杂度：O(log n)，主要用于递归调用栈，最坏情况下可能需要 O(n) 的空间。

易错点

  1. 基准值选择：

    • 如果选择的基准值不平衡（如最小或最大值），可能导致算法效率下降。
    • 选择数组中间位置的元素作为基准值可以尽量避免这种情况。

  2. 分区操作：

    • 在分区操作中，确保指针的正确移动和元素交换，否则可能导致分区失败。
    • 注意指针移动时要检查边界条件，防止越界。

  3. 递归终止条件：

    • 确保递归终止条件正确，否则可能导致无限递归。

  4. 指针移动：

    • 在交换元素后，记得更新指针的位置，否则可能导致死循环。

变体

  1. 三路快速排序：

    • 对于含有大量重复元素的数组，可以将数组分为三部分：小于 pivot 的部分、等于 pivot 的部分和大于 pivot 的部分。
    • 这种方法可以避免重复元素的重复比较。

  2. 随机化选择基准值：

    • 在每次分区时随机选择一个元素作为基准值，从而避免最坏情况的发生。

  3. 小数组使用插入排序：

    • 当数组长度较小时（如 n <= 16），使用插入排序代替快速排序，因为插入排序在小数组上表现更好。

合并两个有序链表

21. 合并两个有序链表

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

方法：双指针

这道题的核心思路是通过双指针遍历两个链表，比较两个链表当前节点的值，将较小的节点连接到新链表中，直到其中一个链表遍历结束。然后将未遍历完的链表直接连接到新链表的末尾。

 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

class Solution:
    def mergeTwoLists(self, list1, list2) -> Optional[ListNode]:
        # 创建一个虚拟节点，作为新链表的头节点前驱
        dummy = ListNode()
        # 创建一个指针 cur，指向新链表的当前节点
        cur = dummy
      
        # 当两个链表都未遍历完时，进行比较
        while list1 and list2:
            if list1.val < list2.val:
                # 如果 list1 的当前节点值较小，将其连接到新链表中
                cur.next = list1
                # 移动 list1 的指针到下一个节点
                list1 = list1.next 
            else:
                # 如果 list2 的当前节点值较小或相等，将其连接到新链表中
                cur.next = list2
                # 移动 list2 的指针到下一个节点
                list2 = list2.next 
            # 移动 cur 指针到新链表的最后一个节点
            cur = cur.next 
      
        # 如果 list1 还有剩余节点，将其连接到新链表的末尾
        if list1:
            cur.next = list1
        # 如果 list2 还有剩余节点，将其连接到新链表的末尾
        if list2:
            cur.next = list2
      
        # 返回新链表的头节点（dummy.next）
        return dummy.next

时空复杂度分析

  • 时间复杂度：O(m + n)，其中 m 和 n 分别是两个链表的长度。我们需要遍历两个链表的所有节点。
  • 空间复杂度：O(1)，除了分配一个虚拟节点外，没有使用额外的空间。

易错点

  1. 虚拟节点的使用：使用虚拟节点可以简化链表的操作，避免处理空链表的特殊情况。
  2. 指针的移动：在每次连接节点后，别忘了移动 cur 指针到新链表的最后一个节点。
  3. 剩余节点的处理：在遍历结束后，一定要将未遍历完的链表直接连接到新链表的末尾，不要遗漏。

变体

  1. 合并 K 个有序链表：可以使用分治法或最小堆来解决。分治法的时间复杂度为 O(kn log k)，其中 k 是链表的数量，n 是每个链表的平均长度。
  2. 合并两个有序链表并去重：在合并时，如果当前节点的值与下一个节点的值相同，则跳过重复的节点。

最长回文子串

5. 最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

方法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

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 定义中心扩展函数
        def expandAroundCenter(left, right) -> str:
            # 当左右指针在边界内且字符相等时，继续扩展
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # 返回当前找到的回文子串
            return s[left+1:right]

        # 初始化最长回文子串为空字符串
        longest = ""
        # 遍历字符串中的每个字符
        for i in range(len(s)):
            # 以当前字符为中心，考虑奇数长度的回文子串
            odd = expandAroundCenter(i, i)
            # 以当前字符和下一个字符为中心，考虑偶数长度的回文子串
            even = expandAroundCenter(i, i+1)
            # 更新最长回文子串
            if len(odd) > len(longest):
                longest = odd
            if len(even) > len(longest):
                longest = even
      
        # 返回最长回文子串
        return longest

时间复杂度分析

  • 时间复杂度：O(n^2)，其中 n 是字符串的长度。对于每个字符，我们都需要向两边扩展，最坏情况下需要扩展整个字符串。
  • 空间复杂度：O(1)，除了存储结果外，算法没有使用额外的空间。

易错点

  1. 边界条件：在扩展时，要确保左右指针不超出字符串的边界。
  2. 奇数和偶数长度的回文子串：需要同时考虑以当前字符为中心的回文子串（奇数长度）和以当前字符及下一个字符为中心的回文子串（偶数长度）。

方法2：动态规划

核心思路

使用动态规划来解决这个问题。定义一个二维数组 dp，其中 dp[i][j] 表示字符串从索引 i 到 j 的子串是否是回文子串。根据回文子串的性质，如果 s[i] == s[j] 且 dp[i+1][j-1] 是回文子串，那么 dp[i][j] 也是回文子串。

代码实现 

 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

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        # 初始化 dp 数组
        dp = [[False] * n for _ in range(n)]
        longest = ""

        # 所有长度为 1 的子串都是回文子串
        for i in range(n):
            dp[i][i] = True
            longest = s[i]

        # 检查长度为 2 的子串
        for i in range(n-1):
            if s[i] == s[i+1]:
                dp[i][i+1] = True
                longest = s[i:i+2]

        # 检查长度大于 2 的子串
        for length in range(3, n+1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and dp[i+1][j-1]:
                    dp[i][j] = True
                    if length > len(longest):
                        longest = s[i:j+1]

        # 返回最长回文子串
        return longest

时间复杂度分析

  • 时间复杂度：O(n^2)，其中 n 是字符串的长度。我们需要填充一个 n x n 的二维数组。
  • 空间复杂度：O(n^2)，用于存储动态规划表。

易错点

  1. 初始化：所有长度为 1 的子串都是回文子串，长度为 2 的子串需要单独检查。
  2. 状态转移方程：只有在 s[i] == s[j] 且 dp[i+1][j-1] 是回文子串时，dp[i][j] 才是回文子串。

变体

  1. 最长回文子序列：与最长回文子串不同，子序列可以不连续。可以使用动态规划来解决，时间复杂度为 O(n^2)。
  2. 计算所有回文子串的数量：可以使用中心扩展法或动态规划来解决，时间复杂度为 O(n^2)。
© 2023 - 2026 壹壹贰捌· 0Days
共书写了48k字·共 14篇文章 京ICP备2023035941号-1