LEETCODE刷题心得-你必须掌握的4类必考题型

前(fei)言(hua):

大约在一年前左右,我第一次打开leetcode的网站。在那之前,我从未想过要进行算法编程方面的学习。作为一名骨灰级AndroidApp程序猿,平时的工作与底层算法毫无干系。我们关心的内容大多是,AndroidOS推出哪些新鲜的功能?Animation又增加了什么绚丽的效果?最近又在流行什么框架?。。。什么?你问我是否关心代码执行效率?对不起,那不是硬件该去解决的问题吗?将你的内存,CPU,GPU,显卡,屏幕再加上手机壳,手机链统统升级一圈,你会发现我的程序速度将得到大幅改善。

算法的重要性

所以我们为什么还要刷题?也许你会快速的回答出来刷题是为了找到更好的工作。那么你是否知道各个大厂为什么在面试时要使用算法题来作为对面试者的评判标准呢?我想大部分人都没有考虑过这个问题,包括我在内很长时间以来都忽略了这个问题的重要性。俗话说面试造火箭,工作拧螺丝。直到一年前我在某个聚会上结识了一位谷歌日本的面试官,他的话让我受益匪浅。在这里简单和大家分享一下。

  1. 对于题库中的题目,不要试图死记硬背。面试时考官虽然会使用过往出过的题目,但他们看中的不仅仅是你快速的写出程序代码,而是想听到你是如何思考的,讲清楚你的思考逻辑与写出正确的代码同样重要。
  2. 如果你能拿到offer,你的面试官很大可能会成为你今后一同工作的同事,面试官是否愿意与你一同工作,你的代码质量至关重要。如果你的代码没有逻辑,没有算法,又臭又长很难被理解,这无端会增加他们code review的时间。对于大厂的码农(尤其谷歌),他们是很厌恶加班的,所以你的代码质量会直接决定你面试的结果。
  3. 将你刷题时养成的思考习惯,活用到你的实际工作中。刷题时通常情况下我们会使用高效率的代码去实现题目要求(至少是为了防止TLE),而很多人到了实际工作中会将刷题时养成的好习惯抛到脑后,恢复到只会使用暴力算法的坏习惯上。这样即使你侥幸拿到了大厂的offer,你也会因你的代码质量而遭到同事的差评,进而增加自身的工作压力。
  4. 关于刷题数量。很多人喜欢问我刷了800题能通过谷歌的面试吗?其实这种问题很难回答,首先你需要对你有自信,如果你真的拥有足够的实力,即是你没刷过Leetcode,你依然有可能拿到任何一家公司的offer。

总结一下上面的内容,面试时考算法只是一种手段,你需要在解题过程中不断的与面试官进行交流,这种交流实际上是在模拟演练你们今后一起工作时的场景,另外如果你有过刷题的经验,你的代码质量会明显高于其他没有经过训练的人,这是你在大厂工作必备的技能之一。

我们上文中多次提到了代码质量,这个概念非常重要。比如一段程序,如果使用某种高效算法,最多10行就可以解决问题,但如果你不了解该算法,上来就暴力解,自以为使用了几十个if分支加上多层循环就已经涵盖了所有test case,当提交代码后才发现,原来if文还远远不够,经过你不断的调试,不断的改进,你会发现你的逻辑越发的难以理解,难以维护,即使你侥幸的通过了所有测试,这时如果让你马上重写一遍代码,你大概率还是一头雾水吧。这就是典型的低质量代码,而高质量代码的背后往往都是成型的算法逻辑,这些逻辑仿佛就是高手间的暗号,你是否属于“自己人”取决于你的代码是否是“内行话”。如果你想加入大厂的世界,掌握算法的重要性也就不言而喻。

如何刷题

刷题的关键在于你要知道该题的本质,即考官想考你什么算法,如果你不能快速的想到某一题的解题思路,那么只有两种可能:

  1. 你根本不会该类题型的解法。
  2. 你可能知道某算法,但是你没能第一时间想到使用该算法。这只能说明你对该算法的掌握还不够熟练,或者你对该算法的使用场景了解的不够全面。

