【秋招突围】2024届秋招笔试-阿里系列笔试题-第一套-三语言题解(Java/Cpp/Python)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系计划跟新各公司春秋招的笔试题

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

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

📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注CSDN同名公主号领取，会在飞书进行同步的跟新。

📖 写在前面

夏天要来了 秋招还会远吗？

前不久春招也算是圆满结束咯，大家有拿到心仪的 offer吗？
接下来互联网的秋招也快来啦，小伙伴们有开始准备了吗？
本次给大家带来24届秋招 阿里系 的笔试题目三语言解析(Java/Python/Cpp)

文末有清隆学长的笔试陪伴打卡小屋活动介绍:
✨丰富的打卡奖励等你来领哦，大厂笔试题汇总，笔试面试经验贴，算法笔试模版…
💽 有兴趣的小伙伴们也可以了解一下，不要错过啦~

🖥 01.字符串重排

问题描述

LYA 有一个只包含 $0$ 和 $1$ 的字符串。她认为字典序小的字符串更加优雅，所以她想通过重新排列字符串中的字符，使得字符串的字典序尽可能小。

LYA 最多可以进行 $k$ 次操作，每次操作可以交换相邻的两个字符。

LYA 很忙，于是她找到了你帮忙，相信这对你来说是小菜一碟。

输入格式

第一行包含两个正整数 $n$ 和 $k$，分别表示字符串的长度和最多可以进行的操作次数。

第二行是一个长度为 $n$ 的只包含 $0$ 和 $1$ 的字符串。

输出格式

输出一行，表示重排后字典序最小的字符串。

样例输入

3 1
101

样例输出

011

数据范围

$1\le n\le 10^5$
$1\le k\le 10^9$

题解

我们可以按照以下的贪心策略来重排字符串：

从左到右遍历字符串，对于当前位置 $i$：

• 如果 $s[i]=0$，说明当前位置已经是最优的，不需要操作，继续遍历下一个位置。
• 如果 $s[i]=1$，我们希望能够把这个 $1$ 尽可能地往后移动。只要 $k>0$ 且 $s[i-1]=1$，就将 $s[i]$ 和 $s[i-1]$ 交换，同时 $k$ 减 $1$。

直观地理解，我们希望把所有的 $0$ 都尽可能地放在字符串的前面，而把所有的 $1$ 都尽可能地放在字符串的后面。

具体实现时，我们可以从左到右遍历字符串，对于每个位置，如果它是 $1$，就尝试将它往后移动，直到无法移动或者操作次数用完为止。

参考代码

• 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先生是一位著名的木雕艺术家,他最近完成了一批精美的木雕作品。这批作品一共有 $n$ 件,每件作品都有一个独一无二的编号,从 $1$ 到 $n$。K小姐是A先生的朋友,她对这批作品很感兴趣,希望能够从中选择一些作品组成自己的收藏。

然而,K小姐有一个独特的收藏爱好,她希望自己收藏的木雕作品中,编号从 $1$ 到 $k$ 的作品均有且只有一件,即她想收藏一个 $k$ 排列。那么请问,在这 $n$ 件作品中,有多少种不同的 $k$ 排列可以被收藏呢?

输入格式

第一行输入一个整数 $n(1\le n\le 10^5)$,表示木雕作品的总数。

第二行输入 $n$ 个整数 $a_i(1\le a_i\le 10^9)$,表示每件作品的编号。

输出格式

一行一个整数,表示有多少种不同的 $k$ 排列可以被收藏,其中 $k\in [1,n]$。

由于答案可能很大,请对 $10^9+7$ 取模。

样例输入

5
1 2 1 3 4

样例输出

8

可被收藏的 $k$ 排列分别为:

• $[1]$
• $[1]$
• $[1,2]$
• $[2,1]$
• $[1,2,3]$
• $[2,1,3]$
• $[1,2,3,4]$
• $[2,1,3,4]$

数据范围

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

题解

我们可以统计出每个数字在数组中出现的次数,然后对于每个长度 $k$,我们计算有多少种方案满足每个数字恰好出现一次。

具体做法是,对于每个长度 $k$,我们先假设第一个数字是 $1$,那么第二个数字就只能从 $2$ 到 $k+1$ 中选择,第三个数字就只能从 $3$ 到 $k+1$ 中选择,以此类推。所以方案数就是 $cnt[1]\times cnt[2]\times \cdots \times cnt[k]$,其中 $cnt[i]$ 表示数字 $i$ 在数组中出现的次数。

最终的答案就是将所有长度的方案数相加即可。

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

参考代码

• 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不同的是，她设计的关卡是在一棵以节点 $1$ 为根的树上进行的。

树上的每个节点都有一个僵尸和一个传送门。僵尸进入某个节点的传送门后，会被传送到该节点的子树中编号最小的节点（除了该节点本身）。

现在K小姐想知道，如果僵尸从每个节点出发，到达叶子节点时，一共能吃掉多少个僵尸。

输入格式

第一行包含一个正整数 $n$，表示树上的节点数量。

接下来 $n-1$ 行，每行包含两个正整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间有一条边。

输出格式

输出一行，包含 $n$ 个空格分隔的正整数。其中第 $i$ 个数表示从第 $i$ 个节点出发，最终能吃掉的僵尸数量。

样例输入

4
1 3
3 2
4 1

样例输出

2 1 2 1

数据范围

$1\le n\le 10^5$
$1\le u,v\le n$

题解

本题可以通过DFS遍历树，并记录每个节点通过传送门后到达的最小编号节点，来求解从每个节点出发能吃掉的僵尸数量。

具体步骤如下：

1. 建立树的邻接表表示。
2. 从根节点开始进行DFS遍历。对于当前节点 $u$：
   • 如果 $u$ 是叶子节点，则从 $u$ 出发只能吃掉 $1$ 个僵尸。
   • 否则，对于 $u$ 的每个子节点 $v$：
     • 递归计算从 $v$ 出发能吃掉的僵尸数量。
     • 在 $u$ 的所有子节点中，找到编号最小的节点 $min\_val$。
   • 从 $u$ 出发能吃掉的僵尸数量为 $nums[min\_val]+1$。
3. 最后输出每个节点出发能吃掉的僵尸数量。

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

参考代码

• 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;
}

🎀 写在最后

🛖 这里介绍一下咱们的笔试打卡小屋

✨ 打卡小屋旨在陪伴大家，养成每日学习的好习惯。在这里，你可以：

• 🤝 与备战笔试的小伙伴相识，找到志同道合的学习小组
• 📝 通过写题解，巩固做题思路，养成良好的记录习惯
• 💡 系统掌握常考算法和数据结构，了解互联网笔试难度
• 🎁 坚持打卡，获得丰厚奖励，激励自己持之以恒

🥰 打卡奖励

7天打卡即可值回票价，心动不如行动！

🕰 每日学习安排

小屋将在每日上午发放打卡题目，包括：

• 一道算法模版题，帮助大家掌握常用算法套路
• 根据算法模版，精选一道对应的大厂笔试真题，巩固算法应用

让我们一起直击笔试重点，攻克常考题型！

📖 打卡小屋涉及题型

小屋从零基础出发，涵盖笔试常考知识点：

基础算法

• 自定义排序
• 二分
• 前缀和
• 差分
• 双指针

基础数据结构

• 栈 & 单调栈
• 队列 & 单调队列
• 并查集
• 优先队列(堆)

搜索

• DFS & BFS 基础应用
• 树的遍历
• 基础图论

动态规划 & 贪心 & 数论

• 快速幂
• 组合数
• 质数 & 因数
• 位运算
• 基础动态规划
• 常见贪心