讲座总结|ACM大神精讲最新北美面试题2


(humidity) #1

讲座嘉宾:Steve

讲座链接:【公开课】ACM大神精讲最新北美面试题 第二讲

讲座总结:6Kunnnnn

题目1 The latest time

题目介绍

![](data:image/svg+xml;utf8,)

给定四个数ABCD,组成时间HH:MM,找到最晚的合法时间。

题目分析

这道题目很简单,我们只需要暴力枚举所有可能性,并检查是否合法,然后找出最晚的时间。这样的算法复杂度为常数,如下图:

![](data:image/svg+xml;utf8,)

代码实现

![](data:image/svg+xml;utf8,)

作者注:其实仅对此题而言,有其他的代码实现方式,比如从小时位开始,依次找到最大的合法的值,类似于贪心算法。

算法优化

上边的方法需要4个for循环,因为要求的时间有4位,但如果题目扩展一下,判断HH:MM:SS或者更多位,这个方法就需要更多的外部for循环,很不灵活。那么如何让代码变得更加extendable?有一种方法就是DFS,深度优先查询。如下图,用used数组来记录第n位是否被访问过,update函数用来更新最大的时间,关键点是当DFS递归完之后,需要回溯,也就是把第i位的元素变成没被访问过。

![](data:image/svg+xml;utf8,)

题目2 Smallest Subarray

题目介绍

给定一个数组A,找到A的某个sub array B,满足条件:B升序排序后,A能成为一个升序排序的数组。求解这样的B数组的最小长度是多少,如下图:

![](data:image/svg+xml;utf8,)

题目分析

最直接的方法就是暴力解法,枚举所有可能的B的情况,然后判断B是否满足条件,若满足记录下B的长度,直到找到B的最短长度为止。但是该方法会很费事,枚举可能的情况就有N方种可能,思路和复杂度如下图:

![](data:image/svg+xml;utf8,)

现在我们进一步分析。假设最小的sub array B为A[L, R],那么B的长度就是R-L+1。根据题目,如果只有在将B排序之后,A才是排序好的话,必须满足B的前部分和后部分在原始的A当中,已经是排序好了的。否则,即便排序了B,B的前半部分或者后半部分如果不是已经排序完成的,A也不可能是排序好的结果。所以,把A从头到尾排序好后,记为A’,则A[1, L-1]和A’[1, L-1]是一致的(也就是在A中已经排好序),同理A[R+1, N]和A’[R+1, N]也是一致的,如下图:

![](data:image/svg+xml;utf8,)

所以可以先排序,然后分别找出A和A’中[1, L-1]和[R+1, N]两部分,也就是分别找到第一个不满足A[L] = A’[L],和不满足A[R] = A’[R]条件的位置,L、R就分别是B的开始和起始位置。此算法的复杂度就是排序A的复杂度+遍历排序后A的复杂度,如下图:

![](data:image/svg+xml;utf8,)

代码实现

![](data:image/svg+xml;utf8,)

作者注:这里的b就是A’,也就是排序好的A数组。

算法优化

(注:下一段为更新内容,原文章有歧义,已按照@张恒 的评论改正)

上一个解法我们进行了排序,但可不可以不进行排序就解决这道题目?现在进一步分析,将B排序后A成为了一个升序数组,但对于原数组A中不属于B的区间,即那些保持位置不变的元素必然满足大于**左边的最大值,否则需要往前移,以及小于右边的最小值,**否则需要往后移。根据这个性质,我们可以分别用两个数组B、C记录某个位置i左边的最大值和右边的最小值,然后i从开始到N遍历A,找到A中哪些元素是排序后没有改变位置的。这个方法也是贪心解法,创建B和C的复杂度为O(N),之后从头开始遍历A复杂度为O(N),每次比较A、B和C的关系是O(1),所以复杂度为O(N),如下图:

![](data:image/svg+xml;utf8,)

题目3 Powers of Two

题目介绍

给定一个数字N,在所有能用2的次方以及+/-表达的式子中,找到2^n的系数kn相加值最小的情况。比如说7的上述两种表示方法,第一种3个系数为1相加为3,第二个2个系数为1和-1,取绝对值后相加为2,第二种情况更好。

![](data:image/svg+xml;utf8,)

这是一道很有难度的题目,欢迎各位去观看原视频内容!

太阁近期课程:

CS103 高频系统设计面试题精讲

CS202 BIG DATA ENGINEER 实战训练营

CS207 无人驾驶深度学习训练营

CS205 UBER车辆监控系统设计实战训练营

CS501 硅谷程序员直通车(第二期)

更多精彩,尽在硅谷高端线上教育社区BitTiger:请猛戳我

公众号:论码农的自我修养

知乎专栏:太阁实验室

微博:@太阁BitTiger

今日头条:太阁BitTiger