缘何要刷题

尽管刷题平素备受诟病,然而不可以仍然不可以认刷题确实能磨炼大家的编程能力,相信每个认真刷题的人都会有认知。现在提供在线编程评测的阳台有众多,比较闻名的有
hihocoderLintCode,以及那里大家关切的
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
上边的难点涵盖了里面绝一大半,上面大概来看下。

理所当然,还有局地标题或许须求有些数学知识去化解,或者是必要部分位运算的技艺去快捷解决。总而言之,大家期望找到岁月复杂度低的解决形式。为了落成这几个目标,我们恐怕必要在一个解题方法中融为一体二种商量,比如在
300. Longest Increasing
Subsequence

中同时采纳了动态规划和二分查找的办法,将复杂度控制在
O(nlogn)。若是用其余办法,时间复杂度可能会高很多,那种难题的运作时刻计算图也相比好玩,可以看看差别解决方案运行时刻的高大差异,如下:

365bet手机app下载 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 时,返回 [365bet手机app下载,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
照旧没有找到工作的人
啊。所以,不要想着刷了成百上千遍就可以找到好工作,毕竟比你刷的还疯狂的大有人在(开个玩笑)。

而是,想想前面列出的那些利益,应该值得大家抽出点时间来刷刷题了吗。

越来越多读书

跟Polly亚学解题
缘何我反对纯算法面试题
聊天刷题
怎么看待中国学童为了进
谷歌、微软等营业所疯狂地刷题?

LeetCode
编程磨练

国内有怎样好的刷题网站?

发表评论

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