【JAVA】1008 数组元素循环右移问题 (20分) PAT乙级 PAT (Basic Level) Practice (中文)

小鱼儿 2022-12-24 09:58 81阅读 0赞

### 你是最棒的 ###

*  前言
 *  题目：1008 数组元素循环右移问题 (20分)
 *  要点：M可能大于N
 *  代码一：暴力
 *  代码二：反转
 *  代码三：投机取巧（输入的时候使用循环队列的思想：）
 *  代码四：优化，减少交换次数，但是比较难

# 前言 #

> **学得越多，不会得越多  
> 种一颗树的最佳时间是十年前，其次就是现在**  
>

> pat所有题解代码都会陆续上传到Github，请好兄弟们自行下载：[https://github.com/233zzh/PAT][https_github.com_233zzh_PAT]  
> qq交流群：1107710098

# 题目：1008 数组元素循环右移问题 (20分) #

> [题目链接：https://pintia.cn/problem-sets/994805260223102976/problems/994805316250615808][https_pintia.cn_problem-sets_994805260223102976_problems_994805316250615808]

一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由\`\`（ A 0 A\_0 A0 A 1 A\_1 A1⋯ A N − 1 A\_\{N-1\} AN−1）变换为（ A N − M A\_\{N-M\} AN−M··· A N − 1 A\_\{N-1\} AN−1 A 0 A\_0 A0 A 1 A\_1 A1··· A N − M − 1 A\_\{N-M-1\} AN−M−1）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

**输入格式:**  
每个输入包含一个测试用例，第1行输入N（1≤N≤100）和M（≥0）；第2行输入N个整数，之间用空格分隔。

**输出格式:**  
在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

**输入样例:**

6 2
    1 2 3 4 5 6

**输出样例:**

5 6 1 2 3 4

# 要点：M可能大于N #

解决办法：

M = M % N; //M可能大于N

# 代码一：暴力 #

import java.util.Scanner;
    
    public class LoopArray { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int M = sc.nextInt();
            M = M % N;
            int[] arr = new int[N];
    
            for (int i = 0; i < N; i++) { 
                arr[i] = sc.nextInt();
            }
    
            for (int i = 0; i < M; i++) { 
                int tmp = arr[N - 1];
                for (int j = N - 1; j > 0; j--) { 
                    arr[j] = arr[j - 1];
                }
                arr[0] = tmp;
            }
    
            for (int i = 0; i < N - 1; i++) { 
                System.out.print(arr[i] + " ");
            }
            System.out.print(arr[N - 1]);
        }
    }

# 代码二：反转 #

**三步走策略：先反转前面部分，再反转后面部分，最后再对整体进行反转。**  
也就是代码中的这三行（如下），关键是参数的设定，哪里该减一，哪里不能减一，（技巧就是用具体数字代入试一试）。  
另外，reverse函数的编写，也是同样，难点是下标的计算，功能是**原地反转。**

1.  reverse(arr, 0, N - M - 1);
2.  reverse(arr, N - M, N - 1);
3.  reverse(arr, 0, N - 1);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzEyNDI3OQ_size_16_color_FFFFFF_t_70_pic_center]

import java.util.Scanner;
    
    /** * Created by IntelliJ IDEA. * * @Author: 张志浩 Zhang Zhihao * @Email: 3382885270@qq.com * @Date: 2020/11/27 * @Time: 17:58 * @Version: 1.0 * @Description: Description */
    public class ShiftRight3 { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int M = sc.nextInt();
            M = M % N; //M可能大于N
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) { 
                int input = sc.nextInt();
                arr[i] = input;
            }
            sc.close();
    
            reverse(arr, 0, N - M - 1);
            reverse(arr, N - M, N - 1);
            reverse(arr, 0, N - 1);
    
            for (int i = 0; i < N - 1; i++) { 
                System.out.print(arr[i] + " ");
            }
            System.out.print(arr[N - 1]);
        }
    
        private static void reverse(int[] arr, int start, int end) { 
            for (int i = start; i <= (start + end) / 2; i++) { 
                int temp = arr[i];
                arr[i] = arr[end + start - i];
                arr[end + start - i] = temp;
            }
        }
    }

# 代码三：投机取巧（输入的时候使用循环队列的思想：） #

一般这种代码没法用，因为一般情况下会给你传一个数组，而不是让你从控制台读取，我们这种投机其实相当于使用了一个新数组，而不是在原来数组上原地变换

import java.util.Scanner;
    
    /** * Created by IntelliJ IDEA. * * @Author: 张志浩 Zhang Zhihao * @Email: 3382885270@qq.com * @Date: 2020/11/27 * @Time: 18:12 * @Version: 1.0 * @Description: Description */
    public class ShiftRight4 { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int M = sc.nextInt();
            M = M % N; //M可能大于N
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) { 
                int input = sc.nextInt();
                arr[(i + M) % N] = input;
            }
            sc.close();
    
            for (int i = 0; i < N - 1; i++) { 
                System.out.print(arr[i] + " ");
            }
            System.out.print(arr[N - 1]);
        }
    }

# 代码四：优化，减少交换次数，但是比较难 #

import java.util.Scanner;
    
    /** * Created by IntelliJ IDEA. * * @Author: 张志浩 Zhang Zhihao * @Email: 3382885270@qq.com * @Date: 2020/11/27 * @Time: 15:03 * @Version: 1.0 * @Description: Description */
    public class ShiftRight2 { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int M = sc.nextInt();
            M = M % N; //M可能大于N
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) { 
                int input = sc.nextInt();
                arr[i] = input;
            }
            sc.close();
            if (N % 2 == 0) { 
                int flag;
                flag = M <= N / 2 ? M : N - M;
                for (int i = 0; i < flag; i++) { 
                    int temp = arr[i];
                    int index = i;
                    /*for (int k = 0; k < N / M; k++) { index = (index + M) % N; int temp1 = arr[index]; arr[index] = temp; temp = temp1; }*/
                    while (true) { 
                        index = (index + M) % N;
                        int temp1 = arr[index];
                        if (temp1 == temp) { 
                            break;
                        }
                        arr[index] = temp;
                        temp = temp1;
                    }
                }
            } else { 
                int temp = arr[0];
                int index = 0;
                for (int k = 0; k < N; k++) { 
                    index = (index + M) % N;
                    int temp1 = arr[index];
                    arr[index] = temp;
                    temp = temp1;
                }
            }
            for (int i = 0; i < N - 1; i++) { 
                System.out.print(arr[i] + " ");
            }
            System.out.print(arr[N - 1]);
        }
    }

[https_github.com_233zzh_PAT]: https://github.com/233zzh/PAT
[https_pintia.cn_problem-sets_994805260223102976_problems_994805316250615808]: https://pintia.cn/problem-sets/994805260223102976/problems/994805316250615808
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzEyNDI3OQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/b865ba253b5541068a2209cbfee5c6a8.png