刷题指南

尽管刷题一向饱受诟病,然则不可不可以认刷题确实能训练我们的编程能力,相信每个认真刷题的人都会有认知。现在提供在线编程评测的阳台有无数,比较出名的有
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)。借使用其他艺术,时间复杂度可能会高很多,那种题材的运作时刻总结图也相比有趣,可以看出分歧解决方案运行时刻的壮烈差异,如下:

ea平台365bet体育在线 1

当然有时候大家会捐躯空间换取时间,比如在动态规划中状态的保留,或者是回想化搜索,防止在递归中总结重复子难点。213.
House Robber
II

一个Discuss会教大家什么用记念化搜索减少程序执行时间。

言语:各有千秋

对一个题材来说,解题逻辑不会因编程语言而分歧,但是具体coding起来语言之间的差距依然很大的。用差别语言去化解同一个标题,可以让大家更好地去领略语言之间的差异,以及特定语言的优势。

ea平台365bet体育在线,速度 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
照旧没有找到工作的人
啊。所以,不要想着刷了成千上万遍就可以找到好干活,毕竟比你刷的还疯狂的大有人在(开个笑话)。

不过,想想前边列出的那多少个好处,应该值得我们抽出点时间来刷刷题了啊。

越多读书

跟波莉亚学解题
怎么自己反对纯算法面试题
闲话刷题
怎样对待中国学童为了进
谷歌(Google)、微软等公司疯狂地刷题?

LeetCode
编程操练

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

发表评论

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