2025.3.9 蚂蚁笔试(个人整理,仅供参考)

第一题

alt alt

答案

import java.util.Scanner;

public class mayiT1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String s = scanner.nextLine();
        String t = scanner.nextLine();
        scanner.close();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {
                System.out.print(Character.toUpperCase(s.charAt(i)));
            } else if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                System.out.print(Character.toLowerCase(s.charAt(i)));
            } else if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                System.out.print((int) t.charAt(i));
            } else {
                System.out.print('_');
            }
        }
    }
}

第二题

alt alt

思路

二叉树即为特殊的图,用邻接表存储,把编号为1的结点当作根(0,0),dfs求每个点的坐标,即可得出答案。

答案

import java.util.*;

public class mayiT2 {
    static List<Integer>[] tree;
    static Map<Integer, Coordinate> map;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        tree = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int i = 1; i <= n - 1; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            tree[u].add(v);
            tree[v].add(u);
        }
        int root = 1;
        map = new HashMap<>();
        visited = new boolean[n + 1];
        visited[1] = true;
        map.put(root, new Coordinate(0, 0));
        dfs(root);
        for (int i = 0; i < q; i++) {
            int c1 = scanner.nextInt();
            int c2 = scanner.nextInt();
            System.out.println(Math.abs(map.get(c1).getX() - map.get(c2).getX()) + Math.abs(map.get(c1).getY() - map.get(c2).getY()));
        }

        scanner.close();
    }

    private static void dfs(int root) {
        boolean left = true; // 是否是左孩子
        tree[root].sort(Integer::compareTo);
        for (int child : tree[root]) {
            if (!visited[child]) {
                visited[child] = true;
                if (left) {
                    left = false;
                    map.put(child, new Coordinate(map.get(root).getX() - 1, map.get(root).getY() - 1));
                    dfs(child);
                } else {
                    map.put(child, new Coordinate(map.get(root).getX() + 1, map.get(root).getY() - 1));
                    dfs(child);
                }
            }
        }
    }

    static class Coordinate {
        int x;
        int y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }
}

第三题

题目描述

给定n个元素ai,要求计算以下表达式的值:

输入描述

第一行包含一个整数n,表示元素的个数,满足1 ≤ n ≤ 10^5^

第二行包含n个整数a1,a2,...,an,其中1 ≤ ai ≤ 10^5^

输出描述

输出一个整数,表示计算得到的值s

示例1

输入

3
1 2 3

输出

9

说明

对于输入的样例,计算过程如下

具体计算:

当i=1时:1+0+0=1

当i=2时:2+1+0=3

当i=3时:3+1+1=5

将所有结果相加,得到S=1+3+5=9

思路

采用 计数优化 方式

  1. 计数数组 count:统计输入数组中每个数的出现次数,加快后续计算。
  2. 前缀和数组 prefixSum:计算前缀和,用于快速统计某个区间的数的个数。
  3. 优化计算 floor(ai/aj)
    • 直接遍历 ai 并累加 floor(ai / aj) 的贡献,避免双重循环暴力计算,提高效率。

时间复杂度

  • 预处理 countprefixSum:O(n)
  • 计算 S:O(n log n) 级别,优于 O(n²)

答案

import java.util.Scanner;

public class mayiT3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        int maxVal = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
            maxVal = Math.max(maxVal, nums[i]);
        }
        scanner.close();

        // 统计每个数出现的次数
        int[] count = new int[maxVal + 1];
        for (int num : nums) {
            count[num]++;
        }

        // 计算前缀和,用于快速查询小于等于某个数的总个数
        int[] prefixSum = new int[maxVal + 1];
        for (int i = 1; i <= maxVal; i++) {
            prefixSum[i] = prefixSum[i - 1] + count[i];
        }

        long ans = 0;
        // 遍历每个可能的 a[i]
        for (int num = 1; num <= maxVal; num++) {
            if (count[num] == 0) { // 跳过未出现的数
                continue;
            }
            // 计算当前 a[i] 对所有 a[j] 的贡献
            for (int k = 1; k * num <= maxVal; k++) {
                int lower = k * num;
                int upper = Math.min(maxVal, (k + 1) * num - 1);
                int numCount = prefixSum[upper] - prefixSum[lower - 1];
                ans += (long) count[num] * k * numCount;
            }
        }
        System.out.println(ans);
    }
}
#笔试##春招##实习#
全部评论
代码写得真不错
点赞 回复 分享
发布于 03-12 17:02 陕西

相关推荐

评论
1
13
分享

创作者周榜

更多
牛客网
牛客企业服务