💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🚠 明天有团子的笔试，小伙伴们准备的咋样了

🥄 本次给大家带来24届校招的团子真题卷，希望能帮到大家

🌈 01.K小姐的字符串变换

问题描述

K小姐拿到了一个仅由 、、 三种字母组成的字符串，她打算对这个字符串进行 次变换。每次变换会将字符串中的所有字母按照以下规则同时变换：

• 将 变成
• 将 变成
• 将 变成

请你帮助K小姐计算出 次变换后的字符串。

输入格式

第一行输入一个由 、、 组成的字符串，长度不超过 。

第二行输入一个正整数 ，表示变换的次数。

输出格式

输出变换 次后的字符串。

样例输入

abc
2

样例输出

caababbcbcca

数据范围

• 字符串长度不超过
• 

题解

本题可以通过模拟的方法求解。我们可以将变换过程迭代 次，每次迭代中，遍历字符串的每个字符，根据变换规则生成新的字符串。重复 次后，即可得到最终的字符串。

具体实现时，可以使用一个临时字符串 来存储每次变换后的结果，然后将 赋值给原字符串 ，进行下一次变换。

时间复杂度为 ，其中 为变换次数， 为字符串长度。空间复杂度为 。

参考代码

• Python

s = input()
n = int(input())

for _ in range(n):
    t = ""
    for ch in s:
        if ch == 'a':
            t += "bc"
        elif ch == 'b':
            t += "ca"
        else:
            t += "ab"
    s = t

print(s)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int n = sc.nextInt();
        
        for (int i = 0; i < n; i++) {
            StringBuilder t = new StringBuilder();
            for (char ch : s.toCharArray()) {
                if (ch == 'a') {
                    t.append("bc");
                } else if (ch == 'b') {
                    t.append("ca");
                } else {
                    t.append("ab");
                }
            }
            s = t.toString();
        }
        
        System.out.println(s);
    }
}

• Cpp

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    int n;
    cin >> s >> n;
    
    for (int i = 0; i < n; i++) {
        string t;
        for (char ch : s) {
            if (ch == 'a') {
                t += "bc";
            } else if (ch == 'b') {
                t += "ca";
            } else {
                t += "ab";
            }
        }
        s = t;
    }
    
    cout << s << endl;
    return 0;
}

⚽️ 02.K小姐的数字游戏

问题描述

K小姐有一个由 个正整数组成的数组 ，她想把这个数组中的所有数字求和，即 。现在，她想把其中一个加号变成减号，但由于K小姐还是小学生，不会负数的加减法，因此计算过程中不能出现负数。

K小姐想知道，改变符号后答案的最小值是多少。如果无法改变符号使得计算过程中不出现负数，则输出 。

输入格式

第一行输入一个整数 （），表示数组的长度。

第二行输入 个整数，表示数组 （）。

输出格式

输出改变符号后的答案的最小值，若无法改变符号使得计算过程中不出现负数，则输出 。

样例输入

3
3 2 1

样例输出

2

数据范围

题解

令数组 的前缀和为 ，即 ，。

接下来枚举每个 。由于整个运算过程不能出现负数，因此如果要将 前面的符号转换为负号，那么就意味着 。由于后面的数都是正数，因此不需要考虑后续的影响。

将 从正号变成负号后，数组和从 变成 ，因此本题的答案为：

如果不存在满足条件的 ，则输出 。

本题的关键是利用前缀和来判断是否可以将某个数字前面的符号改为负号，同时用前缀和来计算改变符号后的数组和。通过枚举每个位置，找到满足条件的最小值即可。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

n = int(input())
a = list(map(int, input().split()))

s = [0] * (n + 1)
for i in range(1, n + 1):
    s[i] = s[i - 1] + a[i - 1]

ans = float('inf')
for i in range(1, n + 1):
    if s[i - 1] >= a[i - 1]:
        ans = min(ans, s[n] - 2 * a[i - 1])

print(ans if ans != float('inf') else -1)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }
        
        long[] s = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[i - 1];
        }
        
        long ans = Long.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            if (s[i - 1] >= a[i - 1]) {
                ans = Math.min(ans, s[n] - 2 * a[i - 1]);
            }
        }
        
        System.out.println(ans == Long.MAX_VALUE ? -1 : ans);
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<long long> s(n + 1);
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i - 1];
    }
    
    long long ans = LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] >= a[i - 1]) {
            ans = min(ans, s[n] - 2 * a[i - 1]);
        }
    }
    
    cout << (ans == LLONG_MAX ? -1 : ans) << endl;
    return 0;
}

🍷 03.K小姐的字符串修改

问题描述

K小姐有一个由 和 组成的字符串 。当字符串中存在相邻的相同字符时，可以将这两个相邻字符删除，得到一个新的字符串。重复这个删除操作，直到字符串中不存在相邻的相同字符为止。

现在，K小姐想对这个字符串进行恰好 次修改，每次修改可以将一个 改为 ，或者将一个 改为 。

K小姐想知道，在对字符串 进行恰好 次修改后，再进行删除操作，最终得到的字符串的最短长度是多少？

输入格式

第一行输入两个正整数 和 （），分别表示字符串 的长度和修改次数。

第二行输入一个长度为 的字符串 ，保证 中的字符只包含 和 。

输出格式

输出一个整数，表示在对字符串 进行恰好 次修改后，再进行删除操作，最终得到的字符串的最短长度。

样例输入

4 1
1010

样例输出

2

数据范围

题解

本题可以使用栈来模拟删除操作。首先，我们将字符串 中的字符依次入栈，如果当前字符与栈顶字符相同，则将栈顶字符弹出，否则将当前字符入栈。这样处理完整个字符串后，栈中剩余的字符就是删除操作后的结果。

设栈中剩余字符的个数为 ，则可以形成 对相邻的不同字符。如果 ，那么我们可以将 对相邻的不同字符修改成相同的字符，然后删除，最终得到的字符串长度为 。

如果 ，那么我们可以先将所有相邻的不同字符修改成相同的字符，然后删除。此时还剩下 次修改机会。如果 为奇数，那么无论如何修改，最终都会剩下 个字符；如果 为偶数，那么如果剩下的修改次数为偶数，则最终可以将所有字符删除，得到空串，否则最终会剩下 个字符。

综上