这道题的重点是对双指针过程的分析,典型的双指针类型题目,博主的代码速度为16ms,战胜90%的答题者,思路比较一般,不过还是分享一下。
算法导论
LeetCode_218: The Skyline Problem
Skyline是一个经典问题了,一开始博主思考先进行高度排序,从高到低来确定关键点。事实上通过优先队列来获取当前位置的最大高度,沿着x轴来遍历是最好的。这篇博客提供了一份19ms的答案,战胜了97%,当然是从讨论区淘出来的,博主没想到这么优秀的方法。
LeetCode_313: Super Ugly Number
这道题一种普遍的解法是动态规划。但是同样是动态规划,也有优劣之分。这篇博客贡献一份36ms(80%+)的答案,推荐这份答案不仅是因为速度,还是因为这种思路十分清晰,当然也可以参考讨论区中的7行的动态规划答案,也是十分优秀的。
LeetCode_373: Find K Pairs with Smallest Sums
寻找K个最大组合,博主最开始使用BFS来做的,算法复杂度$latex O(mn)$,计算和$latex mn$,广度优先搜索$latex V+E = mn+(m-1)(n-1)$,速度13ms。此外,博主对DP的掌握一直不够熟练,顺便贴了另一种使用DP的搜索方法,也是13ms,其实两种思路是差不多的。[mathjax]
LeetCode_378: Kth Smallest Element in a Sorted Matrix
经典的数据结构问题,在算法导论堆排序的思考题中出现过这种结构的排序求解问题,该问题解法多样,很适合学习。
LeetCode_407: Trapping Rain Water II
一道很有意思的题目,题目是计算容器雨水积累量,实际上是利用广度优先搜索来不断收缩边界,计算雨水的积累。由于博主之前图一类的题目接触的比较少,这道题目看了一眼答案。这篇博客除了介绍这道题目本身,还将介绍stl中的优先队列priority queue,优先队列是广度优先搜索(BFS)必要的辅助。作为编程辅助,后面还顺便介绍了C++11的花括弧初始化。
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++实现算法时的一些体会,更多的是算法细节,希望有助于加深对算法的理解的。
Leetcode_524: Longest Word in Dictionary through Deleting
笔记:Leetcode 524 Longest Word in Dictionary through Deleting,分类是sort, two pointer,博主的解法比solution中10行的要快一点,事先对词典进行排序,在词典规模大时,博主解法更有优势。
C++类的成员函数指针
对于一般的函数指针我们都比较了解了,而类的成员函数指针以及调用方式都有所不同。博主在调Bug的过程中,将相关资料整理到这篇博客中,仅供参考。
leetcode_75_SortColors的C++代码
这次击败了100%的C++编程者,题目比较简单,三路快速排(三指针)的解决方法。其实博主一开始还没有想到Follow Up中的计算-还原二次遍历法 :)。既然贴了eazy标签就不解释了,直接上代码。
leetcode_242_ValidAnagram高质量C++代码
这道题标签是eazy,可以排序判断字符串相等,但是只击败了33%的C++编程者,博主自然是不甘心的,于是采用统计词频,并且略施小计,一开始先校验长度,这样就击败了99%。:)
Leetcode_324_wigglySortII高质量C++代码
这道题是Google的面试题,参照WigglySortI,本质就是一个坐标映射,只是中位数有等号,映射时候需要小心,博主第一版代码直接用Sort排序,代码击败65.8%,然后参照大牛代码,使用三路快排,速度已经提起来了。和大牛的代码不同的是,大牛采用高大上的宏函数做坐标映射,博主比较笨,理解那个映射公式花了些时间,索性就用了第一版代码的坐标映射,单独写了一个for循环。大牛代码103ms,博主代码102ms,所以坐标映射部分开销是差不多的,可见代码核心还是在三路快排(三指针)上。
leetcode_Palindrome Partitioning II笔记
Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. For example, given s = "aab"
, Return 1
since the palindrome partitioning ["aa","b"]
could be produced using 1 cut.