百度笔试真题

百度笔试0315

数组删除

哈希表

用哈希表统计出每个数字的出现次数，然后将出现次数在[l,r]范围内的数字加到集合中，再重新构造数组，出现在集合中的不再添加入结果。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取测试数据的组数 T
        int T = sc.nextInt();
        
        // 处理每组测试数据
        for (int t = 0; t < T; t++) {
            // 读取 n, l, r
            int n = sc.nextInt();
            int l = sc.nextInt();
            int r = sc.nextInt();
            
            // 读取数组 a
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            
            // 使用 HashMap 统计每个数字的出现次数
            Map<Integer, Integer> countMap = new HashMap<>();
            for (int num : a) {
                countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            }
            
            // 筛选出需要删除的数字
            Set<Integer> toRemove = new HashSet<>();
            for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
                int count = entry.getValue();
                if (count >= l && count <= r) {
                    toRemove.add(entry.getKey());
                }
            }
            
            // 构造操作后的数组
            List<Integer> result = new ArrayList<>();
            for (int num : a) {
                if (!toRemove.contains(num)) {
                    result.add(num);
                }
            }
            
            // 输出结果
            System.out.println(result.size());
            for (int num : result) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
        
        sc.close();
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

最大的和

贪心

1. 输入处理：使用 BufferedReader 与 StringTokenizer 读取输入数据，保证在大数据量下速度较快。
2. 计算增益：遍历数组，对每个元素计算 delta = (a[i] ^ x) - a[i]。将所有正增益累加，并统计个数、记录正增益最小值；同时对于非正（≤0）增益记录其中的最大值（注意此处包括0）。
3. 决策过程：如果正增益的个数为偶数，则直接选择这些正增益；如果为奇数，则尝试两种方案：舍弃一个正增益（使正增益个数减为偶数）或额外选择一个非正增益，使整体翻转个数变为偶数，取两者中效果较优者。同时若调整方案使得总增益为负，则选择不翻转任何元素（即增益为0）。
4. 输出结果：最后输出原数组和加上最终获得的额外增益。

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        
        for (int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            
            int[] a = new int[n];
            st = new StringTokenizer(br.readLine());
            long total = 0;
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
                total += a[i];
            }
            
            // 计算每个位置翻转的增益 delta = (a ^ x) - a
            long S = 0; // 正增益总和
            int countPositive = 0; 
            int minPositive = Integer.MAX_VALUE; // 正增益中最小的
            int maxNonPositive = Integer.MIN_VALUE; // 非正增益中最大的
            for (int i = 0; i < n; i++) {
                int xorVal = a[i] ^ x;
                int delta = xorVal - a[i];
                if (delta > 0) {
                    S += delta;
                    countPositive++;
                    minPositive = Math.min(minPositive, delta);
                } else {
                    maxNonPositive = Math.max(maxNonPositive, delta);
                }
            }
            
            long extra = 0;
            if (countPositive % 2 == 0) {
                // 如果正增益个数为偶数，直接选择所有正增益
                extra = S;
            } else {
                // 正增益个数为奇数，必须调整
                long optionA = S - minPositive; // 舍弃正增益中最小的
                long optionB = Long.MIN_VALUE;
                if (maxNonPositive != Integer.MIN_VALUE) {
                    // 如果存在非正增益，则可以考虑额外选一个非正增益
                    optionB = S + maxNonPositive;
                }
                extra = Math.max(optionA, optionB);
                // 如果调整后增益为负，则不进行任何翻转
                extra = Math.max(extra, 0);
            }
            long ans = total + extra;
            sb.append(ans).append("\n");
        }
        System.out.print(sb);
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)，输入数组不计入。

总结

题目看着不难，写起来并不容易。之后再好好复习一下。