小朋友都能看懂的题解 | #旋转数组#

问题描述

想象一下，你有一个装满糖果的袋子，里面的糖果按顺序排列，比如 [1, 2, 3, 4, 5, 6]。现在，你的任务是把这些糖果向右移动 M 次。比如，如果 M 是 2，那么最后的两个糖果就要转到最前面，变成 [5, 6, 1, 2, 3, 4]。就像把最后两颗糖果给“提前上场”一样！🍬😄

方案步骤

1. 处理 M 的大小：首先，我们得考虑 M 可能比糖果的数量多，这样就有点像你试图在生日派对上把太多的蜡烛放到蛋糕上。我们只需要把 M 调整为 M % n，这样可以避免无谓的“多余旋转”。比如，如果 M 是 8，而糖果数量是 6，实际上只需要移动 2 次，这就像在派对上用两根蜡烛就能庆祝一样！

2. 反转数组：

   • 反转整个数组：首先，把整个糖果袋子翻个身，糖果顺序变成反的。这样最后的 M 个糖果就会跑到最前面，虽然它们现在是“颠倒”的。
   • 反转前 M 个糖果：接着，再把最前面的 M 个糖果翻回来，这样它们的顺序又回到了原来的样子。
   • 反转剩下的糖果：最后，剩下的糖果也要翻回来，确保它们的顺序也正确，确保每颗糖果都能找到自己的位置。

代码实现

这是我们实现这个巧妙操作的代码：

public int[] solve(int n, int m, int[] a) {
    // 处理 M 的大小
    m = m % n;
    if (m == 0) return a; // 如果不需要移动，直接返回原数组

    // 反转整个数组
    reverse(a, 0, n - 1);
    // 反转前 M 个糖果
    reverse(a, 0, m - 1);
    // 反转剩下的 n-M 个糖果
    reverse(a, m, n - 1);
    return a; // 返回移动后的数组
}

// 反转数组的一部分
private void reverse(int[] a, int start, int end) {
    while (start < end) {
        // 交换 start 和 end 的糖果
        int temp = a[start];
        a[start] = a[end];
        a[end] = temp;
        start++; // 开始位置往后移
        end--;   // 结束位置往前移
    }
}

代码解释

• solve 方法：这是我们搬糖果的地方，先计算实际需要移动的次数。如果 M 是 0，那就啥事都不干，直接把原来的糖果袋子还给你。简单明了！
• reverse 方法：这个方法就像是把糖果袋子里的一部分翻转，让每颗糖果都找到自己的“新位置”。只要 start 和 end 的位置没错，就能顺利完成翻转！

希望这篇文章对你有帮助👍。