面向外企就业的 LeetCode/NeetCode 记录

LeetCode 刷题方法

路线图

NeetCode Roadmap

算法清单

外企基石，必须闭眼手撕：

哈希表
双指针
滑动窗口
二分查找
链表
二叉树（含二叉搜索树 BST）

工程进阶，拉开差距的关键：

回溯算法（排列/组合/子集）
堆/优先队列
栈与队列
图论基础（仅限 BFS / DFS / 拓扑排序）

高级护城河，面试冲刺期再看：

动态规划（仅限 1D DP 和基础背包/最长公共子序列）
字典树 (Trie)
并查集 (Union-Find)
前缀和技巧

题单

设计模式

1. 单例模式 (Singleton) —— C++ 面试必考八股

这是什么：保证一个类只有一个实例，并提供一个全局访问点。
外企考点：不仅会让你手写，还会结合 C++ 问你“线程安全的单例怎么写？”（Meyers Singleton，利用局部静态变量的特性）。
如何融合进你的项目：你的 GPU 监控探针（Agent）运行在 5090 服务器上，它需要读取配置信息（比如本机的 IP、监控频率）。这个 ConfigManager 配置管理器，就必须是一个单例。你在简历上面试时可以说：“为了避免多次读取配置文件造成 I/O 浪费，我用 C++11 的 std::call_once（或局部静态变量）实现了一个线程安全的单例配置中心。”

2. 观察者模式 (Observer) —— 监控系统的灵魂

这是什么：一个对象状态改变，所有依赖它的对象都会收到通知。（也就是发布-订阅机制）。
外企考点：解耦。面试官常问：“如果我加一个新的监控维度，你的代码需要大改吗？”
如何融合进你的项目：你的 5070 Ti 是一直在变化的（温度忽高忽低，显存忽大忽小）。你可以把本地的显卡作为一个 Subject（被观察者），把负责发送网络请求的模块、负责写本地日志的模块作为 Observer（观察者）。显存一旦超过阈值，主动“通知”这些模块报警，而不是让它们写个 while(true) 死循环去轮询。

3. 工厂模式 (Factory) —— 告别满屏的 if-else

这是什么：把创建对象的具体逻辑隐藏起来，提供一个统一的接口。
外企考点：考察你对开闭原则（对扩展开放，对修改封闭）的理解。
如何融合进你的项目：你的调度系统未来不仅能收集 5090 的数据，可能还要收集 AMD 显卡，甚至普通 CPU 的数据。写一个 DeviceFactory，传入 “NVIDIA”，它就吐出一个调用 NVML API 的对象；传入 “CPU”，它就吐出一个读取 /proc/cpuinfo 的对象。

4. 策略模式 (Strategy) —— 调度系统的核心

这是什么：定义一系列算法，把它们一个个封装起来，并且使它们可相互替换。
外企考点：极其高频的设计题。比如“设计一个打车软件的计费模块”。
如何融合进你的项目：你的核心是算力调度。怎么调度？你可以有“轮询策略（Round Robin）”、“最低显存优先策略（Least Loaded）”。把这些策略抽象成接口，运行时动态插拔。这就是顶级的基础设施架构。

刷题记录

NeetCode Roadmap

Contains Duplicate (LeetCode 217)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# 最经典的哈希表题。用一个 Set 来记录我们见过的数字，一边遍历一边查这个数字在不在 Set 里。
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set() # 创建一个空的哈希集合
        
        for num in nums:
            if num in seen:  # 查字典：这个数字我之前见过吗？
                return True  # 见过！直接返回 True
            seen.add(num)    # 没见过，把它记在小本本上
            
        return False # 全都查完了也没重复，返回 False

# time complexity:O(n)
# space complexity:O(n)

1
2
3
4
5
6
7
# Pythonic 的一行解法，利用 set() 去重特性，直接比较原数组长度和去重后 Set 的长度。
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))

# time complexity:O(n)
# space complexity:O(n)

如果你的数组非常大，且重复元素大概率出现在很靠前的位置，解法 1 更优，因为它能“及时止损”。
如果你的数组没有重复元素，或者重复元素在最后面，解法 2 更优，因为底层 C 语言的执行速度会碾压 Python 的 for 循环。

summary:

时间复杂度 (Time Complexity)

