记录自己使用Go学算法的过程 GITHUB地址
Part 1 (TODO💪)
-
数组
- 合并有序数组（Easy）
- 删除有序数组中的重复项（Easy）
- 移动零（Easy）
-
链表
- 反转链表（Easy）
- K 个一组翻转链表（Hard）
- 邻值查找（Medium）（ACWing）
- 环形链表（Medium）
- 环形链表 II （Medium）
-
栈、队列
- 有效的括号（Medium）
- 最小栈（Medium）
- 逆波兰表达式求值（Medium）
- 基本计算器 （Hard）
-
前缀和、差分
- 统计「优美子数组」（Medium）
- 二维区域和检索 - 矩阵不可变（Medium）
- 航班预订统计（Medium）
- 最大子序和（Easy）
-
双指针扫描、滑动窗口
- 两数之和（Easy）
- 两数之和 II - 输入有序数组（Easy）
- 三数之和（Medium）
- 盛最多水的容器（Medium）
-
单调栈、单调队列
- 柱状图中最大的矩形（Hard）
- 滑动窗口最大值（Hard）
- 接雨水（Hard）
-
随机练习
- 加一（Easy）
- 合并两个有序链表（Easy）
- 设计循环双端队列（Medium）
- 和为 K 的子数组（Medium）
-
哈希表、集合、映射
-
LRU
-
递归
-
树
-
分治
-
随机练习
- LRU 缓存机制（Medium）
- 子域名访问计数（Easy）
- 数组的度（Easy）
- 元素和为目标值的子矩阵数量（Hard）
- 合并 K 个升序链表（Hard） (要求：用分治实现，不要用堆)
-
树、二叉树、树的遍历
- 二叉树的中序遍历（Easy）
- N 叉树的前序遍历（Easy）
- N 叉树的层序遍历（Medium）
- 二叉树的序列化与反序列化（Hard）TODO
- 从前序与中序遍历序列构造二叉树（Medium）
-
树的直径、最近公共祖先、树的变形
- 树的直径（此题为 LeetCode 会员题）TODO
- 二叉树的最近公共祖先（Medium）
-
图、图的遍历
-
DFS(深度优先遍历)、BFS(广度优先遍历)
- 电话号码的字母组合（Medium）
- N 皇后（Hard）
- 岛屿数量（Medium）
- 最小基因变化（Medium）
- 矩阵中的最长递增路径（Hard）TODO
-
随机练习
-
二叉堆
-
二叉搜索树
- 二叉搜索树中的插入操作（Medium）
- 后继者（Medium）
- 删除二叉搜索树中的节点（Medium）
- 把二叉搜索树转换为累加树（Medium）TODO
-
二分查找
-
三分查找
- 寻找峰值（Medium）TODO
- 猜数字大小（Easy）TODO
- 分割数组的最大值（Hard）
- 制作 m 束花所需的最少天数（Medium）
-
随机练习
- 设计推特（Medium）
- 数据流的中位数（Hard）
- 简单排序
- 大顶堆小顶堆
- 寻找旋转排序数组中的最小值 II （Hard）
-
排序
-
初级排序算法
-
重要排序算法
-
非比较类排序
- 计数排序
- 桶排序
- 基数排序
-
习题
- 排序数组（Medium）
- 数组的相对排序
- 合并区间（Medium）
- 双关键字快排
- 差分思想 TODO
- 数组中的第 K 个最大元素（Medium）
- 大根堆
- 货仓选址 TODO
- 翻转对（Hard）
- 归并排序 + 计算
-
-
贪心
- 零钱兑换（Medium）TODO
- 柠檬水找零（Easy）
- 分发饼干（Easy）
- 买卖股票的最佳时机 II （Easy）
- 跳跃游戏 II （Medium）
- 完成所有任务的最少初始能量（Hard）(贪心证明过程)
-
随机练习
- 在 D 天内送达包裹的能力（Medium）
- 二分答案
- 在线选举（Medium）TODO
- 爱吃香蕉的珂珂（Medium）
- 二分答案
- 区间和的个数（Hard）TODO
- 在 D 天内送达包裹的能力（Medium）
-
动态规划一
- 零钱兑换（Medium）
- 不同路径 II （Medium）
- 最长公共子序列（Medium）
- 最长递增子序列（Medium）
- 最大子序和（Easy）
- 乘积最大子数组（Medium）TODO
-
动态规划二
-
买卖股票系列问题(附带详细注释)
- 买卖股票的最佳时机（Easy）
- 注意题目只允许买入一次，也就是说之前没有买入也没有卖出过
- 买卖股票的最佳时机 II（Easy）
- 注意题目没有限制买入卖出的次数，但是仍要遵守先买入才能卖出
- 买卖股票的最佳时机 III（Easy）
- 注意题目限制完整交易的次数为2，买入前必须卖掉之前的股票
- 买卖股票的最佳时机 IV （Hard）
- 注意题目限制完整交易的次数为k，买入前必须卖掉之前的股票
- 买卖股票的最佳时机含手续费（Medium）
- 注意题目不限制交易次数，套用买卖股票二的模版即可，买入时减去fee
- 最佳买卖股票时机含冷冻期（Medium）
- 注意题目不限制交易次数，买入前必须卖掉之前的股票
- 与股票三、四对比，同样是三个状态，但是决策上要根据冷冻期进行调整
- 买卖股票的最佳时机（Easy）
-
线性DP问题
- 打家劫舍（Medium）
- 打家劫舍 II - 环形DP （Medium）
- 对比打家劫舍1，第一间屋子可偷可不偷，搜两遍比较大小
- 编辑距离:fire:（Hard）
- dp[i][j] word1 前 i 个字符转换成 word2 前 j 个字符所使用的的最少步数（已达成时）
-
背包问题
- 分割等和子集（Medium）
- 零钱兑换 II （Medium）
- 完全背包模型 + 计数
-
-
随机练习
- 爬楼梯（Easy）
- 三角形最小路径和（Medium）
- 最长递增子序列的个数（Medium）TODO
- 完全平方数（Medium）
- 完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？
- 跳跃游戏（Medium）
- 跳跃游戏 II （Medium）
- 贪心
- DP f[i] 为到达第 i 个位置所需要的最少步数 当我们要求某一个 f[i] 的时候，我们需要找到最早能够经过一步到达 i 点的 j 点 即有状态转移方程：f[i] = f[j] + 1
-
- 满足不等式的最大值（Hard）
- 二元组不等式的推导优化 + 滑动窗口最大值
- 引入deque实现 https://github.com/gammazero/deque/blob/master/deque.go
- 环形子数组的最大和（Medium）TODO
- 满足不等式的最大值（Hard）
-
区间DP
-
树形DP
-
- 实现 Trie (前缀树) （Medium）
- Trie 树的核心思想是空间换时间； 无论保存树的结构、字符集数组还是字符集映射，都需要额外的空间； 利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的； 分组思想--前缀相同的字符串在同一子树中；
- 单词搜索 II （Hard）
- 实现 Trie (前缀树) （Medium）
-
随机练习
- 冗余连接（Medium）
- 并查集
- DFS
- 岛屿数量（Medium）
- 并查集
- DFS
- 冗余连接（Medium）
-
最短路 TODO
- 网络延迟时间（Medium）
- 阈值距离内邻居最少的城市（Medium）
- Dijkstra 求最短路 II （Easy）（ACWing）
-
最小生成树 TODO
- 连接所有点的最小费用（Medium）
-
字符串基础知识
-
- 实现 strStr() （Easy）
- 重复叠加字符串匹配（Medium）TODO
-
回文串系列
- 验证回文串（Easy）
- 验证回文字符串 Ⅱ（Easy）（贪心 + 验证）
- 最长回文子串（Medium）
- 枚举中点，向两边扩展，考虑奇偶
- 二分答案 + RKHash (附带详细注解)
-
字符串与动态规划
-
KMP字符串模版
- 实现 strStr()（Easy）TODO
-
随机练习 TODO
-
- 括号生成（Medium）
- 剪枝：实时维护左右括号的数量，不合法及时停止
- N 皇后（Hard）
- 剪枝：维护两种斜线（行号+列号、行号-列号）的已用值集合，排除造成重复的分支
- 有效的数独（Medium）
- 解数独（Hard）
- 遍历每次找第一个空位置 VS 每次找分支较少的一个空（剪枝）
- 括号生成（Medium）
-
- 单词接龙（Hard）
- 单向BFS
- 双向BFS
- 单词接龙（Hard）
-
- 滑动谜题（Hard）
- 普通BFS
- A*算法 TODO
- 滑动谜题（Hard）
-
随机练习
- 二进制矩阵中的最短路径（Medium）
- BFS
- 有序集合库或平衡树解决 滑动窗口最大值（Hard）
- 使用内置treeMap
- 优先队列
- 有序集合库或平衡树解决 邻值查找（Medium）AcWing TODO
- 设计跳表（Hard）TODO
- 普通平衡树（Medium）AcWing TODO
- 二进制矩阵中的最短路径（Medium）
Part 10 (TODO💪)
好多TODO:joy:，加油。