README.md

杂题备忘录

• 20211118攻克力扣链表题
• 20220102寒假每日一题2022
• 20220108力扣杂题
• 20220318春季每日一题2022
• 20220621夏季每日一题2022
• 20220326 NOI ONLINE 2022

20211118攻克力扣链表题

我看了，力扣题库里『链表』关键词题目总共不到100道。

题库：

• https://leetcode-cn.com/problemset/all/?topicSlugs=linked-list&page=1

笔记：

• ./drafts/20211118linked-list.md
  • 25. K 个一组翻转链表（自己总结的翻转部分链表模板）
  • 109. 有序链表转换二叉搜索树
• ./drafts/20211124linked-list.md

20220102寒假每日一题2022

笔记：

• ./drafts/20220105acwing2022winter.md
  • 2058. 笨拙的手指（秦九韶）
  • 2041. 干草堆（差分与nth_element）
  • 2060. 奶牛选美（两个连通块）
  • 2019. 拖拉机（双端队列广搜）
  • 2014. 岛（优化分析/unique）
  • 2005. 马蹄铁（状态机DFS）
  • 1996. 打乱字母（分析+二分）
• ./drafts/20220111acwing2022winter.md
  • 1987. 粉刷栅栏（差分+离散化）
  • 1978. 奶牛过马路（前缀和最值/双向遍历）
  • 品种邻近（哈希表/滑动窗口）
  • 1960. 闪烁（状态压缩/找规律/陷入循环/抽屉原理）
  • AcWing 1952. 金发姑娘和 N 头牛（差分）
  • 1945. 奶牛棒球（简单推导/双指针/二分）
• ./drafts/20220118acwing2022winter.md
  • 1934. 贝茜放慢脚步（二路归并）
  • 1929. 镜子田地（环图）
  • 1913. 公平摄影（前缀和）
  • 1904. 奶牛慢跑（贪心）
  • 简单题不详记
• ./drafts/20220122acwing2022winter.md
  • 1875. 贝茜的报复（发现规律+取补集/状态压缩+枚举/dfs枚举）
  • 1855. 愤怒的奶牛（二分）
  • 1843. 圆形牛棚（推公式/前缀和）
  • 1826. 农田缩减（枚举）
  • 1813. 方块游戏（枚举）
  • 1801. 蹄子剪刀布（枚举+归纳）
• ./drafts/20220201acwing2022winter.md
  • 1789. 牛为什么过马路 II（枚举在圈的同一侧）
  • 1738. 蹄球（基环图+思维题）
  • 简单题不详记
• ./drafts/20220208acwing2022winter.md
  • 1726. 挤奶顺序（分类讨论+贪心）
  • 1696. 困牛排序（思维题+构造题）
  • 1684. 大型植被恢复（下标+建图+分析）
  • 1471. 牛奶工厂（floyd暴力/反证法找性质）
  • 1460. 我在哪？（最短k子串两两不同：二分+字符串哈希）
  • 简单题不详记
• ./drafts/20220214acwing2022winter.md
  • 1443. 拍照（别固化思维+枚举）
  • 1672. 疯狂的科学家（贪心与最优解集合包含性证明）
  • 简单题不详记

20220108力扣杂题

笔记：

• ./drafts/20220108lc.md
  • 格雷编码（格雷码/镜面找规律/背公式）
  • 306. 累加数（分析/高精度/考察逻辑清晰）
  • 1036. 逃离大迷宫（有限步数BFS/离散化BFS）
  • 334. 递增的三元子序列（贪心/双向遍历/前缀最值）
  • 373. 查找和最小的 K 对数字（优先队列/双指针+二分）
  • 382. 链表随机节点（水塘抽样/大数据流中随机抽样）
  • 1220. 统计元音字母序列的数目（线性DP/矩阵快速幂）
• ./drafts/20220122lc.md
  • 1332. 删除回文子序列（脑筋急转弯）
  • 1414. 和为 K 的最少斐波那契数字数目（贪心+精彩的证明）
  • 1405. 最长快乐字符串（贪心）
  • 1001. 网格照明（哈希化信息）
  • 540. 有序数组中的单一元素（二分+找规律）
• ./drafts/20220214lc.md
  • 1719. 重构一棵树的方案数（思维题发现规律）
  • 688. 骑士在棋盘上的概率（记忆化搜索DP）
  • 432. 全 O(1) 的数据结构（双向链表list的使用）
  • 440. 字典序的第K小数字（构造字典序树并且前序遍历）
  • 1606. 找到处理最多请求的服务器（模拟+set的iterator）
  • 310. 最小高度树（重要：树的性质，到各点距离最短的点存在于图上最长路径上，距离任一结点最远的点一定在树的最长路径上/拓扑排序）
  • 796. 旋转字符串（妙用 string find 与 string::npos）
• ./drafts/20220407lc.md
  • 780. 到达终点（反向推导+为什么用取模而非加法）
  • 398. 随机数索引（水塘抽样/蓄水池抽样）
  • 691. 贴纸拼词（状态压缩+记忆化搜索dfs）
  • 面试题 04.06. 后继者（栈做中序遍历）
  • 668. 乘法表中第k小的数（二分第k大/go的sort.Search）
• ./drafts/20220518lc.md
  • 436. 寻找右区间（二分/双指针/lower_bound四个形参用法/go的sort.Slice重载比较函数）
  • 699. 掉落的方块（有序集合，关于 C++ upper_bound 与红黑树 map 的 end 的理解， prev 函数）
  • 730. 统计不同回文子序列（很好的动态规划）
  • 324. 摆动排序 II（巧解）
  • 899. 有序队列（最小表示法模板题）
  • 761. 特殊的二进制序列（构造/分治）
  • 768. 最多能完成排序的块 II（构造）
• ./drafts/20220905lc.md
  • 652. 寻找重复的子树（递归哈希/编码/C++ tuple/重载 unordered_map哈希函数）
  • 850. 矩形面积 II（不错的扫描线模板+离散化）
  • 银联-3. 风能发电（模拟）
  • 银联-4. 设计自动售货机（双堆模拟懒删除+仿函数）
  • 854. 相似度为 K 的字符串（思路打开，剪枝bfs）
• ./drafts/20220921lc.md
  • 1206. 设计跳表（跳表 skip list ）

20220318春季每日一题2022

笔记：

• ./drafts/20220318acwing2022spring.md
  • 3745. 牛的学术圈 I（双指针）
  • 1683. 困牛放牧（思维题+分类讨论）
  • 1749. 阻挡广告牌 II（模拟）
  • 1921. 重新排列奶牛（好题，数组循环排序/1到N排列，环图模型）
  • 1912. 里程表（逆向思维枚举）
• ./drafts/20220425acwing2022spring.md
  • 3746. 牛的学术圈 II（思维题）
  • 4262. 空调（经典贪心+差分，将第一个序列变成第二个序列）
  • 4367. 拍照2（贪心+双指针）
  • 2049. 奶牛摄影（思维题，发现规律/巧妙思考）
  • 2032. 过度种植（容斥原理/区间求交）
  • 2023. 连接奶牛（全排列/状态压缩DP）
  • 2013. 三条线（思维题，逆向思维/类似最小圆覆盖）

20220621夏季每日一题2022

笔记：

• ./drafts/20220621acwing2022summer.md

20220326 NOI ONLINE 2022