🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新美团近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

**

💻听说明天上午要笔美团啦，这里给大家带来一些去年秋招的题目来练练手。

🎉 祝大家明天超常发挥，笔试AK，rp ++++++

**

01.LYA的魔法药水

问题描述

LYA是一位魔法学徒,她正在学习制作魔法药水。一个合格的魔法药水需要满足以下两个条件:

1. 药水中的材料必须按照一定的顺序排列,材料的魔力值需要严格递增。即对于相邻的两种材料,后一种材料的魔力值必须大于前一种。

2. 相邻两种材料的魔力值之差也需要严格递增。即对于排序后的任意三种连续的材料,第三种与第二种材料魔力值之差必须大于第二种与第一种材料魔力值之差。

现在LYA准备了一组材料,她想知道这组材料是否可以制作出合格的魔法药水。你能帮助她吗?

输入格式

第一行包含一个正整数 $n(1\le n\le 10^5)$,表示材料的数量。

第二行包含 $n$ 个正整数 $a_1,a_2,\dots ,a_n(1\le a_i\le 10^9)$,表示每种材料的魔力值。

输出格式

如果这组材料可以制作合格的魔法药水,输出 "Yes",否则输出 "No"。

样例输入

5
1 3 7 13 21

样例输出

Yes

数据范围

• $1\le n\le 10^5$
• $1\le a_i\le 10^9$

题解

本题可以通过遍历材料的魔力值数组,同时维护相邻两个材料的魔力值之差来判断是否满足题目要求。

具体步骤如下:

1. 遍历材料魔力值数组,检查是否满足严格递增,如果不满足直接输出 "No"。

2. 在遍历的过程中,计算相邻两个材料的魔力值之差,并用一个数组 $b$ 存储。

3. 遍历数组 $b$,检查是否满足严格递增,如果不满足直接输出 "No"。

4. 如果遍历完成后没有出现不满足条件的情况,输出 "Yes"。

时间复杂度 $O(n)$,空间复杂度 $O(n)$。

参考代码

• Python

n = int(input())
a = list(map(int, input().split()))b = [0] * (n - 1)
for i in range(1, n):if a[i] <= a[i - 1]:print("No")exit()b[i - 1] = a[i] - a[i - 1]for i in range(1, n - 1):if b[i] <= b[i - 1]:print("No")exit()print("Yes")

• Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}int[] b = new int[n - 1];for (int i = 1; i < n; i++) {if (a[i] <= a[i - 1]) {System.out.println("No");return;}b[i - 1] = a[i] - a[i - 1];}for (int i = 1; i < n - 1; i++) {if (b[i] <= b[i - 1]) {System.out.println("No");return;}}System.out.println("Yes");}
}

• Cpp

#include <iostream>
#include <vector>using namespace std;int main() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}vector<int> b(n - 1);for (int i = 1; i < n; i++) {if (a[i] <= a[i - 1]) {cout << "No" << endl;return 0;}b[i - 1] = a[i] - a[i - 1];}for (int i = 1; i < n - 1; i++) {if (b[i] <= b[i - 1]) {cout << "No" << endl;return 0;}}cout << "Yes" << endl;return 0;
}

02.K 小姐的魔法书

问题描述

K 小姐是一位热爱收藏古籍的魔法师。她拥有 $n$ 本魔法书,每本书都有 $m$ 页。

这些魔法书中蕴藏着强大的魔力,每一页都记载着神秘的魔法符号。K 小姐相信,如果从每本书中选取一个符号,并按照从上到下的顺序将它们组合成一个新的咒语,就能够释放出非凡的魔力。

现在,K 小姐想知道能否从这些符号中找到一个 "lyasuki" 的咒语。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1\le n,m\le 1000)$,分别表示魔法书的数量和每本书的页数。

接下来 $n$ 行,每行一个长度为 $m$ 的字符串,表示从上到下每本魔法书的符号。

输出格式

如果能够找到 "lyasuki" 的咒语,则输出 "Yes",否则输出 "No"。

样例输入

7 4
lkjh
yqrs
airt
yszx
uvmw
noky
abki

样例输出

Yes

数据范围

• $1\le n,m\le 1000$

题解

本题可以使用贪心的思想来解决。我们可以按照 "lyasuki" 中字符的顺序,从上到下遍历每一本魔法书,看是否能找到对应的字符。

具体做法如下:

