导航菜单
首页 >  大厂面试真题解析  > 教你学习大厂面试算法真题解析入门到进阶

教你学习大厂面试算法真题解析入门到进阶

附Java/C/C++/机器学习/算法与数据结构/前端/安卓/Python/程序员必读书籍书单大全:

书单导航页(点击右侧 极客侠栈 即可打开个人博客):极客侠栈 ①【Java】学习之路吐血整理技术书从入门到进阶最全50+本(珍藏版) ②【算法数据结构+acm】从入门到进阶吐血整理书单50+本(珍藏版) ③【数据库】从入门到进阶必读18本技术书籍网盘吐血整理网盘(珍藏版) ④【Web前端】从HTML到JS到AJAX到HTTP从框架到全栈帮你走更少弯路(珍藏版)    ⑤【python】书最全已整理好(从入门到进阶)(珍藏版) ⑥【机器学习】+python整理技术书(从入门到进阶已经整理好)(珍藏版) ⑦【C语言】推荐书籍从入门到进阶带你走上大牛之路(珍藏版) ⑧【安卓】入门到进阶推荐书籍整理pdf书单整理(珍藏版) ⑨【架构师】之路史诗级必读书单吐血整理四个维度系列80+本书(珍藏版) ⑩【C++】吐血整理推荐书单从入门到进阶成神之路100+本(珍藏) ⑪【ios】IOS书单从入门到进阶吐血整理(珍藏版)

-------------------------------------------------------------------------------------------------------------------------------------------

如今想要收获大厂offer,在面试的前几轮,总是躲不开算法这座大山。

常听人说,算法很难。这话没错。算法本身是是一个艰深的方向。但是算法题却有据可循。通过有针对性的学习和练习,我们完全可以掌握解题的基本方法和技巧,见题拆题,扫清通往offer之路上的障碍。

看看手上这些各个大厂的面试算法真题,我想,不如开始一个新的系列,和大家一起解析真题,学习解题方法,开阔解题思路。头脑越练习,越灵光。

接下来,就让我们来看第一题:

题目

[来自Google]

Given a list of numbers and a number k, return whether any two numbers from the list add up to k

给定一组数字,以及一个数字k,确定这组数字中,是否存在任意两个数字,其相加之和等于k。

解析

初次见到一个问题,如果暂时没有什么特别清晰的思路或灵感,不妨安下心来,首先想一想这道题目的暴力解法。

简单粗暴的暴力解法不考虑效率和美观,只考虑正确性,所以往往效率较低。但是,通过观察暴力解法中冗余或者重复的部分,我们就可以找到进一步优化的切入点,想出更有效率的算法。

小技巧: 在面试中,如果暂时头脑空白,想不到漂亮的解法,不妨坦率地用简洁的话语先描述一下暴力解法,在这个过程中发现思路,找到优化解法。这个过程,也有助于面试官考察你的整体解题思路,还可能给你加分哟

暴力解法

这道题的暴力解法很简单。 只要将数组中所有数字对求和,然后和给定的数字k相比较,就知道是否有和k相等的值了。 假设数组中有n个数字,将暴力解法写成伪代码pseudo code的话,就是这个样子:

function sumEqualsToK(array, k):for i=1 to n-1 for j=i+1 to nif array[i] + array[j] == k return truereturn false

暴力解法使用了两个嵌套在一起的循环,显而易见,它的时间复杂度是O(n^2)。为了降低时间复杂度,我们来分析一下暴力解法中冗余或者重复的部分。

暴力解法试图对数组中 所有 数字对进行求和操作。 这部分操作是否存在冗余的部分呢? 我们能不能减少需要查看的数字对的数量呢? 想要对这一点进行优化,我们就要利用题目中的另一个线索,也就是数字k了。

其实这道题目就是在给元素“配对儿”。 对于数组中的任一数字array[i],如果希望它和它的“另一半”相加之和等于k,那就意味着它的“另一半”的值必须是k-array[i]。 也就是说,只要数组中也存在一个等于k-array[i]的元素,就可以满足相加等于k这个条件了:

例子:k = 10array = [ 4, 2, 5, 6, 8 ]那么我们寻找的“另一半”们就是:[ 10-4, 10-2, 10-5, 10-6, 10-8 ]也就是 [6, 8, 5, 4, 2]这样一来,我们的问题就转换成:给定数组 array = [ 4, 2, 5, 6, 8 ],以及数组 target = [ 6, 8, 5, 4, 2 ],array[i]和target[i]是不是同时存在于array中在这个例子中,大家要格外关注5这个元素5正好是k值的一半,所以array和target都包含了5只有在原数组中包含了两个5,才能相加等于10

好了,现在我们已经有了进一步优化暴力解法的思路了。 在揭晓优化解法的伪代码之前,请你先开动脑筋,试着自己把代码写出来吧

思考~思考~图片来自网络

优化解法

时间到~下面就是优化算法的伪代码了:

function sumEqualsToK(array, k):for i=1 to n if map contains array[i]return true elseput k-array[i] into mapreturn false

在优化算法中,我们使用了一个map来记录我们想要寻找的“另一半”的元素,也就是之前例子里面提到的target

接下来,我们只需要遍历array一次。 如果array[i]已经和map中的元素相符,就说明array[i]和我们之前遍历到的某一个元素恰好是相加为k的“一对儿”,算法直接返回true。 如果不相符,那么我们就把k-array[i]放进map中去,期待接下来遍历到的元素能够和k-array[i]相符。

这个优化算法只需要遍历array一次,所以它的时间复杂度只有O(n)。而我们最多也只会将array中所有元素的“另一半”放进map中去,所以算法的空间复杂度也是O(n)

实现

想出解法只是第一步,为了正确地实现解法,我们还需要考虑实现中的细节。 让我们想一想这个问题的输入和输出:

输出

这个问题的输出很简单,就是一个boolean值,true/false

输入

题目中对于输入的表达较为模糊 没有说明array的长度,也没有说明元素和k的具体类型 格外要注意的是,由于在解题过程中需要进行求和操作,我们要谨慎选择在实现中使用的变量类型。两数之和的范围可能远远大于单一数字的范围,所以根据实现语言的不同,要小心避免求和操作造成溢出

小技巧:在面试中,遇到题目中比较模糊的描述,一定记得要和面试官沟通,以便得到

相关推荐: