LeetCode Hot100-Day 0

Created by: Yuanpeng QU
Created time: 2025年8月13日 21:29

HOT100 抱佛脚计划

日期 主题焦点 核心模式 目标Hot 100题号 每日定性目标
Day 1 数组与指针基础 双指针, 滑动窗口 1, 11, 15, 26, 283, 75, 42, 3, 76, 239, 438, 560 掌握线性扫描、原地修改以及寻找配对/区间的核心技巧。
Day 2 链表操作 快慢指针, 链表原地反转 2, 19, 21, 23, 141, 142, 160, 206, 24, 25, 92 精通链表的节点操作、环检测和反转。K路合并(23)作为堆的预热。
Day 3 树与图遍历基础 树的BFS, 树的DFS 102, 103, 199, 104, 94, 144, 145, 101, 100, 226, 114, 543, 200 固化树的递归与迭代遍历范式，解决对称性、深度、路径等基础问题。
Day 4 递归、回溯与搜索 子集/回溯, 改进的二分查找 17, 22, 39, 46, 78, 90, 79, 33, 34, 153, 162, 69 学习如何系统性地探索解空间，并掌握在有序结构中高效搜索的技巧。
Day 5 堆与优先队列应用 前K个元素, 双堆, K路合并 215, 347, 295, 23 (复习), 56, 57 (区间合并) 掌握利用堆解决排序、中位数和合并问题。穿插区间合并作为调剂。
Day 6 动态规划 (Part 1) 1D DP, 基础DP 70, 198, 53, 121, 5, 300, 139, 322, 55, 45, 338 建立DP思维，从最基础的爬楼梯、打家劫舍开始，理解状态定义和转移。
Day 7 动态规划 (Part 2) 与图 2D DP, 背包, 拓扑排序 62, 64, 221, 152, 32, 72, 96, 416, 207, 210, 128 挑战更复杂的DP问题（矩阵、字符串编辑），并掌握基础图算法。
Day 8 复盘、综合与模拟 所有模式, 杂项 146, 208, 48, 136, 191, 复习Day1-7标记的难题 解决LRU等设计题，复习所有模式，进行2-3次完整的模拟面试。

1.两数之和(Two Sum)[easy]

一句话概括题意：在一个数组里找两个数，让他们的和等于指定目标值

思路：

  • 我自己的思路：暴力求解O(N^2) 不是最优
1
2
3
4
for i in range(len(nums)):
	for j in range(i+1,len(nums)):
		if nums[i] + nums[j] == target:
			return [i, j]
  • 核心：用hashmap (python里面的字典)，时间为O(N), i+j == target可以转化为 j == target - i
1
2
3
4
5
6
7
hashmap = {}
for idx, i in enumerate(nums):
	j = target - i
	if j in hashmap:
		return [idx, hashmap[j]]
	else:
		hashmap[i] = idx # 把{idx:i}存入哈希表
  • 注意：hashmap[value] = key，或者hashmap[key] = value 语法上都对，但是取决于查询目标。在“两数之和”里，我们的目标是查询值，所以必须用值来做 key。

76. 最小覆盖子串[hard]

给定两个字符串s和t，求s里包含t中所有字符的最小字符串，没有就返回“”

根本想不到（

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
import collections
class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        need = collections.defaultdict(int)
        window = collections.defaultdict(int)
        left, right = 0, 0
        start, valid = 0, 0

        min_len = float('inf') # 初始化最小字串的长度为无穷

        for char in t:
          need[char] += 1 # need字典初始化，将需要比对的t转换为字符后储存在字典里，这里的+=1 则能计算每个字符数
        
        while right < len(s):
          c = s[right]
          right += 1

          if c in need:
            window[c] += 1
            
            # 关键1
            if window[c] == need[c]: # 这个if是在上一个的里面
              valid += 1
					
					# 关键2
          while valid == len(need):
            
            if right - left < min_len:
              start = left # 这个也在if里
              min_len = right - left
            
            # 这两句在if后面
            d = s[left]
            left += 1
						
						# 关键3
            if d in need:
              if window[d] == need[d]:
                valid -= 1
              window[d] -= 1
        return "" if min_len == float('inf') else s[start: start + min_len]
  • 最主要的记法：滑动窗口+2x哈希表
  • 两个哈希表，一个need将t字符串里的所有字符按照{字符：出现次数}保存，另一个哈希表window用于记录s字符串中滑动窗口两个指针中间的窗口部分的字符数量，同样按照上面的格式储存，need显然只需要执行一次，也就是将t储存后剩下的都是起判断作用
  • 哈希表初始化： import collections → need = collections.defaultdict(int) 因为value是字符次数
  • **关键1：**使用一个valid变量来判断读取到某个属于need的字符c的时候window[c]是否和need[c]次数相等，相等就说明这个字符已经达到输出要求了，valid+=1，这样最后valid ==len(need)的时候window里面就已经有所有need数量的字符了。
  • **关键2：**关键1过后，左边的指针left就可以往右边移动了，当然移动之前得先确认好现在的最小字符串长度是多少（因为是第一次达到关键1结果，所以直接min_len = right-left）注意min_len初始化的时候是min_len = float(’inf’)无穷大，因为要用作判断if right-left < min_len，这表示最小字符串有更小的值了，需要更新。更新完min_len后就可以将left往前挪1了，挪的同时需要保存原来的left指向的地方（d = s[left]），这里还需要在开始部分定义一个start=0用于保存最小字符串的起始位置。
  • **关键3：**对d进行判断，如果被删掉的这个d是属于need的话，那就还需要再判断一下如果窗口里面d的数量已经和need 相等了，那被删掉后就不满足valid == len(need)条件了，也就是说这个时候valid要-1，跳出内循环while，for循环重新判断新的right和c。如果窗口里d的数量还是比need里的多，就说明还能继续删。

11. 盛最多水的容器[mid]

给一个数组height，元素表示高度，求这些统计图里的柱子围起来的水的最大体积，显然水的多少由最矮那边决定。

  • 模板：典中典双指针（两侧靠拢版）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height) <= 1: # 其实可以直接max_area = 0就行了
            return 0

        left, right = 0, len(height)-1
        max_area = 0
        while left < right:
            tall = min(height[left], height[right])
            area = tall * (right - left)
            if area > max_area:
                max_area = area
            if height[left] < height[right]: # 高度如果相等的话向左向右移动都可以！！
                left += 1
            else: # 这里是左移了
                right -= 1
        return max_area
  • 这题想到了tall = min(height[left], height[right])以及使用max_area = area来储存最大体积，但是唯一的错误就是把两个指针都设在左边了，最开始写的是left, right = 0, 1, while的条件成了：while right < len(height): 这样其实到最后还是变成暴力求解，复杂度为N平方
  • 关键就是左右两边向中间靠拢的双指针，而不是同向。并且应该是哪边矮则哪边向中间靠拢，因为高的那边靠拢的话得到的结果可能还是矮的那边更矮，并且向中间靠拢底长也变短了。