$O(1)$ 常数级：终极目标。代码特征：直接通过索引取值 nums[0]，或者在字典/集合中查值 if key in my_dict:。
$O(\log n)$ 对数级：极快。代码特征：二分查找。每次操作砍掉一半（如 while left < right: 配合 mid）。
$O(n)$ 线性级：外企最爱的标准解法。代码特征：一层无嵌套的 for 循环，从头到尾扫一遍。
$O(n \log n)$：通常是排序的极限。代码特征：代码里调用了 nums.sort()，或者用了归并/快速排序。
$O(n^2)$ 平方级：面试危险信号。代码特征：两层嵌套的 for 循环。面试官通常会让你把它优化到 $O(n)$。

空间复杂度 (Space Complexity)

$O(1)$：只新建了几个变量（如双指针 left, right），没有开辟随数据规模增大的新空间。
$O(n)$：新建了一个和原数组一样大的字典（哈希表）、集合（Set）或新数组。外企极度喜欢用空间换时间。

Pythonic 循环

抛弃 for(int i=0; i<n; i++)，只记以下三种：

只取值：for num in nums:
只取索引：for i in range(len(nums)):
既要索引又要值：for i, num in enumerate(nums):

核心标准库 (绝不重复造轮子)

collections.Counter (计数器)
场景：完成词频/元素频率统计。直接替代 count[i] = count[i] + 1 循环。
用法：

1
2
from collections import Counter
count = Counter(nums) 

collections.deque (双端队列)
场景：做 BFS（广度优先搜索）必用。两头增删都是 $O(1)$，绝不用普通 list 做队列。
用法：

1
2
3
4
from collections import deque
q = deque([1, 2])
q.append(3)      # 尾部进队
q.popleft()      # 头部出队

heapq (优先队列 / 堆)
场景：解决 “Top K” (前K个最大/最小) 问题。替代 C++ 的 std::priority_queue。
用法：

1
2
3
4
import heapq
heapq.heapify(nums)      # $O(n)$ 原地建堆
heapq.heappush(nums, 2)  # 压入元素
val = heapq.heappop(nums) # 弹出最小值

Valid Anagram (LeetCode 242)

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

## 1
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s)!=len(t):
            return False     
        temp = [0] * 26

        for i in range(len(s)):
            temp[ord(s[i])-ord('a')]=temp[ord(s[i])-ord('a')]+1
            temp[ord(t[i])-ord('a')]=temp[ord(t[i])-ord('a')]-1

        for i in range(26):
            if temp[i]!=0:
                return False

        return True

# time complexity:O(m+n)
# space complexity:O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# 2 神奇 Python 小函数

from collections import Counter
return Counter(s) == Counter(t)

# time complexity:O(m+n)
# space complexity:O(1)

# 3 或者

return sorted(s) == sorted(t)

# time complexity:O(nlogn+mlogm)
# space complexity:O(1)/O(n+m)

summary:

ord(char) —— 字符转索引

用法：index = ord(char) - ord('a')
场景：将 ‘a’-‘z’ 映射到 0-25，配合数组做计数。
相关用法：chr(code)。ord() 的逆运算，如 chr(97) 返回 'a'，常用于将计算后的索引还原为字符。

sorted(s) —— 排序法

用法：return sorted(s) == sorted(t)
场景：快速验证变位词（Anagram）。两个字符串排序后应完全一致。
相关用法：list.sort(reverse=True)。sorted() 返回新列表，支持所有可迭代对象；list.sort() 是列表的原地排序（无返回值）。

Counter —— 词频统计

用法：return Counter(s) == Counter(t)
场景：工程代码中一行解决词频统计，底层是 Hash Map。
相关用法：Counter(s).most_common(k)。返回前 k 个高频元素，解决 Top K 问题的神器。

[0] * n —— 数组快速初始化

用法：count = [0] * 26
场景：建立固定长度的计数桶（Bucket），比 dict 更快更省空间。
相关用法：[[0] * n for _ in range(m)]。构建二维数组（矩阵）的正确写法，必须用列表推导式以避免引用拷贝错误。

