TB前卫网

TB前卫网店铺大全为您精选最好的精品店铺导航,欢迎您。收藏本站

LeetCode 刷题指南(1):为什么要刷题

栏目:科技数码   发布时间:2016/07/28   来源:Python开发者   编辑:PythonCoder

Python开发者


来源:伯乐在线专栏作者 - selfboot  

链接:http://blog.jobbole.com/103848/



是一个非常棒的

LeetCode 是一个特别棒的 OJ(Online Judge)平台,搜集了很多公司的面试题目。相对于其他 OJ 平台而言,有着下面的几个优点:

  • 题目全体来自业内大公司的真实面试

  • 不用途理输入输出,精力全放在解决具体问题上

  • 题目有丰厚的讨论,可以参考他人的思路

  • 精确知道自我代码在所有提交待码中运行效力的排名

  • 支撑多种主流语言:C/C++,Python, Java

  • 可以在线进行测试,利便调试



下面是我刷 LeetCode 的一些收成,但愿能够勾引大家有空时刷刷题目。

问题:抽象思惟

波利亚用三本书:《How To Solve It》、《数学的发现》、《数学与料想》)来试图阐明人类解决问题的一般性的思惟策略,总结起来主要有下列几种:

  • 时刻不忘未知量。即时刻别忘怀你到底想请求啥,问题是啥。(动态计划中问题状况的设定)

  • 试错。对题目这里捅捅那里捣捣,用上所有的已经知量,或者使用所有你想到的操作手法,尝试着看看能不能得到有用的结论,能不能离谜底近一步(回溯算法中走不通就回退)。

  • 求解一个相似的题目。相似的题目或许有相似的结构,相似的性质,相似的解方案。通过考察或者回想一个相似的题目是如何解决的,或许就可以借用一些首要的点子(对比 Ugly Number 的三个题目:263. Ugly Number, 264. Ugly Number II, 313. Super Ugly Number)。

  • 用特例启迪思考。通过斟酌一个适合的特例,可以利便咱们快速寻觅出一般问题的解。

  • 反过来推导。至于很多题目而言,其请求的结论自身就暗藏了推论,无论这个推论是充沛的仍是必要的,都极可能对解题有协助。



刷 LeetCode 的最大益处就是可以锻炼解决问题的思惟能力,相信我,如何去思考自身也是一个需要不断学习以及练习的技巧。

另外,大量高质量的题目可以加深咱们对计算机科学中经典数据结构的深入理解,从而可以快速用适合的数据结构去解决现实中的问题。咱们看到许多ACM大牛,拿到题目后当即就可以想出解法,大概就是由于他们至于各种数据结构有着深入的认识吧。LeetCode 上面的题目涵盖了几近所有经常使用的数据结构:

  • Stack:简单来讲拥有落后先出的特性,具体利用起来也是妙不可言,可以看看题目 32. Longest Valid Parentheses。

  • Linked List:链表可以快速地插入、删除了,然而查找对比费时(具体操作链表时结合图会简单许多,另外要注意空节点)。通常链表的相干问题可以用双指针奇妙的解决,160. Interp of Two Linked Lists 可以帮咱们从新审视链表的操作。

  • Hash Table:应用 Hash 函数来将数据映照到固定的一块区域,利便 O(1) 时间内读取和修改。37. Sudoku Solver 数独是一个经典的回溯问题,配合 HashTable 的话,运行时间将大幅减少。

  • Tree:树在计算机学科的利用十分广泛,经常使用的有二叉搜寻树,红黑书,B+树等。树的树立,遍历,删除了相对于来讲对比繁杂,通常会用到递归的思路,113. Path Sum II 是一个不错的开胃菜。

  • Heap:特殊的完整二叉树,“等级森严”,可以用 O(nlogn) 的时间繁杂度来进行排序,可以用 O(nlogk) 的时间繁杂度找出 n 个数中的最大(小)k个,具体可以看看 347. Top K Frequent Elements。



