【秋招笔试】8.25蚂蚁秋招-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 编程一对一辅导

✨ 本系列打算持续跟新 春秋招笔试题

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

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 80+ 套笔试题,笔试真题 会在第一时间跟新

🍄 题面描述等均已改编,如果和你笔试题看到的题面描述不一样请理解,做法和题目本质基本不变。

🧩 备战秋招还没订阅的朋友们可以冲一下啦,当试题收集至 100 套后,价格会进行一波调整~

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

alt

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

🍥 本次难度不小,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) {
  

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

学长刷题笔记 文章被收录于专栏

这里收集了超全的刷题笔记,欢迎大家的订阅,会持续跟新的

全部评论
没有算法岗的题解吗
点赞 回复 分享
发布于 08-28 23:57 河南
算法和开发是同一套卷吗
点赞 回复 分享
发布于 08-30 08:35 北京

相关推荐

10-11 17:45
门头沟学院 Java
走吗:别怕 我以前也是这么认为 虽然一面就挂 但是颇有收获!
点赞 评论 收藏
分享
11-06 15:41
门头沟学院 Java
等大佬释放捡剩菜,还有机会吗
普通上班族1:0offer+0池子。
点赞 评论 收藏
分享
2 3 评论
分享
牛客网
牛客企业服务