跳转至

算法宝典

算法宝典、leetcode500、algorithms roadmap等的编撰，感谢以下团体的帮助：

  • Leetcode的题
  • Neetcode的教程和roadmap
  • TikTok的面试（给了我刷题和整理数据结构及算法知识的动机）

Python基本功

list

注意，list是引用对象，所以在backtrack或者其他需要存储list值的情况的时候，需要用list(cur_list)进行一个转换处理。list(cur_list)代表创建一个cur_list的副本。

list处理中的一些常见处理方法

zip：可以同时遍历两个list
for elementA, elementB in zip(listA, listB)
注意如果list长度不一样，最短的遍历完成后就会结束遍历

...

...

在list中插入值

ls.insert(2, 'X')
在index为2的地方插入新的值，后面的值顺延

...

...

...

tuple

tuple在python中非常重要和常见，以下是常见用法：

# 建立元组
t = (1, 2, 3)

# 解包元组
a, b, c = (1, 2, 3)

把tuple转换为string：

t = ('a,', 'b', 'c')
result = ''.join(t)

...

...

String

String Slicing是一个重点，很容易弄错。注意字符串string是不可变对象，所以切片后相当于创建了一个新的字符串，如果想修改原字符串的话需要重新赋值。

# 切片的时候[a:b]是不包含s[b]这个字符的，所以：
s[:k] 会获取索引 0 到 k-1的所有元素，因此其长度正好是k
s[x:x+k] 会切一个长度为k的字符串
s[x:x] 会切出一个空字符，即''
s[:-1] 会删掉字符串最后一个元素

string可以直接replace内容，注意这个method是返回新字符

s = "lsjkflsdjf//slkdfjsldkf"
s = s.replace("//", "/")      # 将字符串中的 // 替换为 /
s = s.replace("//", "/", 2)   # 最多替换2次

string的.join()方法在连接list或者tuple的时候，是在所有元素中间进行连接；并且，必须确保所有元素都是string，否则会TypeError。

s = '\'.join(list)

string的split()方法对于首字符和尾字符，切掉以后会保留一个空字符：

string = "/a/b/c/d/e/"
result = string.split("/")
上述操作的结果是：['', 'a', 'b', 'c', 'd', 'e', '']

查找字符串中是否有xxx:

