【秋招突围】2024届秋招-阿里系列笔试题-第一套
大家好这里是清隆学长 ，一枚热爱算法的程序员
✨ 本系计划跟新各公司春秋招的笔试题
感谢大家的订阅➕ 和 喜欢
写在前面
夏天来了 秋招还会远吗？
前不久春招也算是圆满结束咯，大家有拿到心仪的 offer吗？ 接下来互联网的秋招也快来啦，小伙伴们有开始准备了吗？ 本次给大家带来24届秋招 阿里系 的笔试题目三语言解析(Java/Python/Cpp)
01.字符串重排
问题描述
LYA 有一个只包含 和 的字符串。她认为字典序小的字符串更加优雅，所以她想通过重新排列字符串中的字符，使得字符串的字典序尽可能小。
LYA 最多可以进行 次操作，每次操作可以交换相邻的两个字符。
LYA 很忙，于是她找到了你帮忙，相信这对你来说是小菜一碟。
输入格式
第一行包含两个正整数 和 ，分别表示字符串的长度和最多可以进行的操作次数。
第二行是一个长度为 的只包含 和 的字符串。
输出格式
输出一行，表示重排后字典序最小的字符串。
样例输入
3 1
101
样例输出
011
数据范围
题解
我们可以按照以下的贪心策略来重排字符串：
从左到右遍历字符串，对于当前位置 ：
- 如果 ，说明当前位置已经是最优的，不需要操作，继续遍历下一个位置。
- 如果 ，我们希望能够把这个 尽可能地往后移动。只要 且 ，就将 和 交换，同时 减 。
直观地理解，我们希望把所有的 都尽可能地放在字符串的前面，而把所有的 都尽可能地放在字符串的后面。
具体实现时，我们可以从左到右遍历字符串，对于每个位置，如果它是 ，就尝试将它往后移动，直到无法移动或者操作次数用完为止。
参考代码
- Python
n, k = map(int, input().split())
string = list(input())
for i in range(n):
if string[i] == "0":
tmp = i
while tmp > 0 and string[tmp - 1] == "1" and k > 0:
string[tmp], string[tmp - 1] = string[tmp - 1], string[tmp]
tmp -= 1
k -= 1
if k == 0:
break
print("".join(string))
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
scanner.nextLine(); // Consume the newline character
String str = scanner.nextLine();
char[] charArray = str.toCharArray();
for (int i = 0; i < n; i++) {
if (charArray[i] == '0') {
int tmp = i;
while (tmp > 0 && charArray[tmp - 1] == '1' && k > 0) {
char tempChar = charArray[tmp];
charArray[tmp] = charArray[tmp - 1];
charArray[tmp - 1] = tempChar;
tmp -= 1;
k -= 1;
}
if (k == 0) {
break;
}
}
}
System.out.println(String.valueOf(charArray));
}
}
- Cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<char> str(n);
for (int i = 0; i < n; i++) {
cin >> str[i];
}
for (int i = 0; i < n; i++) {
if (str[i] == '0') {
int tmp = i;
while (tmp > 0 && str[tmp - 1] == '1' && k > 0) {
swap(str[tmp], str[tmp - 1]);
tmp -= 1;
k -= 1;
}
if (k == 0) {
break;
}
}
for (char ch : str) {
cout << ch;
}
cout << endl;
return 0;
}
02.木雕艺术家的创作
问题描述
A先生是一位著名的木雕艺术家,他最近完成了一批精美的木雕作品。这批作品一共有 件,每件作品都有一个独一无二的编号,从 到 。K小姐是A先生的朋友,她对这批作品很感兴趣,希望能够从中选择一些作品组成自己的收藏。
然而,K小姐有一个独特的收藏爱好,她希望自己收藏的木雕作品中,编号从 到 的作品均有且只有一件,即她想收藏一个 排列。那么请问,在这 件作品中,有多少种不同的 排列可以被收藏呢?
输入格式
第一行输入一个整数 ,表示木雕作品的总数。
第二行输入 个整数 ,表示每件作品的编号。
输出格式
一行一个整数,表示有多少种不同的 排列可以被收藏,其中 。
由于答案可能很大,请对 取模。
样例输入
5
1 2 1 3 4
样例输出
8
可被收藏的 排列分别为:
数据范围
题解
我们可以统计出每个数字在数组中出现的次数,然后对于每个长度 ,我们计算有多少种方案满足每个数字恰好出现一次。
具体做法是,对于每个长度 ,我们先假设第一个数字是 ,那么第二个数字就只能从 到 中选择,第三个数字就只能从 到 中选择,以此类推。所以方案数就是 ,其中 表示数字 在数组中出现的次数。
最终的答案就是将所有长度的方案数相加即可。
时间复杂度为 ,空间复杂度为 。
参考代码
- Python
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (n + 1)
for x in a:
cnt[x] += 1
res = 0
MOD = 10 ** 9 + 7
temp = 1
for i in range(1, n + 1):
if cnt[i] == 0:
break
temp = (temp * cnt[i]) % MOD
res = (res + temp) % MOD
print(res)
- Java
import java.util.*;
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[] cnt = new int[n + 1];
for (int x : a) {
cnt[x]++;
}
int res = 0;
int MOD = 1000000007;
int temp = 1;
for (int i = 1; i <= n; i++) {
if (cnt[i] == 0) {
break;
}
temp = (int) ((long) temp * cnt[i] % MOD);
res = (res + temp) % MOD;
}
System.out.println(res);
}
}
- Cpp
#include <bits/stdc++.h>
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> cnt(n + 1, 0);
for (int x : a) {
cnt[x]++;
}
int res = 0;
const int MOD = 1e9 + 7;
int temp = 1;
for (int i = 1; i <= n; i++) {
if (cnt[i] == 0) {
break;
}
temp = (int) ((long long) temp * cnt[i] % MOD);
res = (res + temp) % MOD;
}
cout << res << endl;
return 0;
}
⌚️ 03.K小姐的树形关卡设计
问题描述
K小姐最近沉迷于设计一款类似于植物大战僵尸（PVZ）的游戏关卡。与PVZ不同的是，她设计的关卡是在一棵以节点 为根的树上进行的。
树上的每个节点都有一个僵尸和一个传送门。僵尸进入某个节点的传送门后，会被传送到该节点的子树中编号最小的节点（除了该节点本身）。
现在K小姐想知道，如果僵尸从每个节点出发，到达叶子节点时，一共能吃掉多少个僵尸。
输入格式
第一行包含一个正整数 ，表示树上的节点数量。
接下来 行，每行包含两个正整数 和 ，表示节点 和节点 之间有一条边。
输出格式
输出一行，包含 个空格分隔的正整数。其中第 个数表示从第 个节点出发，最终能吃掉的僵尸数量。
样例输入
4
1 3
3 2
4 1
样例输出
2 1 2 1
数据范围
题解
本题可以通过DFS遍历树，并记录每个节点通过传送门后到达的最小编号节点，来求解从每个节点出发能吃掉的僵尸数量。
具体步骤如下：
- 建立树的邻接表表示。
- 从根节点开始进行DFS遍历。对于当前节点 ：
- 如果 是叶子节点，则从 出发只能吃掉 个僵尸。
- 否则，对于 的每个子节点 ：
- 递归计算从 出发能吃掉的僵尸数量。
- 在 的所有子节点中，找到编号最小的节点 。
- 从 出发能吃掉的僵尸数量为 。
- 最后输出每个节点出发能吃掉的僵尸数量。
时间复杂度为 ，空间复杂度为 。
参考代码
- Python
def dfs(u, fa):
if len(graph[u]) == 1:
nums[u] = 1
return u
min_node = n
for v in graph[u]:
if v == fa:
continue
min_node = min(min_node, dfs(v, u))
nums[u] = nums[min_node] + 1
return min(u, min_node)
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
graph[u].append(v)
graph[v].append(u)
nums = [0] * n
dfs(0, -1)
print(*nums)
- Java
import java.util.*;
public class Main {
static int n;
static List<Integer>[] graph;
static int[] nums;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
graph = new List[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < n - 1; i++) {
int u = sc.nextInt() - 1;
int v = sc.nextInt() - 1;
graph[u].add(v);
graph[v].add(u);
}
nums = new int[n];
dfs(0, -1);
for (int i = 0; i < n; i++) {
System.out.print(nums[i] + " ");
}
}
static int dfs(int u, int fa) {
if (graph[u].size() == 1) {
nums[u] = 1;
return u;
}
int minNode = n;
for (int v : graph[u]) {
if (v == fa) {
continue;
}
minNode = Math.min(minNode, dfs(v, u));
}
nums[u] = nums[minNode] + 1;
return Math.min(u, minNode);
}
}
- Cpp
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
vector<int> graph[N];
int nums[N];
int dfs(int u, int fa) {
if (graph[u].size() == 1) {
nums[u] = 1;
return u;
}
int minNode = N;
for (int v : graph[u]) {
if (v == fa) {
continue;
}
minNode = min(minNode, dfs(v, u));
}
nums[u] = nums[minNode] + 1;
return min(u, minNode);
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(0, -1);
for (int i = 0; i < n; i++) {
cout << nums[i] << " ";
}
return 0;
}