首页 > 学院 > 开发设计 > 正文

PAT BASIC 1008

2019-11-11 05:18:24
字体:
来源:转载
供稿:网友

思路:

这个题题意表达得可能没那么清楚,如果说要求只能开O(N)的数组,时间复杂度也是O(N),那就是一个比较有趣的题。

我们可以用三次反转的方法来思考这个题。

如果说我要把xy这个字符串的y字串移到x子串的左边,变成yx,我记x^T为将x反转,如果x=”abc”,那么x^T=”cba”。

这样,这里就有一个比较有意思的式子了

yx=(x^T y^T)^T

也就是说我们只需要进行三次反转,就可以实现我的操作。时间复杂度为6N,即O(N)

代码:

#include<iostream>using namespace std;int num[100];int n, m;void reverse(int left, int right);void reverse(int left, int right){ int i, t; for (i = left; i <= (left + right) / 2; i++) { t = num[i]; num[i] = num[left + right - i]; num[left + right - i] = t; }}int main(){ int count = 0, pos = 0; int i, j, t; cin >> n >> m; m = m%n; for (i = 0; i < n; i++) cin >> num[i]; reverse(0, n - m - 1); reverse(n - m, n - 1); reverse(0, n - 1); for (i = 0; i < n - 1; i++) cout << num[i] << " "; cout << num[n - 1]; //while (1) //{ //} return 0;}
上一篇:c regex 用法

下一篇:XMLParser 详解

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表