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

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

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

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

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

🪔蚂蚁笔试题来啦！！！！

🍥 本次难度不小，T2和T3都比较难写

1️⃣ 结论题

2️⃣ 枚举+贪心，细节比较容易出错

3️⃣ bitset优化

📚 01.LYA 的括号序列拼接

问题描述

LYA 是一位热爱编程的高中生，最近她在学习数据结构时对括号序列产生了浓厚的兴趣。她发现，如果在括号序列中适当地插入加号和数字 1，就可以得到一个合法的算术表达式。

例如，"(())" 可以变成 "((1))"，"()()" 可以变成 "(1)+(1)"，这些都是合法的表达式。

现在，LYA 手头有四种不同的括号片段：

1. 个 "(("
2. 个 "))"
3. 个 "()"
4. 个 ")("

LYA 想知道，是否可以将这些括号片段拼接成一个合法的括号序列。你能帮助她解决这个问题吗？

输入格式

输入的第一行是一个整数 ，表示测试数据的组数。

接下来的 行，每行包含四个整数 ，分别表示 LYA 拥有的四种括号片段的数量。

输出格式

对于每组测试数据，如果能够将给定的括号片段拼接成一个合法的括号序列，输出一行 "YES"，否则输出一行 "NO"。

样例输入

2
1 1 1 1
1 2 1 1

样例输出

YES
NO

数据范围

题解

结论题

要构成合法的括号序列，需要满足以下条件：

1. 左括号和右括号的数量必须相等。
2. 在任何前缀中，左括号的数量必须大于或等于右括号的数量。

基于这些条件，我们可以得出以下结论：

1. "((" 和 "))" 的数量必须相等，即 。
2. 如果存在 ")(" 片段（），那么必须有 "((" + "))"片段（）来匹配它。

因此，判断条件可以简化为：

1. 如果 ，则无法构成合法序列。
2. 如果 且 ，则无法构成合法序列。
3. 其他情况下，都可以构成合法序列。

时间复杂度： 空间复杂度：

参考代码

• Python

# 读取测试用例数量
t = int(input())

# 处理每个测试用例
for _ in range(t):
    # 读取四种括号片段的数量
    a, b, c, d = map(int, input().split())
    
    # 判断是否可以构成合法括号序列
    if a != b:
        print("NO")  # 左右括号数量不匹配
    elif d > 0 and a == 0:
        print("NO")  # 存在")("但没有 "((" + "))" 匹配
    else:
        print("YES")  # 其他情况均可构成合法序列

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();  // 读取测试用例数量

        for (int i = 0; i < t; i++) {
            // 读取四种括号片段的数量
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            int d = scanner.nextInt();

            // 判断是否可以构成合法括号序列
            if (a != b) {
                System.out.println("NO");  // 左右括号数量不匹配
            } else if (d > 0 && a == 0) {
                System.out.println("NO");  // 存在")("但没有 "((" + "))" 匹配
            } else {
                System.out.println("YES");  // 其他情况均可构成合法序列
            }
        }
        scanner.close();
    }
}

• Cpp

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;  // 读取测试用例数量

    while (t--) {
        int a, b, c, d;
        // 读取四种括号片段的数量
        cin >> a >> b >> c >> d;

        // 判断是否可以构成合法括号序列
        if (a != b) {
            cout << "NO" << endl;  // 左右括号数量不匹配
        } else if (d > 0 && a == 0) {
            cout << "NO" << endl;  // 存在")("但没有 "((" + "))" 匹配
        } else {
            cout << "YES" << endl;  // 其他情况均可构成合法序列
        }
    }
    return 0;
}

🌸 02.K小姐的完美数字

问题描述

K小姐是一位数字艺术家，她对数字有着独特的审美。在她眼中，一个完美的数字应该是每一位数字都不重复的。现在，她正在创作一件数字艺术品，需要为作品选择一个完美数字。她已经有了一个初步的想法，但她想知道，在不小于这个初步想法的所有可能数字中，最小的完美数字是多少。

例如，如果她的初步想法是 1233，那么最小的完美数字应该是 1234。如果初步想法是 9876，那么最小的完美数字就是 9876 本身。

请你帮助 K小姐 找出这个最小的完美数字。

输入格式

第一行输入一个正整数 ，表示测试用例的数量。

接下来的 行，每行输入一个正整数 ，表示 K小姐 的初步想法。

输出格式

对于每个测试用例，输出一行，表示不小于初步想法的最小完美数字。

样例输入

3
1233
9876
1

样例输出

1234
9876
1

数据范围

题解

贪心+枚举，从右向左遍历数字的每一位。

1. 如果当前位的数字在之前没有出现过，继续向左遍历。
2. 如果遇到重复的数字，将该位数字增加到一个未使用过的数字。
3. 如果增加后导致进位，则继续向左处理。
4. 对于修改位右侧的所有数字，重新填充未使用过的最小数字。
5. 如果整个数字都处理完仍无法得到完美数字，则需要增加一位。

参考代码

• Python

def find_next_perfect(s):
    n = len(s)
    pos = -1
    
    # 找到第一个重复的数字
    for i in range(n):
        if s[:i].find(s[i]) != -1:
            pos = i
            break
    

    if pos == -1:
        return s
    
    # 找到第一个可以增加的数位
    while pos >= 0:
        k = 1
        while str(int(s[pos]) + k) in s[:pos]:
            k += 1
        if int(s[pos]) + k < 10:
            s = s[:pos] + str(int(s[pos]) + k) + s[pos+1:]
            break
        pos -= 1
    
    if pos == -1:
        s = ''.join([str(i) for i in range(1, n + 2)])
        s = s[0] + '0' + s[1:]
    else:
        used = set(s[:pos+1])
        all_dig = [str(c) for c in range(10) if str(c) not in used]
        all_dig.sort()
        for i in range(pos + 1, n):
            s = s[:i] + all_dig.pop(0) + s[i+1:]
    
    return s

def main():
    t = int(input())
    for _ in range(t):
        s = input()
        print(find_next_perfect(s))

if __name__ == "__main__":
    main()

• Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            char[] s = br.readLine().toCharArray();
            System.out.println(findNextPerfect(s));
        }
    }

    public static String findNextPerfect(char[] s) {
        int n = s.length;
        int pos = -1;
        // 找到第一个重复的数字
        for (int i = 0; i < n; i++) {
            if (new String(s, 0, i).indexOf(s[i]) != -1) {
                pos = i;
                break;
            }
        }
        if (pos == -1) {
            return new String(s);
        }
        // 找到第一个可以增加的数位
        while (pos >= 0) {
            int k = 1;
            while (new String(s, 0, pos).indexOf(Character.forDigit(s[pos] - '0' + k, 10)) != -1) {
                k++;
            }
            if (s[pos] - '0'