遇到不会做的题目时,最好的办法就是看答案!因为无论你如何创新,你大概率不会发明出一种更优秀的新算法。记住一点,我们刷题的目的是学习算法,而不是创造算法。起初,你可能发现每一道题你都需要去谷歌一下,而更令人崩溃的是有的题目你连答案都看不懂!这会是你刷题期间遇到的第一个瓶颈,因为你刚刚进入这个圈子,很多算法和概念你都还傻傻分不清,这需要时间去慢慢积累。你可以选择每周巩固一种算法,积少成多,因为你必须相信一点,算法的数量是有限的。

接下来进入本篇文章的重点,到底哪些算法是我们必须掌握的?我们来列举一下(排名不分先后):

第一:二分查找

二分查找类型的题目在leetcode中的比重大约占据了7%左右,这类算法虽然难度不大,但是是二分的边界条件是一个经常出错的地方,下面这篇文章我们着重的分析和总结了每种二分方式下的边界条件问题。

LEETCODE常见算法之二分查找超详细白话讲解


第二:动态规划

动态规划也被称为DP,在leetcode中的比重接近15%,这类题型也是各厂面试官的最爱,如果你仍然无法熟练运用该算法进行解题,强烈建议参考下面两篇文章:

LEETCODE常见算法之动态规划DP超详细白话讲解(上)

LEETCODE常见算法之动态规划DP超详细白话讲解(下)


第三:深度优先搜索

刷题时,你会发现大量的树形结构或者图形结构题目,对于这类题目,深度优先搜索DFS算法是你的选择之一。

LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(上)

LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(下)


第四:广度优先搜索

既然提到了DFS,那么BFS也是你不得不掌握的技能,它与DFS的区别和联系有哪些?请看下文:

LEETCODE常见算法之广度优先搜索BFS超详细白话讲解


总结:

其实,你需要掌握的算法远不止上述这四种,但当你对算法有了一定的理解之后,你会发现,所有算法之间都是相通的。而刷题也是同理,当你的刷题量到达几百题时,你会发现很多题目都是相同的,只是他们的描述方式不同,或者他是某几道题的合体而已。另外记住一点,千万不要因为某种算法或者某道题目难于理解而放弃你的刷题之路,对于无法理解的题目你可以选择暂时跳过,当你的刷题量累加到一定程度之后,再回头看那些曾经认为的难题往往会迎刃而解。另外,大家应该知道一个现实,Leetcode中的算法题目实际上是相对简单的,对于很多算法竞赛高手来说,leetcode最多只能作为他们休闲娱乐的游戏,没有任何难度。因此对于我们普通码农来说,不要过于害怕刷难题,难题本身的难点并不在于算法,而在于你如何将题目转化为你能理解的范畴。

本博客今后会继续分享leetcode中最新题目的解题思路,并不定期的更新更多的算法讲解,祝大家刷题愉快!

发表在 leetcode | 标签为 , , | 留下评论

LEETCODE常见算法之动态规划DP超详细白话讲解(下)

接上文:LEETCODE常见算法之动态规划DP超详细白话讲解(上)

上一篇文章,我们使用了一道简单的例子来解释了动态规划的解题思路。本文我们来挑战一道相对复杂的问题,来对动态规划有一个更加深刻的理解。

先看例题:


LEETCODE 1312. 让字符串成为回文串的最少插入次数

给你一个字符串 s ,每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。


继续阅读
发表在 leetcode | 标签为 , , , , , | 3条评论

LEETCODE常见算法之动态规划DP超详细白话讲解(上)

动态规划是Leetcode中比较常见的一类题型,面试时也经常被问到,还记得刚开始刷题时,我对这种题目非常恐惧,经常一头雾水,完全找不到思路。甚至看了别人的讲解后依然一知半解。但随着刷题量的增加,突然发现动态规划也没有那么复杂,绝大部分的题目都是大同小异,甚至让我感觉很多Hard级别的题目中,动态规划题目是相对容易的。本篇文章,我决定用实际的例子来分析,让大家明白动态规划到底是何方神圣。

