蚂蚁笔试 蚂蚁金服 蚂蚁笔试题 0320
笔试时间：2025年03月20日
历史笔试传送门：
第一题
题目：圈圈的字符串
小红酷爱圈圈字符。小红认为:"a'，b，d，e,g，o，p，q]这些字符为圈圈字符，因为它们都带有一个圆圈。我们认为一个字符串是圈圈字符串当前仅当这个字符串中的圈圈字符数量大于非圈圈字符数量。现在小红打算把这个字符串分成若干个非空字符串，请你帮助她求出这些非空字符串中最多可以有多少个圈圈字符串。
输入描述
一个字符串 8，输入保证仅含小写字母且长度不超过 10^5。
输出描述
1个整数，表示最多可以切出多少个圈圈字符串。
样例输入
abc
样例输出
2
参考题解
要最大化分割出的圈圈字符串数量，可以采用贪心策略：每当当前子串满足圈圈字符数大于非圈圈字符数时，立即将其分割出来。这样可以确保后续字符有更多机会形成新的有效子串。判断圈圈字符：使用集合存储所有圈圈字符，便于快速判断。遍历字符串：维护一个平衡值 balance，遇到圈圈字符加1，否则减1。及时分割：当 balance 大于0时，说明当前子串有效，立即分割，并重置 balance 以处理后续字符。统计结果：每次分割时计数，最终结果即为最大可能的分割数。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int main() {
string str;
cin >> str;
// 定义圈圈字符集合
unordered_set<char> circle_chars = {'a', 'b', 'd', 'e', 'g', 'o', 'p', 'q'};
int max_count = 0; // 记录最大圈圈字符串数量
int current_balance = 0; // 当前字符的平衡值
for (char c : str) {
// 更新平衡值：圈圈字符加1，非圈圈减1
current_balance += circle_chars.count(c) ? 1 : -1;
// 当平衡值为正时，分割并重置
if (current_balance > 0) {
max_count++;
current_balance = 0;
}
}
cout << max_count << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
Set<Character> circleChars = new HashSet<>(Arrays.asList('a', 'b', 'd', 'e', 'g', 'o', 'p', 'q'));
int maxCount = 0;
int currentBalance = 0;
for (char c : str.toCharArray()) {
currentBalance += circleChars.contains(c) ? 1 : -1;
if (currentBalance > 0) {
maxCount++;
currentBalance = 0;
}
}
System.out.println(maxCount);
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
circle_chars = {'a', 'b', 'd', 'e', 'g', 'o', 'p', 'q'}
s = input()
max_count = 0
current_balance = 0
for c in s:
current_balance += 1 if c in circle_chars else -1
if current_balance > 0:
max_count += 1
current_balance = 0
print(max_count)
第二题
题目：小苯的数组
小苯有一个长度为 n, 的数组 a，他希望你在 a 上维护两种操作，具体来说:修改:他每次给出一个数字 v，表示a 中所有的数字和 υ取较小者。形式化的:对于i(1 <=i<= n)，执行:ai := min(ai,v)。查询:查询数组中所有数字的和是多少。他觉得这个问题过于困难，请你帮他处理一下这些操作吧。
输入描述
本题有多组测试数据。输入的第一行包含一个正整数 T(1 < T < 100)，表示数据组数。接下来包含 T 组数据，每组数据的格式如下:第一行两个正整数 n,q(1 < n,q < 2 x 10^5)，分别表示数组 a 的长度和操作的次数。第二行 n, 个正整数 a¡(1 < a < 10^9)，表示数组 a。接下来 n 行，每行一个操作，输入格式为:1 v表示修改操作(1 < υ< 109)2 表示查询操作。(保证所有测试数据中，n,q的总和都不超过2x10^5。)
输出描述
对于每组测试数据:对于每个 2 操作，输出一行一个整数表示答案。
样例输入
1
5 3
1 2 3 4 5
2
1 2
2
样例输出
15
9
解释：首先查询数组的总和为:1-2+4+5+3=15.接着我们进行一次操作，将所有元素和v=2取 min，数组变为:{1,2,2,2,2}。再次查询数组的总和为:1十2十2+2+2=9。
参考题解
数据结构选择：使用有序映射（std::map）来维护数组中不同数值及其出现次数，利用其自动排序特性高效处理范围查询。总和维护：维护一个全局总和变量，每次修改操作时直接更新，避免每次查询时重新计算。修改操作处理：对于每个修改操作，找到所有比目标值大的元素，调整总和并将这些元素的计数合并到目标值对应的条目中。高效元素处理：利用二分查找快速定位需要处理的元素范围，确保每个元素最多被处理有限次，均摊时间复杂度合理。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
using ll = long long; // 使用长整型以避免溢出
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); // 优化输入输出
int T;
cin >> T;
while (T--) {
int n, q;
cin >> n >> q;
vector<int> arr(n);
map<int, int> num_counts; // 数值到出现次数的有序映射
ll total = 0;
// 读取初始数组并初始化映射和总和
for (int i = 0; i < n; ++i) {
cin >> arr[i];
num_counts[arr[i]]++;
total += arr[i];
}
while (q--) {
int op;
cin >> op;
if (op == 1) { // 处理修改操作
int val;
cin >> val;
auto it = num_counts.upper_bound(val); // 找到第一个大于val的数的位置
int merged_count = 0;
// 合并所有大于val的数到val
while (it != num_counts.end()) {
int num = it->first;
int cnt = it->second;
total -= (ll)(num - val) * cnt; // 更新总和
merged_count += cnt; // 累计合并次数
it = num_counts.erase(it); // 删除原记录
}
if (merged_count > 0) {
num_counts[val] += merged_count; // 合并到val的计数中
}
} else { // 处理查询操作
cout << total << '\n';
}
}
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.uti
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
投递蚂蚁集团等公司9个岗位 >
查看18道真题和解析