题目描述:
一个数组A中存有N(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向右移M(≥0)个位置,即将A中的数据由(A0 A1⋯AN−1)变换为(AN−M ⋯AN−1 A0 A1 ⋯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
思路:
很显然只要让这些数字组成一个循环,我们输出的时候,从后面指定个数的数字开始输出,循环一遍输出完毕就可以了,因此这里用循环链表作为存储结构
复制代码
1
2
3有一个需要注意的小问题就是,我们要移动的个数不一定小于数字总个数, 也就是说,我们又可能会移动超过一个循环的距离
代码实现:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96#include <iostream> #include <string> #include <math.h> using namespace std; typedef class LNode* PtrToNode; //循环链表 class LNode { public: int data; PtrToNode next; public: LNode() { data = 0; next = NULL; } LNode(int data) { this->data = data; next = NULL; } }; class List { public: PtrToNode head; PtrToNode tail; public: List() { head = tail = new LNode(); head->next = NULL; } void append(int data) { //尾部追加元素 tail->next = new LNode(data); //如果为空, if (head->next == NULL) { head->next = tail->next; } //尾指针后移 tail = tail->next; //循环指向首节点 tail->next = head->next; } void print() { PtrToNode temp = head->next; while (temp != tail) { if (temp != head->next) { cout << " "; } cout << temp->data; temp = temp->next; } if (head->next == tail) { cout << temp->data; } else { cout << " " << temp->data; } } }; //上面就是循环链表的简单定义和基本操作,没什么难的 //我用的是带头结点的,其实这里不涉及头部的插入删除,用不带头结点的可能会更好理解 int main() { int m, n; cin >> n >> m; //存入链表 List* list = new List(); for (int i = 0; i < m; i++) { int data; cin >> data; list->append(data); } //循环移位,移动头指针的位置 //这里的循环终止条件要注意,我们是要把指针移动到后面m个的起始处, //所以并不是简单的移动 (m % n) 个 for (int i = 0; i < n - m % n; i++) { list->head->next = list->head->next->next; list->tail = list->tail->next; } list->print(); return 0; }
最后
以上就是无情荔枝最近收集整理的关于(PAT)BasiclLevel_c++ #1008 数组元素循环右移问题的全部内容,更多相关(PAT)BasiclLevel_c++内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复