1. 将 "lyasuki" 转换为字符数组 index。
2. 从上到下遍历每本魔法书,用指针 l 表示当前需要匹配的字符在 index 中的位置,用指针 r 表示当前遍历到的魔法书的编号。
3. 如果当前魔法书包含 index[l] 字符,则 l 和 r 都向后移动一位。
4. 如果当前魔法书不包含 index[l] 字符,则只将 r 向后移动一位。
5. 重复步骤 3 和 4,直到 l 到达 index 的末尾或 r 到达最后一本魔法书。
6. 如果 l 到达了 index 的末尾,说明找到了 "lyasuki" 咒语,输出 "Yes",否则输出 "No"。

时间复杂度 $O(nm)$,空间复杂度 $O(n)$。

参考代码

• Python

n, m = map(int, input().split())
index = list("lyasuki")
books = [input() for _ in range(n)]l = r = 0
while l < len(index) and r < n:if index[l] in books[r]:l += 1r += 1print("Yes" if l == len(index) else "No")

• Java

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt();char[] idx = "lyasuki".toCharArray();sc.nextLine();String[] books = new String[n];for (int i = 0; i < n; i++) {books[i] = sc.nextLine();}int l = 0, r = 0;while (l < idx.length && r < n) {if (books[r].indexOf(idx[l]) != -1) {l++;}r++;}System.out.println(l == idx.length ? "Yes" : "No");}
}

• Cpp

#include <iostream>
#include <string>
using namespace std;int main() {int n, m;cin >> n >> m;string idx = "lyasuki";string books[1005];for (int i = 0; i < n; i++) {cin >> books[i];}int l = 0, r = 0;while (l < idx.size() && r < n) {if (books[r].find(idx[l]) != string::npos) {l++;}r++;}cout << (l == idx.size() ? "Yes" : "No") << endl;return 0;
}

03.K小姐的蛋糕店

题目描述

K小姐开了一家蛋糕店,店里有 $n$ 种不同口味的蛋糕。每种蛋糕都有一个美味度,第 $i$ 种蛋糕的美味度为 $a_i$。

K小姐想要通过一些操作,使得第一种蛋糕的美味度 $a_1$ 成为所有蛋糕中最高的。她可以进行以下两种操作:

1. 将 $a_1$ 的美味度乘以 $2$。
2. 选择一种蛋糕 $i(2\le i\le n)$,将其美味度 $a_i$ 变成 $\lfloor \frac{a_i}{2}\rfloor$。

现在K小姐想知道,最少需要多少次操作,才能使得第一种蛋糕的美味度成为最高。

输入格式

第一行输入一个正整数 $n(1\le n\le 10^5)$,表示蛋糕的种类数。

第二行输入 $n$ 个正整数,第 $i$ 个数为 $a_i(1\le a_i\le 10^9)$,表示第 $i$ 种蛋糕的美味度。

输出格式

输出一个整数,表示最少需要的操作次数。

样例输入

6
1 1 4 4 1 4

样例输出

2

样例解释

将第一种蛋糕的美味度连续乘 $2$ 两次,就可以使其美味度达到 $4$,成为所有蛋糕中最高的。

数据范围

• $1\le n\le 10^5$
• $1\le a_i\le 10^9$

题解

本题可以用贪心的思想来解决。首先统计出有多少种蛋糕的美味度高于第一种蛋糕,记为 $cnt$。然后进行如下操作:

• 如果 $cnt\ge 2$,就将第一种蛋糕的美味度乘以 $2$,同时更新 $cnt$ 的值。
• 如果 $cnt=1$,就将唯一比第一种蛋糕美味度高的那种蛋糕的美味度除以 $2$,同时更新 $cnt$ 的值。

重复上述操作,直到 $cnt=0$,此时第一种蛋糕的美味度就成为了最高。

总操作次数即为最少需要的操作次数。

时间复杂度为 $O(n\log M)$,其中 M = max ⁡ { a i } M=\max\{a_i\} M=max{ai​}。空间复杂度为 $O(n)$。

参考代码

• Python

n = int(input())
a = list(map(int, input().split()))a1 = a[0]
cnt = sum(ai > a1 for ai in a[1:])
ops = 0while cnt > 0:if cnt >= 2:a1 *= 2cnt = sum(ai > a1 for ai in a[1:]) else:for i in range(1, n):if a[i] > a1:a[i] //= 2if a[i] <= a1:cnt -= 1breakops += 1print(ops)

• Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}int a1 = a[0];int cnt = 0;for (int i = 1; i < n; i++) {if (a[i] > a1) {cnt++;}}int ops = 0;while (cnt > 0) {if (cnt >= 2) {a1 *= 2;cnt = 0;for (int i = 1; i < n; i++) {if (a[i] > a1) {cnt++;}}} else {for (int i = 1; i < n; i++) {if (a[i] > a1) {a[i] /= 2;if (a[i] <= a1) {cnt--;}break;}}}ops++;}System.out.println(ops);}
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;int main() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}int a1 = a[0];int cnt = 0;for (int i = 1; i < n; i++) {if (a[i] > a1) {cnt++;}}int ops = 0;while (cnt > 0) {if (cnt >= 2) {a1 *= 2;cnt = 0;for (int i = 1; i < n; i++) {if (a[i] > a1) {cnt++;}}} else {for (int i = 1; i < n; i++) {if (a[i] > a1) {a[i] /= 2;if (a[i] <= a1) {cnt--;}break;}}}ops++;}cout << ops << endl;return 0;
}

