Go 算法刷题路线与复盘方法

本轮只做理论正文与源码静态复核；下列命令、示例和测试均未执行。已有输出按代码推演或历史记录理解，不作为本轮运行证据。

LeetCode

• 中国站
• 国际站
• PS
  • 建议在中国站做完之后，可以去看下国际站，国际上对题目的理解
• 解题语言全部使用 Golang

解题顺序

• 按照 Tag 分类
• 从简单到困难

解题方法

• 先思考、写出方法
• 写出伪代码
• 写出自己答案
• 运行查看结果 维度
• 复习
  • 第一遍：解题
  • 第二遍：写出最优解题方案
  • 第三遍：最快时间写出解题答案

解题 Tag顺序

• 数组
• 链表
• 哈希表
• 字符串
• 双指针
• 栈与队列
• 二叉树
• 回溯算法
• 贪心算法
• 动态规划
• 单调栈
• Other

算法性能分析

详细可以查看本站文章：基本概念与复杂度

• 时间复杂度：运行时需要的总步数，通常时问题规模的函数（大 O 表示）
  • 常数 O(1)＜ 对数阶 O(log2n) ＜ 线性阶 O(n) ＜ 线性对数阶 O(nlog2n) ＜ 平方阶 O(n^2) ＜ 多项式阶 O(n^C) ＜ 指数阶 O(C^n)
  • 时间复杂度分析基本策略：从内向外分析，从最深层开始分析
  • 计算每层实际执行次数并求和；循环层数本身不能决定复杂度。双指针的内外循环也可能总共只移动O(n)次，折半循环可能是O(log n)。
• 空间复杂度：执行时所占用的储存空间，通常时问题规模的函数,运行过程中临时占用存储空间大小的度量
  • 程序代码所占用的空间
  • 输入数据所占用的空间
  • 辅助变量 所占用的空间（估算额外空间复杂度时，分析辅助变量和递归栈所占空间）

书面复盘示例

以窗口右端 i 和左端 j 为例，内层循环虽然嵌在外层，却只把 j 向右推且从不回退。把所有轮的移动次数合并统计：i 至多 n 次，j 至多 n 次，合计至多 2n。若每次窗口内重扫元素、复制窗口或把 j 归零，这个线性结论就不再成立。

查看图表代码

题目：外层遍历n项，内层指针j从0递增到n且从不回退，能否直接判O(n²)？提示：统计j总递增次数。

参考答案

不能；若每步常数工作，两指针全程各移动至多n次，总时间O(n)，辅助索引O(1)。输入数组本身是否计入空间应先约定。历史性能数值不替代这种计数推导。