【秋招突围】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

可被收藏的 排列分别为:

数据范围

题解

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

具体做法是,对于每个长度 ,我们先假设第一个数字是 ,那么第二个数字就只能从 到 中选择,第三个数字就只能从 到 中选择,以此类推。所以方案数就是 ,其中 表示数字 在数组中出现的次数。

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

时间复杂度为 ,空间复杂