README.md

algorithm-note-java

「记录那些年的算法生涯」 目前已整理完acwing的代码，蓝桥杯相关代码持续更新中🙄...

👇面试必刷题型分类题单（Leetcode / acwing / 蓝桥杯）

基础算法：

- 【快速排序/选择】：
    [LC]：17.14. 最小K个数、215. 数组中的第K个最大元素

- 【归并排序】：
    [LC]：剑指 Offer 51. 数组中的逆序对

-【二分】：
    [LC]：69. Sqrt(x)、2141. 同时运行 N 台电脑的最长时间、778. 水位上升的泳池中游泳、2187. 完成旅途的最少时间、
        153. 寻找旋转排序数组中的最小值、2055. 蜡烛之间的盘子、2024. 考试的最大困扰度、5219. 每个小孩最多能分到多少糖果、
        410. 分割数组的最大值、1044. 最长重复子串、6098. 统计得分小于 K 的子数组数目、719. 找出第 K 小的数对距离(二分套二分)
        668. 乘法表中第k小的数（二分套有序技巧）、786. 第 K 个最小的素数分数（二分套二分）
        793. 阶乘函数后 K 个零（数学 + 二分）、1439. 有序矩阵中的第 k 个最小数组和（二分 + dfs）、
        2398. 预算内的最多机器人数目（二分 + 滑动窗口）、6210. 最小化数组中的最大值（二分 + 从后往前 + 溢出判断）
        1235. 规划兼职工作（二分 + 序列DP）、1751. 最多可以参加的会议数目 II（二分 + 序列DP）、2448. 使数组相等的最小开销（二分凸函数）
        754. 到达终点数字（二分 + 贪心分情况讨论）、 1802. 有界数组中指定下标处的最大值（二分 + 贪心）、2251. 花期内花的数目
        1574. 删除最短的子数组使剩余数组有序
    [蓝桥杯]：2017 9 分巧克力、2019 研究生 扫地机器人

- 【高精度】：
    [LC]：415. 字符串相加、2. 两数相加

- 【前缀和与差分】：
    【一维前缀和】：
        [LC]：209. 长度最小的子数组、2145. 统计隐藏数组数目、2100. 适合打劫银行的日子、2055. 蜡烛之间的盘子、6035. 选择建筑的方案数、4926. 将字符串翻转到单调递增、828. 统计子串中的唯一字符（前后缀处理 + 乘法原理）面试题 17.05.  字母与数字（前缀和 + 哈希表）、1749. 任意子数组和的绝对值的最大值、
         238. 除自身以外数组的乘积（前缀积）
    【二维前缀和】：
        [LC]：1314. 矩阵区域和、剑指 Offer II 013. 二维子矩阵的和、363. 矩形区域不超过 K 的最大数值和
    【一维差分】：
        [LC]：1109. 航班预订统计、1893. 检查是否区域内所有整数都被覆盖、1094. 拼车、2145. 统计隐藏数组数目、798. 得分最高的最小轮调、6044. 花期内花的数目
    【二维差分】：
    【前后缀分解】： 
        [LC]：2484. 统计回文子序列数目

- 【树状数组】：
    [LC]: 303. 区域和检索 - 数组不可变、307. 区域和检索 - 数组可修改、2426. 满足不等式的数对数目

- 【双指针】：
    [LC]：3. 无重复字符的最长子串、2024. 考试的最大困扰度、713. 乘积小于 K 的子数组、2444. 统计定界子数组的数目（枚举左端点）、795. 区间子数组个数（枚举左端点）、16. 最接近的三数之和、15. 三数之和、75. 颜色分类、209. 长度最小的子数组、18. 四数之和（排序+剪枝+去重+双指针）、2779. 数组的最大美丽值（排序+双指针）

- 【滑动窗口】：
    [LC]：904. 水果成篮、209. 长度最小的子数组、713. 乘积小于 K 的子数组

- 【位运算】：
    [LC]：1356. 根据数字二进制下 1 的数目排序

- 【离散化】：
    [LC]：6044. 花期内花的数目

- 【区间合并】:
    [LC]：56. 合并区间

数据结构：

- 【栈】：
    [LC]:  856. 括号的分数、895. 最大频率栈（多个栈）
    [Acwing]: 3302. 表达式求值、454. 表达式求值

- 【单调栈】：
    [LC]：496. 下一个更大元素 I、503. 下一个更大元素 II、907. 子数组的最小值之和、901. 股票价格跨度、795. 区间子数组个数、84. 柱状图中最大的矩形、85. 最大矩形

- 【单调队列】：
    [LC]：239. 滑动窗口最大值（最小值）

- 【KMP】
    [LC]: 28. 实现 strStr()、1392. 最长快乐前缀

- 【Trie】
    [LC]: 1233. 删除子文件夹
    [AcWing] 143. 最大异或对

- 【并查集】：
    [LC]: 765. 情侣牵手、200. 岛屿数量、778. 水位上升的泳池中游泳、839. 相似字符串组、827. 最大人工岛、1697. 检查边长度限制的路径是否存在
    [Acwing]: 4216. 图中的环、1242. 修改数组

- 【字符串哈希】：
    [Acwing]: 139. 回文子串的最大长度
    [LC]: 1044. 最长重复子串、1392. 最长快乐前缀、214. 最短回文串、2223. 构造字符串的总得分和、2430. 对字母串可执行的最大删除数

- 【堆】：
    [LC]: 6170. 会议室 III、895. 最大频率栈（堆 + map）、23. 合并K个升序链表
    