算法:时间空间

  • 分而治之:有点相似“大事化小、小事化了”的思想,经典的归并排序以及快速排序都用到这类思想,可以看看 Search a 2D Matrix II 来理解这类思想。

  • 动态计划:有点相似数学中的归纳总结法,找出状况转移方程,然后逐渐求解。 309. Best Time to Buy and Sell Stock with Cooldown 是理解动态计划的一个不错的例子。

  • 贪心算法:有时候只顾局部利益,终究也会有最佳的全局收益。122. Best Time to Buy and Sell Stock II 看看该如何“贪心”。

  • 搜寻算法(深度优先,广度优先,二分搜寻):在有限的解空间中找出知足前提的解,深度以及广度通常对比费时间,二分搜寻每一次可以将问题范围缩小一半,所以对比高效。

  • 回溯:不断地去试错,同时要注意悬崖勒马,走不通就换条路,终究也能找到解决问题策略或了解问题无解,可以看看 131. Palindrome Partitioning。



固然,还有一部份问题可能需要一些数学知识去解决,或是需要一些位运算的技能去快速解决。总之,咱们但愿找到时间繁杂度低的解决策略。为了到达这个目的,咱们可能需要在一个解题策略中融会多种思想,譬如在 300. Longest Increasing Subsequence 中同时用到了动态计划以及二分查找的策略,将繁杂度节制在 O(nlogn)。如果用其他策略,时间繁杂度可能会高许多,这类题目的运行时间统计图也对比成心思,可以看到不同解决方案运行时间的巨大悬殊,以下:

当然有时候我们会牺牲空间换取时

固然有时候咱们会牺牲空间换取时间,譬如在动态计划中状况的储存,或是记忆化搜寻,防止在递归中计算重复子问题。213. House Robber II 的一个Discuss会教咱们如何用记忆化搜寻减少程序履行时间。

语言:各有千秋

对一个问题来讲,解题逻辑不会因编程语言而不同,然而具体coding起来语言之间的差别仍是很大的。用不同语言去解决同一个问题,可让咱们更好地去理解语言之间的悬殊,和特定语言的优势。

速度 VS 代码量

C++ 以高效灵便著称,LeetCode 很好地印证了这一点。至于绝大多数题目来讲,c++ 代码的运行速度要远远超过 python 和其他语言。以及 C++ 相比,Python 允许咱们用更少的代码量实现一样的逻辑。通常情况下,Python程序的代码行数只至关于对应的C++代码的行数的三分之一摆布。

以 347 Top K Frequent Elements 为例,给定一个数组,求数组里呈现频率最高的 K 个数字,譬如至于数组 [1,1,1,2,2,3],K=2 时,返回 [1,2]。解决该问题的思路对比常规,首先用 hashmap 记录每一个数字的呈现频率,然后可以用 heap 来求呈现频率最高的 k 个数字。

如果用 python 来实现的话,主要逻辑部份用两行代码就足够了,以下:

num_count = collections.Counter(nums)

return heapq.nlargest(k, num_count, key=lambda x: num_count[x])



固然了,要想写出短小俊雅的 python 代码,需要对 python 思想和模块有很好的知道。关于 python 的相干知识点讲授,可以参考这里。

而用 C++ 实现的话,代码会多许多,带来的益处就是速度的奔腾。具体代码在这里,树立大小为 k 的小顶堆,每一次进堆时以及堆顶进行对比,核心代码以下:

// Build the min-heap with size k.

for(auto it = num_count.begin(); it != num_count.end(); it++){

  if(frequent_heap.size() push(*it);

  }

  else if(it->second >= frequent_heap.top().second){

      frequent_heap.pop();

      frequent_heap.push(*it);

  }

}



语言的悬殊

咱们都了解 c++ 以及 python 是不同的语言,它们有着显著的区分,无非一不谨慎咱们就会忘怀它们之间的差别,从而写出bug来。不信?来看 69 Sqrt(x),实现 int sqrt(int x)。这题目是经典的二分查找(固然也能够用更高档的牛顿迭代法),用 python 来实现的话很容易写出 AC 的代码。

如果用 C++ 的话,相信许多人也能避开求中间值的整型溢出的坑:int mid = low + (high - low) / 2;,因而写出下面的代码:

int low = 0, high = x;

while(low // int mid = (low+high) / 2,  may overflow.

  int mid = low + (high - low) / 2;

  if(x>=mid*mid && x1)*(mid+1)) return mid;

  else if(x 1;

  else low = mid + 1;

}



