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


(xmnz) #1

讲座嘉宾:Steve

讲座链接:ACM大神精讲最新北美面试题 第三讲

讲座总结:6Kunnnnn

题目1 Inventory is Full

题目介绍

这道题类似于经典的背包问题,每种宝藏除了总数量和单位价值外,还有每个Slot能存下的最大数量,如下图:

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

题目分析

直接暴力解法,枚举出所有的可能性,然后看哪种宝藏组合的价值最大,但显然,这种解法过于耗时。进一步分析,如果我们想要背包的价值最大化,我们需要尽可能的多放进宝物。也就是说,若某个Slot里面的宝藏M没有装满,且M有足够剩余的数量,那我们应当继续用这个宝藏装满这个Slot,否则这个Slot就没有被最大的利用。那么近一步来讲,如果想要某个宝藏没有剩余,对于那些装这个宝藏的Slot们,要么这些Slot都满,要么宝藏不足以装满其中的一个但仅限于一个Slot,也就是最多存在一个不满的格子

所以,我们可以分为两种情况来考虑。第一,根据A求出一个宝藏需要至少需要多少个Slot才能装满,也就是Ai除以Si并向上取整,这时候每个Slot的价值都是Pi * Si;第二,这些Slot数量中,判断是否存在一个Slot装不满的情况,如果有,这个Slot的价值就由Pi * Si变成了 Pi * (Ai mod Si)。比如,某个宝藏,N=10 A=10 P=2 S=3,那么有3个Slot能装满该宝藏,每个价值为6,有一个格子只能装10 % 3 = 1个宝藏,价值为2 * 1 = 2。如下图:

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

那么,根据这个思路,我们完全可以遍历所有宝藏,求出每一个宝藏的Slot价值的两种情况,然后根据这些价值排序,再进一步遍历,从大到小选择,直到N个Slot被装满了为止。可以看出,这是一种贪心算法,也就是每一步都选择最大值。复杂度主要是排序的复杂度,如下图:

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

代码实现

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

思路补充

这道题目类似于经典背包问题,但是区别是没有考虑宝藏的weight,所以这个简化的weight为1的问题可以直接用greedy算法。而DP适用于weight不为常熟的情况,但并不适用这道题。

题目2 Total Hamming Distance

题目介绍

Input就是N个整数,output就是这些整数两两之间,用位表达后每一位上不相同的值的个数的最终求和,也就是对于位的汉明距离求和。(注:广义的汉明距离就是指两个变量之间,每个对应位置之间值的差异,不过这道题定义为值不相同的个数。)

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

题目分析

暴力算法的话,对于任意一对Ai和Aj,找出它们的汉明距离,然后将所有组合的汉明距离相加求和,但是过于费时,只适用于数据量小的情况。进一步分析,对于找出某位上值不相等的位运算,可以用异或xor来计算,也就是位相同为0,不同为1。此外,这道题目我们可以不从单个的Ai和Aj的组合来考虑,而是从所有数字A的位来考虑(从column而不是row考虑)。因为求和只需考虑1的情况,所以如果按照位来计算,对于所有数字A,他们的每一位k求出0和1的数量分别为B0(k)和B1(k)的话,不同的位的总数量就是B0(k) * B1(k)个,具体分析例子如下图:

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

复杂度的话,input的值域最大为M,那么对于任意的A,最多有logM位,而对于每一位,需要遍历每个整数在此位置的0和1的个数,总共有N次操作,所以整体的复杂度就是O(N * logM),具体如下图:

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

代码实现

**

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

思路补充

对于这种binary表达的题目,往往都可以用到Bit操作来解决,而此题目特殊之处在于,Bit操作中,每一位之间没有影响,所以我们可以直接按照每一位来单独处理。而且,题目的汉明距离求和,也是类似于积分Integration的概念,我们往往可以用预先处理的方法来减少计算复杂度,比如上边的解法中,首先找出0和1的数量的乘积就是预先处理中间结果,这样能减少之后最终求和的复杂度。希望大家能够理解这些技巧,做到熟练掌握。

题目3 Target Sum

题目介绍

**

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

题目分析

首先,暴力解法的话,需要枚举各种可能,每一个数字前的正负号分两种情况,那么暴力解法的时间复杂度就是O(2^N),只能解决N比较小的情况。

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

进一步分析的话,如果从等式左边的最右边开始思考可以发现,对于最后的数字,我们不需要考虑之前的数字的正负号情况,只需要考虑从1到N-1的这些数字的和为多少即可。换句话说,如果前边的数字,无论如何改变他们的正负号,只要他们的和一定,就可以认定他们的状态一致,而我们更关心的是他们是什么状态。比如说,如下图,最后一位是1,Sum为3,前边4个1,无论正负号如何变,只要和为4或者2即可满足条件,也就是状态4和状态2是成立的,其他的状态均不成立。所以我们可以进一步的归纳,对于位置i的数字,前边的1到i-1的数字的正负号不重要,重要的是前边这些数字的和有哪些状态,值分别为多少,以及哪些状态是成立的

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

现在进一步将上边的思路形式化,对于第N个数字An,和这个数字需要求和的S,用 f(N, S) 来表示满足条件的状态个数。这个问题可以拆分成为两个子问题,就是找到前N-1个数求和后分别为S - An 和 S + An的状态的个数,即An为+和-的情况,按照f(N, S) 的定义递归,也就分别是 f(N-1, S - An) 和 f(N-1, S + An),如下图。然而,可能出现子问题中间出现overlap的情况,为了避免重复计算,需要额外的空间来保存计算的中间结果也就是 f(N, S)的值。这样的解法就是memorized search,计划搜索,类似于DP,利用额外的空间来存储中间过程避免重复运算,而且考虑了无后效性 non after effect,就是之前所做的决策并不重要,重要的是最终的状态是什么。但不同的是不需要像DP一样做中间的决策(虽然这道题目还是可以用DP来解决)。时间和空间的复杂的分别为N * S。

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

代码实现

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

非递归的方法如下图,其中**-MAXM和MAXM分别为所有数字符号为负和正的情况下的最值**,也就是把所有数字为负加起来的和,或者所有数字为正数加起来的和。

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

算法优化

进一步优化的话,当S很大的时候,可以利用滚动数组来减少空间复杂度,具体的讲解可以观看原视频。

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

太阁近期课程:

DS203 UBER用户数据分析实战训练营

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

DS103 DATA ANALYTICS 系列课程:TABLEAU 基础及职场应用

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

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

知乎专栏:太阁实验室

微博:@太阁BitTiger

今日头条:太阁BitTiger