最近几天无聊,又去上 LeetCode 探智商下限了(划掉

数组 Array:

1. 二分查找:

此类题整体较简单,而且在编码过程中不一定需要使用二分查找,用一些 hash based 的数据结构也是不错的选择。在 C++ 下借助 set, map 或是 binary_search + vector 都可以较为轻松的解决。

参考题目: Two SumTwo Sum II - Input array is sorted3 Sum

2. 高精度计算:

此类题整体较简单,基本就是使用数组来进行超大规模的加减计算。

参考题目: Plus One

3. 递归计算:

递归计算在我们接触 C 语言的时候就已经开始接触了,所以应该是不困难的。借助一维或是多维数组来缓存计算结果可以有效提升递归的执行效率,防止出现爆栈、或是递归太久这种坑爹的情景。

参考题目: Pascal's TrianglePascal's Triangle II

4. 数组元素查找与删改:

目前看到的有查找查重、去重、移动和删除,去重和统计出现次数方面使用 set/map 就基本摆平了;移动的话参考插入排序,依次前移或者后移;删除的话,直接将元素 swap 到数组尾部,然后重新标记数组大小就完成了。都还是蛮简单的。

参考题目: Remove Duplicates from Sorted ArrayContains DuplicateContains Duplicate IIMajority ElementThird Maximum NumberMedian of Two Sorted Arrays

5. 最大子列和以及类似问题:

难易程度看题目,简单的问题 O(n) 的遍历就能解决,稍复杂的从动态规划入手,如果遇到其他类型的到时候再补充。

参考题目: Maximum SubarrayBest Time to Buy and Sell StockBest Time to Buy and Sell Stock II

6. 排序:

考虑到现在各类语言都已经有自己的排序方法,直接排序的问题都不难。当然有些题目里排序作为关键的步骤然而想不到时……

参考题目: Merge Sorted Array

6. 前缀、后缀和与运算律:

感觉没啥好说的这个……到时候在补充吧

参考题目: Product of Array Except Self

7. 概率与统计相关:

比如 A -> B 有多少中走法啦,如何从样本容量超级大的样本中随机抽样啦这种,递《概率论与数理统计》(划掉

参考题目: Unique PathsUnique Paths II

8. 搜索:

比如给一个数组,一个起点,一些限制规则,让你找出一个最怎么怎么样的路径。这类题目熟练的 DFS, BFS 可破,不算难。对于部分题目,逆向搜索会有奇效。当然必须的标记(flag)和缓存结果也是必要的。

参考题目: Minimum Path Sum

inf. 无归类:

一个简单的 O(n) 遍历:Container With Most Water
上一题的拓展,当然重新动规也是可以的:Trapping Rain Water

数学 Math

inf. 无归类:

一个简单的进制转换(然而我特么 WA 了一次摔):Excel Sheet Column Title

基础数据结构

1. 树

简单的很基础,比如找最大深度啊,某种遍历。复杂的等遇到了再补充。 参考题目 Minimum Depth of Binary Tree