华为2021年3月10日软件笔试题第二题解析
最近舍友参加了华为软件笔试,我拿到题目后也尝试做了一下,感觉第二题十分巧妙,于是写篇博客记录一下。
题目描述
司机小王到仓库拉货。仓库管理员已经提前将货物打包装箱,并摆成一排。包装箱从1开始编号。各个包装箱存放的货物数组成一个集合M={M1, M2. …, Mn}。货车一次最多运送K件货物。为了最大化动力,小王想一次从中挑选出K的整数倍件货物,再分批运输。仓库管理员为了方便管理,要求小王必须选择编号连续的包装箱,如可选择1、2、3号箱,不能选择2、4、6号箱。
如果运输K整数倍件货物,请帮小王计算有多少种挑选方式。
输入描述
包装箱数为N,货车一次运送货物的最大数为K
各箱子存放的货物数:M1, M2, M3, M4, …
输入为二行,格式如下:
N K
MI M2 M3 M4 …
N和K的取值范围皆为[1, 100000]
第i个包装箱存放货物数的取值范围也是[1, 100000]
分析
因为是连续序列问题,所以开始我考虑使用的是滑动窗口,但分析后发现不可行。
滑动窗口的一般方法是首先扩大窗口,当出现某种情况使窗口不能满足条件时再缩小窗口。但该题不同在于:无法通过局部条件判断需要缩小窗口,即不可能因为当前窗口不满足k的整数倍就能保证继续扩大窗口后不能满足k的整数倍。
接着我又想到使用动态规划对区间求和,然后遍历判断各个区间是否符合条件。经验告诉我们这是正确的,但动态规划需要一个二维数组标记区间和,空间复杂度为O(N^2),同时需要遍历该二维数组,时间复杂度也为O(N^2),在 N 取值范围为[1,100000]的情况下,这样的复杂度是我们不能接受的。
遍历枚举?虽然降低了空间复杂度,但时间复杂度比动态规划还要高得多,更加无法接受。
遇事不决看题解,随便找了几个题解看,这篇题解给出了一种时间复杂度为O(n+k)的解法,给了我很大的启发。
这种解法的基本思路基于如下原理:
- 用货物 0-j 的和与货物 0-i 的和做差,得到的差是货物 i-j 的和,如果该和可以被 k 整除,即货物 0-j 的和模k等于货物 0-i 的和模k,则该区间满足条件。
该结论的数学表示是:
(Sum[j]-Sum[i])%k=0 => Sum[j] = n*k + Sum[i] => Sum[j]%k = Sum[i]%k
- 当多个位置 a、b、c… 满足 Sum[a]%k=Sum[b]%k=Sum[c]%k=… 时,记位置个数为 t ,在这些位置中任意挑选两个位置即可构成一个满足条件的区间,因此此时满足条件的区间个数为 C(t,2) 。
C(t,2)是数学排列组合,展开为 t*(t-1)/2 。
具体操作如下:
使用长度为 n 的数组 M 存储仓库货物数,输入完毕后另开一个长度为 n 的数组 Sum,令 Sum[i] 表示 M[0]+M[1]+…+M[i],此时 Sum[j]-Sum[i] 表示货物 i 到货物 j 的区间货物总数。
开一个长度为 k 的数组 count ,遍历 Sum 数组,对任意 0 - n 间的索引 x,使 count[Sum[x]%k]+=1。
遍历 count 数组,对任意 0 - k 间的索引 y,如果 count[y]>1,则 result = result + C(count[y],2),最后返回 result 。
在实际代码表示中,我们可以省去 M 和 Sum 数组,在输入的同时对 count 进行相关操作。这样的话,我们只需要处理 n 个输入,遍历长度为 k 的数组,时间复杂度为 O(n+k) ,同时只使用了一个长度为 k 的 count 数组,空间复杂度为 O(k) ,是该问题的最优解。
代码
我的 Golang 代码如下:
1 | package main |