小米校招笔试编程题

moye Lv6
  2024-10-12 09:14:18 2024-10-12 09:14:18 创建   2025-12-11 14:39:48 2025-12-11 14:39:48 更新      

题 1

题目描述：

小明在研究一个有趣的数组翻转操作问题，其中为了考虑均衡，他会同时翻转相邻的两个数。他有一个长度为 N 的数组 a[]，并可以进行任意次数操作：选择相邻的两个数，翻转这两个数的符号，即将 a[i] 和 a[i+1] (0 ≤ i ≤ n-1) 的符号都翻转。符号翻转的意思是正数变负数，负数变正数，在程序中即 `num = -num`，也即数字中的取相反数；当然 0 翻转后还是 0。小明的任务是找到经过任意次数（可以为 0 次）这些操作后，能够获得的最优数组 a[]。

输入描述：

第一行包含一个整数 N，表示数组的长度。
第二行包含 N 个整数，a[1], a[2],…, a[N]。
1 ≤ N ≤ 30000，−1000000000 ≤ a[i] ≤ 1000000000。

输出描述：

输出一个整数，表示经过任意次数操作后数组的最大和。

思路

解题思路：

  1. 理解题目：

    • 可以选择任意次数的操作，每次操作翻转相邻的两个数的符号。
    • 翻转操作只能改变偶数个元素的符号，无法单独翻转一个元素的符号。
    • 目标是通过这些操作，使数组的总和最大。

  2. 关键分析：

    • 翻转相邻的两个数，相当于同时翻转这两个数的符号。
    • 通过多次操作来翻转任意偶数个元素的符号。
    • 如果能翻转所有负数的符号，那么数组的总和会增加。
    • 但是，如果负数的个数是奇数，无法全部翻转负数的符号。

  3. 算法步骤：

    • 初始化：

      • 计算数组的初始和 S0。
      • 定义 SumPos 记录翻转负数后的总收益（负数变正数增加的值）。
      • 定义 n_neg 记录数组中负数的个数。
      • 定义 MinPos 记录翻转负数后最小的收益（即绝对值最小的负数翻转后增加的值）。
      • 定义 MaxNeg 记录翻转正数后最大的损失（即绝对值最小的正数翻转后减少的值）。

    • 遍历数组元素：

      • 对于每个元素 a[i]：
        • 计算翻转该元素符号后对总和的影响 delta = -2 * a[i]。
        • 如果 a[i] 是负数：
          • 将 delta（正值）加到 SumPos 上。
          • n_neg 加 1。
          • 更新 MinPos，使其为最小的 delta。
        • 如果 a[i] 是正数：
          • 更新 MaxNeg，使其为最大的 delta（负值，绝对值最小的正数）。

    • 计算最大总和：

      • 如果负数的个数是偶数：
        • 可以翻转所有负数，最大总和为 S0 + SumPos。
      • 如果负数的个数是奇数：
        • 方案一： 翻转除了收益最小的那个负数外的所有负数，最大总和为 S0 + SumPos - MinPos。
        • 方案二： 翻转所有负数，并额外翻转一个正数（损失最小的正数），最大总和为 S0 + SumPos + MaxNeg。
        • 选择两者中的最大值作为最终结果。

  4. 注意事项：

    • 当没有正数可供翻转时（即数组全为负数），只能选择方案一。
    • 翻转正数会减少总和，所以要选择损失最小的正数进行翻转。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int N = in.nextInt();
        long[] a = new long[N];
        long S0 = 0;          // 初始数组和
        long SumPos = 0;      // 翻转负数后的总收益
        int n_neg = 0;        // 负数的个数
        long MinPos = Long.MAX_VALUE;   // 翻转负数后的最小收益
        long MaxNeg = Long.MIN_VALUE;   // 翻转正数后的最大损失

        for (int i = 0; i < N; i++) {
            a[i] = in.nextLong();
            S0 += a[i];
            long delta = -2 * a[i];
            if (a[i] < 0) {
                SumPos += delta;  // delta 为正值
                n_neg++;
                if (delta < MinPos) {
                    MinPos = delta;  // 更新最小收益
                }
            } else {
                // delta 为负值
                if (delta > MaxNeg) {
                    MaxNeg = delta;  // 更新最大损失
                }
            }
        }

        long totalSum;
        if (n_neg % 2 == 0) {
            // 负数个数为偶数，翻转所有负数
            totalSum = S0 + SumPos;
        } else {
            // 负数个数为奇数
            // 方案一：不翻转收益最小的负数
            long option1 = S0 + SumPos - MinPos;
            if (MaxNeg != Long.MIN_VALUE) {
                // 方案二：额外翻转一个正数
                long option2 = S0 + SumPos + MaxNeg;
                totalSum = Math.max(option1, option2);  // 选择最大值
            } else {
                totalSum = option1; // 没有正数可翻转，只能选择方案一
            }
        }
        System.out.println(totalSum);
    }
}