先看下动态规划的定义:

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

摘自维基百科

定义里有一句话非常关键,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。如果你无法理解这句话的含义没有关系,下面我们会用实际的例子来说明。

另外,什么题适合使用动态规划来解题呢?这是一个非常有价值的问题,虽然我还没有刷满Leetcode的全部题目,不过我还是总结出了两点心得:

继续阅读
发表在 leetcode | 标签为 , , , , , | 3条评论

LEETCODE 1363. Largest Multiple of Three 解题思路分析

题目大意:

形成三的最大倍数

给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。

由于答案可能不在整数数据类型范围内,请以字符串形式返回答案。

如果无法得到答案,请返回一个空字符串。

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE 465. Optimal Account Balancing 解题思路分析

题目大意:

有一群朋友去度假,度假期间,他们会相互借钱,比如 Alice 帮助Bill支付了他的午饭费用10美金,之后 Chris 帮助 Alice 支付了5美金的打车费。我们将每笔借款使用(x,y,z)来表示,即x借了z美金给y,假设Alice, Bill和Chris 的编号分别是0,1,2。那么上述所有的借款可以表示为 [[0, 1, 10], [2, 0, 5]]

题目会给出一群人的所有借款情况,求将所有欠款还清最少需要多少次。

注意:

  1. 每笔借款使用 (x, y, z) 的形式表示,其中x!=y, z>0。
  2. 每个人的id不一定是连续的,他们的id可能是0,1,2。也可能是0,2,6。
继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE 26. Remove Duplicates from Sorted Array 解题思路分析

题目大意:

删除排序数组中的重复项

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE 717. 1-bit and 2-bit Characters 解题思路分析

题目大意:

1比特与2比特字符

有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。

现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE 897. Increasing Order Search Tree 解题思路分析

题目大意:

递增顺序查找树

给定一个树,按中序遍历重新排列树,使树中最左边的结点现在是树的根,并且每个结点没有左子结点,只有一个右子结点。

继续阅读
发表在 leetcode | 标签为 , , , , | 留下评论

LEETCODE 350. Intersection of Two Arrays II 解题思路分析

题目大意:

两个数组的交集 II

给定两个数组,编写一个函数来计算它们的交集。

继续阅读
发表在 leetcode | 标签为 , , | 留下评论

LEETCODE 786. K-th Smallest Prime Fraction 解题思路分析

题目大意:

第 K 个最小的素数分数

一个已排序好的表 A,其包含 1 和其他一些素数.  当列表中的每一个 p<q 时,我们可以构造一个分数 p/q 。

那么第 k 个最小的分数是多少呢?  以整数数组的形式返回你的答案, 这里 answer[0] = p 且 answer[1] = q.

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE 326. Power of Three 解题思路分析

题目大意:

3的幂

给定一个整数,写一个函数来判断它是否是 3 的幂次方。

示例 1:

输入: 27
输出: true

示例 2:

输入: 0
输出: false

示例 3:

输入: 9
输出: true

示例 4:

输入: 45
输出: false

进阶:
你能不使用循环或者递归来完成本题吗?


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=326

解题思路分析:

本题是一道纯数学题目,并且题目要求不能使用递归和循环。其实在int型取值范围内,3的幂运算的结果只有21个即:3的0次幂到3的20次幂。因此,我们只要判断3的20次幂与n的余数是否为0即可。

实现代码:

public boolean isPowerOfThree(int n) {
    return n>0 && Math.pow(3, 20) % n == 0;
}

本题解法执行时间为11ms。

Runtime: 11 ms, faster than 87.46% of Java online submissions for Power of Three.

Memory Usage: 40.6 MB, less than 6.25% of Java online submissions for Power of Three.

发表在 leetcode | 标签为 , , | 留下评论

LEETCODE 725. Split Linked List in Parts 解题思路分析

题目大意:

分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1,也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出,并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例: 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论