当前位置：首页 > article >正文

豆包MarsCode：构造特定数组的逆序拼接

article 2025/1/19 23:48:17

问题描述

在这里插入图片描述

思路分析

1. 数组的组成：

我们要根据 i 的不同值拼接出不同长度的子数组。
对于每个 i 从 1 到 n，我们要把数字从 n 逆序到 i 拼接成一个子数组。
- 例如，当 i = 1 时，拼接 [n, n-1, ..., 1]。
- 当 i = 2 时，拼接 [n, n-1, ..., 2]。
- 一直到 i = n，拼接的数组只有 [n]。

2. 数组的拼接顺序：

每次拼接的数组要依次放入最终结果数组中。因此，我们需要有一个结果数组来保存这些拼接后的数组。

3. 计算结果数组的长度：

每个子数组的长度是由当前 i 决定的。对于 i = 1，拼接的是 n 到 1，长度为 n；对于 i = 2，拼接的是 n 到 2，长度为 n-1；依此类推，直到 i = n，拼接的数组长度为 1。
因此，总长度就是：

$\text{totalLength} = n + (n-1) + (n-2) + ... + 1 = \frac{n(n+1)}{2}$

显而易见这是一个等差数列的求和公式。

4. 实现步骤：

第一步，计算最终数组的总长度（totalLength）。
第二步，创建一个大小为 totalLength 的结果数组。
第三步，使用两层循环：
- 外层循环遍历 i 从 1 到 n。
- 内层循环从 n 逆序填充到当前的 i。
最后，返回这个结果数组。

参考代码（Java）

import java.util.Arrays;

public class Main {
    public static int[] solution(int n) {
        // 先计算出数组的总长度
        int totalLength = 0;
        for (int i = 1; i <= n; i++) {
            totalLength += (n - i + 1);
        }

        // 创建一个结果数组
        int[] result = new int[totalLength];
        int index = 0;

        // 按照规则填充结果数组
        for (int i = 1; i <= n; i++) {
            // 填充当前的部分 [n, n-1, ..., i]
            for (int j = n; j >= i; j--) {
                result[index++] = j;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.equals(solution(3), new int[]{3, 2, 1, 3, 2, 3}));
        System.out.println(Arrays.equals(solution(4), new int[]{4, 3, 2, 1, 4, 3, 2, 4, 3, 4}));
        System.out.println(Arrays.equals(solution(5), new int[]{5, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 5, 4, 5}));
    }
}

代码分析

1. 计算数组总长度

int totalLength = 0;
for (int i = 1; i <= n; i++) {
    totalLength += (n - i + 1);
}

在这个部分，代码通过一个循环来计算最终结果数组的总长度。
对于每个 i 从 1 到 n，我们需要拼接一个长度为 (n - i + 1) 的子数组。例如：
- 当 i = 1 时，长度是 n（拼接 [n, n-1, ..., 1]）。
- 当 i = 2 时，长度是 n - 1（拼接 [n, n-1, ..., 2]）。
- 一直到 i = n 时，长度是 1（拼接 [n]）。
将每个长度累加，最终得出结果数组的总长度。

2. 创建结果数组

int[] result = new int[totalLength];
int index = 0;

根据计算得到的 totalLength 创建一个新的整数数组 result，用来存储最终拼接的结果。
使用 index 来跟踪我们在 result 数组中的位置。每次填充一个元素时，index 会增加。

3. 填充结果数组

for (int i = 1; i <= n; i++) {
    // 填充当前的部分 [n, n-1, ..., i]
    for (int j = n; j >= i; j--) {
        result[index++] = j;
    }
}

外层循环：i 从 1 遍历到 n，代表我们要填充的每个子数组的起始位置。
内层循环：对于每个 i，从 n 到 i 逆序填充结果数组。内层循环的次数由 i 决定：
- 对于 i = 1，内层循环会填充 n, n-1, ..., 1。
- 对于 i = 2，内层循环会填充 n, n-1, ..., 2。
- 直到 i = n，只填充 n。
每次填充一个数字时，index 会增加，确保结果数组按顺序填充。