04.LYA的魔法卡牌

问题描述

LYA是一名魔法学徒,她有一套由 $n$ 张卡牌组成的魔法卡牌。每张卡牌上都有一个魔力值 $a_i(1\le a_i\le 10^9)$。

现在,LYA需要从这套卡牌中移除恰好 $k$ 张卡牌,使得剩下的卡牌满足以下条件:对于任意两张卡牌,它们的魔力值要么互为倍数,要么其中一张卡牌的魔力值是另一张的倍数。特别地,如果移除后卡牌数量为 $1$ 或 $0$,也视为满足条件。

LYA想知道,一共有多少种不同的移除方案呢?

输入格式

第一行包含两个整数 $n$ 和 $k(1\le k\le n\le 10^3)$,分别表示初始卡牌数量和需要移除的卡牌数量。

第二行包含 $n$ 个整数,第 $i$ 个整数表示第 $i$ 张卡牌的魔力值 $a_i(1\le a_i\le 10^9)$。

数据保证初始卡牌的魔力值两两不同。

输出格式

输出一个整数,表示不同的移除方案数。

样例输入

3 1
1 2 4

样例输出

3

数据范围

• $1\le k\le n\le 10^3$
• $1\le a_i\le 10^9$
• 初始卡牌的魔力值两两不同

题解

本题可以使用动态规划求解。令 $dp[i][j]$ 表示考虑前 $i$ 张卡牌,保留 $j$ 张卡牌的方案数。

首先,我们对卡牌按照魔力值从小到大排序。然后,我们可以得到以下状态转移方程:

• 对于第一张卡牌,只有一种方案,即 $dp[1][1]=1$。
• 对于第 $i$ 张卡牌,如果我们不保留它,则方案数等于不考虑第 $i$ 张卡牌时的方案数,即 $dp[i][j]=dp[i-1][j]$。
• 如果我们保留第 $i$ 张卡牌,则需要枚举第 $i$ 张卡牌之前的所有卡牌,如果它们的魔力值是第 $i$ 张卡牌魔力值的因数,则可以转移状态,即 $dp[i][j]+=dp[k][j-1]$,其中 $a[i]$ 是 $a[k]$ 的倍数。

最后,我们将所有 $dp[i][n-k]$ 的值求和即可得到答案。

时间复杂度为 $O(n^3)$,空间复杂度为 $O(n^2)$。

参考代码

• Python

n, k = map(int, input().split())
a = list(map(int, input().split()))if n == k:print(1)exit()a.sort()
m = n - k 
dp = [[0] * (m + 1) for _ in range(n + 1)]for i in range(1, n + 1):dp[i][1] = 1for i in range(1, n + 1):for j in range(1, i):if a[i - 1] % a[j - 1] == 0:for l in range(1, min(m, i) + 1):dp[i][l] += dp[j][l - 1]ans = 0
for i in range(1, n + 1):ans += dp[i][m]print(ans)

• Java

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}if (n == k) {System.out.println(1);return;}Arrays.sort(a);int m = n - k;long[][] dp = new long[n + 1][m + 1];for (int i = 1; i <= n; i++) {dp[i][1] = 1;}for (int i = 1; i <= n; i++) {for (int j = 1; j < i; j++) {if (a[i - 1] % a[j - 1] == 0) {for (int l = 1; l <= Math.min(m, i); l++) {dp[i][l] += dp[j][l - 1];}}}}long ans = 0;for (int i = 1; i <= n; i++) {ans += dp[i][m];}System.out.println(ans);}
}

• Cpp

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;int main() {int n, k;cin >> n >> k;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}if (n == k) {cout << 1 << endl;return 0;}sort(a.begin(), a.end());int m = n - k;vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));for (int i = 1; i <= n; i++) {dp[i][1] = 1;}for (int i = 1; i <= n; i++) {for (int j = 1; j < i; j++) {if (a[i - 1] % a[j - 1] == 0) {for (int l = 1; l <= min(m, i); l++) {dp[i][l] += dp[j][l - 1];}}}}long long ans = 0;for (int i = 1; i <= n; i++) {ans += dp[i][m];}cout << ans << endl;return 0;
}

