algorithm

log

Learning! Code more, test more and learn more.
This folder contains some test codes. Some of them are my test on online judges, and some are just the test for the new algorithm.

• Date: 05/07/2014 Change to another lab, but still coding. Keep going!
• Date: 28/09/2014 Repeated course, so sad!
• Date: 11/12/2014 Change the folder structure
• Date: 28/09/2020 Add conclusion

Plan

1. C++/C，在没有java现有数据结构/模板方法/语法糖协助下，能不能更快地使用比较简单的语言本身的支持来实现解题
2. 挑战时间、空间最佳，而不仅仅是通过
3. 图是一直想深入理解的，实际问题怎么转为图的方式解决；

Conclusion

1. Algebra
   • BigNumber: 2. 两数相加, 989. 数组形式的整数加法
   • Arithmetic: 15. 三数之和, 18. 四数之和
   • 1006. 笨阶乘, 633. 平方数之和 首尾指针, 1734. 解码异或后的排列
   • 12. 整数转罗马数字, 461. 汉明距离, 477. 汉明距离总和
   • 1608. 特殊数组的特征值
2. Search / Match
   • DFS: 51. N 皇后, 52. N皇后 II
   • BFS: 1239. 串联字符串的最大长度, 752. 打开转盘锁, 743. 网络延迟时间
   • 1178. 猜字谜 二进制,压缩,优化小集交大集的搜索
   • 74. 搜索二维矩阵
   • 81. 搜索旋转排序数组 II 条件式分治搜索, 153. 寻找旋转排序数组中的最小值
   • 28. 实现 strStr() KMP字符串匹配算法, 1011. 在 D 天内送达包裹的能力 二分搜索的适用场景, 275. H 指数 II
   • 403. 青蛙过河 记忆化搜索, 802. 找到最终的安全状态 三态标记DFS, 413. 等差数列划分 复用DFS
   • 1774. 最接近目标价格的甜点成本, 2319. 判断矩阵是否是一个 X 矩阵
3. Sort
   • Merge: 977. 有序数组的平方
   • 164. 最大间距 基数排序
   • 321. 拼接最大数 单调栈结合了归并的思想
   • 1046. 最后一块石头的重量 插入(排序), 注意插入尾部情形
4. Dynamic Programming
   • 837. 新21点, 746. 使用最小花费爬楼梯, 338. 比特位计数, 879. 盈利计划, 518. 零钱兑换 II, 877. 石子游戏
   • With Tree: 530. 二叉搜索树的最小绝对差
   • 62. 不同路径 可以用组合方法解题
   • dijkstra: 1631. 最小体力消耗路径
   • 354. 俄罗斯套娃信封问题, 115. 不同的子序列
   • 面试题 17.21. 直方图的水量, 213. 打家劫舍 II, 91. 解码方法, 1269. 停在原地的方案数
   • 313. 超级丑数, 233. 数字 1 的个数
   • 70. 爬楼梯
5. Mathematics
   • 134. 加油站 差分累积计算, 166. 分数到小数
   • 204. 计数质数, 368. 最大整除子集, 342. 4的幂
   • 930. 和相同的二元子数组, 168. Excel表列名称
   • 剑指 Offer 52 转为两个链表和的追及问题
   • 1374. 生成每种字符都是奇数个的字符串 数字分解
6. Graph
   • shorest path: 127. 单词接龙 或者参考题解的双向BFS
   • DAG: 406. 根据身高重建队列
   • Matrix: 1030. 距离顺序排列矩阵单元格 矩阵遍历
7. Tree
   • Traversal: 94. 中序遍历, 145. 后序遍历, 144. 前序遍历, 103. 锯齿形层序遍历, 341. 扁平化嵌套列表迭代器, 872. 叶子相似的树, 993. 二叉树的堂兄弟节点, 1609. 奇偶树
   • Maintain: 701. 插入操作
   • 并查集: 947. 移除最多的同行或同列石头 二维构造一维并查集, 1579. 保证图可完全遍历, 778. 水位上升的泳池中游泳
   • Others: 116. 填充下一个右侧节点指针, 117. 填充下一个右侧节点指针 II, 222. 完全二叉树的节点个数 利用完全二叉树的特征剪枝统计
   • 783. 二叉搜索树节点最小距离, 208. 实现 Trie (前缀树), 938. 二叉搜索树的范围和
   • 897. 递增顺序搜索树, 1104. 二叉树寻路 Z型遍历, 687. 最长同值路径
   • 559. N 叉树的最大深度 递归遍历, 623. 在二叉树中增加一行
8. List
   • Cycle: 142. 环形链表 II
   • Swap: 328. 奇偶链表 指针操作, 92. 反转链表 II
   • 724. 寻找数组的中心索引 数组等值分割, 82. 删除排序链表中的重复元素 II, 80. 删除有序数组中的重复项 II
   • 480. 滑动窗口中位数 滑动窗口结合数据结构, 1004. 最大连续1的个数 III, 456. 132 模式, 220. 存在重复元素 III, 611. 有效三角形的个数
   • 1310. 子数组异或查询, 1190. 反转每对括号间的子串
   • 138. 复制带随机指针的链表 栅栏创建避免索引, 1743. 从相邻元素对还原数组
   • 581. 最短无序连续子数组, 1705. 吃苹果的最大数目
   • 1078. Bigram 分词
9. stack & queue
   • 232. 用栈实现队列, 726. 原子的数量
   • 224. 基本计算器 栈操作算式, 917. 仅仅反转字母
10. Engineering
    • SQL:
    • Class Design: 622. 设计循环队列
11. Inspiration
    • 234. 回文链表 借用递归实现单向链表的'优雅'反向
    • 381. O(1) 时间插入、删除和获取随机元素 - 允许重复 复合数据结构
    • 31. 下一个排列 计算全排列指定值下一个顺序值, 非递归方式规则推导
    • 135. 分发糖果 巧妙分治
    • 995. K 连续位的最小翻转次数
    • 面试题 17.10. 主要元素 二次遍历
    • 859. 亲密字符串, 899. 有序队列
12. 贪心
    • 861. 翻转矩阵后的得分 理解行转列转的顺序不影响结果, 在此基础进行贪心
    • 738. 单调递增的数字 结合数值类数据特征进行贪心
    • 455. 分发饼干 贪心+剪枝, 1838. 最高频元素的频数
    • 330. 按要求补齐数组 基于数学的贪心, 难题, 1403. 非递增顺序的最小子序列
13. Map
    • 面试题 10.02. 变位词组
14. Others
    • data compress 925. 长按键入, simulating 763. 划分字母区间 659. 分割数组为连续子序列
    • array operation 57. 插入区间, 941. 有效的山脉数组
    • bit/binary 1356. 根据数字二进制下 1 的数目排序 考虑递推(转移函数)处理
    • 54. 螺旋矩阵, 59. 螺旋矩阵 II
    • string: 482. 密钥格式化, 2000. 反转单词前缀, 1624. 两个相同字符之间的最长子字符串, 面试题 01.09. 字符串轮转
    • 1995. 统计特殊四元组, 1408. 数组中的字符串匹配, 2351. 第一个出现两次的字母