刷题窍门

注意题目中的条件

有一些题目中的条件本质是暗示：

• 设计一个O(logN)的算法：基本使用分治法，排序数组
• 无需考虑额外的空间：可以开辟空间，空间换时间（哈希表）
• 数据规模大概是10000：设计一个O(n^2)的算法也可以实现（计算次数最终不超过1亿）

当没有思路的时候

• 使用几个简单的测试用例，试验一下结果
• 不要忽视暴力解法。暴力解法通常是思考的起点
• 想一遍常见的算法思路；遍历常见的数据结构；空间换时间（例如hash表）
• 数据预处理（排序；傅里叶变换）
• 在瓶颈处找答案：O(NlogN) + O(N^2)

实际编写代码时的问题

• 判断极端条件（参数验证）：数组为空、字符串长度为0、数量为0、指针null
• 变量名的语义化
• 代码模块化、复用性

怎样写出一个正确的算法

• 明确变量的含义：每一个变量都有固定的定义
• 考虑边界：对于数组的访问变量，一定要考虑边界（JS不需要考虑，Python和C需要注意）
• 循环不变量：维护循环中变量的含义，仔细比对边界
• 最好先写出思路：先理清思路再编码，不要急着写几句你所认为“对”的代码
• 小数据量调试：空集、无正确答案集；有正确答案查看每轮的改变
• 大数据量测试

时间复杂度

O 即时间复杂度，在计算时需要注意两点

• 取时间复杂度更高的作为结果 O(nlogn+ n ) = O(nlogn)
• 虽然会忽略常数系数，但要记得有这个东西
• 不相关的数据不可以合并：例如既涉及到数组长度，和字符串长度，那么这个两个数据量不能直接用一个n就表示完了，得n+s

算法的事件复杂度与用例相关

快速排序

• 平均： O(nlogn)
• 最差： O(n^2)
• 最好： O(nlogn)

空间复杂度

空间复杂度即多开的一个辅助数组，但要注意，递归调用是有空间代价的。

如果递归层数等于n, 并且每层使用了一个变量，那么这个空间复杂度都是n,而不是1

对数器的概念和使用

• 有一个你想要测的方法a
• 实现一个绝对正确但是复杂度不好的方法b
• 实现一个随机样本产生器
• 实现比对的方法
• 把方法a和方法b比对很多次来验证方法a是否正确
• 如果有一个样本使得比对出错，打印样本分析是哪个方法出错
• 当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

局部与宏观

当题目在局部的变化很绕的时候，考虑宏观思路（之字形打印矩阵）

算法面试

把面试官当作一个朋友，共同在开发中碰到了这样一个问题，一起探讨，一起思考。 展示出你的逻辑，思考的过程，优化的方法，以及所处理的问题是否在实际中有用。思维最重要！

就算做不出来，也要展示出往那个方向上，努力可能得到正确的解。

使用基础方法做出来，尽量想一些优化的方法，并定量描述优化前后的差距。

解决问题的思路：面对一个问题时，不要简单的，极端的用对或者错这样的态度来看待这个问题，而要能够思考的更加全面一些。

---

Last update: November 23, 2021