Related Questions
- Rotate String: abcdefg, offset=3 -> efgabcd
- Rotate Words List: I love you -> you love I
Conclusion
Binary Search
-- Exclude half every time
Sorted Array
-- If array is sorted, try binary search
-- If array is not sorted, try sort it first
解题思路：针对1中的例子，先转置“abcd”为“dcba”，“efg”转置为“gfe”，此时string由“abcdefg”变为了“dcbagfe”，然后转置string得到“efgabcd”
示例代码：
#include "string.h"
// Move the first n chars in a string to its end
char* LeftRotateString(char* pStr, unsigned int n)
{
if(pStr != NULL)
{
int nLength = static_cast<int>(strlen(pStr));
if(nLength > 0 || n == 0 || n > nLength)
{
char* pFirstStart = pStr;
char* pFirstEnd = pStr + n - 1;
char* pSecondStart = pStr + n;
char* pSecondEnd = pStr + nLength - 1;
// reverse the first part of the string
ReverseString(pFirstStart, pFirstEnd);
// reverse the second part of the strint
ReverseString(pSecondStart, pSecondEnd);
// reverse the whole string
ReverseString(pFirstStart, pSecondEnd);
}
}
return pStr;
}
// Reverse the string between pStart and pEnd
void ReverseString(char* pStart, char* pEnd)
{
if(pStart == NULL || pEnd == NULL)
{
while(pStart <= pEnd)
{
char temp = *pStart;
*pStart = *pEnd;
*pEnd = temp;
pStart ++;
pEnd --;
}
}
}
算法效率测试
下面那长长一坨，有两百多行的代码是干嘛用的呢？
这段代码介绍了几种常见的反转算法，而且编写了一个可以计算算法执行时间的函数。
输入接口：
algnum：你选的算法
numtests：测试次数
n：反转起始位置
rotdist：要反转的数据的长度
/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */
/* rotate.c -- time algorithms for rotating a vector
Input lines:
algnum numtests n rotdist
algnum:
1: reversal algorithm
2: juggling algorithm
22: juggling algorithm with mod rather than if
3: gcd algorithm
4: slide (don't rotate): baseline alg for timing
To test the algorithms, recompile and change main to call testrot
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 10000000
int x[MAXN];
int rotdist, n;
/* Alg 1: Rotate by reversal */
void reverse(int i, int j)
{ int t;
while (i < j) {
t = x[i]; x[i] = x[j]; x[j] = t;
i++;
j--;
}
}
void revrot(int rotdist, int n)
{ reverse(0, rotdist-1);
reverse(rotdist, n-1);
reverse(0, n-1);
}
/* Alg 2: Juggling (dolphin) rotation */
int gcd(int i, int j)
{ int t;
while (i != 0) {
if (j >= i)
j -= i;
else {
t = i; i = j; j = t;
}
}
return j;
}
void jugglerot(int rotdist, int n)
{ int cycles, i, j, k, t;
cycles = gcd(rotdist, n);
for (i = 0; i < cycles; i++) {
/* move i-th values of blocks */
t = x[i];
j = i;
for (;;) {
k = j + rotdist;
if (k >= n)
k -= n;
if (k == i)
break;
x[j] = x[k];
j = k;
}
x[j] = t;
}
}
void jugglerot2(int rotdist, int n)
{ int cycles, i, j, k, t;
cycles = gcd(rotdist, n);
for (i = 0; i < cycles; i++) {
/* move i-th values of blocks */
t = x[i];
j = i;
for (;;) {
/* Replace with mod below
k = j + rotdist;
if (k >= n)
k -= n;
*/
k = (j + rotdist) % n;
if (k == i)
break;
x[j] = x[k];
j = k;
}
x[j] = t;
}
}
/* Alg 3: Recursive rotate (using gcd structure) */
void swap(int i, int j, int k) /* swap x[i..i+k-1] with x[j..j+k-1] */
{ int t;
while (k-- > 0) {
t = x[i]; x[i] = x[j]; x[j] = t;
i++;
j++;
}
}
void gcdrot(int rotdist, int n)
{ int i, j, p;
if (rotdist == 0 || rotdist == n)
return;
i = p = rotdist;
j = n - p;
while (i != j) {
/* invariant:
x[0 ..p-i ] is in final position
x[p-i..p-1 ] = a (to be swapped with b)
x[p ..p+j-1] = b (to be swapped with a)
x[p+j..n-1 ] in final position
*/
if (i > j) {
swap(p-i, p, j);
i -= j;
} else {
swap(p-i, p+j-i, i);
j -= i;
}
}
swap(p-i, p, i);
}
int isogcd(int i, int j)
{ if (i == 0) return j;
if (j == 0) return i;
while (i != j) {
if (i > j)
i -= j;
else
j -= i;
}
return i;
}
void testgcd()
{
int i,j;
while (scanf("%d %d", &i, &j) != EOF)
printf("%d\n", isogcd(i,j) );
}
/* Alg 4: slide (don't rotate): baseline alg for timing*/
void slide(int rotdist, int n) /* Benchmark: slide left rotdist (lose 0..rotdist-1) */
{ int i;
for (i = rotdist; i < n; i++)
x[i-rotdist] = x[i];
}
/* Test all algs */
void initx()
{
int i;
for (i = 0; i < n; i++)
x[i] = i;
}
void printx()
{ int i;
for (i = 0; i < n; i++)
printf(" %d", x[i]);
printf("\n");
}
void roterror()
{
fprintf(stderr, " rotate bug %d %d\n", n, rotdist);
printx();
exit (1);
}
void checkrot()
{ int i;
for (i = 0; i < n-rotdist; i++)
if (x[i] != i+rotdist)
roterror();
for (i = 0; i < rotdist; i++)
if (x[n-rotdist+i] != i)
roterror();
}
void testrot()
{ for (n = 1; n <= 20; n++) {
printf(" testing n=%d\n", n);
for (rotdist = 0; rotdist <= n; rotdist++) {
/* printf(" testing rotdist=%d\n", rotdist); */
initx(); revrot(rotdist, n); checkrot();
initx(); jugglerot(rotdist, n); checkrot();
initx(); jugglerot2(rotdist, n); checkrot();
initx(); gcdrot(rotdist, n); checkrot();
}
}
}
/* Timing */
void timedriver()
{ int i, algnum, numtests, start, clicks;
while (scanf("%d %d %d %d", &algnum, &numtests, &n, &rotdist) != EOF) {
initx();
start = clock();
for (i = 0; i < numtests; i++) {
if (algnum == 1)
revrot(rotdist, n);
else if (algnum == 2)
jugglerot(rotdist, n);
else if (algnum == 22)
jugglerot2(rotdist, n);
else if (algnum == 3)
gcdrot(rotdist, n);
else if (algnum == 4)
slide(rotdist, n);
}
clicks = clock() - start;
printf("%d\t%d\t%d\t%d\t%d\t%g\n",
algnum, numtests, n, rotdist, clicks,
1e9*clicks/((float) CLOCKS_PER_SEC*n*numtests));
}
}
/* Main */
int main()
{ /* testrot(); */
timedriver();
return 0;
}
