我的Go算法之旅

记录自己使用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）
  
  

Part 2

• 哈希表、集合、映射

  
  
  
  
  • 两数之和
  • 字母异位词分组
  • 串联所有单词的子串
  
  

• LRU

  
  
  
  
  • LRU 缓存机制
  
  

• 递归

  
  
  
  
  • 子集
  • 组合
  • 全排列
  
  

• 树

  
  
  
  
  • 翻转二叉树
  • 验证二叉搜索树
  • 二叉树的最大深度
  • 二叉树的最小深度
  
  

• 分治

  
  
  
  
  • Pow(x, n)
  • 括号生成
  
  

• 随机练习

  
  
  
  
  • LRU 缓存机制（Medium）
  • 子域名访问计数（Easy）
  • 数组的度（Easy）
  • 元素和为目标值的子矩阵数量（Hard）
  • 合并 K 个升序链表（Hard） (要求：用分治实现，不要用堆)
  
  

Part 3

• 树、二叉树、树的遍历

  
  
  
  
  • 二叉树的中序遍历（Easy）
  • N 叉树的前序遍历（Easy）
  • N 叉树的层序遍历（Medium）
  • 二叉树的序列化与反序列化（Hard）TODO
  • 从前序与中序遍历序列构造二叉树（Medium）
  
  

• 树的直径、最近公共祖先、树的变形

  
  
  
  
  • 树的直径（此题为 LeetCode 会员题）TODO
  • 二叉树的最近公共祖先（Medium）
  
  

• 图、图的遍历

  
  
  
  
  • 冗余连接（Medium）
  • 课程表（Medium）
  
  

• DFS(深度优先遍历)、BFS(广度优先遍历)

  
  
  
  
  • 电话号码的字母组合（Medium）
  • N 皇后（Hard）
  • 岛屿数量（Medium）
  • 最小基因变化（Medium）
  • 矩阵中的最长递增路径（Hard）TODO
  
  

• 随机练习

  
  
  
  
  • 从中序与后序遍历序列构造二叉树（Medium）
  • 课程表 II （Medium）
  • 被围绕的区域（Medium）
  
  

Part 4

• 二叉堆

  
  
  
  
  • 合并 K 个升序链表（Hard）
  • 滑动窗口最大值（Hard）
  
  

• 二叉搜索树

  
  
  
  
  • 二叉搜索树中的插入操作（Medium）
  • 后继者（Medium）
  • 删除二叉搜索树中的节点（Medium）
  • 把二叉搜索树转换为累加树（Medium）TODO
  
  

• 二分查找

  
  
  
  
  • 二分查找（Easy）
  • 在排序数组中查找元素的第一个和最后一个位置（Medium）
  • x 的平方根（Easy）
  • 搜索二维矩阵（Medium）
  • 寻找旋转排序数组中的最小值（Medium）
  
  

• 三分查找

  
  
  
  
  • 寻找峰值（Medium）TODO
  • 猜数字大小（Easy）TODO
  • 分割数组的最大值（Hard）
  • 制作 m 束花所需的最少天数（Medium）
  
  

• 随机练习

  
  
  
  
  • 设计推特（Medium）
  • 数据流的中位数（Hard）
    
    
    • 简单排序
    • 大顶堆小顶堆
    
    
  • 寻找旋转排序数组中的最小值 II （Hard）
  
  

Part 5

• 排序

  
  
  
  

  • 初级排序算法

    
    
    
    
    • 选择排序（该放哪个数了）
    • 插入排序（这个数该放哪）
    • 冒泡排序
    
    

  • 重要排序算法

    
    
    
    
    • 堆排序（Heap Sort是对选择排序的优化，利用二叉堆高效选出最小值）TODO
    • 希尔排序（Shell Sort是对插入排序的优化）TODO
    • 归并排序（基于分治，先排序左右子数组，然后合并两个有序数组）
    • 快速排序（基于分治，先调配出左右子数组，然后对左右子数组分别进行排序）
      
      
      • 不带pivot
      • 带pivot
      
      
    
    

  • 非比较类排序

    
    
    
    
    • 计数排序
    • 桶排序
    • 基数排序
    
    

  • 习题

    
    
    
    
    • 排序数组（Medium）
    • 数组的相对排序
    • 合并区间（Medium）
      
      
      • 双关键字快排
      • 差分思想 TODO
      
      
    • 数组中的第 K 个最大元素（Medium）
      
      
      • 大根堆
      
      
    • 货仓选址 TODO
    • 翻转对（Hard）
      
      
      • 归并排序 + 计算
      
      
    
    
  
  

• 贪心

  
  
  
  
  • 零钱兑换（Medium）TODO
  • 柠檬水找零（Easy）
  • 分发饼干（Easy）
  • 买卖股票的最佳时机 II （Easy）
  • 跳跃游戏 II （Medium）
  • 完成所有任务的最少初始能量（Hard）(贪心证明过程)
  
  

• 随机练习

  
  
  
  
  • 在 D 天内送达包裹的能力（Medium）
    
    
    • 二分答案
    
    
  • 在线选举（Medium）TODO
  • 爱吃香蕉的珂珂（Medium）
    
    
    • 二分答案
    
    
  • 区间和的个数（Hard）TODO
  
  

Part 6

• 动态规划一

  
  
  
  
  • 零钱兑换（Medium）
  • 不同路径 II （Medium）
  • 最长公共子序列（Medium）
  • 最长递增子序列（Medium）
  • 最大子序和（Easy）
  • 乘积最大子数组（Medium）TODO
  
  

