LeetCode_146: LRUCache 使用STL-list

在LeetCode的题目中,考察list操作的比较少,所以这道题也算是经典了,只有17%的通过率也足以说明问题。STL的list模板是一个环形双链表,其支持链表的基本操作,并且封装了reverse、sort、merge、splice等算法,为链表的操作提供许多遍历,这篇博客会根据在STL源码分析中的内容进行简单介绍。

阅读更多

算法导论总结(五)散列表

LeetCode刷了两百多题,再来一波总结,题目刷多了很多不做笔记就忘记了,这里也算是巩固一下。这一节主要总结散列表类型的题目。散列表、桶排序等算法最大的特点就是时间复杂度是O(1)。这对于需要考虑算法时间复杂度的题目来说提升是常常需要考虑的方法。这篇博客没有太多原理的解释,都是对着题目做的随手笔记 ,比较乱,请见谅。

阅读更多

LeetCode_210: CourseScheduleII 拓扑排序

这道题与前一版本207一样,只不过前一版本要求判断是否有环,而当前版本还要给出可行顺序,那么这个问题就自然而然的归为拓扑排序了。这篇博客将对有向图和无向图中是否存在环这一问题进行归纳,并且给出一个较为简洁的拓扑排序代码。拓扑排序,简单的说就是不断将度为0的点提取出来,提取的顺序就是拓扑排序。在算法导论中,给出了DFS和BFS解法,其中DFS采用完成时间倒序作为拓扑排序,我们需要了解拓扑排序问题的解法是多样的,这篇博客给出的代码不算唯一的。

阅读更多

LeetCode_174: Dungeon Game 动态规划

做了一道很有意思的题目,要求是从左上角开始,在HP不掉到0的情况下,到达右下角。虽然明显是使用动态规划来解,但是其中隐藏了一些技巧 。这里,如果从左上角开始进行DP将使得问题复杂化,技巧就是反向,从终点开始反向DP,这篇博客将详细这种方法的应用条件。

阅读更多

LeetCode_134: Gas Station

这道题目可以使用一般的DP来做,但是博主想到的方法更加直接:对于判断是否存在解,直接把数组累加,如果和非负,那么必然存在一个位置,使得从这个位置开始进行累加的所有结构都非负。在进行累加的过程中,找到累加和最小的位置,从这个位置的下一个位置开始,就可以保证在累加过程中,累加曲线的最小值最大(想象积分曲线的过程,积分的终点sum相同,一个先下降再上升,一个先上升再下降)。有点绕,多想想 :)

阅读更多

LeetCode_068: Text Justification

又是一道通过率不过20%的题,总结这种通过率比较多的题目,发现其中很多原理并不难,导致通过率比较低的原因是各种极端情况,还有就是题目理解和表述不够清晰。比如自己实现Atoi,如果列出要处理的各种情况,写出来并不难。这道题也是一样,其实没什么难度,只是有些情况下,具体说来就是最后一行或者一行的最后一个单词,需要特殊处理。

阅读更多

LeetCode_131: Palindrome Partition 回文字符串

回文字符串问题可以看做是一个划分链问题,这个和算法导论中介绍动态规划时的矩阵链乘法是一样的,找到一个最优的划分方案。很自然的想到动态规划来得到一个回文串的真值表,然后就是要列举出所有的情况,回溯法可以做到,自然而然的DP+BackTracking解决掉。

阅读更多

LeetCode_010: 正则表达式匹配 与 044: 通配符匹配

最近在攻略动态规划,在做正则表达式匹配的时候看错了题目,发现写出来的是通配符匹配,后来看了下什么是正则表达式才明白过来。这两道题都是有很多解法的题目,按照标签刷题目还是限制了自己的思路,一开始就没有往其它地方想。事实上,通配符匹配用贪心算法(可以看做一种特殊的动态规划)更合适。

阅读更多

算法导论总结(三)树

树作为重要的数据结构,在很多领域有着重要的用途。在LeetCode中对数的考察主要分为三个方面,一是树的遍历,二是BST(二叉搜索树),三是和树相关的算法。有时,树也常常被看做一个图,做BFS和DFS,树的考察是相当灵活的。这篇博客就这些问题做部分小结。

阅读更多

LeetCode_023: Merge k Sorted Lists

        一种结合链表和优先队列的优雅解法,巧妙之处在于使用优先队列出队元素,可以直接得到下一个入队元素,算法复杂度是O(nlgn)。联想到如果不是优先队列结构,那么我们可以使用同样的解法,只是我们需要在队列中记录每个元素属于哪一行,而使用链表结构就避免了这种麻烦。

阅读更多

LeetCode_126: Word Ladder II

最近总是Rank到很难的题目,这次遇到了LeetCode中通过率最低的题目。这道题目是一个图相关的问题,同时牵扯到很多坑,很多细节,即使思路正确稍不注意内存超出,时间超出都是常事儿,自己做出来还是需要废一番功夫的。博主写了BFS算法的大概就放弃了,后面翻了几份代码,找了个最简洁的 ,这里也只能讲解一下别人的代码了。

阅读更多