2024-阿里系列笔试题02-三语言题解(Java/Cpp/Python)

时间：2024-06-17 10:47:45 作者：字数：10299字

本次给大家带来24届秋招阿里系的笔试题目三语言解析(Java/Python/Cpp)

文末有清隆学长的笔试陪伴打卡小屋活动介绍:

丰富的打卡奖励等你来领哦，大厂笔试题汇总，笔试面试经验贴，算法笔试模版....

有兴趣的小伙伴们也可以了解一下，不要错过啦~

01.K小姐的魔药配方

问题描述

K小姐是一位魔药大师，她有种魔药材料。每种材料都包含一定比例的稀有元素和普通元素。第种材料中，稀有元素的比例为，普通元素的比例为。

K小姐想要配制一种魔药，要求稀有元素的比例不低于。她可以选择任意多种材料，将它们混合在一起。

请问，K小姐最多可以配制出多少份这样的魔药？

输入格式

第一行包含一个正整数（），表示材料的种类数。

第二行包含个整数（），表示每种材料中稀有元素的比例。

第三行包含个整数（），表示每种材料中普通元素的比例。

保证对于每种材料，有。

输出格式

输出一个整数，表示K小姐最多可以配制出的魔药份数。

样例输入

3
50 60 30
50 40 70

样例输出

数据范围

题解

我们可以先将材料按照稀有元素的比例从高到低排序。然后从前往后选择材料，直到选择的材料中稀有元素的总比例不再大于等于。

设前种材料中，稀有元素的总比例为，普通元素的总比例为。如果，那么前种材料就可以用来配制魔药。

我们可以用贪心的思想来证明这一做法的正确性。对于当前选择的材料，如果替换成任何一种未选择的材料，那么稀有元素的总比例一定会下降，因为未选择的材料的稀有元素比例一定小于等于当前材料。因此，我们的选择方案是最优的。

时间复杂度为，空间复杂度为。

参考代码

Python

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
materials = sorted(zip(a, b), reverse=True)
sum_a = sum_b =0
ans =0
forx, yinmaterials:
ifsum_a + x >= sum_b + y:
sum_a += x
sum_b += y
ans += x
else:
break
print(ans)

Java

importjava.util.*;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc =newScanner(System.in);
intn = sc.nextInt();
int[] a =newint[n];
int[] b =newint[n];
for(inti =0; i < n; i++) {
a[i] = sc.nextInt();
}
for(inti =0; i < n; i++) {
b[i] = sc.nextInt();
}
int[][] materials =newint[n][2];
for(inti =0; i < n; i++) {
materials[i] =newint[]{a[i], b[i]};
}
Arrays.sort(materials, (x, y) -> y[0] - x[0]);
intsumA =0, sumB =0;
intans =0;
for(int[] m : materials) {
if(sumA + m[0] >= sumB + m[1]) {
sumA += m[0];
sumB += m[1];
ans += m[0];
}else{
break;
}
}
System.out.println(ans);
}
}

#include<iostream>
#include<algorithm>
usingnamespacestd;
constintN =1e5+10;
inta[N], b[N];
intmain(){
intn;
cin>> n;
for(inti =0; i < n; i++) {
cin>> a[i];
}
for(inti =0; i < n; i++) {
cin>> b[i];
}
vector<pair<int,int>> materials;
for(inti =0; i < n; i++) {
materials.emplace_back(a[i], b[i]);
}
sort(materials.begin(), materials.end(), greater<pair<int,int>>());
intsumA =0, sumB =0;
intans =0;
for(auto& m : materials) {
if(sumA + m.first >= sumB + m.second) {
sumA += m.first;
sumB += m.second;
ans += m.first;
}else{
break;
}
}
cout<< ans <<endl;
return0;
}

️ 02.K小姐的魔法阵

问题描述

K小姐在探索一座神秘的魔法塔时，发现了一个奇特的魔法阵。这个魔法阵由个魔法石组成，每个魔法石上都刻有一个正整数。然而，由于年代久远，魔法阵上的数字已经变得模糊不清。