• 动态规划二

  
  
  
  

  • 买卖股票系列问题(附带详细注释)

    
    
    
    
    • 买卖股票的最佳时机（Easy）
      
      
      • 注意题目只允许买入一次，也就是说之前没有买入也没有卖出过
      
      
    • 买卖股票的最佳时机 II（Easy）
      
      
      • 注意题目没有限制买入卖出的次数，但是仍要遵守先买入才能卖出
      
      
    • 买卖股票的最佳时机 III（Easy）
      
      
      • 注意题目限制完整交易的次数为2，买入前必须卖掉之前的股票
      
      
    • 买卖股票的最佳时机 IV （Hard）
      
      
      • 注意题目限制完整交易的次数为k，买入前必须卖掉之前的股票
      
      
    • 买卖股票的最佳时机含手续费（Medium）
      
      
      • 注意题目不限制交易次数，套用买卖股票二的模版即可，买入时减去fee
      
      
    • 最佳买卖股票时机含冷冻期（Medium）
      
      
      • 注意题目不限制交易次数，买入前必须卖掉之前的股票
      • 与股票三、四对比，同样是三个状态，但是决策上要根据冷冻期进行调整
      
      
    
    

  • 线性DP问题

    
    
    
    
    • 打家劫舍（Medium）
    • 打家劫舍 II - 环形DP （Medium）
      
      
      • 对比打家劫舍1，第一间屋子可偷可不偷，搜两遍比较大小
      
      
    • 编辑距离（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
    
    
  
  

Part 7

• DP的优化

  
  
  
  
  • 满足不等式的最大值（Hard）
    
    
    • 二元组不等式的推导优化 + 滑动窗口最大值
    • 引入deque实现 github.com/gammazero/deque/blob/ma...
    
    
  • 环形子数组的最大和（Medium）TODO
  
  

• 区间DP

  
  
  
  
  • 戳气球（Hard）
  • 合并石头的最低成本（Hard）
  
  

• 树形DP

  
  
  
  
  • 打家劫舍 III （Medium）
  
  

• 字典树

  
  
  
  
  • 实现 Trie (前缀树) （Medium）
    
    
    • Trie 树的核心思想是空间换时间；
      无论保存树的结构、字符集数组还是字符集映射，都需要额外的空间；
      利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的；
      分组思想–前缀相同的字符串在同一子树中；
    
    
  • 单词搜索 II （Hard）
  
  

• 并查集

  
  
  
  
  • 模版
  • 省份数量（Medium）
  • 被围绕的区域（Medium）
  
  

• 随机练习

  
  
  
  
  • 冗余连接（Medium）
    
    
    • 并查集
    • DFS
    
    
  • 岛屿数量（Medium）
    
    
    • 并查集
    • DFS
    
    
  
  

Part 8

• 最短路 TODO

  
  
  
  
  • 网络延迟时间（Medium）
  • 阈值距离内邻居最少的城市（Medium）
  • Dijkstra 求最短路 II （Easy）（ACWing）
  
  

• 最小生成树 TODO

  
  
  
  
  • 连接所有点的最小费用（Medium）
  
  

• 字符串基础知识

  
  
  
  
  • 字符串转换整数 (atoi) （Medium）
  
  

• Rabin Karp字符串哈希算法

  
  
  
  
  • 实现 strStr() （Easy）
  • 重复叠加字符串匹配（Medium）TODO
  
  

• 回文串系列

  
  
  
  
  • 验证回文串（Easy）
  • 验证回文字符串 Ⅱ（Easy）（贪心 + 验证）
  • 最长回文子串（Medium）
    
    
    • 枚举中点，向两边扩展，考虑奇偶
    • 二分答案 + RKHash (附带详细注解)
    
    
  
  

• 字符串与动态规划

  
  
  
  
  • 正则表达式匹配（Hard）
  • 不同的子序列（Hard）
  
  

• KMP字符串模版

  
  
  
  
  • 实现 strStr()（Easy）TODO
  
  

• 随机练习 TODO

  
  

Part 9

• 搜索剪枝

  
  
  
  
  • 括号生成（Medium）
    
    
    • 剪枝：实时维护左右括号的数量，不合法及时停止
    
    
  • N 皇后（Hard）
    
    
    • 剪枝：维护两种斜线（行号+列号、行号-列号）的已用值集合，排除造成重复的分支
    
    
  • 有效的数独（Medium）
  • 解数独（Hard）
    
    
    • 遍历每次找第一个空位置 VS 每次找分支较少的一个空（剪枝）
    
    
  
  

• 迭代加深、折半搜索与双向搜索

  
  
  
  
  • 单词接龙（Hard）
    
    
    • 单向BFS
    • 双向BFS
    
    
  
  

• 启发式搜索：A* 算法

  
  
  
  
  • 滑动谜题（Hard）
    
    
    • 普通BFS
    • A*算法 TODO
    
    
  
  

• 随机练习

  
  
  
  
  • 二进制矩阵中的最短路径（Medium）
    
    
    • BFS
    
    
  • 有序集合库或平衡树解决 滑动窗口最大值（Hard）
    
    
    • 使用内置treeMap
    • 优先队列
    
    
  • 有序集合库或平衡树解决 邻值查找（Medium）AcWing TODO
  • 设计跳表（Hard）TODO
  • 普通平衡树（Medium）AcWing TODO
  
  

Part 10 (TODO)

END

好多TODO，加油。