Two Sum (LeetCode 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# 直接暴力双循环遍历
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []
# time complexity:O(n^2)
# space complexity:O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 双指针排序

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        A = []
        for i, num in enumerate(nums):
            A.append([num, i])

        A.sort()
        i, j = 0, len(nums) - 1
        while i < j:
            cur = A[i][0] + A[j][0]
            if cur == target:
                return [min(A[i][1], A[j][1]),
                        max(A[i][1], A[j][1])]
            elif cur < target:
                i += 1
            else:
                j -= 1
        return []

# time complexity:O(nlogn)
# space complexity:O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# Hash Map 两遍遍历
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indices = {}  # val -> index

        for i, n in enumerate(nums):
            indices[n] = i

        for i, n in enumerate(nums):
            diff = target - n
            if diff in indices and indices[diff] != i:
                return [i, indices[diff]]
        return []
# time complexity:O(n)
# space complexity:O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# Hash Map 一遍遍历
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index

        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i

# time complexity:O(n)
# space complexity:O(n)

summary:

nums.index(val) —— 列表查找

用法：idx = nums.index(target - n)
场景：查找值对应的索引。面试大忌：在 for 循环里用它，时间复杂度直接退化为 $O(n^2)$。因为它底层是线性扫描。
相关用法：hash_map[key]。面试官想看的是用哈希表将查找降维到 $O(1)$。

Two Pointers —— 双指针法

用法：l, r = 0, len(nums) - 1，配合 while l < r。
场景：仅适用于已排序数组。如果是乱序数组求 Two Sum，排序需 $O(n \log n)$ 且会打乱原始索引（需额外记录），不如哈希表法 $O(n)$ 优。
相关用法：nums.sort()。双指针的前置条件通常是数组有序。

range(i + 1, n) —— 内层循环起点

用法：for j in range(i + 1, len(nums)):
场景：暴力解法（Brute Force）中，内层循环必须从 i + 1 开始。
相关意义：两层含义：一是避免自己加自己（题目限制）；二是去重，避免计算了 (A, B) 又计算 (B, A)。

enumerate(nums) —— 枚举遍历

用法：for i, n in enumerate(nums):
场景：需要同时获取索引 (index) 和值 (value)。这是 Two Sum 这类题的标准起手式。
相关用法：range(len(nums))（只拿索引）、for n in nums（只拿值）。不要在需要索引时手动维护一个 count 变量，太土。

Group Anagrams (LeetCode 49)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# sorting 
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)
        for s in strs:
            sortedS = ''.join(sorted(s))
            res[sortedS].append(s)
        return list(res.values())
# time complexity:O(m∗nlogn)
# space complexity:O(m*n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# hashmap
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            res[tuple(count)].append(s)
        return list(res.values())

# time complexity:O(m*n)
# space complexity:O(m*n)

summary:

tuple(mutable_obj) ——不仅是转换

用法：key = tuple(count)
场景：字典的 Key 必须是不可变类型 (Immutable)。列表 (List) 是可变的，不能作为 Key，必须转化为元组 (Tuple) 才能作为哈希表的键。
相关用法：frozenset。不可变集合，也可以做 Key。

list(d.values()) —— 字典值导出

用法：return list(res.values())
场景：题目只需要返回分好组的列表（List of Lists），不需要 Key。
相关坑点：Python 3 中 d.values() 返回的是一个视图对象 (View)，必须用 list() 强转才能符合题目要求的返回类型 List[List[str]]。

''.join(sorted(s)) —— 字符串标准化

用法：key = "".join(sorted(s))
场景：将字符串排序并重组为用作 Key 的不可变对象。sorted(s) 返回的是列表 ['a', 'e', 't']（可变，不可做 Key），必须用 join 拼回字符串 "aet"。
相关用法：tuple(sorted(s))。如果不拼回字符串，转成元组也可以做 Key。

Top K Frequent Elements (LeetCode 347)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# Counter + most_common
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counts=Counter(nums)
        t1=counts.most_common(k)
        t2=[]
        for i in t1:
            t2.append(i[0])
        return t2

# time complexity:O(nlogn)
# space complexity:O(n)

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

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        arr = []
        for num, cnt in count.items():
            arr.append([cnt, num])
        arr.sort()

        res = []
        while len(res) < k:
            res.append(arr.pop()[1])
        return res

# time complexity:O(nlogn)
# space complexity:O(n)

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

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        heap = []
        for num in count.keys():
            heapq.heappush(heap, (count[num], num))
            if len(heap) > k:
                heapq.heappop(heap)

        res = []
        for i in range(k):
            res.append(heapq.heappop(heap)[1])
        return res
# time complexity:O(nlogk)
# space complexity:O(n+k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#Bucket Sort
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        freq = [[] for i in range(len(nums) + 1)]

        for num in nums:
            count[num] = 1 + count.get(num, 0)
        for num, cnt in count.items():
            freq[cnt].append(num)

        res = []
        for i in range(len(freq) - 1, 0, -1):
            for num in freq[i]:
                res.append(num)
                if len(res) == k:
                    return res
