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

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

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

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

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

01.LYA 的独特字符串

问题描述

LYA 有一个由 $n$ 个小写字母组成的字符串 $s$。她想从中选出 $k$ 个字符，使得这 $k$ 个字符组成的子串中不同字符的个数最多。

请你帮助 LYA 计算，在最优方案下，这个子串中最多有多少个不同的字符。

输入格式

第一行包含两个正整数 $n$ 和 $k$，分别表示字符串 $s$ 的长度和要选择的字符个数。

第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写字母组成。

输出格式

输出一个整数，表示在最优方案下，选出的 $k$ 个字符组成的子串中不同字符的最大个数。

样例输入

7 4
abacaba

样例输出

3

数据范围

• $1\le k\le n\le 10^5$
• 字符串 $s$ 仅由小写字母组成

题解

这个问题可以转化为从字符串 $s$ 中选择 $k$ 个字符，使得选出的字符集合的大小最大。

我们可以用一个集合（set）来维护当前选择的字符集合，遍历字符串 $s$，将每个字符加入集合，直到选择了 $k$ 个字符为止。最终集合的大小即为最多能得到的不同字符数。

如果字符串 $s$ 中不同字符的总数小于 $k$，那么答案就是 $s$ 中不同字符的总数。

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

参考代码

• Python

n, k = map(int, input().split())
s = input()
chars = set()
for c in s:chars.add(c)if len(chars) == k:break
print(len(chars))

• 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));String[] line = br.readLine().split(" ");int n = Integer.parseInt(line[0]);int k = Integer.parseInt(line[1]);String s = br.readLine();Set<Character> chars = new HashSet<>();for (char c : s.toCharArray()) {chars.add(c);if (chars.size() == k) {break;}}System.out.println(chars.size());}
}

• Cpp

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;int main() {int n, k;string s;cin >> n >> k >> s;unordered_set<char> chars;for (char c : s) {chars.insert(c);if (chars.size() == k) {break;}}cout << chars.size() << endl;return 0;
}

02.卢小姐的城市之旅

题目描述

卢小姐计划去旅行，她要走遍 $n$ 个城市。从一个城市到相邻的城市需要消耗 $1$ 单位的体力。每个城市都有特色美食，每份售价为 $a_i$，卢小姐可以在每个城市购买任意份美食。

卢小姐想要用最少的花费走完全程，但是她希望每个城市的美食不要吃太多，即在一个城市重复进餐的次数的最大值最小。

卢小姐想知道一种满足上述条件的美食购买方案。如果有多种方案，输出任意一种即可。

输入格式

第一行输入一个整数 $n$（$1\le n\le 10^5$），表示城市个数。

第二行输入 $n$ 个整数，表示每个城市的美食售价 $a_i$（$1\le a_i\le 10^5$）。

输出格式

输出一行整数，表示每个城市购买的美食份数。

样例输入

4
1 2 1 4

样例输出

2 0 1 0

样例解释

在第 $1$ 个城市购买 $2$ 份美食，花费 $2$。
在第 $2$ 个城市购买 $0$ 份美食，花费 $0$。
在第 $3$ 个城市购买 $1$ 份美食，花费 $1$。
在第 $4$ 个城市购买 $0$ 份美食，花费 $0$。

此时总花费为 $3$，在同一个城市重复进餐次数的最大值为 $2$（第 $1$ 个城市）。

数据范围

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

题解

本题可以使用贪心 + 优先队列来解决，即所谓反悔贪心

我们可以维护一个优先队列，存储每个城市的美食售价和当前在该城市进餐的次数。每次从优先队列中取出售价最低且进餐次数最少的城市，在该城市多购买一份美食，然后将其重新插入优先队列。重复这个过程直到到达最后一个城市。

这样做的正确性在于，我们总是选择售价最低且进餐次数最少的城市购买美食，可以尽量均匀地分配进餐次数，从而使得在同一个城市重复进餐次数的最大值最小。

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

参考代码

• Python

import heapqn = int(input())
a = list(map(int, input().split()))pq = [(a[i], 0, i) for i in range(n)]
heapq.heapify(pq)ans = [0] * n
for _ in range(n - 1):price, cnt, idx = heapq.heappop(pq)ans[idx] += 1heapq.heappush(pq, (price, cnt + 1, idx))print(*ans)

• Java

