小米校招笔试编程题

2024 年 10 月 12 日 星期六(已编辑)
23

阅读此文章之前，你可能需要首先阅读以下的文章才能更好的理解上下文。

小米校招笔试编程题

题 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. 注意事项：

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

代码实现：

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，表示每次操作的参数。

限制条件

输出描述：

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

输入示例：

5 3
1 2 1 3 2 0 5 4 0

输出示例：

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 指针遍历整个链表，输出宝石编号。

代码实现：

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());
    }
}

示例输入输出：

输入： 5 3 1 2 1 3 2 0 5 4 0

输出： 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。

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...