1.前言

2021年春招，参加的3.10机试，三道题600分A了540分，第二道对了70%，其它全对。
第二题主要是没有优化算法，复杂度为O(n^2)，结果超时了，睡了一觉之后，才理清思路，然后这篇文章也是主要讲下第二题思路。

2.题目

自己没有截屏，用的牛客网中的题目。水印也是别人的，没办法。

（1）图片版

（2）文字版

感觉看图片过于眼疼，碰巧在牛客网找到有人发了文字版的，就顺手牵羊了。

1.小明抽到字符串，小红抽到一个更长的，小红有限次的替换一个字母为另一个，比如最大替换次数为2
请判断小红每次游戏时候能不能成功替换字母从而包含小明的字符串，可以请输出最小替换次数，不可以或者不需要替换输出0；
输入三行：第一行小明的字符串
第二行小红的字符串（长一些）
第三行是最大允许替换次数

2.一排包装箱从1编号，各个包装箱存放的货物数组成一个集合M={M1,M2,…,Mn}
货车一次最多运送K件货物
小王想一次从中挑选K的整数倍件货物，再分批运输。
仓库管理员为了方便要求小王必须选择连续的包装箱，比如可选择1、2、3号箱，不能选2、4、6
如果运输K整数倍件货物，请帮小王计算有多少种挑选方式
输入：
包装箱数N，货车最大一次运送的数量为K件
各个箱子存放的货物M1，M2，M3。。。
输入为两行：N K
M1 M2 M3。。。
N和K取值范围为[1,100000]
第i个包装箱存放货物的取值范围也是[1,100000]
输出：一行输出有多少种方式，如果不存在可行的方式，输出0

3.N个广播站，站点之间有些有连接，有些没有。有连接的站点在接受到广播后会互相发送。给定一个N*N的二维数组matrix,
数组的元素都是字符’0’或者’1’。matrix[i][j]=‘1’,则代表i和j站点之间有连接，matrix[i][j] = '0’代表没连接，
现在要发一条广播，问初始最少给几个广播站发送，才能保证所有的广播站都收到消息
输入：一行数据代表二维数组的各行，用逗号分隔。保证每个字符串所含的字符数一样
比如：110,110，001
输出：返回初始最少需要发送广播站个数

3.解析

（1）字母替换

暴力法OC，这道题在leetcode貌似有类似的。第一次没考虑超过允许替换字符串的限制，只通过90%，后面加了个判断就行。

（2）挑选货物

1.暴力法

这道题我开始是暴力法做的，通过计算i,j之间的数值之和，看能否被K整除得到，但是这样子算法复杂度为O(n^2)，而N的范围过万，这是行不通的，使用二维的动态规划也是同样的道理，这样不但时间复杂度高，而且空间复杂度也高。

2.改进法

睡觉的时候在思考这个问题，后面想出了一个合适的算法。

1.首先我先下个定义，假设sum[i]表示从0到i的货物数量之和，那么从a到b的货物之和就可以表示为sum[b]-sum[a]。

2.这里可以做个优化，对sum[i]进行%K处理，这样就可以避免累加的数值过大，超过界限。

3.接下来，我们就只需要统计0-N-1货物中相同sum[i]的个数即可。如果存在sum[a]=sum[b]，表明存在一个可行方案。

4.这就意味题目变成组合数问题，如果有n个相同点，那么就是n(n-1)/2，其中这里我指的相同点是说sum[a]=sum[b]=sum[c]=p，而且这个p最多为K个，也就是我们只要遍历K次即可。

5.复杂度分析：读取数字的时候进行累加运算，复杂度为O(N)，后面统计K次的组合数问题，因此最终算法复杂度为O(N+K)。

算法实现：

（1）数据读取。读取数字的时候进行加工处理。读取第i个数，假设为c。那么sum[i]=(sum[i-1]+c)%K。假设i为0的时候，sum[0]=c。此处循环N次。并且开始的时候准备个a[K]的数组，初始值为0，用于记录相同值的个数，假设sum[i]=k，那么a[k]++，表示等于k的值加1。

（2）数据计算。根据a[K]，我们循环K次，把每次a[i]中的值，以n(n-1)/2的方式加进最后的返回值ret。当然这个ret初始值为0

纠正：这里没考虑a[0]的特殊性，所以a[0]要加1。

（3）输出结果。

参考代码：

#include <stdlib.h>
#include <stdio.h>


#define LEN 100001
int main()
{
	int sum[LEN] = {0};
	int a[LEN] = { 0 };
	int m;
	int N, K;
	int ret = 0;
	scanf("%d%d", &N, &K);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &m);
		if (i == 0)
			sum[0] = m % K;
		else
			sum[i] = (sum[i - 1] + m) % K;
		a[sum[i]]++;
	}
	a[0]++;
	//有位大佬提醒这里还要进行加1处理，因为考虑当sum[i]=0时，是不需要取两数相减的。
	for (int i = 0; i < K; i++)
	{
		ret = ret + a[i] * (a[i] - 1) / 2;
	}
	printf("%dn", ret);
	return 0;
}

（3）发广播

bfs+染色，复杂度目测是O(V+E)。尴尬的是我在写的时候喜欢把函数写成dfs（明明不是），希望面试官不看笔试吧，又不然真的有点尴尬。

4.后序

以后有时间的时候再补充下代码和图片，最近只能先记录下自己的思路，如果有错也可以告诉我更正。

题目难度系数不高，但我是真的考的时候没想到，呜呜呜！！！！

最后

以上就是务实秋天为你收集整理的华为春招机试2021（第二题：挑选货物）1.前言2.题目3.解析4.后序的全部内容，希望文章能够帮你解决华为春招机试2021（第二题：挑选货物）1.前言2.题目3.解析4.后序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。