import java.util.*;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();}PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) ->x[0] != y[0] ? x[0] - y[0] : x[1] - y[1]);for (int i = 0; i < n; i++) {pq.offer(new int[]{a[i], 0, i});}int[] ans = new int[n];for (int i = 0; i < n - 1; i++) {int[] top = pq.poll();ans[top[2]]++;pq.offer(new int[]{top[0], top[1] + 1, top[2]});}for (int x : ans) {System.out.print(x + " ");}}
}

• Cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;typedef pair<int, pair<int, int>> PII;int main() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}priority_queue<PII, vector<PII>, greater<PII>> pq;for (int i = 0; i < n; i++) {pq.emplace(a[i], make_pair(0, i));}vector<int> ans(n);for (int i = 0; i < n - 1; i++) {auto top = pq.top();pq.pop();int price = top.first, cnt = top.second.first, idx = top.second.second;ans[idx]++;pq.emplace(price, make_pair(cnt + 1, idx));}for (int x : ans) {cout << x << " ";}return 0;
}

03.卢小姐的元素调整之旅

问题描述

K小姐和A先生在玩一款名为“元素调整”的游戏。K小姐有一串宝石，每颗宝石都有一个能量值。为了保持宝石的和谐，K小姐希望通过调整能量值，使得她的宝石串中的能量值不递减，并且每颗宝石的能量值必须与A先生提供的宝石能量值匹配。

K小姐可以通过施加魔法来增加或减少宝石的能量值（每次操作改变 $1$ 单位能量）。她想知道，为了达到目标，最少需要施展多少次魔法。

输入格式

第一行包含两个正整数 $n,m$，分别表示 K小姐和 A先生宝石串的长度。

第二行共 $n$ 个空格分开的正整数 $a_1,a_2,\dots ,a_n$，表示 K小姐宝石串的初始能量值。

第三行共 $m$ 个空格分开的正整数 $b_1,b_2,\dots ,b_m$，表示 A先生宝石串的能量值。

输出格式

输出一个整数，表示 K小姐达到目标所需的最少魔法施展次数。

样例输入

5 4
3 5 3 8 10
1 2 3 4

样例输出

12

数据范围

$1\le n,m\le 2\times 10^3$

$1\le a_i,b_i\le 10^9$

题解

要使 K小姐的宝石串能量值不递减且每颗宝石的能量值都存在于 A先生的宝石串中，我们可以采用动态规划的方法。我们定义状态 $dp[i][j]$ 为考虑到 K小姐的前 $i$ 颗宝石，并且第 $i$ 颗宝石的能量调整为 A先生宝石串中第 $j$ 颗的能量值时，所需的最小魔法施展次数。状态转移方程为：

$$dp[i][j]=\min (dp[i-1][j],dp[i-1][j-1])+|a_i-b_j|$$

最终答案为 ${\min }_{1\le j\le m}dp[n][j]$。

参考代码

• Python

INF = float('inf')n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))b.sort()dp = [[INF] * (m + 1) for _ in range(n + 1)]
for j in range(m + 1):dp[0][j] = 0for i in range(1, n + 1):for j in range(1, m + 1):val = abs(a[i - 1] - b[j - 1])dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + valans = min(dp[n])
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 INF = Integer.MAX_VALUE;int n = sc.nextInt(), m = sc.nextInt();int[] a = new int[n];int[] b = new int[m];for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}for (int i = 0; i < m; i++) {b[i] = sc.nextInt();}Arrays.sort(b);int[][] dp = new int[n + 1][m + 1];for (int[] row : dp) {Arrays.fill(row, INF);}for (int j = 0; j <= m; j++) {dp[0][j] = 0;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {int val = Math.abs(a[i - 1] - b[j - 1]);dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + val;}}int ans = Arrays.stream(dp[n]).min().orElse(INF);System.out.println(ans);}
}

• Cpp

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;int main() {const int INF = 1e9;int n, m;cin >> n >> m;vector<int> a(n), b(m);for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < m; i++) {cin >> b[i];}sort(b.begin(), b.end());vector<vector<int>> dp(n + 1, vector<int>(m + 1, INF));for (int j = 0; j <= m; j++) {dp[0][j] = 0;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {int val = abs(a[i - 1] - b[j - 1]);dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + val;}}int ans = *min_element(dp[n].begin(), dp[n].end());cout << ans << endl;return 0;
}

写在最后

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