K小姐凭借自己的魔法知识，了解到这个魔法阵的数字排列满足以下规律：如果将魔法石上的数字按顺序排列成一个序列，那么对于任意的，都有。

现在，K小姐希望你能帮助她还原这个神秘的魔法阵。

输入格式

输入只包含一个正整数（），表示魔法阵中魔法石的数量。

输出格式

如果能够还原出符合条件的魔法阵，则输出一行，包含个正整数，表示还原后的魔法阵中每个魔法石上的数字。如果有多个可能的解，输出任意一个即可。

如果无法还原出符合条件的魔法阵，则输出一行，包含一个整数。

样例输入

样例输出

2 5 3 1 4

数据范围

题解

我们可以根据给定的规律，直接构造出符合条件的魔法阵。

首先，我们可以发现，如果为的倍数或者的倍数加，那么就一定存在符合条件的魔法阵。否则，无法构造出符合条件的魔法阵。

对于为的倍数或者的倍数加的情况，我们可以按照以下方式构造魔法阵：

对于为奇数且，令，。
对于为奇数且，令，。
如果为奇数，令。

按照上述方式构造出的序列即为符合条件的魔法阵。

时间复杂度为，空间复杂度为。

参考代码

Python

n = int(input())
a = [0] * (n +1)
ifn %4==0orn %4==1:
foriinrange(1, n //2+1,2):
a[i] = i +1
a[i +1] = n - i +1
a[n - i +1] = n - i
a[n - i] = i
ifn %2!=0:
a[n //2+1] = n //2+1
print(' '.join(map(str, a[1:])))
else:
print(-1)

Java

importjava.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc =newScanner(System.in);
intn = sc.nextInt();
int[] a =newint[n +1];
if(n %4==0|| n %4==1) {
for(inti =1; i <= n /2; i +=2) {
a[i] = i +1;
a[i +1] = n - i +1;
a[n - i +1] = n - i;
a[n - i] = i;
}
if(n %2!=0) {
a[n /2+1] = n /2+1;
}
for(inti =1; i <= n; i++) {
System.out.print(a[i] +" ");
}
}else{
System.out.println(-1);
}
}
}

#include<iostream>
usingnamespacestd;
constintN =1e5+10;
inta[N];
intmain(){
intn;
cin>> n;
if(n %4==0|| n %4==1) {
for(inti =1; i <= n /2; i +=2) {
a[i] = i +1;
a[i +1] = n - i +1;
a[n - i +1] = n - i;
a[n - i] = i;
}
if(n %2!=0) {
a[n /2+1] = n /2+1;
}
for(inti =1; i <= n; i++) {
cout<< a[i] <<" ";
}
}else{
cout<<-1<<endl;
}
return0;
}

03.K小姐的魔法咒语

问题描述

K小姐是一位强大的魔法师，她掌握了许多神奇的魔法咒语。这些咒语都是由小写字母组成的字符串。

在这些咒语中，有一类特殊的咒语，它们满足以下条件：在咒语中，有且仅有一种字母出现了偶数次，其余字母都出现了奇数次。

现在，K小姐想知道，给定一个字符串，它的子序列中有多少个是特殊咒语。注意，子序列可以不连续，但必须保持原有的相对顺序。

答案可能很大，请对取模。

输入格式

输入一个由小写字母组成的字符串，长度不超过。

输出格式

输出一个整数，表示特殊咒语的数量，答案需要对取模。

样例输入

abccc

样例输出

数据范围

字符串长度不超过。

题解

我们可以用组合数学的方法来解决这个问题。

对于每一种字母，我们统计它在字符串中出现的次数。如果某个字母出现了至少两次，那么我们可以选择其中的两个位置，组成一个特殊咒语的子序列。

设第种字母出现了次，那么我们可以从中选择个位置的方案数为。

对于其他字母，我们可以选择是否将它们包含在子序列中。如果包含，就选择它们出现的所有位置；如果不包含，就一个位置也不选。因此，对于每种其他字母，我们有种选择方案。

