amtoaer

晓风残月

叹息似的渺茫,你仍要保存着那真!
github
x
telegram
steam
nintendo switch
email

華為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) 的解法,给了我很大的启发。

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

  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 代码如下:

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)
}
載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。