Leetcode

这个界面会记录我在写 LeetCode 的时候总结到的关键知识点以及几个典型题目，或者有收获的题目的知识。

代码大多都是用 Python3 来写的。

我的 LeetCode.cn 主页

算法掌握度

代码随想录打卡

代码随想录 ↗

学而不思则罔，思而不学则殆。 -- 从学开始

数组 📊

• 1. 数组理论基础 ↗ - (数组是物理上连续的数据结构，通过下标获取值)
• 2. 二分查找 ↗ - (左毕右闭区间 [left, right]，根据中点循环更新区间，直到中点命中目标)
• 3. 移除元素 ↗ - (双指针法，逐个原地更新原数组，快指针读取原数组，慢指针更新得到新数组)
• 4. 有序数组的平方 ↗ - (双指针比大小，变成微笑曲线，头尾比较得到较大的，从复制数组尾部开始放)
• 5. 长度最小的子数组 ↗ - (双指针法实现滑动窗口，连续数组下可完全遍历，默认快指针移动，满足条件则慢指针移动收缩)
• 6. 螺旋矩阵II ↗ - (模拟填写顺序，上右下左，不涉及算法，用四个指针约束当前处理的边界，并填入矩阵，左开右闭处理完该行/列再到下一步)
• 7. 区间和 ↗ - (前缀和计算区间和，前缀和数组，则 区间和 等于 前缀和数组[a] 减去 前缀和数组[b]，另 ACM 输入输出模式 python 用 sys.stdin.read)
• 8. 开发商购买土地 ↗
• 9. 总结篇 ↗ - (二分法，双指针法，滑动窗口，模拟，前缀和)

链表 🔗

