【秋招笔试】8.25蚂蚁秋招-三语言题解
🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 编程一对一辅导
✨ 本系列打算持续跟新
春秋招笔试题
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
🍒 本专栏已收集
80+
套笔试题,笔试真题
会在第一时间跟新🍄 题面描述等均已改编,如果和你笔试题看到的题面描述不一样请理解,做法和题目本质基本不变。
🧩 备战秋招还没订阅的朋友们可以冲一下啦,当试题收集至
100
套后,价格会进行一波调整~🍹 感谢各位朋友们的订阅,你们的支持是我们创作的最大动力 💞
🪔蚂蚁笔试题来啦!!!!
🍥 本次难度不小,T2和T3都比较难写
1️⃣ 结论题
2️⃣ 枚举+贪心,细节比较容易出错
3️⃣ bitset优化
📚 01.LYA 的括号序列拼接
问题描述
LYA 是一位热爱编程的高中生,最近她在学习数据结构时对括号序列产生了浓厚的兴趣。她发现,如果在括号序列中适当地插入加号和数字 1,就可以得到一个合法的算术表达式。
例如,"(())" 可以变成 "((1))","()()" 可以变成 "(1)+(1)",这些都是合法的表达式。
现在,LYA 手头有四种不同的括号片段:
- 个 "(("
- 个 "))"
- 个 "()"
- 个 ")("
LYA 想知道,是否可以将这些括号片段拼接成一个合法的括号序列。你能帮助她解决这个问题吗?
输入格式
输入的第一行是一个整数 ,表示测试数据的组数。
接下来的 行,每行包含四个整数 ,分别表示 LYA 拥有的四种括号片段的数量。
输出格式
对于每组测试数据,如果能够将给定的括号片段拼接成一个合法的括号序列,输出一行 "YES",否则输出一行 "NO"。
样例输入
2
1 1 1 1
1 2 1 1
样例输出
YES
NO
数据范围
题解
结论题
要构成合法的括号序列,需要满足以下条件:
- 左括号和右括号的数量必须相等。
- 在任何前缀中,左括号的数量必须大于或等于右括号的数量。
基于这些条件,我们可以得出以下结论:
- "((" 和 "))" 的数量必须相等,即 。
- 如果存在 ")(" 片段(),那么必须有 "((" + "))"片段()来匹配它。
因此,判断条件可以简化为:
- 如果 ,则无法构成合法序列。
- 如果 且 ,则无法构成合法序列。
- 其他情况下,都可以构成合法序列。
时间复杂度: 空间复杂度:
参考代码
- 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
数据范围
题解
贪心+枚举,从右向左遍历数字的每一位。
- 如果当前位的数字在之前没有出现过,继续向左遍历。
- 如果遇到重复的数字,将该位数字增加到一个未使用过的数字。
- 如果增加后导致进位,则继续向左处理。
- 对于修改位右侧的所有数字,重新填充未使用过的最小数字。
- 如果整个数字都处理完仍无法得到完美数字,则需要增加一位。
参考代码
- 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%内容,订阅专栏后可继续查看/也可单篇购买
这里收集了超全的刷题笔记,欢迎大家的订阅,会持续跟新的