【笔试题解】2024-08-17-美团秋招
大家好这里是程序员基德，今天给大家带来的是美团笔试题(改编题面)的题目解析。
感兴趣的朋友可以来订阅基德的笔试专栏，感谢大家的支持。
互联网刷题必备宝典🔗
第一题：最大公约数
题目内容
小基对最大公约数很感兴趣，她会询问你 次。每次询问给出一个大于 1 的正整数
，你需要找到一个数字
，使得
为素数。
注：请给出满足条件的最小值作为答案。
输入描述
第一行输入一个整数 ，表示有
个待测数字。
接下来
行，每行包含一个整数
，表示待测的数字。
输出描述
对于每一组测试数据，在一行上输出一个整数，代表数字 。
样例1
输入：
2
114
15
输出：
2
3
题解
这道题的关键是理解所有大于 1 的合数均可以表示为若干个素数的积。因此，只需要找到输入数字的一个素因子，答案就是该数除以这个素因子。
时间复杂度：
空间复杂度：
三语言参考代码
- C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int k;
cin >> k;
while(k--) {
int n;
cin >> n;
bool isPrime = true;
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) {
cout << i << endl;
isPrime = false;
break;
}
}
if(isPrime) {
cout << n << endl;
}
}
return 0;
}
- Python
def find_min_factor(n):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return i
return n
k = int(input())
for _ in range(k):
n = int(input())
print(find_min_factor(n))
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
while(k-- > 0) {
int n = sc.nextInt();
boolean isPrime = true;
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) {
System.out.println(i);
isPrime = false;
break;
}
}
if(isPrime) {
System.out.println(n);
}
}
}
}
第二题：数组极差
题目内容
小基有一个长度为 的数组，每次操作可以选择两个下标
和
，将
减去 1，将
加上 1。小基想知道最少需要多少次操作，可以使数组极差最小。
数组的极差为数组中最大值和最小值的差。
输入描述
第一行输入一个整数 ，表示数组的长度。
第二行输入
个整数
，代表数组的元素。
输出描述
在一行上输出一个整数，表示最少需要多少次操作。
样例1
输入：
5
1 2 3 4 5
输出：
3
题解
这道题的关键是贪心思想。要让极差最小，应该将所有数尽量靠近平均值。对于每个数，计算其与平均值的差值，这些差值的总和除以 2 就是最少需要的操作次数。
时间复杂度：
空间复杂度：
三语言参考代码
- C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
cin >> n;
vector<ll> nums(n);
ll sum = 0;
for(int i = 0; i < n; i++) {
cin >> nums[i];
sum += nums[i];
}
ll avg = sum / n;
ll maxAvg = avg;
if(sum % n != 0) maxAvg = avg + 1;
ll countMax = 0, countMin = 0;
for(int i = 0; i < n; i++) {
if(nums[i] < avg) countMin += (avg - nums[i]);
else if(nums[i] > maxAvg) countMax += (nums[i] - maxAvg);
}
cout << max(countMax, countMin) << endl;
return 0;
}
- Python
n = int(input())
nums = list(map(int, input().split()))
mean = sum(nums) / n
total1 = sum(int(mean - x) for x in nums if x < mean)
total2 = sum(int(x - mean) for x in nums if x > mean)
print(max(total1, total2))
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] nums = new long[n];
long sum = 0;
for(int i = 0; i < n; i++) {
nums[i] = sc.nextLong();
sum += nums[i];
}
long avg = sum / n;
long maxAvg = avg;
if(sum % n != 0) maxAvg = avg + 1;
long countMax = 0, countMin = 0;
for(int i = 0; i < n; i++) {
if(nums[i] < avg) countMin += (avg - nums[i]);
else if(nums[i] > maxAvg) countMax += (nums[i] - maxAvg);
}
System.out.println(Math.max(countMax, countMin));
}
}
第三题：游戏对决
题目内容
小基和小柯在玩一个游戏，游戏中有一个长度为 的数组
和一个固定的整数
。游戏规则如下，双方都会执行最优策略：
第一步，小基选择一个非空的区间 ，将这个区间中的所有数字都乘上
。
第二步，小柯选择一个非空的区间
，将这个区间中的所有数字都乘上
。
记 ，小柯想让
尽可能小，小基想让
尽可能大，需要求出最后
的值。
输入描述
第一行输入两个整数 和
。
第二行输入
个整数
。
输出描述
输出一个整数表示答案。
样例1
输入：
6 2
-1 -2 -3 1 2 3
输出：
0
说明：
小基会选择区间 ，数组变成
；
小柯会选择区间
，数组变成
；
数组总和为 0。
题解
这是一道博弈论和动态规划结合的问题。关键是理解双方都会采取最优策略。对于小柯来说，如果 ，应该选择和最小的区间；如果
，应该选择和最大的区间。而小基需要在考虑到小柯的策略后，选择能使最终结果最大的区间。
时间复杂度：
空间复杂度：
三语言参考代码
- C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
ll dp[MAXN][MAXN][2]; // [i][j][0/1] 表示区间[i,j]的最小/最大值
ll a[MAXN], sum[MAXN];
int main() {
int n;
ll k;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i-1] + a[i];
}
// 初始化dp数组
for(int len = 1; len <= n; len++) {
for(int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if(len == 1) {
dp[i][j][0] = dp[i][j][1] = a[i];
} else {
ll s = sum[j] - sum[i-1];
dp[i][j][0] = min({dp[i+1][j][0], dp[i][j-1][0], s});
dp[i][j][1] = max({dp[i+1][j][1], dp[i][j-1][1], s});
}
}
}
ll ans = LLONG_MIN;
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
ll s1 = sum[j] - sum[i-1];
ll s2;
if(k > 0) {
s2 = dp[i][j][0];
} else {
s2 = dp[i][j][1];
}
ans = max(ans, s1 * (k-1) + s2 * k * (k-1));
}
}
cout << sum[n] + ans << endl;
return 0;
}
- Python
def solve():
n, k = map(int, input().split())
a = list(map(int, input().split()))
if k == 0:
return 0
# 前缀和
psum = [0] * (n + 1)
for i in range(n):
psum[i + 1] = psum[i] + a[i]
# 区间dp
dp = [[[float('inf'), float('-inf')] for _ in range(n + 1)] for _ in range(n + 1)]
# 初始化长度为1的区间
for i in range(n):
dp[i][i][0] = dp[i][i][1] = a[i]
# 枚举区间长度
for l in range(2, n + 1):
for i in range(n - l + 1):
j = i + l - 1
s = psum[j + 1] - psum[i]
dp[i][j][0] = min(dp[i + 1][j][0], dp[i][j - 1][0], s)
dp[i][j][1] = max(dp[i + 1][j][1], dp[i][j - 1][1], s)
ans = float('-inf')
for i in range(n):
for j in range(i, n):
s1 = psum[j + 1] - psum[i]
s2 = dp[i][j][0] if k > 0 else dp[i][j][1]
ans = max(ans, s1 * (k - 1) + s2 * k * (k - 1))
return psum[n] + ans
print(solve())
- Java
import java.util.*;
public class Main {
static final int MAXN = 1005;
static long[][][] dp = new long[MAXN][MAXN][2];
static long[] a = new long[MAXN];
static long[] sum = new long[MAXN];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long k = sc.nextLong();
for(int i = 1; i <= n; i++) {
a[i] = sc.nextLong();
sum[i] = sum[i-1] + a[i];
}
// 初始化dp数组
for(int len = 1; len <= n; len++) {
for(int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if(len == 1) {
dp[i][j][0] = dp[i][j][1] = a[i];
} else {
long s = sum[j] - sum[i-1];
dp[i][j][0] = Math.min(Math.min(dp[i+1][j][0], dp[i][j-1][0]), s);
dp[i][j][1] = Math.max(Math.max(dp[i+1][j][1], dp[i][j-1][1]), s);
}
}
}
long ans = Long.MIN_VALUE;
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
long s1 = sum[j] - sum[i-1];
long s2 = k > 0 ? dp[i][j][0] : dp[i][j][1];
ans = Math.max(ans, s1 * (k-1) + s2 * k * (k-1));
}
}
System.out.println(sum[n] + ans);
}
}
互联网刷题笔试宝典 文章被收录于专栏
互联网刷题笔试宝典，这里涵盖了市面上大部分的笔试题合集，希望助大家春秋招一臂之力
投递UCloud等公司6个岗位 >