• 1. 链表理论基础 ↗ - (定义链表用 O(1) 两端增减，O(n) 查询，物理上随机分布。)
• 2. 移除链表元素 ↗ - (删除链表节点仅需 current = dummy.next，current.next = current.next.next)
• 3. 设计链表 ↗ - (五个链表的常用操作，跳出操作的边界条件很关键，get，addAtHead，addAtTail，addAtIndex`)
• 4. 反转链表 ↗ - (双指针法，循环操作模，前一个节点 previous，当前节点 current，后一个节点 after，输入 pre 则有后两个)
• 5. 两两交换链表中的节点 ↗ - (画图理解，按模块循环处理，单模块涉及三个 pre -> cur -> aft，更改指向，下一循环更新模块，边界 while 可以最后设置)
• 6. 删除链表的倒数第N个节点 ↗ - (双指针，快慢指针，虚拟头节点，快针先走 n + 1，然后快慢针一起走)
• 7. 链表相交 ↗ - (交错相接法，while 条件为 node1 != node2，相交或都为 None 时退出)
• 8. 环形链表II ↗ - (双指针快慢指针两步法，一 求 fast(2) slow(1) 相遇点，二 根据先验求 node1(head 开始) 和 node2(相遇点 开始) 的交点，即为结果)
• 9. 总结篇 ↗ - (虚拟头节点，链表基本操作，思维导图解释环形链表找入口的算法)

哈希表 🗂️

• 1. 哈希表理论基础 ↗ - (高级数组，哈希映射位置，O(1)时间复杂度，碰撞用拉链法/线性探测法)
• 2. 有效的字母异位词 ↗ - (26位数组记录对应值，一加一减，全为零则满足，字母用 ascii 值 ord() 计算下标)
• 3. 两个数组的交集 ↗ - (使用 set 或者用数组记录，下标即为数字)
• 4. 快乐数 ↗ - (用集合，记录中间的数字 n，数字位平方和用字符串逐个取，循环判断)
• 5. 两数之和 ↗ - (哈希法记录经过的数字，找找和它匹配的那个数字是否在曾经经过的数字里，字典存储)
• 6. 四数相加II ↗ - (分为两组暴力分别求 AB CD 之和，哈希法记录 AB 和的字典 O(1)，遍历 CD之和找字典中满足条件的)
• 7. 赎金信 ↗ - (O(3n) 类似有效字母异位词，数组记录 字母 出现次数，用字母编号作为 key，区别是只需要小于等于)
• 8. 三数之和 ↗ - (双指针法，固定前一个数，后两个数先排序，再用双指针从两端起查找)
• 9. 四数之和 ↗ - (类似 三数之和 区别在于固定前两个数固定第一个数，第二个数求剩下两个的和是否满足，双指针前后找标值)
• 10. 总结篇 ↗ - (哈希表用于快速判断一个值是否在集合里，小数据时数组作为哈希表，大数据时 dict 作为哈希表)

字符串 📝

双指针法 👥

栈与队列 📚

• 1. 栈与队列理论基础 ↗ - (python queue 的实现是基于 deque，deque 的 c 源码是实现了 双向循环链表 + 定长数组)

• 2. 用栈实现队列 ↗ - (入栈和出栈两个栈，腾空入栈到出栈实现 FIFO，出栈还有值时别腾空入栈)

• 3. 用队列实现栈 ↗ - (用两个队列实现一个栈，其中一个入栈出栈，另一个用来腾空第一个队列，取出最后一个抛出)

• 4. 有效的括号 ↗ - (用栈存储，遇到匹配的括号则消掉，有三种情况出错，从右括号开始、最后还有剩余、对应的括号不匹配)

• 5. 删除字符串中的所有相邻重复项 ↗ - (用数组实现，双指针法单数组处理，相邻情景下先同步再判断)

• 6. 逆波兰表达式求值 ↗ - (运算的后缀表达式有利于计算机运算，用栈保存，如果遇到符号，则把前两个数取出根据符号运算，结果压回)

• 7. 滑动窗口最大值 ↗ - (创建单调队列保存数值型的最大值队列，双向队列，push，pop，front 方法，push 等于时也可允许重复值)

• 8. 前K个高频元素 ↗ - (用 小顶堆 来维护频数数组，弹出时自动弹出最小值，留下最多的，实际使用 优先队列)

• 9. 栈与队列总结 ↗ - (栈与队列的基本实现，底层实现，栈在计算机系统中的应用，单调队列和优先队列)

二叉树 🌳

回溯算法 🔄

贪心算法 🎯

动态规划 📈

单调栈 📊

图论 🌐

链表

知识

链表的结构可以认为是一个“节点”，一般会初始化为一个链表实例

• 指代一个链表节点实例
• 需要调用 .val 方法才能获取值
• 调用 .next 方法可以获取下一个节点

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

一个经典的链表可以用列表的形式表示，但它不是链表：[1,2,3,4,5] 或 [1,2,3,4,5,null]

而是一个链，并且最终的节点通常指向空：[1] -> [2] -> [3] -> [4] -> [5] -> null

链表和变量表示

链表变量代表的是一整个节点，而不是单个值。eg: head.val, head.next

这是理解链表和链表相关代码的重要内容，因为对于一个链表，要意识到

• 通过 node.val 获取值
• 通过 node.next 获取下一个值
• 通过迭代获取整个链表的内容

这意味着虽然我们会表示 node: [1] -> [2] -> [3] -> [4] -> [5] -> null，但事实上，它是 node: [1] -> ?

除非"事先知道"，否则我们只能通过遍历这个节点的方式才能知道这个链表实际上是怎样的

# node: ?
def show_listnode(node:ListNode) -> List:
    show_list = []

    cur = node
    while cur.next:
        show_list.append(cur.val)
        cur = cur.next

    return show_list
# node list: [1,2,3,4,5]

• 链表的变量的实际是指针，且是单个节点的指针，指向内存中的某个物理数据。因此无论多少个变量，只要指向同一个节点（如 head），他们一致。如果其中一个修改，另一个也修改。
  • a=head, b=head, a.val=1 => b.val -> 1

暂存链表节点

暂存是一个非常好的思路。cur 和 tem = cur.next ，我们就迭代得到了两个链表

• cur: [1, 2, 3, 4, 5, null]
• tem: [2, 3, 4, 5, null]

这两个链表依托于同一个物理数据实体，但他们往下的链是不同的。

通过这样的方式，我们可以在不改变 cur 原有链表的前提下，处理一个链表复制。

如，通过暂存节点更新指针。cur = list1, cur = cur.next。

• list1: [1, 2, 3, 4, 5, null]
• cur: [2, 3, 4, 5, null]

虚拟头节点

新建链表应该创建虚拟头，虚拟头应该为 dummy = ListNode(0)，之后返回时去掉头，返回 dummy.next。

• dummy: [0,55,63,4,2,3,null]
• dummy.next: [55,63,4,2,3,null]

这个技巧用于防止头节点为空的问题。如果我们不规定新的链表有头节点，那么新链表很可能为 head: null。显然，此时 head 的类型不是 ListNode 也就没有 val 和 next 方法。

通过创建 new 节点跟踪链表尾部来更新链表尾部

• 通过创建 new 来跟踪新链表表的尾部，并且更新迭代链表。常见操作：

  • 指定新下一个节点 new.next = target
  • 更新 new new = new.next

• 新链表变量（如 cur = headA）是原链表的 “指针引用”，只要不直接修改 headA 本身（如 headA = new_node），仅操作新变量（如 cur = cur.next）不会改变原链表结构，headA 始终指向原链表头部，不会失效。

经典问题

• 滑动窗口：https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/description/
  • head 指针， tail 指针，分别移动
• 两链表相交判定与焦点查找： https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/description/
  • 双指针单次跨链
  • 总路程守恒：pA = a+c+b, pB = b+c+a

栈与队列

我在我的这篇博客中讨论了 python 中 queue 库的队列 queue.Queue() 和栈 queue.LifoQueue() 是基于 deque 实现的。而 deque 的 C 语言底层是通过构建一个 双向循环链表 + 定长数组 实现的。

回溯算法

回溯算法的经典流程、模板（from 代码随想录）

def backtracking(参数):

    if (终止条件):
        存放结果;
        return;

    for i in [子节点集合]:
        # 剪枝 （可选）
        if (剪枝条件): continue;

        处理节点;
        backtracking(参数); # 递归
        回溯节点 撤销处理结果

哈希表 / 哈希法

哈希法本质是一种 “以值作为键”的方法 -- { key: 值, value: 要保存的东西 }

哈希表则是通过哈希函数，让所有的的值都转为数字 key，插入表中