05.K 小姐的珠宝搭配

问题描述

K 小姐是一位珠宝设计师,她有 $n$ 颗宝石。现在,她想把这些宝石两两配对,设计出独特的珠宝首饰。

为了让珠宝更加美观,K 小姐规定,在每一对宝石 $(a,b)$ 中,第一颗宝石的大小 $a$ 必须小于等于第二颗宝石的大小 $b$。

现在,K 小姐想知道,在满足上述条件的情况下,她最多能设计出多少种不同的宝石搭配方案。

注意,$(a,b)$ 和 $(b,a)$ 被视为同一种搭配方案。

输入格式

第一行包含一个整数 $n$ $(1\le n\le 10^5)$,表示宝石的数量。

第二行包含 $n$ 个整数,第 $i$ 个整数 $a_i$ $(1\le a_i\le 10^9)$ 表示第 $i$ 颗宝石的大小。

输出格式

输出一个整数,表示最多能设计出的不同宝石搭配方案数。

样例输入

8
1 1 2 2 2 2 3 3

样例输出

4

数据范围

• $1\le n\le 10^5$
• $1\le a_i\le 10^9$

题解

本题可以使用贪心的思想来解决。我们可以先将宝石按照大小进行排序,然后统计每种大小的宝石的数量。

接下来,我们按照宝石数量从多到少的顺序进行配对。对于数量最多的宝石,我们优先与其他种类的宝石进行配对。如果配对完所有其他种类的宝石后,该种宝石还有剩余,则再将剩余的宝石两两配对。

具体步骤如下:

1. 将宝石按照大小进行排序。
2. 使用字典 dict_ 统计每种大小的宝石的数量。
3. 将字典转换为列表 a_,其中每个元素为 $(size,count)$ 的元组,表示宝石的大小和数量。
4. 将列表 a_ 按照宝石数量从多到少进行排序。
5. 遍历列表 a_,对于每种宝石:
   • 从下一种宝石开始,依次与其配对,直到当前宝石数量为 $0$ 或者遍历完所有其他种类的宝石。
   • 如果当前宝石还有剩余,则将剩余的宝石两两配对。
6. 输出配对的总数。

时间复杂度为 $O(n\log n)$,空间复杂度为 $O(n)$。

参考代码

• Python

n = int(input())
a = list(map(int, input().split()))
a.sort()count = {}
for x in a:count[x] = count.get(x, 0) + 1pairs = [(size, cnt) for size, cnt in count.items()]
pairs.sort(key=lambda x: x[1], reverse=True)res = 0
for i in range(len(pairs) - 1):while count[pairs[i][0]] > 0:j = i + 1while j < len(pairs) and count[pairs[j][0]] > 0:count[pairs[i][0]] -= 1count[pairs[j][0]] -= 1res += 1j += 1if count[pairs[i][0]] >= 2:count[pairs[i][0]] -= 2res += 1print(res)

• Java

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();Arrays.sort(a);Map<Integer, Integer> count = new HashMap<>();for (int x : a) {count.put(x, count.getOrDefault(x, 0) + 1);}List<int[]> pairs = new ArrayList<>();for (int size : count.keySet()) {pairs.add(new int[]{size, count.get(size)});}pairs.sort((p1, p2) -> p2[1] - p1[1]);int res = 0;for (int i = 0; i < pairs.size() - 1; i++) {while (count.get(pairs.get(i)[0]) > 0) {int j = i + 1;while (j < pairs.size() && count.get(pairs.get(j)[0]) > 0) {count.put(pairs.get(i)[0], count.get(pairs.get(i)[0]) - 1);count.put(pairs.get(j)[0], count.get(pairs.get(j)[0]) - 1);res++;j++;}if (count.get(pairs.get(i)[0]) >= 2) {count.put(pairs.get(i)[0], count.get(pairs.get(i)[0]) - 2);res++;}}}System.out.println(res);}
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;int main() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}sort(a.begin(), a.end());unordered_map<int, int> count;for (int x : a) {count[x]++;}vector<pair<int, int>> pairs;for (auto p : count) {pairs.emplace_back(p.first, p.second);}sort(pairs.begin(), pairs.end(), [](const auto& p1, const auto& p2) {return p1.second > p2.second;});int res = 0;for (int i = 0; i < pairs.size() - 1; i++) {while (count[pairs[i].first] > 0) {int j = i + 1;while (j < pairs.size() && count[pairs[j].first] > 0) {count[pairs[i].first]--;count[pairs[j].first]--;res++;j++;}if (count[pairs[i].first] >= 2) {count[pairs[i].first] -= 2;res++;}}}cout << res << endl;return 0;
}

写在最后

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。