算法（零）：基础

#1 位运算与进位制

• 位运算是计算机最基础的运算，包括位模式或二进制数的一元和二元操作（&、|、^、~、«、»）

• 很多位运算的问题具有较强的技巧性，需要很熟悉各个位运算符的性质

• 0136 只出现一次的数字

• 0191 位1的个数

• 0201 数字范围按位与

• 0260 只出现一次的数字 III

• 0338 比特位计数

• 0137 只出现一次的数字 II

#2 排序

• 最常用的是快速排序、归并排序、堆排序，其思想也不仅应用在排序中
• 特别的，当数据范围相对于数据规模较小时，计数排序可能更快。而桶排序的应用较为灵活，能巧妙地解决一些问题。
• 解决很多数组问题时，都可以先排序。比如取不重复元组的问题，通用方法是：
  • 先排序，然后每轮取元素时，相同的数跳过，即可保证元组不重复

python 中一般直接调用 sort 函数来排序，采用的是 TimSort算法，一种结合了归并排序和插入排序的混合排序算法。

• 0021 合并两个有序链表
• 0506 相对名次
• 0912 排序数组
• 1030 距离顺序排列矩阵单元格
• 0023 合并K个升序链表
• 0147 对链表进行插入排序
• 0148 排序链表
• 0274 H 指数
• 0853 车队
• 0179 最大数
• 0215 数组中的第K个最大元素
• 0164 最大间距
• 0220 存在重复元素 III

#3 递归与分治

• 递归是指函数自己调用自己的语法现象
• 一般递归用于将问题不断转化为规模更小的子问题，直到变为可以直接求解的最简单子问题。这也就是分治法的思想。

递归是自顶向下的，思考逻辑比较自然直接，但有时递归层数太多会爆栈。 所以还需要掌握非递归的写法，也就是自底向上的递推写法。

• 0050 Pow(x, n)
• 0078 子集
• 0779 第K个语法符号
• 0060 排列序列
• 0301 删除无效的括号
• 0372 超级次方
• 0390 消除游戏
• 0395 至少有 K 个重复字符的最长子串
• 0273 整数转换英文表示
• 1823 找出游戏的获胜者

#4 dfs与bfs

• dfs（深度优先搜索算法）和 bfs（广度优先搜索算法）都是图形搜索方法，

• 不同的在于 dfs 先尽可能深的搜索一个分支，再尝试别的路径，而 bfs 按离起点的距离一层层搜索。

• dfs 常借助递归实现，而 bfs 常借助队列实现。

• dfs 的思想就是回溯，是一种暴力通用解法。有时可以提前判断分支不满足要求，提前返回，被称为剪枝。

• 0022 括号生成

• 0045 跳跃游戏 II

• 0078 子集

• 0386 字典序排数

• 0051 N 皇后

• 0079 单词搜索

• 0093 复原IP地址

• 0401 二进制手表

• 0994 腐烂的橘子

• 0037 解数独

• 0127 单词接龙

• 0529 扫雷游戏

#5 双指针与滑动窗口

• 双指针算法一般指两个指针在数组上相向移动来解决问题的算法。

• 双指针算法常应用在具有某种有序性质的问题上，本质上是一种减少了搜索范围的贪心。

• 广义来说，用两个变量在线性结构上遍历来解决问题的方法都可以归为双指针算法。比如链表上的快慢指针、部分滑动窗口问题。

• 用双指针来解决滑动窗口问题时，两个指针同向移动，常应用在某种限制条件下的窗口最值问题。

• 0003 无重复字符的最长子串

• 0167 两数之和 II - 输入有序数组

• 0209 长度最小的子数组

• 0345 反转字符串中的元音字母

• 0643 子数组最大平均数 I

• 0011 盛最多水的容器

• 0016 最接近的三数之和

• 0424 替换后的最长重复字符

• 0438 找到字符串中所有字母异位词

• 0713 乘积小于K的子数组

• 0030 串联所有单词的子串

• 0042 接雨水

• 0076 最小覆盖子串

• 0992 K 个不同整数的子数组

#6 二分与倍增

• 二分查找是一种针对有序集合的高效查找算法，时间复杂度为 O(logN)
• 二分查找每一轮通过检查中间元素，将查找范围缩小一半
• python 中可以直接调用 bisect 来实现二分查找

有时中间元素的判定较为复杂，不是直接比较，可以用 bisect 的 key 实现

• 0034 在排序数组中查找元素的第一个和最后一个位置
• 0069 x 的平方根
• 0074 搜索二维矩阵
• 0278 第一个错误的版本
• 0374 猜数字大小
• 0033 搜索旋转排序数组
• 0081 搜索旋转排序数组 II
• 0153 寻找旋转排序数组中的最小值
• 0154 寻找旋转排序数组中的最小值 II
• 0162 寻找峰值
• 0222 完全二叉树的节点个数
• 0004 寻找两个正序数组的中位数
• 0209 长度最小的子数组

#7 前缀和与差分

• 前缀和是一种常用的解决区间查询问题的算法。

• 当数组固定时，根据前缀和即可在 O(1) 时间查询任意区间的和。

• 0303 区域和检索 - 数组不可变

• 0134 加油站

• 0304 二维区域和检索 - 矩阵不可变

#8 贪心与构造

• 贪心算法是一种高效的搜索方法。在每一步，都选择当前最好的分支，最终即能得到最优解。