string.find('xxx)
如果有的话会返回首次出现的位置
如果没有的话会返回-1

把string对象转换为list：

string = "helloworld"
ls = list(string)

...

...

...

iter()

iter()是一个强大的迭代器，可以迭代任何可迭代对象，如list, tuple, str, set, dict, generator等。

比如说，假如set中现在只剩下了一个元素，应该怎么办呢？

cur_set = set([15])
iter = iter(cur_set)
this_element = next(iter)

dict (hashmap)

hashmap的key必须是不可变的，但是可以存放list作为value。

hashmap的常见用法：

# 创建hashmap/dict
hashmap = {}
hashmap = dict(name='Bob', age=25)
hashmap = dict(list_x)
hashmap = dict(zip(list_a, list_b))

# 访问元素
hashmap['name']
hashmap.get('name') # 如果没有，会return None
hashmap.get('name',0) # 如果没有，会创建并给予默认值0

# 添加及修改元素
hashmap['key'] = 30
hashmap['key'] = 60 # 修改上面的30（value）

# 删除元素
del hashmap['key'] # 如果不存在会报错
hashmap.pop('key') # 删除并return 对应的value
hashmap.pop('key', "Not Found") # 删除，如果删除失败则返回自定义字符

# clear 清空hashmap
hashmap.clear()

# traverse
for key in hashmap:
    ...
for key in hashmap.keys():
    ...
for value in hashmap.values():
    ...
for key, value in hashmap.items():
    ...

# 获取key的数量
len(hashmap)

# 查找key是否在hashmap中
if key in hashmap:
    ...

# update() 暂时用不到
# copy() 暂时用不到

有一个非常常见的用法，就是比较两个hashmap是否相等。在这种题目中，一定要注意，假设hashmap存储的是元素和频率，那么当一个元素的频率降低到0后，一定要记得删除，否则两个hashmap是不相等的。

基本数学运算

除法:

-1 / 2 == - 0.5
float(-1) / 2 == - 0.5
int(-1/2) == 0  # 向零截断
-1 // 2 == -1   # 向下取整（向负无穷大取整）

注意，如果遇到两个整数相除，算法比赛和leetcode的要求都是向零截断，即保持和C/C++行为一致。

为了防止错误，请使用标准写法： int(float(1)/2)

那么什么时候用向下取整呢？在下面场景中，需要用向下取整：

  • 二分查找中mid=(left+right)//2，可以让mid始终偏左，从而避免无限循环
  • 把n个元素划分为k个区间，每个区间最多容纳n//k个元素
  • tree中的parent索引：parent = (i-1)//2; left_child = 2*i+1, right_child = 2*i + 2

...

...

字母处理

把字母转变为数字，然后偏移后再恢复为字母

base = ord('A')
new_letter = base + 3
new_letter = chr(new_letter) # 转回为D

如果偏移量可能超过Z的范围，可以这么写：
letter = 'A'
offset = 3
new_letter = chr((ord(letter) - ord('A') + offset) % 26 + ord('A'))  # new_letter 为 D

一些常用的处理字母的方法

# 设置一个长度为26的字母频率表
alphabet_counts = [0] * 26

# 出现了一个字母，更新该字母的频率（假设都是大写字母）
alphabet_index = ord(THIS_ALPHA) - ord('A')
alphabet_counts[alphabet_index] += 1

# 找到频率最高的字母和其频率
初始化 max_frequency = 0
初始化 most_frequent_alpha_index = -1
遍历并更新

...

...

Matrix处理

坐标与边界时核心

方向数组用来控制移动，比如最常用的：

directions = [
    [0, 1],
    [0, -1],
    [-1, 0],
    [1, 0]
]

...

...

...

deque

deque即double-ended queue，双端队列。deque的特点是无论从头部还是尾部添加删除元素都很快，都是O(1)时间。

主要用法：

# 创建deque
from collections import deque
queue = deque()
queue = deque([1, 2, 3, 4])

# 从两端添加元素
queue.append(5)      # 从右端添加元素
queue.appendleft(0)  # 从左端添加元素

# 从两端删除元素
queue.pop()     # return 弹出的元素
queue.popleft() # return 弹出的元素

# 旋转
queue = deque(['a', 'b', 'c', 'd', 'e'])
queue.rotate(2)   # 向右旋转2步，变成 ['d', 'e', 'a', 'b', 'c']
queue.rotate(-3)  # 向左旋转3步，变成 ['b', 'c', 'd', 'e', 'a']

...

heapq

heapq是最小堆

import heapq

（1）创建一个最小堆 O(N)
min_heap = []

（2）添加一个元素到最小堆中 O(logN)
heapq.heappush(min_heap, element)

（3）取出最小堆中得最小值（也就是堆顶） O(1)
min_val = min_heap[0]

（4）删除最小值并得到这个数字 O(logN)
removed_val = heapq.heappop(min_heap)

注意，heap不能任意删除元素，如果要删除某个元素，删除后就需要重新建堆：

heap.remove(element)
heapq.heapify(heap) # O(N)的时间复杂度！

...

...

python中的函数

def outer_function(x):
    y = 10  # 这是一个局部变量，只存在于 outer_function 内部

    def inner_function(z):
        # 在这里：
        # z 是 inner_function 的参数
        # x 是一个自由变量 (它不是 inner_function 的参数，也不是其内部定义的局部变量)
        # y 也是一个自由变量 (同上)
        # result 是 inner_function 内部的局部变量
        result = x + y + z
        return result
    return inner_function

# 调用 outer_function，它返回 inner_function
my_closure = outer_function(5)

# 现在调用返回的 inner_function
# 即使 outer_function 已经执行完毕，my_closure (即 inner_function) 仍然能记住 x 和 y 的值
print(my_closure(2)) # 输出: 5 + 10 + 2 = 17

...

Python中的实例变量和类变量

在python中，self声明的变量就是实例变量instance variable。写在函数之前、class之后，和class同级的类变量在python中不需要用self声明，比如：

class MyClass:
    # 这是一个类变量
    # 属于 MyClass 这个类本身，所有 MyClass 的实例都共享它
    class_variable_name = "I belong to the class!"

    def __init__(self, instance_value):
        # 这是一个实例变量
        # 属于 MyClass 的每一个具体实例
        self.instance_variable_name = instance_value

    def show_variables(self):
        # 通过类名访问类变量
        print(f"Class Variable: {MyClass.class_variable_name}")
        # 通过 self 访问实例变量
        print(f"Instance Variable: {self.instance_variable_name}")

# 创建实例
obj1 = MyClass("Value for obj1")
obj2 = MyClass("Value for obj2")

# 访问类变量（推荐通过类名）
print(MyClass.class_variable_name) # 输出: I belong to the class!

# 访问实例变量
print(obj1.instance_variable_name) # 输出: Value for obj1
print(obj2.instance_variable_name) # 输出: Value for obj2

# 验证共享性：修改类变量会影响所有实例
MyClass.class_variable_name = "I've been changed by the class!"
print(obj1.class_variable_name) # 输出: I've been changed by the class!
print(obj2.class_variable_name) # 输出: I've been changed by the class!

Closure 闭包

在 Python 的嵌套函数中，如果要修改的变量是一个位于嵌套函数之外的 可变对象（mutable object） ，比如列表（list）、集合（set）或字典（dict），你是可以修改这个对象自身的内容的，因为你并没有对变量名进行重新赋值。

但是，你不能在嵌套函数中对外部函数的变量进行重新赋值（re-assignment） ，除非使用了 nonlocal 关键字。

Closure可以理解为python中函数的一个个性化副本。因为他不是class的instance，所以closure不是instance，但却是一个可以根据导入参数而个性化定制的函数副本。

注意：在嵌套函数内部访问外部函数是可以的，但是不能修改！python的闭包（closure）只允许访问，而不允许修改！

如果要修改，需要用nonlocal（python3中引入）！

def create_coffee_brewer(preferred_temperature):
    """
    这个函数用来创建一个“咖啡冲泡器”。
    它会记住你偏好的温度。
    """
    print(f"咖啡机设置：记住您的偏好温度是 {preferred_temperature}°C")

    # 这是一个嵌套函数，它才是真正的“冲泡”动作
    def brew_coffee(coffee_type):
        print(f"开始冲泡 {coffee_type}...")
        print(f"使用预设温度 {preferred_temperature}°C 进行冲泡。")
        print("您的咖啡冲泡好了！享受吧！")
        print("-" * 30) # 分隔线

    return brew_coffee # 返回这个冲泡函数

# 小明喜欢喝 92°C 的咖啡
xiaoming_brewer = create_coffee_brewer(92) 
# 输出：咖啡机设置：记住您的偏好温度是 92°C

# 小红喜欢喝 88°C 的咖啡
xiaohong_brewer = create_coffee_brewer(88)
# 输出：咖啡机设置：记住您的偏好温度是 88°C

print("\n--- 不同的咖啡冲泡 ---")

# 现在小明开始冲泡他的拿铁
xiaoming_brewer("拿铁")
# 输出：
# 开始冲泡 拿铁...
# 使用预设温度 92°C 进行冲泡。
# 您的咖啡冲泡好了！享受吧！
# ------------------------------

# 小红开始冲泡她的美式
xiaohong_brewer("美式")
# 输出：
# 开始冲泡 美式...
# 使用预设温度 88°C 进行冲泡。
# 您的咖啡冲泡好了！享受吧！
# ------------------------------

# 即使 create_coffee_brewer 函数已经执行完了，
# xiaoming_brewer 和 xiaohong_brewer 仍然分别“记住”了它们各自的温度。

...

Assert

python中assert很简单。

...

Array/List/Stack/SlidingWindow

因为在python中，array, dynamic list, stack都是用list来实现，所以这里归为一类。

1. Array/List 面试核心技巧汇总

下面是8个你应该熟练掌握的核心技巧。

1. 双指针 (Two Pointers)

这是最基本也是最高频的技巧之一，通过使用两个指针在数组上同向或反向移动来解决问题。

  • 核心思想 ：通过指针的移动，将 O(N²) 的暴力解法优化到 O(N)。
  • 适用场景/题目关键词 ：
  • 排序数组 (Sorted Array) ：这是双指针最常见的应用场景。
  • 寻找数对 (Find a pair) ：如“两数之和”、“三数之和”。
  • 回文判断 (Palindrome) ：一个指针从头，一个指针从尾。
  • 原地修改/删除 (In-place modification) ：如“删除有序数组中的重复项”、“移动零”。
  • 链表中的环、中点 ：快慢指针是其在链表中的变体。

  • 如何判断 ：

  • 反向指针 (Colliding Pointers) ：题目涉及已排序的数组，并且要求寻找满足特定条件的数对或 三元组 。指针一个在头 left，一个在尾 right，向中间靠拢。

  • 快慢指针 (Fast & Slow Pointers) ：主要用于 链表 ，判断是否有环、寻找环的入口、寻找中点。在数组中可用于“删除重复项”等。一个指针走得快，一个走得慢。

  • 同向指针 (Same-direction Pointers) ：通常与滑动窗口结合，一个指针 j探索新元素，一个指针 i收缩边界。

  • 典型例题 ：

  • LeetCode 1: Two Sum (若数组已排序)
  • LeetCode 15: 3Sum
  • LeetCode 125: Valid Palindrome
  • LeetCode 26: Remove Duplicates from Sorted Array

2. 滑动窗口 (Sliding Window)

在数组上维护一个大小可变的“窗口”，不断滑动这个窗口来寻找满足特定条件的最优子数组/子串。

  • 核心思想 ：维护一个窗口 [i, j]，通过移动 j来扩大窗口，在不满足条件时移动 i来收缩窗口。避免了暴力枚举所有子数组的 O(N²) 复杂度。
  • 适用场景/题目关键词 ：
  • 连续子数组/子串 (Contiguous/Consecutive Subarray/Substring) ：这是最明确的信号。
  • 最长/最短... (Longest/Shortest...) : 要求找到满足条件的最长或最短的连续子数组。
  • 最大/最小... (Maximum/Minimum...) : 例如求“和最大的定长子数组”。
  • 包含... (Contains...) : 例如“找到包含所有目标字符的最短子串”。
  • 如何判断 ：题目要求对连续子数组进行操作，并且求解的目标是 最值 （最长、最短、最多、最少）。滑动窗口通常处理的条件是 单调的 ，比如窗口扩大，窗口内的不同字符数会增加或不变，不会减少。
  • 典型例题 ：
  • LeetCode 3: Longest Substring Without Repeating Characters
  • LeetCode 76: Minimum Window Substring
  • LeetCode 209: Minimum Size Subarray Sum (注意和前缀和问题的区别，这里数组元素为正)

3. 前缀和 (Prefix Sum)

我们刚刚深入讨论过的技巧，通过预计算累加和来快速求得任意区间的和。

  • 核心思想 ：sum(i, j) = prefix_sum[j] - prefix_sum[i-1]。将“求区间和”这个O(N)的操作降为O(1)。
  • 适用场景/题目关键词 ：
  • 子数组的和 (Subarray Sum) ：这是最直接的信号。
  • 和为K (Sum equals K) ：寻找和为特定值的子数组个数或是否存在。
  • 矩阵的子矩阵和 (Submatrix Sum) ：可以扩展到二维。
  • 如何判断 ：题目反复要求计算 不同子数组的和 ，特别是当数组中包含负数时（滑动窗口失效），或者要求寻找和为定值K的子数组个数时。通常需要搭配哈希表来存储和出现的频率。
  • 典型例题 ：
  • LeetCode 560: Subarray Sum Equals K
  • LeetCode 523: Continuous Subarray Sum (和为K的倍数)
  • LeetCode 304: Range Sum Query 2D - Immutable

4. 哈希表 (Hash Map / Dictionary)

一种“万金油”工具，利用键值对提供O(1)复杂度的查找、插入和删除。

  • 核心思想 ：空间换时间。
  • 适用场景/题目关键词 ：
  • 频率统计 (Frequency Count) ：如“出现次数超过一半的元素”。
  • 查找/匹配 (Lookup/Matching) ：如“两数之和”的原地哈希解法。
  • 去重 (Deduplication) 。
  • 需要记录历史信息 ：最典型的就是与“前缀和”技巧的结合。
  • 如何判断 ：当题目需要快速知道“某个元素是否存在”或“某个元素出现了几次”时，就应该立刻想到哈希表。它本身是一种数据结构，但使用它解决问题已经成为一种核心技巧。
  • 典型例题 ：
  • LeetCode 1: Two Sum
  • LeetCode 49: Group Anagrams
  • 与几乎所有其他技巧结合使用。

在有序集合中进行高效查找的算法。

  • 核心思想 ：每次将搜索空间减半，实现O(log N)的查找效率。
  • 适用场景/题目关键词 ：
  • 已排序数组 (Sorted Array) ：最直接的应用场景。
  • 寻找特定值/边界 (Find an element/boundary) ：如“寻找第一个/最后一个出现的位置”。
  • 旋转排序数组 (Rotated Sorted Array) 。
  • 答案是一个范围内的整数 ：当题目可以转化为“猜答案”时，例如“求一个最小值X，使得...条件成立”，可以在答案的取值范围 [min_val, max_val] 上进行二分。

  • 如何判断 ：

  • 数组已排序是首要信号。

  • 题目虽然没说数组有序，但可以抽象出一个 单调的判断函数 。例如，题目的解在一个范围内，并且当 x是解时，所有 >x的值也满足某种性质，这时就可以对答案进行二分。

  • 典型例题 ：

  • LeetCode 704: Binary Search
  • LeetCode 33: Search in Rotated Sorted Array
  • LeetCode 875: Koko Eating Bananas (对答案进行二分)

6. 单调栈/队列 (Monotonic Stack/Queue)

维护一个内部元素单调递增或递减的栈/队列。

  • 核心思想 ：在遍历数组时，通过维护栈内元素的单调性，可以O(1)地找到当前元素左边/右边第一个比它大/小的元素。
  • 适用场景/题目关键词 ：
  • 下一个更大/更小元素 (Next Greater/Smaller Element) 。
  • 子数组范围问题 ：例如“计算所有子数组的最小值之和”。
  • 柱状图/矩形面积 ：如“柱状图中最大的矩形”。
  • 如何判断 ：当问题需要寻找一个元素与其左/右侧第一个更大或更小元素之间的关系时，这几乎是单调栈的“专用赛道”。
  • 典型例题 ：
  • LeetCode 496: Next Greater Element I
  • LeetCode 84: Largest Rectangle in Histogram
  • LeetCode 907: Sum of Subarray Minimums

7. 原地修改 / 循环排序 (In-place Modification / Cyclic Sort)

在不使用额外数据结构（或只使用O(1)额外空间）的情况下，通过在原数组上进行元素交换来达到目的。

  • 核心思想 ：利用数组的索引和值之间的关系来放置元素。
  • 适用场景/题目关键词 ：
  • 空间复杂度要求O(1) 。
  • 数组元素在特定范围内，如 1到N 。
  • 寻找重复/缺失的数字 (Find duplicate/missing number) 。
  • 如何判断 ：当题目明确要求 O(1)空间复杂度，并且数组元素范围和数组长度有密切关系时（如 N个元素，范围是 [1, N]），应优先考虑能否将数字 i 放到数组的第 i-1 个索引位置。
  • 典型例题 ：
  • LeetCode 448: Find All Numbers Disappeared in an Array
  • LeetCode 287: Find the Duplicate Number
  • LeetCode 41: First Missing Positive

8. 贪心 + 排序 (Greedy + Sorting)

先对数组进行排序，然后根据某种贪心策略进行选择，以期得到全局最优解。

  • 核心思想 ：排序使得问题呈现出某种规律，从而让每一步的局部最优选择能够导向全局最优。
  • 适用场景/题目关键词 ：
  • 区间问题 (Intervals) ：如合并区间、无重叠区间、会议室安排。
  • 分配/调度问题 。
  • 如何判断 ：当问题涉及多个“物品”或“事件”（如区间），需要从中选择一部分来满足某个条件或达到最优时，可以尝试先排序，再遍历做贪心选择。排序的依据（按起点、按终点）是解题关键。
  • 典型例题 ：
  • LeetCode 56: Merge Intervals
  • LeetCode 435: Non-overlapping Intervals
  • LeetCode 452: Minimum Number of Arrows to Burst Balloons

...

Sliding Window

滑动窗口非常考验思考。

寻找最长长度的子序列问题

寻找最长长度的子序列问题，其对于window的设置有两个特点要记住：

  • 高水位原则：算法目的是找到最高水位，因此不关心退步，即比最高window更小的window是不需要精确维护的
  • 乐观锁（参考leetcode424）：window的潜力由一个过去的max_freq锁死。当且仅当新的window超过该潜力的时候，才需要更新，否则不需要更新。

...

...

所有子序列问题合集

下面将常见的题型、思想和解法进行归类：

类型一：连续子数组/子串问题

这类问题通常要求在数组的一个连续片段上进行计算。

子类型 核心方法 适用场景 经典例题
求最值/特定性质 滑动窗口 (Sliding Window) 寻找满足某个条件的最长/最短/数量最多的连续子数组。窗口可以根据条件进行伸缩。 LeetCode 3: 无重复字符的最长子串``LeetCode 209: 长度最小的子数组
和/差有关 前缀和 + 哈希表 (Prefix Sum + HashMap) 求解子数组的和等于某个值 k的问题。哈希表用来存储 {前缀和: 出现次数/索引}，快速查找 prefixSum - k是否存在。 LeetCode 560: 和为 K 的子数组``LeetCode 523: 连续的子数组和
最大/最小和 动态规划 (Kadane's Algorithm) 寻找连续子数组的最大和。dp[i]定义为以 nums[i]结尾的最大子数组和。 LeetCode 53: 最大子数组和

类型二：非连续子序列问题

这类问题允许你从数组中挑选元素，只要保持相对顺序即可。动态规划 (Dynamic Programming, DP) 是解决这类问题的王牌。

子类型 核心方法 适用场景 & DP状态定义 经典例题
最长递增/递减子序列 1. 动态规划 (O(N2)) `` 2. DP + 二分查找 (O(NlogN)) dp[i]通常定义为以 nums[i]结尾的 LIS 的长度。更优的解法维护一个“耐心排序”数组。 LeetCode 300: 最长递增子序列 (LIS)
两个序列的公共问题 二维动态规划 (O(MtimesN)) 比较两个字符串/数组 s1,s2。dp[i][j]通常定义为 s1的前 i个字符和 s2的前 j个字符的解。 LeetCode 1143: 最长公共子序列 (LCS)``LeetCode 72: 编辑距离
组合/计数类子序列 背包类动态规划 / DFS + 记忆化 问题可以转化为：是否能从数组中挑选一些元素（一个子序列）凑成目标值 target。 LeetCode 416: 分割等和子集 LeetCode 494: 目标和LeetCode 322: 零钱兑换 (背包思想)
回文子序列 区间动态规划 dp[i][j]通常定义为从 i到 j的区间内的解。依赖于更小区间 dp[i+1][j-1]的解。 LeetCode 516: 最长回文子序列

类型三：本质是集合问题的子序列问题

比如128题，最长连续子序列，本质是一个集合问题。

...

Sorting and Searching

排序和搜索问题

Sorting

Quick Sort

...

常见的Searching

核心搜索算法概览

算法 (Algorithm) 时间复杂度 (Time Complexity) 空间复杂度 (Space Complexity) 数据结构要求 核心思想
线性搜索 (Linear Search) O(n) O(1) 无要求 逐个检查
二分搜索 (Binary Search) O(logn) O(1)或O(logn) 必须有序 分而治之 (Divide and Conquer)
哈希查找 (Hash Search) 平均O(1), 最坏O(n) O(n) 哈希表 (Hash Table) 直接映射
广度优先搜索 (BFS) O(V+E), V for nodes, E for edges O(W) 图 (Graph) / 树 (Tree) 逐层扩展，找最短路径
深度优先搜索 (DFS) O(V+E), W for the widest layer's nodes O(H) 图 (Graph) / 树 (Tree) 一条路走到底再回头

判定条件容易写错，一定是left <= right，因为左右指针相遇后还要再检查一次这个最后一个元素。

Graph

DFS

常用DFS模板：

import collections
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0

        rows = len(grid)
        cols = len(grid[0])
        count = 0

        # 在开头先把移动的方向（一般都是四个）
        directions = [
            [0,1],
            [0,-1],
            [1,0],
            [-1,0]
        ]

        def dfs(r,c):
            for direction in directions:
                dx, dy = direction
                new_r, new_c = r + dx, c + dy

                if 0 <= new_r < rows and 0 <= new_c < cols and grid[new_r][new_c] == '1':
                    grid[new_r][new_c] = '0'
                    dfs(new_r, new_c)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":
                    count += 1
                    dfs(r, c)

        return count

BFS

BFS遍历图的时候，添加到队列的是当前queue中popleft得到的node所有的有效的、未访问过的邻居。

常用BFS模板：

import collections
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0

        rows = len(grid)
        cols = len(grid[0])
        count = 0

        # 在开头先把移动的方向（一般都是四个）
        directions = [
            [0,1],
            [0,-1],
            [1,0],
            [-1,0]
        ]

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":
                    count += 1
                    queue = deque() # empty queue
                    queue.append((r,c)) # add to queue
                    while queue:
                        cur_r, cur_c = queue.popleft()
                        for direction in directions:
                            dx, dy = direction
                            new_r, new_c = cur_r + dx, cur_c + dy
                            if 0 <= new_r < rows and 0 <= new_c < cols and grid[new_r][new_c] == '1':
                                # 有的题需要设置一个visited(set)来记录是否访问过
                                grid[new_r][new_c] = '0'
                                queue.append((new_r,new_c))

        return count

常用BFS改DFS的方法：

import collections
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0

        rows = len(grid)
        cols = len(grid[0])
        count = 0

        directions = [
            [0,1],
            [0,-1],
            [1,0],
            [-1,0]
        ]

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":
                    count += 1

                    # ※ 把BFS中这里的deque改为stack就可以了
                    stack = []
                    stack.append((r,c)) # add to stack
                    while stack:
                        cur_r, cur_c = stack.pop()
                        for direction in directions:
                            dx, dy = direction
                            new_r, new_c = cur_r + dx, cur_c + dy
                            if 0 <= new_r < rows and 0 <= new_c < cols and grid[new_r][new_c] == '1':
                                grid[new_r][new_c] = '0'
                                stack.append((new_r,new_c))

        return count

上述反映了DFS的本质是个stack，如果是dijskta的话就是把stack换成heap

Shortest Path

首先path题，比如从左上角找到右下角，不需要全局循环，而是从起点开始一层一层找。找最短路径用BFS。

连通检查的时候务必记住三点检查，缺一不可：

  1. 是否出界
  2. 是否访问过
  3. 是否通路

然后在队列中，我们不光记录r, c, 还要记录length。

最短路径基本思路如下：

首先检查起点和终点，如果起点和终点是障碍物，直接结束

初始化队列，元素为(row, col, path_length)
创建visited集合
构建方向数组

当队列中还有元素的时候：
    头元素出队
    检查头元素是否已经到达终点，如果已经到达，那么就return通路
    探索合法方向的邻居：
    检查邻居的有效性（三点检查缺一不可）
    将有效的邻居加入队列和visited集合

如果循环结束后还没有找到终点，说明没有通路

为什么检查到元素达到终点就能立刻return呢？这是因为BFS探索是一层一层往外探索的，所以BFS第一次找到的路径，一定是最短的！

多源扩散

如果一个matrix中有多个源头同时进行扩散，那么非常适合用BFS来解决。只要把源头全部入队，然后开始一层一层（层序遍历），就可以完成。

...

Backtracking

1. Permutation/Combination

排列组合问题长得很像，解题的时候都是在常规回溯上进行Pruning，只是根据排列or组合的不同需要选择startIndex or used list来pruning。

这两个工具的选用，取决于一个根本问题：你是在解决“组合(Combination)”问题还是“排列(Permutation)”问题？

  1. startIndex 标记为核心的主框架：用于组合类问题 (Subsets, Combination Sum)
  2. 核心目的 ：避免产生重复的 组合 。
  3. 问题特征 ：元素的顺序不重要。[1, 2] 和 [2, 1] 被视为同一个组合。
  4. 工作原理 ：通过 startIndex，我们强制规定了下一次选择的数 必须在当前数之后 （或就是当前数）。例如，当你选择了 nums[i] 之后，下一次递归从 backtrack(i+1) 开始，你就再也没有机会回头去选择 nums[i] 之前的数了。这天然地保证了所有组合都是按索引升序的，从而避免了 [1, 2] 和 [2, 1] 同时出现。
  5. 一句话总结 ：startIndex 是为了防止往回取数，从而避免重复组合。
  6. used 数组为核心的主框架：用于排列类问题 (Permutations)
  7. 核心目的 ：记录在当前路径下，哪些位置的数已经被使用过。
  8. 问题特征 ：元素的顺序很重要。[1, 2] 和 [2, 1] 是两个不同的排列。
  9. 工作原理 ：在生成排列时，你每次都需要从所有数中进行选择（除了已经用过的）。所以 for 循环必须每次都从 0 开始。used 数组就像一个笔记本，告诉你对于当前正在构建的这个排列，哪些数字（通过它们的原始索引）已经被放进去了，不能再放了。
  10. 一句话总结 ：used 数组是为了防止同一个元素在一个排列中被重复使用。

对于你正在做的 Subsets II 这道题，它是一个组合问题（子集的顺序不重要），所以我们选择 startIndex 方案。

如何选择正确的回溯方法？（决策清单）

当遇到一个回溯问题时，可以按以下顺序问自己几个问题来确定模板：

问题1：结果中的元素顺序是否重要？

  • 是 (顺序重要) -> 这是排列问题 -> 使用 used 数组 ，for 循环从 0 开始。
  • 否 (顺序不重要) -> 这是组合/子集问题 -> 使用 startIndex ，for 循环从 startIndex 开始。

问题2：输入数组中是否有重复元素？

  • 是 -> 需要去重 -> 必须先排序 nums.sort() ，然后在 for 循环中加入剪枝逻辑。
  • 排列问题的剪枝：if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue
  • 组合问题的剪枝：if i > startIndex and nums[i] == nums[i-1]: continue
  • 否 -> 不需要去重 -> 使用基础模板即可。

问题3：输入数组中的元素是否可以被无限次重复使用？ (主要针对组合问题)

  • 是 (例如 LeetCode 39. Combination Sum) -> 递归时 startIndex 不变，即 backtrack(i, ...)，允许下一轮继续选择当前数。
  • 否 (例如 LeetCode 40. Combination Sum II / Subsets) -> 递归时 startIndex 加一，即 backtrack(i + 1, ...)，不允许重复使用同一个位置的元素。

回溯问题思路清单

下表列举了最核心的排列组合问题的区别及注意要点：

目标 (Problem) 关键点 (Key Points) 回溯主干逻辑 (Core Logic) 去重/剪枝逻辑 (Pruning)
46. Permutations
(全排列) [1,2,3]		 排列(顺序重要)
无重复元素		 used数组记录已用元素。
for循环从 0到 n-1 。
递归 backtrack()。		 无
47. Permutations II
(全排列II) [1,1,2]		 排列(顺序重要)
有重复元素需要避免重复结果		 used数组。循环从 0到 n-1 。
递归 backtrack()。		 先排序
剪枝条件 ：如果当前数字与前一个相同，
并且前一个相同的数字在当前排列中
没有被使用，则跳过当前数字。
if i > 0 && nums[i] == nums[i-1] && !used[i-1]
78. Subsets
(子集)
  [1,2,3]		 组合(顺序不重要)
无重复元素		 startIndex记录起点。
for循环从 startIndex到 n-1。
递归 backtrack(i + 1)。		 无
90. Subsets II
(子集II) [1,2,2]		 组合(顺序不重要)
有重复元素		 startIndex记录起点。循环从 startIndex到 n-1。
递归 backtrack(i + 1)。		 先排序 。
剪枝条件 ：在同一层递归中，
如果当前数字与前一个数字相同，
则跳过当前数字。
39. Combination Sum
(组合总和)  [2,3,6,7],target=7		 组合(顺序不重要)
无重复元素
元素可无限复用		 startIndex记录起点。
for循环从 startIndex到 n-1。
递归 backtrack(i)(注意是 i不是 i+1)。		 可选剪枝：若 sum + nums[i] > target
则可提前终止 (因为数组已排序)。
40. Combination Sum II
(组合总和II) 
 [10,1,2,7,6,1,5]		 组合(顺序不重要)
元素不可复用		 startIndex记录起点。
for循环从 startIndex到 n-1。
递归 backtrack(i + 1)。		 先排序 。剪枝条件 ：在同一层递归中，
如果当前数字与前一个数字相同，
则跳过当前数字。

核心要点 ：

  • 看到 排列 ，立刻想到 used 数组 。
  • 看到 组合/子集 ，立刻想到 startIndex 。
  • 看到 输入有重复 ，立刻想到 先排序，后剪枝 。
  • 看到 元素可复用 ，立刻想到递归时 startIndex 不加一 (backtrack(i))。

把这个清单和决策流程记在心里，以后再遇到回溯问题，你就能迅速地选择正确的工具和模板来解决了。

...

...

...

...

DP

对于求职者来说，DP 的熟练程度往往能决定面试的层级和结果，尤其是在 Google、Meta、ByteDance 这类重视算法能力的公司。

为什么面试官喜欢考动态规划？

面试官用 DP 问题不是为了难住你，而是因为它能非常有效地考察候选人的多项核心能力：

  1. 抽象建模能力 ：能否将一个看似复杂的问题，抽象成一个数学模型（状态和状态转移）。
  2. 逻辑分解能力 ：能否将一个大问题，拆解成性质相同、规模更小的子问题。
  3. 最优子结构和重复子问题 ：是否能识别出问题是否具备 DP 的两个核心特征。
  4. 思维严谨性 ：能否清晰地定义 DP 状态、推导状态转移方程，并处理好边界条件和初始值。
  5. 代码实现能力 ：能否将脑中的递推公式，无误地转化为清晰的代码。

一个能流畅地分析并解决 DP 问题的人，通常意味着他具备了很强的逻辑思维和解决复杂问题的潜力。

面试中常见的 DP 类型有哪些？

你不需要掌握所有 DP 的花样，但以下几个经典模式是面试的“高频区”，掌握它们的性价比极高：

1. 入门级/基础模型

这类题通常是用来破冰或检验你是否了解 DP 的基本概念。

  • 斐波那契数列 (Fibonacci Number)
  • 爬楼梯 (Climbing Stairs)

2. 一维序列 DP (Linear DP)

这是最常见、最基础的模式，在一个序列（数组）上进行动态规划。

  • 打家劫舍 (House Robber) : 学习如何在不相邻的元素中取最优解。
  • 最长递增子序列 (Longest Increasing Subsequence) : O(n^2) 和 O(n log n) 两种解法都能体现你的水平。
  • 最大子数组和 (Maximum Subarray) : 虽然有更优的 O(n) 解法，但它也是 DP 的一个好例子。

3. 二维矩阵/网格 DP (Grid DP)

在一个二维网格上从起点走到终点，求解路径数量或最优路径。

  • 不同路径 (Unique Paths) : 网格 DP 的入门题。
  • 最小路径和 (Minimum Path Sum)

4. 字符串 DP (String DP)

涉及两个或多个字符串的匹配、编辑等问题。

  • 最长公共子序列 (Longest Common Subsequence) : 极其经典，是很多字符串 DP 问题的基础。
  • 编辑距离 (Edit Distance) : Hard 难度，但思想非常有代表性，是双字符串 DP 的“天花板”之一。

5. 背包问题 (Knapsack Problem)

这是一个超级模式，有多种变体，是面试的热点。

  • 0-1 背包 : 每个物品只能选一次。（如 分割等和子集 (Partition Equal Subset Sum) ）
  • 完全背包 : 每个物品可以无限次选择。（如 零钱兑换 (Coin Change) ）

对于大多数 NG 和社招面试，能熟练掌握以上 5 种模式，就已经能覆盖 80%以上 的 DP 面试题了。至于更高级的区间 DP、树形 DP、状态压缩 DP 等，除非你面的岗位非常核心或级别很高，否则遇到的概率较小。

如何在面试中优雅地解答一道 DP 题？

如果你在面试中遇到一道疑似 DP 的题，可以遵循一个非常清晰的沟通和解题步骤，这会让面试官对你的评价大大加分：

  1. 先上暴力解（通常是递归） 不要一上来就想 DP。先用最直观的递归（自顶向下）把问题的逻辑讲清楚。比如：“我们可以定义一个函数 solve(i)，它表示从第 i 个位置开始能得到的最终答案……”
  2. 指出重复子问题（画出递归树） 在纸上或白板上画出递归树，明确地告诉面试官：“我们可以看到，solve(i-k) 这样的子问题被重复计算了很多次，这里存在优化空间。”
  3. 加入备忘录（记忆化搜索） 在暴力递归的基础上，引入一个 memo 数组或哈希表，存储已经计算过的子问题的结果，避免重复计算。这其实就是 自顶向下 (Top-Down) 的 DP ，对于很多面试来说，这已经是一个非常好的答案了。
  4. （进阶）转为迭代（DP Table） 如果时间允许，或者你想展示更强的能力，可以进一步转为 自底向上 (Bottom-Up) 的 DP 。
  5. 定义 DP 数组含义 : “现在我们换一种思路，用一个 dp 数组来解决。dp[i] 的含义是……” (这是最关键的一步！)
  6. 推导状态转移方程 : “dp[i] 的值可以由 dp[i-1] 和 dp[i-2] 推导出来，关系是……”
  7. 确定遍历顺序和初始值 : “我们需要从左到右遍历，并且 dp[0] 和 dp[1] 的初始值分别是……”

这个“ 暴力递归 -> 记忆化搜索 -> DP Table ”的思考路径，能清晰地展示你的思维过程，即使最后没能写出最优解，面试官也会对你的分析能力非常满意。

总之，DP 是硬核，但更是你展示算法实力的绝佳舞台。 把它当作一个必须攻克的山头，你的面试竞争力会提升一个档次。

...

算法天梯题目整理

本部分的内容主要是整理算法天梯内容，即我正在维护的一个“Algorithm Roadmap”项目：https://jeffliulab.github.io/algorithm-roadmap/

Stack类

Stack >> 辅助栈/节点强化思想

Min Stack（两种方法，强化节点或者使用辅助栈）

Stack >> 括号问题

Valid Parentheses：用stack来判断是否是valid括号组合 Evaluate Reverse Polish Notation：逆波兰运算 Generate Parentheses：生成括号

辅助栈/节点强化思想 >> 单调栈 Monotonic Stack

保持单调递增或者单调递减，用于高效解决“下一个更大/下一个更小”问题。在pop和push的时候，单调栈始终保持stack内元素值按照单调顺序排列。

单调递增stack：top保持最大，用于查找下一个更小

单调递减stack：top保持最小，用于查找下一个更大

  1. Daily Temperatures