复杂度分析：

  • 时间复杂度： O(N)，其中 N 为数组的长度。只需遍历数组一次。
  • 空间复杂度： O(1)，除了存储输入数组外，额外空间使用常数级别的变量。

题 2

题目描述：

小明正在欣赏他的一串宝石项链，这个项链还没有封口，是一条链，初始时从左到右宝石分别编号为 (1, 2, 3, …, n)。然而经过一段时间观赏后，小明觉得他应该把某些宝石取下，放到项链的前面或后面去。小明现在正式进行调整项链，想请你帮忙模拟一下他的若干次调整，看看最后的项链顺序。

输入描述：

  • 第一行包含两个整数 n 和 q，分别表示宝石的数量和操作次数。
  • 第二行包含 3q 个整数 a_1, b_1, op_1, a_2, b_2, op_2, ..., a_q, b_q, op_q，表示每次操作的参数。

限制条件

  • $1 \leq n, q \leq 50000$
  • $1 \leq a_i, b_i \leq n$
  • $a_i \neq b_i$

输出描述：

输出一行整数，表示所有操作完成后，宝石从左到右的顺序。

输入示例：

1
2
5 3
1 2 1 3 2 0 5 4 0

输出示例：

1
3 2 1 5 4

操作过程解释：

  • 初始的宝石顺序是 1 2 3 4 5。
  1. 第一次操作：把编号 1 的宝石取下，放到编号 2 的后面。
  2. 第二次操作：把编号 3 的宝石取下，放到编号 2 的前面。
  3. 第三次操作：把编号 5 的宝石取下，放到编号 4 的前面。

思路

问题描述：

小明正在欣赏他的一串宝石项链，这个项链还没有封口，是一条链，初始时从左到右宝石分别编号为 (1, 2, 3, \dots, n)。他想通过多次操作来调整宝石的顺序，每次操作将某个宝石取下，放到另一个宝石的前面或后面。任务是模拟这些操作，输出最终项链的宝石顺序。

解题思路：