• 能用贪心算法解决的问题，对于贪心正确性的证明往往更加复杂。因此很多时候需要依赖一定的直觉才能想到贪心策略，即先构造后证明。

• 而有些不能用贪心解决的问题，如果对用例的考虑不够周全，容易错误地采用贪心策略。因此使用贪心一定要慎重。

• 0502 IPO

• 0871 最低加油次数

• 1642 可以到达的最远建筑

• 1792 最大平均通过率

• 0402 移掉K位数字

• 0406 根据身高重建队列

• 1705 吃苹果的最大数目

• 0316 去除重复字母

• 0321 拼接最大数

#9 dp

• 动态规划是一种特殊的递归，适用于有重叠子问题的场景
• 动态规划也有递归和非递归两种形式。递归形式的动态规划也叫记忆化递归。

python 在递归函数上加一个 @lru_cache(None) 的装饰器即可实现记忆化递归。非递归形式一般初始化一个 k（动态参数个数）维的数组保存子问题的结果。

递归层数太多时容易爆栈，用非递归形式更好。但有时所求问题只会用到稀疏的子问题，此时用递归形式更节省时间。

• 0062 不同路径
• 0070 爬楼梯
• 0096 不同的二叉搜索树
• 0279 完全平方数
• 0397 整数替换
• 0509 斐波那契数
• 0338 比特位计数
• 0343 整数拆分
• 0790 多米诺和托米诺平铺
• 0552 学生出勤记录 II
• 0005 最长回文子串
• 0135 分发糖果
• 0264 丑数 II
• 0053 最大子序和
• 0152 乘积最大子数组
• 0413 等差数列划分
• 0467 环绕字符串中唯一的子字符串
• 0689 三个无重叠子数组的最大和
• 0329 矩阵中的最长递增路径
• 0576 出界的路径数
• 0688 骑士在棋盘上的概率
• 0764 最大加号标志
• 0174 地下城游戏
• 0221 最大正方形
• 0741 摘樱桃
• 0005 最长回文子串
• 0516 最长回文子序列
• 0087 扰乱字符串
• 0664 奇怪的打印机
• 0312 戳气球
• 0375 猜数字大小 II
• 0546 移除盒子
• 0730 统计不同回文子序列 子序列
• 0300 最长递增子序列
• 0354 俄罗斯套娃信封问题
• 0368 最大整除子集
• 0376 摆动序列
• 0673 最长递增子序列的个数 股票
• 0121 买卖股票的最佳时机
• 0122 买卖股票的最佳时机 II
• 0123 买卖股票的最佳时机 III
• 0188 买卖股票的最佳时机 IV
• 0309 最佳买卖股票时机含冷冻期
• 0714 买卖股票的最佳时机含手续费 背包
• 0474 一和零
• 0518 零钱兑换 II
• 0638 大礼包
• 0691 贴纸拼词

状压

• 0416 分割等和子集
• 0473 火柴拼正方形
• 0526 优美的排列
• 0698 划分为k个相等的子集
• 0805 数组的均值分割

优化

• 0808 分汤
• 0629 K个逆序对数组
• 0813 最大平均值和的分组
• 0514 自由之路
• 0264 丑数 II
• 0300 最长递增子序列
• 0313 超级丑数
• 0673 最长递增子序列的个数
• 0805 数组的均值分割

#10 数学

• 一些问题涉及到数学的代数知识：

  • 基础的四则运算、平方开根、进制转换等
  • 排列组合、概率统计
  • 数论知识，包括质数、同余、因式分解、乘法逆元等

• 一些问题涉及到数学的几何知识，包括斜率、面积、凸包等。

• 0007 整数反转

• 0050 Pow(x, n)

• 0069 x 的平方根

• 0102 整数转罗马数字

• 0171 Excel 表列序号

• 0029 两数相除

• 0043 字符串相乘

• 0168 Excel 表列名称

• 0202 快乐数

• 0367 有效的完全平方数

• 0400 第 N 位数字

• 0829 连续整数求和

• 0166 分数到小数

• 0169 多数元素

• 0229 求众数 II

• 0273 整数转换英文表示

• 0343 整数拆分

排列组合

• 0062 不同路径
• 0119 杨辉三角 II
• 0357 计算各个位数不同的数字个数
• 0060 排列序列
• 0096 不同的二叉搜索树
• 0902 最大为 N 的数字组合
• 1012 至少有 1 位重复的数字
• 1916 统计为蚁群构筑房间的不同顺序 概率统计
• 0382 链表随机节点
• 0384 打乱数组
• 0398 随机数索引
• 0470 用 Rand7() 实现 Rand10()
• 0478 在圆内随机生成点 数论
• 0172 阶乘后的零
• 0231 2 的幂
• 0258 各位相加
• 0263 丑数
• 0914 卡牌分组
• 1250 检查「好数组」
• 0204 计数质数
• 0279 完全平方数
• 0319 灯泡开关
• 0365 水壶问题
• 0650 只有两个键的键盘
• 0866 回文素数
• 1819 序列中不同最大公约数的数目
• 2183 统计可以被 K 整除的下标对数目 几何
• 0223 矩形面积
• 0149 直线上最多的点数
• 0335 路径交叉 扫描线
• 0218 天际线问题
• 0391 完美矩形
• 0850 矩形面积 II
• 1851 包含每个查询的最小区间