前不久春招也算是圆满结束咯，大家有拿到心仪的 offer吗？接下来互联网的秋招也快来啦，小伙伴们有开始准备了吗？本次给大家带来24届秋招阿里系的笔试题目三语言解析(Java/Python/Cpp)
文末有清隆学长的笔试陪伴打卡小屋活动介绍:
丰富的打卡奖励等你来领哦，大厂笔试题汇总，笔试面试经验贴，算法笔试模版....
有兴趣的小伙伴们也可以了解一下，不要错过啦~
01.LYA 的魔法宝石
问题描述
LYA 是一位热爱收藏魔法宝石的女孩。她希望收集颗宝石，并且要求这些宝石的魔法值两两不相等。此外，所有宝石的魔法值的最大公约数必须为。
为了尽可能节省购买成本，LYA 希望选择魔法值之和最小的宝石组合。请你帮助 LYA 计算并输出宝石魔法值之和的最小值。
输入格式
输入包含两个正整数和，分别表示宝石的数量和魔法值的最大公约数。
输出格式
输出一个正整数，表示满足条件的宝石魔法值之和的最小值。
样例输入
3 2样例输出
12数据范围
题解
本题可以通过构造法来解决。为了让宝石的魔法值之和最小，我们可以将魔法值构造为的倍数，并且按照从小到大的顺序选择。
具体步骤如下：
初始化结果变量为，表示宝石魔法值之和。
从到遍历每个宝石：
计算当前宝石的魔法值。
将累加到结果变量中。
输出结果变量的值。
时间复杂度：，其中为宝石的数量。空间复杂度：。
参考代码
Python
n, k = map(int, input().split())
res =0
foriinrange(1, n +1):
temp = i * k
res += temp
print(res)Java
importjava.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner in =newScanner(System.in);
intn = in.nextInt();
intk = in.nextInt();
longres =0;
for(inti =1; i <= n; i++) {
longtemp = i * k;
res += temp;
}
System.out.println(res);
}
}Cpp
#include<iostream>
usingnamespacestd;
intmain(){
intn, k;
cin>> n >> k;
longlongres =0;
for(inti =1; i <= n; i++) {
longlongtemp = i * k;
res += temp;
}
cout<< res <<endl;
return0;
}02.卢小姐的布料选购计划
问题描述
卢小姐是一位服装设计师,她计划从一家面料商那里购买一段布料用于设计新款连衣裙。商家提供了一卷总长为米的布料,但其中只有某些区间的布料质地符合要求。
商家允许卢小姐从这卷布料中选择一段长度为米的连续区间购买。卢小姐希望在选定的区间内,符合要求的布料段总长度尽可能长。请你帮助卢小姐计算,最优方案下可以购得多少米符合要求的布料。
输入格式
第一行输入三个正整数,分别代表布卷的总长度、布卷上符合要求的布料段数量以及卢小姐计划购买的布料长度。
接下来的行,每行输入两个正整数,表示第段符合要求的布料的起始位置和终止位置(单位:米)。
输出格式
输出一个整数,表示最优方案下可以购得的符合要求的布料总长度。
样例输入
10 3 6
1 3
4 5
7 9样例输出
4数据范围
符合要求的布料段之间互不重叠。
题解
本题可以使用双指针滑动窗口的方法求解。我们可以枚举购买布料的左端点,并维护一个右端点,使得当前窗口内的布料长度不超过。在枚举过程中,我们统计窗口内符合要求的布料段长度之和,并更新答案。
具体步骤如下:
将所有符合要求的布料段按照起始位置从小到大排序。
初始化左右指针和,表示当前枚举的区间范围。
遍历布料段,将右指针不断右移,直到当前区间长度超过或遍历完所有布料段。
统计当前区间内符合要求的布料段长度之和,更新答案。
如果右指针已经到达最后一个布料段,直接更新答案;否则,计算当前区间右端点与下一个布料段左端点之间的空白部分长度,更新答案为
将左指针右移一个布料段,同时将减去对应的布料段长度,继续枚举下一个区间。
时间复杂度为,其中排序的时间复杂度为,双指针遍历的时间复杂度为。空间复杂度为。
参考代码
Python
classSolution:
defmaxCoverLength(self, n: int, m: int, k: int, segments: List[List[int]])-> int:
segments.sort()
ans = cover =0
left = right =0
whileright < m:
whileright < mandsegments[right][1] - segments[left][0] <= k:
cover += segments[right][1] - segments[right][0]
right +=1
ifright == m:
ans = max(ans, cover)
else:
remain = max(0, segments[left][0] + k - segments[right][0])
ans = max(ans, cover + remain)
cover -= segments[left][1] - segments[left][0]
left +=1
returnansJava
classSolution{
publicintmaxCoverLength(intn,intm,intk,int[][] segments){
Arrays.sort(segments, (a, b) -> a[0] - b[0]);
intans =0, cover =0;
intleft =0, right =0;
while(right < m) {
while(right < m && segments[right][1] - segments[left][0] <= k) {
cover += segments[right][1] - segments[right][0];
right++;
}
if(right == m) {
ans = Math.max(ans, cover);
}else{
intremain = Math.max(0, segments[left][0] + k - segments[right][0]);
ans = Math.max(ans, cover + remain);
}
cover -= segments[left][1] - segments[left][0];
left++;
}
returnans;
}
}Cpp
classSolution{
public:
intmaxCoverLength(intn,intm,intk,vector<vector<int>>& segments){
sort(segments.begin(), segments.end());
intans =0, cover =0;
intleft =0, right =0;
while(right < m) {
while(right < m && segments[right][1] - segments[left][0] <= k) {
cover += segments[right][1] - segments[right][0];
right++;
}
if(right == m) {
ans = max(ans, cover);
}else{
intremain = max(0, segments[left][0] + k - segments[right][0]);
ans = max(ans, cover + remain);
}
cover -= segments[left][1] - segments[left][0];
left++;
}
returnans;
}
};03.LYA 的珍珠项链
问题描述
LYA 有一条由颗不同颜色珍珠串成的项链。她想通过改变其中某一颗珍珠的颜色来提升项链的美观度。根据专家的建议，项链的美观度等于任意连续的珍珠子串中，各颜色出现次数的最大值。
现在给定项链上每颗珍珠的颜色，以及 LYA 可以将某颗珍珠改变成的目标颜色，请你计算改变后项链的最大美观度是多少？
输入格式
第一行包含一个正整数，表示项链的条数。
接下来对于每条项链，第一行包含两个正整数和，分别表示项链的长度和目标颜色。第二行包含个正整数，表示初始时项链上每颗珍珠的颜色。
输出格式
对于每条项链，输出一行一个整数，表示改变后项链的最大美观度。
样例输入
3
5 10
5 -1 -5 -3 2
2 -3
-5 -2
6 10
4 -2 -11 -1 4 -1样例输出
15
-2
15数据范围
所有项链的总长度不超过
题解
本题可以使用动态规划求解。设表示不改变第颗珍珠颜色的最大美观度，表示将第颗珍珠改变为目标颜色的最大美观度。则有以下状态转移方程：
最终答案为。
时间复杂度，空间复杂度。
参考代码
Python
t = int(input())
for_inrange(t):
n, c = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0] *2for_inrange(n)]
dp[0][0] = a[0]
dp[0][1] = c
res = max(dp[0])
foriinrange(1, n):
dp[i][0] = max(dp[i-1][0] + a[i], a[i])
dp[i][1] = max(dp[i-1][0] + c, c, dp[i-1][1] + a[i], a[i])
res = max(res, dp[i][0], dp[i][1])
print(res)Java
importjava.util.*;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc =newScanner(System.in);
intt = sc.nextInt();
while(t-- >0) {
intn = sc.nextInt(), c = sc.nextInt();
int[] a =newint[n];
for(inti =0; i < n; i++) {
a[i] = sc.nextInt();
}
System.out.println(maxBeauty(a, c));
}
}
privatestaticlongmaxBeauty(int[] a,intc){
intn = a.length;
long[][] dp =newlong[n][2];
dp[0][0] = a[0];
dp[0][1] = c;
longres = Math.max(dp[0][0], dp[0][1]);
for(inti =1; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0] + a[i], a[i]);
dp[i][1] = Math.max(Math.max(dp[i-1][0] + c, c),
Math.max(dp[i-1][1] + a[i], a[i]));
res = Math.max(res, Math.max(dp[i][0], dp[i][1]));
}
returnres;
}
}Cpp
#include<iostream>
#include<vector>
usingnamespacestd;
longmaxBeauty(vector<int>& a,intc){
intn = a.size();
vector<vector<long>>dp(n,vector<long>(2));
dp[0][0] = a[0];
dp[0][1] = c;
longres = max(dp[0][0], dp[0][1]);
for(inti =1; i < n; i++) {
dp[i][0] = max(dp[i-1][0] + a[i], (long)a[i]);
dp[i][1] = max(max(dp[i-1][0] + c, (long)c),
max(dp[i-1][1] + a[i], (long)a[i]));
res = max(res, max(dp[i][0], dp[i][1]));
}
returnres;
}
intmain(){
intt;
cin>> t;
while(t--) {
intn, c;
cin>> n >> c;
vector<int>a(n);
for(inti =0; i < n; i++) {
cin>> a[i];
}
cout<< maxBeauty(a, c) <<endl;
}
return0;
}