- 【链表】：
    [LC]: 206. 反转链表、25. K 个一组翻转链表(指针分组 + 反转链表)、142. 环形链表 II（快慢指针 + 数学推导）、138. 复制带随机指针的链表（就近复制 + 遍历三次）、148. 排序链表（获取第K个节点 + 快慢指针 + 合并链表）

树与图：

- 【DFS】
    [LC]: 2049. 统计最高分的节点数目、5289. 公平分发饼干（回溯+剪枝）、6243. 到达首都的最少油耗（思想转换）、105. 从前序与中序遍历序列构造二叉树（构造）、106. 从中序与后序遍历序列构造二叉树、 1238. 循环码排列、124. 二叉树中的最大路径和、979. 在二叉树中分配硬币（思路转换）

- 【BFS】
    [LC]: 773. 滑动谜题、6054. 逃离火灾、854. 相似度为 K 的字符串、934. 最短的桥（DFS + BFS）、1210. 穿过迷宫的最少移动次数（三个状态的BFS）、864. 获取所有钥匙的最短路径（BFS + 状态压缩）、1129. 颜色交替的最短路径、279. 完全平方数、297. 二叉树的序列化与反序列化、240. 搜索二维矩阵 II（利用矩阵有序的性质抽象成二叉搜索树）

- 【dijkstra】
    [LC] 882. 细分图中的可到达节点

- 【SPFA】:
    [LC]：841. 钥匙和房间

- 【二分图】：
    [LC]: LCP 04. 覆盖

- 【拓扑排序】：
    [LC]: 2392. 给定条件下构造矩阵

数学知识：

- 【质数】：
    [LC]: 204. 计数质数、2507. 使用质因数之和替换后可以取到的最小值（分解质因数）、2427. 公因子的数目（GCD + 分解质因数）

- 【公约数】：
    [LC]：1447. 最简分数、6015. 统计可以被 K 整除的下标对数目、2427. 公因子的数目（GCD + 分解质因数）

- 【其他】：
    [LC]: 面试题 17.19. 消失的两个数字

动态规划：

- 【背包问题】：
    【分组背包】：
        [LC]: 2218. 从栈中取出 K 个硬币的最大面值和、 2463. 最小移动总距离
    【完全背包】：
        [LC]: 518. 零钱兑换 II
        
- 【股票问题】：
    [LC]: 121. 买卖股票的最佳时机（两状态）、买卖股票的最佳时机 III（三状态）、188. 买卖股票的最佳时机 IV（三状态）、309. 最佳买卖股票时机含冷冻期（两状态）、1911. 最大子序列交替和

- 【小偷问题】：
    [LC]: 213. 打家劫舍 II（巧妙化解问题 + 普通DP） 、337. 打家劫舍 III（记忆化搜索）
    
- 【线性DP】：
    [LC]: 10. 正则表达式匹配、72. 编辑距离、688. 骑士在棋盘上的概率、6058. 统计打字方案数、32. 最长有效括号、926. 将字符串翻转到单调递增、1235. 规划兼职工作（二分 + 序列DP）、1751. 最多可以参加的会议数目 II（二分 + 序列DP）、6238. 统计构造好字符串的方案数（类似于本质上升序列）799. 香槟塔、152. 乘积最大子数组、53. 最大子数组和、1638. 统计只差一个字符的子串数目（线性DP + 乘法原理）、2684. 矩阵中移动的最大次数、1749. 任意子数组和的绝对值的最大值（双DP）
    [蓝桥杯]：本质上升序列(蓝桥杯2020国赛)、6168. 恰好移动 k 步到达某一位置的方法数目、6203. 矩阵中和能被 K 整除的路径

- 【区间DP】：
    [LC]: 312. 戳气球、1547. 切棍子的最小成本、2430. 对字母串可执行的最大删除数（字符串hash + 区间DP）、6232. 最小移动总距离（贪心 + 区间DP）、 2472. 不重叠回文子字符串的最大数目（dp求回文字串 + 无重叠区间）、813. 最大平均值和的分组（前缀和 + 区间DP）

- 【数位DP】:
    [LC]: 2376. 统计特殊整数、902. 最大为 N 的数字组合

- 【其他DP】：
    [LC]: 2267. 检查是否有合法括号字符串路径、 1140. 石子游戏 II

- 【状态压缩DP】：
    [LC]: 464. 我能赢吗
       

贪心

- 【讨论】：
    [LC]: 754. 到达终点数字（二分 + 贪心分情况讨论）

- 【排序】：
    [LC]: 2448. 使数组相等的最小开销（排序 + 枚举点 + 前缀和）、6217. 使数组相似的最少操作次数（排序 + 分组）、6232. 最小移动总距离（贪心 + 区间DP）、 15. 三数之和

- 【中位数】：
    [LC]: 6216. 使数组相等的最小开销、 https://leetcode.cn/contest/zj-future2022/problems/kflZMc/

- 【区间问题】：
    [LC]: 435. 无重叠区间、 2472. 不重叠回文子字符串的最大数目（dp求回文字串 + 无重叠区间）

- 【构造】：
    [LC]: 667. 优美的排列 II

其他

- 【分治】：
    [LC]: 53. 最大子数组和
- 【计算贡献/乘法原理】：
    [LC]: 828. 统计子串中的唯一字符、6050. 字符串的总引力

- 【分类讨论】
    [LC]: 2508. 添加边使所有节点度数都为偶数
    
- 【原地hash】:
    [LC]: 41. 缺失的第一个正数