Skip to content

记录在acwing、leetcode、leetcode周赛、蓝桥杯、codeforces上做的所有题的代码/题解/思路等;总结面试必刷的题单(偏hard)

License

Notifications You must be signed in to change notification settings

huangPengL/algorithm-note-java

Repository files navigation

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. 缺失的第一个正数

About

记录在acwing、leetcode、leetcode周赛、蓝桥杯、codeforces上做的所有题的代码/题解/思路等;总结面试必刷的题单(偏hard)

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages