美团笔试真题

美团笔试0308

小牛的文本加密

模拟

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取测试数据组数
        int T = sc.nextInt();
        sc.nextLine(); // 读取换行符，避免下一行读取问题

        // 处理每一组测试数据
        for (int t = 0; t < T; t++) {
            // 读取加密字符串
            String s = sc.nextLine();
            StringBuilder tString = new StringBuilder(); // 解密后的字符串
            int p = 0; // 位移记录

            // 遍历字符串s
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);

                // 如果是数字字符
                if (Character.isDigit(ch)) {
                    int x = ch - '0'; // 将字符转换为数字

                    if (p == 0) {
                        p = x; // 如果p是0，则直接将x赋值给p
                    } else {
                        p = 10 * p + x; // 否则将p左移一位并加上x
                    }
                } else { // 如果不是数字字符
                    // 先将t字符串左移p位
                    if (p > 0) {
                        String tStr = tString.toString();
                        tString.delete(0, p); // 删除前p个字符
                        tString.append(tStr.substring(0, p)); // 将这部分字符添加到末尾
                    }

                    // 重置p
                    p = 0;

                    // 对字符串t进行修改
                    if (ch == 'R') {
                        tString.reverse(); // 如果字符是'R'，则反转字符串t
                    } else {
                        tString.append(ch); // 否则将字符添加到t末尾
                    }
                }
            }

            // 输出解密后的字符串
            System.out.println(tString.toString());
        }

        sc.close();
    }
}

以上代码居然不能ac，会超时。

要优化您的代码，减少不必要的操作，您可以考虑以下几个方面：

减少字符串复制操作： StringBuilder.delete() 和 StringBuilder.append() 的频繁调用可能会引发性能问题。可以通过使用队列或者更直接的操作来减少这些问题。

位移优化： 您在每次位移时，直接删除并追加字符串的做法会导致性能问题，尤其是在字符串长度较大的情况下。可以考虑通过记录偏移量来避免重复操作。

时间复杂度：$O(n^2)$
空间复杂度：O(n)（用于存储字符串和解密后的结果）。

小牛架炮

排序+哈希表

数据结构设计
- Cannon 类：用于表示炮台，包括它的坐标 (x, y) 和它的索引 index。
- Map<Integer, List> rowMap：记录每个行上所有炮台的信息，键是列坐标 y，值是该行上所有炮台的列表。
- Map<Integer, List> colMap：记录每个列上所有炮台的信息，键是行坐标 x，值是该列上所有炮台的列表。
- Cannon[] cannons：存储所有炮台的数组，方便后续的计算。
预处理：存储炮台位置

遍历输入的每个炮台的 (x, y) 坐标，构造炮台对象，并将其放入对应行和列的 rowMap 和 colMap 中。
排序

对每一行和每一列的炮台按坐标排序：
对 rowMap 中的每个列表按 x 坐标升序排列。
对 colMap 中的每个列表按 y 坐标升序排列。这样排序是为了方便后续通过二分查找定位炮台的位置，从而更容易判断哪些炮台是可以被攻击到的。
计算每个炮台能攻击到的目标数

对于每个炮台：
同行：找到它所在行的所有炮台，利用二分查找确定该炮台在同行中的位置。然后检查它左边和右边是否有其它炮台，若存在，且它们距离该炮台不超过一个单位，它们就可以被攻击。
同列：同样的方法处理同列的炮台，判断它上边和下边是否有可以攻击到的炮台。
对于同行和同列的炮台，加入一个 targets 集合，以避免重复计算。
输出

最后，输出每个炮台能够攻击到的炮台的数量，即 targets 集合的大小。

import java.util.*;

public class Main {
    static class Cannon {
        int x, y, index;
        
        Cannon(int x, int y, int index) {
            this.x = x;
            this.y = y;
            this.index = index;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 使用HashMap预处理，存储同行和同列的炮
        Map<Integer, List<Cannon>> rowMap = new HashMap<>();
        Map<Integer, List<Cannon>> colMap = new HashMap<>();
        Cannon[] cannons = new Cannon[n];
        
        // 读取输入的同时进行预处理
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            Cannon cannon = new Cannon(x, y, i);
            cannons[i] = cannon;
            
            // 将炮添加到对应的行和列中
            rowMap.computeIfAbsent(y, k -> new ArrayList<>()).add(cannon);
            colMap.computeIfAbsent(x, k -> new ArrayList<>()).add(cannon);
        }
        
        // 预先对每行每列的炮进行排序
        for (List<Cannon> row : rowMap.values()) {
            row.sort((a, b) -> Integer.compare(a.x, b.x));
        }
        for (List<Cannon> col : colMap.values()) {
            col.sort((a, b) -> Integer.compare(a.y, b.y));
        }
        
        // 计算每个炮可以攻击到的目标数
        for (int i = 0; i < n; i++) {
            Cannon current = cannons[i];
            Set<Integer> targets = new HashSet<>();
            
            // 检查同行的炮
            List<Cannon> sameRow = rowMap.get(current.y);
            if (sameRow != null && sameRow.size() > 1) {
                // 找到当前炮在行中的位置
                int pos = Collections.binarySearch(sameRow, current, 
                    (a, b) -> Integer.compare(a.x, b.x));
                
                // 检查左边
                if (pos > 1) {
                    targets.add(sameRow.get(pos-2).index);
                }
                // 检查右边
                if (pos < sameRow.size()-2) {
                    targets.add(sameRow.get(pos+2).index);
                }
            }
            
            // 检查同列的炮
            List<Cannon> sameCol = colMap.get(current.x);
            if (sameCol != null && sameCol.size() > 1) {
                // 找到当前炮在列中的位置
                int pos = Collections.binarySearch(sameCol, current, 
                    (a, b) -> Integer.compare(a.y, b.y));
                
                // 检查下边
                if (pos > 1) {
                    targets.add(sameCol.get(pos-2).index);
                }
                // 检查上边
                if (pos < sameCol.size()-2) {
                    targets.add(sameCol.get(pos+2).index);
                }
            }
            
            System.out.println(targets.size());
        }
    }
}