为了高效地模拟宝石的移动操作，使用双向链表的数据结构。但由于操作次数和宝石数量较大（最高可达 50000），所以需要一个能够在常数时间内完成插入和删除操作的数据结构。利用数组来模拟链表：

  1. 初始化链表：

    • left[] 数组： left[i] 存储编号为 i 的宝石左边相邻宝石的编号。
    • right[] 数组： right[i] 存储编号为 i 的宝石右边相邻宝石的编号。
    • 初始时，宝石按照编号从左到右排列，构建初始的双向链表。

  2. 执行操作：

    • 移除宝石 ai：
      • 如果 ai 的左邻宝石存在（left[ai] ≠ 0），则将其右邻接到 ai 的右邻宝石上：right[left[ai]] = right[ai]。
      • 如果 ai 的右邻宝石存在（right[ai] ≠ 0），则将其左邻接到 ai 的左邻宝石上：left[right[ai]] = left[ai]。
      • 断开 ai 自身的链接（可选，因为后续会重新设置 ai 的 left 和 right）。
    • 插入宝石 ai 到宝石 bi 的前面或后面：
      • 如果 op = 0（插到前面）：
        • left[ai] = left[bi]；
        • right[ai] = bi；
        • 如果 left[bi] ≠ 0，则 right[left[bi]] = ai；
        • left[bi] = ai。
      • 如果 op = 1（插到后面）：
        • left[ai] = bi；
        • right[ai] = right[bi]；
        • 如果 right[bi] ≠ 0，则 left[right[bi]] = ai；
        • right[bi] = ai。

  3. 输出结果：

    • 找到链表的头部（left[i] = 0 的宝石 i）。
    • 从头开始，按照 right 指针遍历整个链表，输出宝石编号。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner  = new Scanner(System.in);
        int n = scanner.nextInt(); // 宝石数量
        int q = scanner.nextInt(); // 操作次数

        int[] left = new int[n + 1];  // left[i] 表示编号为 i 的宝石左边的宝石编号
        int[] right = new int[n + 1]; // right[i] 表示编号为 i 的宝石右边的宝石编号

        // 初始化链表
        for (int i = 1; i <= n; i++) {
            left[i] = i - 1;
            right[i] = i + 1;
        }
        left[1] = 0;      // 第一个宝石左边没有宝石
        right[n] = 0;     // 最后一个宝石右边没有宝石

        // 读取操作
        int[] ai = new int[q];
        int[] bi = new int[q];
        int[] op = new int[q];
        for (int i = 0; i < q; i++) {
            ai[i] = scanner.nextInt();
            bi[i] = scanner.nextInt();
            op[i] = scanner.nextInt();
        }

        // 执行操作
        for (int i = 0; i < q; i++) {
            int a = ai[i];
            int b = bi[i];
            int operation = op[i];

            // 移除宝石 a
            int aLeft = left[a];
            int aRight = right[a];

            if (aLeft != 0) {
                right[aLeft] = aRight;
            }
            if (aRight != 0) {
                left[aRight] = aLeft;
            }

            // 插入宝石 a 到宝石 b 的前面或后面
            if (operation == 0) {
                // 插到前面
                left[a] = left[b];
                right[a] = b;
                if (left[b] != 0) {
                    right[left[b]] = a;
                }
                left[b] = a;
            } else {
                // 插到后面
                left[a] = b;
                right[a] = right[b];
                if (right[b] != 0) {
                    left[right[b]] = a;
                }
                right[b] = a;
            }
        }

        // 找到链表头部
        int current = 0;
        for (int i = 1; i <= n; i++) {
            if (left[i] == 0) {
                current = i;
                break;
            }
        }

        // 输出最终宝石顺序
        StringBuilder result = new StringBuilder();
        while (current != 0) {
            result.append(current).append(" ");
            current = right[current];
        }
        // 去除最后一个空格并输出
        System.out.println(result.toString().trim());
    }
}

示例输入输出：

输入：

1
2
5 3
1 2 1 3 2 0 5 4 0

输出：

1
3 2 1 5 4

解释：

  • 初始状态： 1 2 3 4 5
  • 操作 1： 将宝石 1 移到宝石 2 的后面，结果：2 1 3 4 5
  • 操作 2： 将宝石 3 移到宝石 2 的前面，结果：3 2 1 4 5
  • 操作 3： 将宝石 5 移到宝石 4 的前面，结果：3 2 1 5 4

复杂度分析：

  • 时间复杂度： O(n + q)，其中 n 是宝石数量，q 是操作次数。

    • 初始化链表需要 O(n) 时间。
    • 每次操作的时间复杂度为 O(1)，共执行 q 次操作。
    • 遍历链表输出结果需要 O(n) 时间。

  • 空间复杂度： O(n)，需要存储 left[] 和 right[] 数组，每个大小为 n+1。

  • 标题: 小米校招笔试编程题
  • 作者: moye
  • 创建于 : 2024-10-12 09:14:18
  • 更新于 : 2025-12-11 14:39:48
  • 链接: https://www.kanes.top/2024/10/12/小米校招笔试编程题/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
小米校招笔试编程题
  1. 1. 题 1
    1. 1.1. 题目描述：
    2. 1.2. 输入描述：
    3. 1.3. 输出描述：
    4. 1.4. 思路
  2. 2. 题 2
    1. 2.1. 题目描述：
    2. 2.2. 输入描述：
    3. 2.3. 限制条件
    4. 2.4. 输出描述：
    5. 2.5. 输入示例：
    6. 2.6. 输出示例：
    7. 2.7. 操作过程解释：
    8. 2.8. 思路
    9. 2.9. 问题描述：
    10. 2.10. 解题思路：
    11. 2.11. 代码实现：
    12. 2.12. 示例输入输出：
    13. 2.13. 复杂度分析：