程序员面试－循环移位 - 修订版

小鱼儿 2021-12-07 14:04 171阅读 0赞

题目要求：

将字符串str进行循环移位，要求算法空间复杂度O(1),时间复杂度O(n)

思路：

假设str需要循环移位k位，则将其分为前后两部分，分别长k和n-k,称AB

则循环移位的过程即为XY->YX. 可由XT即转置完成，(XTYT)T=(YT)T(XT)T=YX

实现如下：

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  /\*
2.  \* Reverse\_String.cpp
3.  \*
4.  \* Created on: May 22, 2012
5.  \* Author: sophia
6.  \*/
7.  
8.  \#include"stdio.h" 
9.  \#include"string.h" 
10. 
11. void Reverse(char\* str, int s, int e)
12. \{
13. char tmp;
14. while (s < e)
15. \{
16. tmp = str\[s\];
17. str\[s\] = str\[e\];
18. str\[e\] = tmp;
19. s++;
20. e--;
21. \}
22. \}
23. 
24. void RightReverse(char\* str, int k, int n)
25. \{
26. if (k > 0 && n > 0)//avoid exception 
27. \{
28. Reverse(str, 0, k - 1);
29. Reverse(str, k, n - 1);
30. Reverse(str, 0, n - 1);
31. printf("%s\\n", str);
32. \}
33. \}
34. 
35. int main()
36. \{
37. char str\[25\];
38. int k, n;
39. while (scanf("%s%d", str, &k) != EOF)
40. \{
41. n = strlen(str);
42. if (k > n)
43. k %= n;
44. RightReverse(str, k, n);
45. \}
46. \}

/*
     * Reverse_String.cpp
     *
     *  Created on: May 22, 2012
     *      Author: sophia
     */
    
    #include"stdio.h"
    #include"string.h"
    
    void Reverse(char* str, int s, int e)
    {
    	char tmp;
    	while (s < e)
    	{
    		tmp = str[s];
    		str[s] = str[e];
    		str[e] = tmp;
    		s++;
    		e--;
    	}
    }
    
    void RightReverse(char* str, int k, int n)
    {
    	if (k > 0 && n > 0)//avoid exception
    	{
    		Reverse(str, 0, k - 1);
    		Reverse(str, k, n - 1);
    		Reverse(str, 0, n - 1);
    		printf("%s\n", str);
    	}
    }
    
    int main()
    {
    	char str[25];
    	int k, n;
    	while (scanf("%s%d", str, &k) != EOF)
    	{
    		n = strlen(str);
    		if (k > n)
    			k %= n;
    		RightReverse(str, k, n);
    	}
    }

[view plain]: http://blog.csdn.net/abcjennifer/article/details/7592659#