最近舍友参加了华为软件笔试,我拿到题目后也尝试做了一下,感觉第二题十分巧妙,于是写篇博客记录一下。

题目描述

司机小王到仓库拉货。仓库管理员已经提前将货物打包装箱,并摆成一排。包装箱从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)的解法,给了我很大的启发。

这种解法的基本思路基于如下原理:

  1. 用货物 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

  1. 当多个位置 a、b、c… 满足 Sum[a]%k=Sum[b]%k=Sum[c]%k=… 时,记位置个数为 t ,在这些位置中任意挑选两个位置即可构成一个满足条件的区间,因此此时满足条件的区间个数为 C(t,2) 。

C(t,2)是数学排列组合,展开为 t*(t-1)/2 。


具体操作如下:

  1. 使用长度为 n 的数组 M 存储仓库货物数,输入完毕后另开一个长度为 n 的数组 Sum,令 Sum[i] 表示 M[0]+M[1]+…+M[i],此时 Sum[j]-Sum[i] 表示货物 i 到货物 j 的区间货物总数。

  2. 开一个长度为 k 的数组 count ,遍历 Sum 数组,对任意 0 - n 间的索引 x,使 count[Sum[x]%k]+=1。

  3. 遍历 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package main

import "fmt"

func main() {
var (
n, k int
tmp int
current int
count []int
result int
)
fmt.Scanln(&n, &k)
count = make([]int, k)
// 输入货物列表,实时累加
for i := 0; i < n; i++ {
fmt.Scan(&tmp)
current = (current + tmp) % k
count[current] += 1
}
for _, v := range count {
if v > 1 {
result += v * (v - 1) / 2
}
}
fmt.Println(result)
}