LeetCode_057: Insert Interval

这道题就是区间插入问题,目前看到的解法主要有三种,一种是直接分析区间重叠,具有O(n)时间和O(n)空间复杂度,另一种是用二叉搜索树来做,还有一种是借助了STL库中的equal_range方法来做,写法比较优雅。这篇博客主要给出第一种解法和第三种解法的代码

阅读更多

LeetCode_164: Maximum Gap

经典的线性时间排序问题,题目标签是hard,主要是要求了线性时间内解决问题,那么很自然想到基数排序和桶排序了。除此之外还有一种常用的线性时间排序,计数排序可以看做间隔为1的桶排序,在数字比较集中且可转化为整数时比较有效,因此计数排序不适合本题目。

阅读更多

LeetCode_274: H-index

H指数的计算,这道题是典型的排序思路,博主第一次使用一般的排序方法写,后来发现整数这种用基数排序更合适,同时需要考虑很多特例,博主贴了这两份代码。由于测试案例的原因,基数排序速度上的优势没有体现出来。

阅读更多

算法导论总结(一)之排序C++

博主之前刷过一遍《算法导论》(Introduction to Algorithms),但是看得多写得少,于是最近抽空动手写写下里面的算法。排序是经典问题了,于是决定将书中的排序算法一一使用C++实现。这篇博客一方面是对排序算法本身的总结(这个书上都有啦),另一方面是博主在使用C++实现算法时的一些体会,更多的是算法细节,希望有助于加深对算法的理解的。

阅读更多