很惋惜,这样的代码依然存在整型溢出的问题,由于mid*mid 有可能大于 INT_MAX,正确的代码在这里(https://github.com/xuelangZF/LeetCode/blob/master/BinarySearch/69_Sqrt_x.cpp)。当咱们被 python 的自动整型转换宠坏后,就很容易忘怀c++整型溢出的问题。

除臭名昭著的整型溢出问题,c++ 以及 python 在位运算上也有着一点不同。以 371 Sum of Two Integers 为例,不用 +, – 实现 int 型的加法 int getSum(int a, int b)。其实就是摹拟计算机内部加法的实现,很显明是一个位运算的问题,c++实现起来对比简单,以下:

int getSum(int a, int b) {

    if(b==0){

        return a;

    }

    return getSum(a^b, (a&b)1);

}



但是用 python 的话,情况变的繁杂了许多,归根到底仍是由于 python 整型的实现机制,具体代码在这里(https://github.com/xuelangZF/LeetCode/blob/master/BitManipulation/371_SumOfTwoIntegers.py)。

讨论:百家之长

如果说 LeetCode 上面的题目是一块块金子的话,那末评论区就是一个装点着钻石的矿山。多少次,当你挖空心思终究 AC,兴趣勃发地来到评论区筹备吹水。结果迎接你的却是巨匠级的代码。因而,你高呼:尼玛,竞然可以这样!然后闭关去思考那些优良的代码,顺便默默鄙视自我。

除优良的代码,有时候还会有直观的解题思路分享,利便看看他人是如何解决这个问题的。@MissMary在“两个排序数组中找出中位数”这个题目中,给出了一个很棒的解释:Share my o(log(min(m,n)) solution with explanation(https://discuss.leetcode.com/topic/4996/share-my-o-log-min-m-n-solution-with-explanation/2),取得了400多个zan。

你也能够评论大牛的代码,或提出改良方案,无非有时候可能并不是如你预期同样改良昆裔码会运行地更好。在 51. N-Queens 的讨论 Accepted 4ms c++ solution use backtracking and bitmask, easy understand (https://discuss.leetcode.com/topic/13617/accepted-4ms-c-solution-use-backtracking-and-bitmask-easy-understand)中,@binz 在讨论区中疑惑自我将数组 vector (取值非零即一)改成 vector 后,运行时间变慢。@prime_tang 随后就给出建议说最佳不要用 vector,并给出了两个 StackOverflow 谜底。

当你逛讨论区久了,你可能会有那末一两个偶像,譬如@StefanPochmann。他的一个粉丝 @agave 曾问 StefanPochmann 一个问题:

Hi Stefan, I noticed that you use a lot of Python tricks in your solutions, like “v += val,” and so on… Could you share where you found them, or how your learned about them, and maybe where we can find more of that? Thanks!



StefanPochmann 也不厌其烦地给出了自我的谜底:

@agave From many places, though I’d say I learned a lot on CheckiO and StackOverflow (when I was very active there for a month). You might also find some by googling python code golf.



原来大神也是在 StackOverflow 上修炼的,看来需要在《为何离不开 StackOverflow》中添加一个理由了:由于 StefanPochmann 都混迹于此。

相似这样友好,充溢技术味道的讨论,在 LeetCode 讨论区遍地都是,绝对值得咱们去好好探寻。

成长:大有利处

偶尔会听旁边人说 XX 大牛 LeetCode 刷了3遍,胜利进微软,还拿了 special offer!听起来好像刷题就能够解决工作问题,无非要了解还有刷5遍 LeetCode 依然没有找到工作的人呢。所以,不要想着刷了许多遍就能够找到好工作,毕竞比你刷的还疯狂的大有人在(开个玩笑)。

无非,想一想前面列出的那些益处,应当值得大家抽出点时间来刷刷题了吧。

专栏作者简介 (  )


selfboot:酷爱计算机技术的学生...书中追求心灵的镇静...selfboot,自启动,只有自我能启动自我所以不要寄但愿于他人,自己演变展翅飞翔吧!

打赏支持作者写出更多好文章

打赏支撑作者写出更多好文章,谢谢!




【本日微信公号举荐】

更多推荐请看

更多举荐请看《》

其中举荐了包含技术、设计、极客 以及 值得关注的技术以及设计公家号》,发现精彩!

【公众号】:Python开发者
【微信号】:PythonCoder
【微宣言】:人生苦短,我用Python。伯乐在线旗下账号「Python开发者」分享Python相关的技术文章、工具资源、精选课程、热点资讯等。

下一篇:它凭什么击败谷歌,夺得戛纳数字类设计大奖?
*版权声明及防欺诈提醒