蚂蚁笔试0309第三题

7 道多选 4 道单选：设计模式，计算机网络，操作系统，数据结构，kmp，排序算法等java 2 道单选，2 道多远：基础知识，代码结果，==，equals ，hashcode 三道编程题第一题签到题，模拟判断输出第二题树上曼哈顿距离，建树然后算，只过了 25第三题，求数组的各个序对相除求和，暴力 20，二分好像可以又菜了#蚂蚁# #蚂蚁求职进展汇总# #软件开发笔面经# #实习# #大厂#

蚂蚁第一题 签到题，按着规则一个一个字符来就行第二题 数上节点的曼哈顿距离首先对连线排序，根据第一个值从小到大排，相同时根据第二个值从小大到排，Hashset记录某节点有没有子树，HashMap记录节点的坐标 然后按序遍历连线，父节点没有子树的话，该节点就是左子树（x-1,y-1)，有的话就是右子树(x+1,y-1)。 第三题 求所有i和j组合的 nums[i] / nums[j]题目范围是 105，逐个遍历O(n²)一定会超时由于nums[i]的范围是105之内，对于重复的分子会有很多重复的结果。我们可以枚举每个值作为分母的情况。对于nums[i], 区间 [ k*nums[i] , ...

1，模拟一下就好，别忘了处理换行和回车，代码略。2，bfs一下，找出每个点的坐标，o1输出就可以了。void bfs(int u) {    queue q;    q.push(u);    pos[u] = {0, 0};    mark[u] = 1;    while (q.size() > 0) {        int v = q.front();        q.pop();        int l = - 1, r = -1;        for (auto x : g[v]) {            if (mark[x]) continue;            mark[x] = 1;            q.push(x);            if (l == -1) l = x;            else {                r = x;                if (l > r) swap(l, r);             }        }        if (l != -1) {            pos[l] = pair(pos[v].x - 1, pos[v].y - 1);        }        if (r != -1) {            pos[r] = pair(pos[v].x + 1, pos[v].y - 1);        }    } }3，可以发现，我们要计算的是每个数整除其他数之后的和。其实可以反过来想，我们要计算每个数作为除数，其他数除他之后的和。对于数i来说，[j * i, j * i + i - 1]这个范围内的数除以i等于j，那我们可以枚举每个i和每个j，维护一个前缀和来快速算出[j * i, j * i + i - 1]这个范围内的贡献，贡献数是i的数量 * 范围内数的个数 * j。时间复杂度是n + n/2 + n /3 +... = nlogn代码如下，cnt[i]是数字i的数量，sum[i]是前cnt[i]的前缀和，N是数的最大范围1e5;    for (int i = 1; i < N; i ++) {        if (cnt[i] == 0) continue;        for (int j = 1; j * i < N; j ++) {            res += 1ll * (sum[min(i * j + i - 1, N - 1)] - sum[i * j - 1]) * cnt[i] * j;        }    }#笔试# #蚂蚁# #蚂蚁笔试#

2025年3月9日 19：00-20：40选择题45分：7道基础单选，4道基础不定项，2道 Java 单选，2道 Java 不定项考点：计算机网络、操作系统、设计模式、数据库、二叉树、Java 内存地址…编程题55分：字符串对照实验：第一行输入一个字符串长度，第二行输入一个字符串，第三行输入一个字符串（仅有大小写字母）。若第 1 个字符串在第 i 个位置的字符为大写字母，则输出第 2 个字符串在第 i 个位置的字符的大写字母；若第 1 个字符串在第 i 个位置的字符为小写字母，则输出第 2 个字符串在第 i 个位置的字符的小写字母；若第 1 个字符串在第 i 个位置的字符为数字，则输出第...