LEETCODE 刷题笔记

一、刷题原则与规范

1. 刷题规则

• 难度换算: 1道难题 = 2道中等题 = 6道简单题
• 每日目标：做到需要收费的时候每天4题及其以下
• 160题附近开始收费，此时已完成所有基础数据结构（除图外）

2. 编码规范

• 变量定义域按照C语言使用（更加规范）
• 算法实现需同时保证性能和可读性
• 变量命名规则：
  • des_XXX: 表示目标值
  • rec_f: 表示递归/迭代函数

3. 算法实现标准

• 时间复杂度：需要达到最低
• 空间复杂度：不超过O(n)即可，非必要不降低到O(1)

二、核心知识体系

1. 数据结构基础

• 排序算法：需要全部掌握
• 图论：包括线性表和二叉树（都是特殊的图）
• 哈希：需要能够手动实现

2. 算法实现方式

• 循环实现
• 递归实现
• 重要概念：递归 == 循环 + 栈
  • 递归和循环的空间、时间复杂度一般相同
  • 递归本质是通过栈和循环实现

3. 基础数据结构

1. 线性表
2. 字符串（特殊的线性表）
3. 树
   • 线段树(segment tree)
   • 树状数组(Binary Indexed Tree，BIT)
4. 图

4. 核心算法思想

4.1 贪心算法

• 典型应用：最长递增子序列

4.2 动态规划

• 一般动态规划
• 记忆化动态规划
  • Memoization(375)
  • 记忆化搜索（从后往前看的递归动态规划）
• 动态规划本质：
  • 数学归纳法（递推公式）
  • f(x) = f(x - 1) + f(x - 2) + ...

4.3 回溯算法(216)

if condition_if:
    des_arr.append(path[:])
else:
    for condition_for:
        path.append()
        traceback()
        path.pop()

4.4 分治算法

三、难题分类总结

1. 贪心算法难题

题号	时间复杂度	题目	完成方法
300	O(nlog(n))	Longest Increasing Subsequence
162			未证明可行性
179			内置排序算法，想到但不能排序出来
334	O(n)	triplet	两个数组最优置换

特殊情况说明：

• 179题排序示例：

nums = [2, 1, 3, 4, 1, 2, 3, 4]
def cmp(x, y):
    return x - y # -1 理解为每次x取出最小的一个x
nums.sort(key=functools.cmp_to_key(cmp))
print(nums)  # [1, 1, 2, 2, 3, 3, 4, 4]       

2. 回溯思想难题

• 核心题目：39, 78, 90

3. 动态规划难题

• 关键题目：73, 139, 337(二叉树的动态规划), 392(使用动态规划理解是难点)

4. 需要优化的题目

题目序号	题目描述	总结
105	需要加深二叉树 先序|中序 遍历特性的理解	?
106	需要加深二叉树 中序|后序 遍历特性的理解	?
130	广度优先遍历/二维数组	?
307	线段树/树状数组	?

5. 未解决题目

题目序号	知识点	序号
95(3)、96(3)[需要做出98题再来做这两题]	树的遍历	1
241	和 95 一个类型	2
292	NIM游戏和博弈论	3
309	股票买卖/要冷却	4
310[超时后看答案解出来的,类似找重心的过程]	减节点/树的直径	5

四、特殊专题

1. 位运算

编号	知识点
201	...

2. 数学专题

题目序号	题目知识
204	prime
279	四平方定理
372	super pow

372题重要知识点

• (x * y) % m == ((x % m)*(y % m)) % m
• 该表达式可以分类讨论证明，具有递归累计效果

3. 有趣的题目

题目序号	描述
205	同构字符串
207	图的遍历、环的判定
227	一般表达式求值
232	双栈实现队列&&T(n) = O(1)
238	productExceptSelf
241	表达式添加括号的不同方法
274	计数排序
287	Floyd 数组重复数字判定/抽屉原理
292	NIM游戏、博弈论
319	灯泡开关(brainteaser)
380	Insert Delete GetRandom O(1)
496	Next Greater Element I

五、技巧总结

二进制操作技巧

操作	意义
x&(x - 1)	用来去除 x 的最右边的 1
x&(-x)	lowbit，也就是取出最低位1代表的数字(也就是最右边的1和后面的0)