但是，我们需要排除掉同时选择两个位置的情况，因为那样就不是特殊咒语了。排除的方案数为。

因此，对于每种出现至少两次的字母，它对答案的贡献为：

我们将所有的贡献相加，就得到了最终的答案。

时间复杂度为，空间复杂度为。其中为字符串长度。

参考代码

Python

mod =10**9+7
c = [[0]*3for_inrange(200010)]
sums = [0]*27
counts = [0]*27
definit():
foriinrange(2,200010):
c[i][2] = i * (i -1) //2% mod
defget_res(x):
res =1
foriinrange(1,27):
ifx != i:
res = (res * sums[i]) % mod
returnres
defqmi(a, b, mod):
res =1
whileb:
ifb &1:
res = (res * a) % mod
a = (a * a) % mod
b >>=1
returnres
if__name__ =="__main__":
s = input()
foriins:
counts[ord(i) - ord('a') +1] +=1
init()
foriinrange(1,27):
sums[i] = ((qmi(2, counts[i], mod)) % mod - c[counts[i]][2] + mod) % mod
res =0
foriinrange(1,27):
ifcounts[i] >=2:
res = (res + c[counts[i]][2] * get_res(i) % mod) % mod
print(res)

Java

importjava.util.Scanner;
publicclassMain{
staticlong[][] c =newlong[200010][3];
staticlong[] sums =newlong[27];
staticlongmod = (long)1e9+7;
staticlong[] counts =newlong[27];
staticvoidinit(){
for(inti =2; i <200010; i++) {
c[i][2] = (long) i * (i -1) /2% mod;
}
}
staticlonggetRes(intx){
longres =1;
for(inti =1; i <=26; i++) {
if(x != i) {
res = (res * sums[i]) % mod;
}
}
returnres;
}
staticlongqmi(longa,longb,longmod){
longres =1;
while(b >0) {
if((b &1) ==1) res = (res * a) % mod;
a = (a * a) % mod;
b >>=1;
}
returnres;
}
publicstaticvoidmain(String[] args){
Scanner scanner =newScanner(System.in);
String s = scanner.next();
for(inti =0; i < s.length(); i++) {
counts[s.charAt(i) -'a'+1]++;
}
init();
for(inti =1; i <=26; i++) {
sums[i] = ((qmi(2, counts[i], mod)) % mod - c[(int) counts[i]][2] + mod) % mod;
}
longres =0;
for(inti =1; i <=26; i++) {
if(counts[i] >=2) {
res = (res + c[(int) counts[i]][2] * getRes(i) % mod) % mod;
}
}
System.out.println(res);
scanner.close();
}
}

#include<iostream>
usingnamespacestd;
longlongc[200010][3];
longlongsums[27], mod =1000000007, counts[27];
strings;
voidinit(){
for(inti =2; i <200010; i++) {
c[i][2] = ((longlong)i * (i -1) /2) % mod;
}
}
longlonggetRes(intx){
longlongres =1;
for(inti =1; i <=26; i++) {
if(x != i) {
res = (res * sums[i]) % mod;
}
}
returnres;
}
longlongqmi(longlonga,longlongb,longlongmod){
longlongres =1;
while(b) {
if(b &1) res = (res * a) % mod;
a = (a * a) % mod;
b >>=1;
}
returnres;
}
intmain(){
cin>> s;
for(inti =0; i < s.size(); i++) {
counts[s[i] -'a'+1]++;
}
init();
for(inti =1; i <=26; i++) {
sums[i] = ((qmi(2, counts[i], mod)) % mod - c[counts[i]][2] + mod) % mod;
}
longlongres =0;
for(inti =1; i <=26; i++) {
if(counts[i] >=2) {
res = (res + c[counts[i]][2] * getRes(i) % mod) % mod;
}
}
cout<< res;
return0;
}

相关文章推荐

上一篇：2024届秋招笔试-小红书笔试题01-三语言题解(Java/Cpp/Python) 下一篇：是时候总结一波了，数据分析求职面试笔试题！