# time complexity:O(n)
# space complexity:O(n)

summary:

count.get(num, 0) —— 字典计数初始化

用法：count[num] = 1 + count.get(num, 0)
场景：统计频次时，若 key 首次出现就给默认值 0，避免 KeyError。
相关用法：defaultdict(int)。效果等价，写法更短：count[num] += 1。

arr.pop()[1] —— 取“当前最大频次元素”

用法：先把 [cnt, num] 放进数组并升序排序，再 arr.pop() 拿末尾最大频次对。
含义：arr.pop() 返回 [cnt, num]，[1] 取的是 num。
场景：Sorting 解法中每次弹出一个最高频元素，直到拿满 k 个。

freq = [[] for _ in range(len(nums) + 1)] —— 桶数组初始化

用法：创建 n + 1 个桶，索引代表“出现次数”，桶里存“出现该次数的数字”。
为什么是 n + 1：元素最高频次可能是 n（全相同），所以要开到下标 n。
相关用法：二维数组初始化统一用列表推导式，避免 [[...]] * n 引用拷贝坑。

Bucket Sort —— Top K 的线性解法

流程：先 count 频次，再把数字丢进 freq[cnt]，最后从高频桶倒序取数直到凑够 k。
复杂度：时间 O(n)，空间 O(n)。
适用场景：数据量大、追求线性复杂度时优先。

Heap (Min-Heap) —— Top K 的工程常用解法

思路：维护一个大小为 k 的最小堆，堆里存 (freq, num)。
操作：每来一个新元素先 heappush，若堆超 k 就 heappop，最终堆内即 Top K。
复杂度：时间 O(n log k)，空间 O(n + k)；当 k << n 时常比全排序更优。

words list

integer 整数
distinct 不同的
duplicate 重复的
constraint 约束条件
approach 方法
time/space complexity 时间/空间复杂度
valid 有效的
anagram 字谜（回文构筑法）
indices 索引
assume 假设
pitfall 陷阱
Brute Force 暴力解法
sublist 子列表
group 分组
enumerate 枚举
Bucket Sort 桶排序
heap 优先队列，堆
min-heap 最小堆
such that 使得
algorithm 算法
discard 放弃
intersection 交集
union 并集
intuition 直觉
Throughout 自始至终
consecutive 连续的
sequence 序列
implement 实施
parenthesis 括号
binary tree 二叉树
traversal 遍历
level order traversal 层序遍历
interval 区间
overlap 重叠
palindrome 回文

tips

1. 语言与阵地

语言死绑 Python：追求极简 API 和开发速度，避开 C++ 繁琐的模板代码。
平台死绑美区：只在 LeetCode.com 刷，强迫适应全英文题目与约束条件。

2. 路线与开销

唯一指定路线：只刷 NeetCode Roadmap。打通它 = 自动通关 Blind 75 + NeetCode 150。
绝不打周赛：外企不考竞赛级偏门题，别浪费周末断联日。
零氪金原则：绝不买 $297 NeetCode Premium。只在收到面试通知的前一个月，买 $35 LeetCode 官方会员突击公司专属题库 (Company Tags)。

3. 核心刷题 SOP (15分钟法则)

Step 1 (闭卷 15 分钟)：拿到题自己想，没思路或写不出立刻停手，绝生死磕。
Step 2 (开卷偷师)：看 NeetCode 免费视频，学 Python 模板和英文思路 (Think Out Loud)。
Step 3 (半闭卷手敲)：关掉视频，凭记忆自己敲到 AC。允许随时查 Python API（如字典操作、内置函数），现阶段不要为默写语法浪费时间。

4. 兜底退路与国内大厂补丁 (Pivot 方案)

唯一需要加练的（考前 1 个月突击）：外企不考中间件的死记硬背。但如果在 2027 年春招/秋招前决定转面国内互联网业务岗，需额外花 1个月 狂背“国产特色八股文”：MySQL 底层（B+树索引）、Redis（缓存穿透/雪崩）、以及各类高并发锁机制。 仅作为临时补丁，勿在日常备战中分散精力。

5. NeetCode 的正确打开方式

NeetCode 的 Visualize the algorithm step by step 功能非常便于理解算法流程，至少对我来说，可视化地过一遍算法流程，就很清晰了。

链接

funny

Throughout heaven and earth I alone am the dumb one, I tried to solve this with trie.