LeetCode 刷题指南(一):为什么而刷题

虽说刷题一直受诟病,不过不可否认刷题确实会锻炼我们的编程能力,相信每个认真刷题的人数还见面发生认知。现在供在线编程评测的阳台有很多,比较显赫的有
hihocoder,LintCode,以及这里我们关心的
LeetCode。

代码提交曲线

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.
    Intersection 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。

算法:时间空间

咱们懂得,除了数据结构,具体算法在一个序中为是非常首要的,而算法效率的心地则是时空复杂度和空中复杂度。通常状态下,人们更关注时间复杂度,往往想找到比
O( n^2 )
快的算法,在数据量比较异常的动静下,算法时间复杂度最好是O(logn)或者O(n)。计算机课中经典的算法思想就那基本上,LeetCode
上面的问题涵盖了里绝大多数,下面大致来拘禁下。

  • 分而治之:有点类似“大事化小、小事化了”的思维,经典的统一排序和速排序都为此到这种思考,可以省
    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)。如果用任何艺术,时间复杂度可能会见大多,这种题材的运转时刻统计图也比较有意思,可以看来不同解决方案运行时刻的丕差距,如下:

ea平台365bet体育在线 1

自然有时候我们会牺牲空间换取时间,比如在动态规划中状态的保留,或者是记忆化搜索,避免在递归中计算重复子问题。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() < k){
      frequent_heap.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 <= high){
  // int mid = (low+high) / 2,  may overflow.
  int mid = low + (high - low) / 2;
  if(x>=mid*mid && x<(mid+1)*(mid+1)) return mid;
  else if(x < mid*mid)  high = mid - 1;
  else low = mid + 1;
}

坏惋惜,这样的代码仍然在整型溢起底问题,因为mid*mid 有或不止
INT_MAX,正确的代码在这里。当我们给
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
整型的贯彻机制,具体代码在这里。

议论:百家的丰富

一旦说 LeetCode
上面的问题是一块块金的话语,那么评论区就是一个点缀在钻的矿山。多少次,当您绞尽脑汁终于
AC,兴致勃发地来到评论区准备吹水。结果迎接你的也是大师级的代码。于是,你高呼:尼玛,竟然可以这么!然后闭关去思维那些可以之代码,顺便偷鄙视自己。

除却优异的代码,有时候还会时有发生直观的解题思路分享,方便探望别人是哪些缓解者问题之。@MissMary以“两只排序数组中找寻来中位数”这个问题中,给闹了一个大过硬的诠释:Share
my o(log(min(m,n)) solution with
explanation,获得了400多个赞。

乃吗可以评大牛的代码,或者提出改善方案,不过有早晚也许并非要你预期一样改进后码会运行地再好。在
51.
N-Queens
的讨论 Accepted 4ms c++ solution use backtracking and bitmask, easy
understand
中,@binz 在讨论区中纳煮自己以反复组 vector<int>
(取值非零即一)改吧 vector<bool> 后,运行时变慢。@prime_tang
随后便受起建议说最不要为此 vector<bool>,并给闹了两个
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
仍然没有找到工作的人口啊。所以,不要想在刷了众多不折不扣就是得找到好干活,毕竟比你刷的尚狂之大有人在(开单玩笑)。

但是,想想前列有的那些好处,应该值得大家抽出点时间来刷刷题了咔嚓。

重新多读书

跟波利亚学解题ea平台365bet体育在线
怎自己反对纯算法面试题
拉刷题
什么样对待中国学生为进
Google、微软当企业疯狂地刷题?
LeetCode
编程训练
境内产生什么好之刷题网站?

发表评论

电子邮件地址不会被公开。 必填项已用*标注