PAT乙级1008

蔚落 2021-10-19 12:14 412阅读 0赞

# 题目链接 #

[https://pintia.cn/problem-sets/994805260223102976/problems/994805316250615808][https_pintia.cn_problem-sets_994805260223102976_problems_994805316250615808]

--------------------

查了查网上的题解，情况如下：

*  一种方法是和我（题解一）一样的
 *  这个方法真的奇葩，并不交换数组元素位置，只是根据n和m改变输出顺序，我个人觉得不可取
    
    参考链接：[https://blog.csdn.net/qq\_35283188/article/details/77370798][https_blog.csdn.net_qq_35283188_article_details_77370798]
 *  这种方法应该是最符合题目要求的，三次逆置法（题解二），感觉很像上学期算法设计与分析考试里的一道题。
    
    参考链接：[https://www.cnblogs.com/cdp1591652208/p/7161684.html][https_www.cnblogs.com_cdp1591652208_p_7161684.html]
 *  还有一个方法，看起来挺玄乎的，没看懂就没怎么看
    
    参考链接：[https://blog.csdn.net/qq\_22194315/article/details/52625679][https_blog.csdn.net_qq_22194315_article_details_52625679]

# 题解一 #

我这个方法应该是移了n+m次，看起来只用了一个数组，其实也是用了两个数组吧……惭愧惭愧

// PAT BasicLevel 1008 // https://pintia.cn/problem-sets/994805260223102976/problems/994805316250615808 #include <iostream> using namespace std; int main() { // 获取用户输入的n和m以及n个整数 int n,m; int arr[200]; cin >> n >> m; for(int i=0;i<n;i++){ cin >> arr[i]; } // m==0则不用移动 if(m>0){ // 假如有10个数，右移13位其实相当于13%10=3位。 // 所以m一定小于n，所以把数组大小定义为200 m = m % n; // 整体右移m位 for(int i=n-1;i>=0;i--){ arr[i+m]=arr[i]; } // 把最右侧的m个数字循环右移到左侧 for (int i = n-1; i < n + m;i++){ arr[i%n]=arr[i]; } } // 输出结果 cout << arr[0]; for(int i=1;i<n;i++){ cout << ' ' << arr[i]; } //system("pause"); return 0; }

# 题解二 #

这道题的参考链接里说这是链表，讲错了吧，这儿哪有链表……核心在于三次逆置

但时间（3ms）与内存占用（400KB左右）和题解一差不多，可能测试用例输入规模不够大吧。

// PAT BasicLevel 1008 // httarrs://arrintia.cn/arrroblem-sets/994805260223102976/arrroblems/994805316250615808 #include <iostream> #include <algorithm> using namespace std; int main() { // 获取用户输入的n和m以及n个整数 int n,m; cin >> n >> m; int* arr=new int[n]; for(int i=0;i<n;i++){ cin >> arr[i]; } // m==0则不用移动 if(m>0){ // 假如有10个数，右移13位其实相当于13%10=3位。 // 所以m一定小于n，所以把数组大小定义为200 m = m % n; // 三次逆置 reverse(arr, arr + n - m); reverse(arr + n - m, arr + n); reverse(arr, arr + n); } // 输出结果 cout << arr[0]; for(int i=1;i<n;i++){ cout << ' ' << arr[i]; } //system("pause"); delete[] arr; return 0; }

--------------------

作者：[@臭咸鱼][Link 1]

转载请注明出处：[https://chouxianyu.github.io][https_chouxianyu.github.io]

欢迎讨论和交流!

--------------------

转载于:https://www.cnblogs.com/chouxianyu/p/11297909.html

[https_pintia.cn_problem-sets_994805260223102976_problems_994805316250615808]: https://pintia.cn/problem-sets/994805260223102976/problems/994805316250615808
[https_blog.csdn.net_qq_35283188_article_details_77370798]: https://blog.csdn.net/qq_35283188/article/details/77370798
[https_www.cnblogs.com_cdp1591652208_p_7161684.html]: https://www.cnblogs.com/cdp1591652208/p/7161684.html
[https_blog.csdn.net_qq_22194315_article_details_52625679]: https://blog.csdn.net/qq_22194315/article/details/52625679
[Link 1]: https://github.com/chouxianyu
[https_chouxianyu.github.io]: https://chouxianyu.github.io