Author:bakari Date:2012.9.8
昨天在写一个旋转字符串的函数时,写着写着发现有好多种方法,最简单的莫过于替换然后覆盖再插入。不要小看这种小的算法,其实这其中蕴含着很多容易忽略的编程的细节。下面就跟随着我的文字来由浅入深进行巩固和再学习。总结下来此问题的算法大约有五个,这是在分得很细的情况下,前面的两个是自己想的,后面的三个参考了一个叫July的大神的思路。其实这些算法总体的思路大同小异,但这些细节问题也让我的思维有了很大的开阔。下面就由浅入深一一分析:
思路一:
此思路是最容易想到的,就是进行简单的替换,覆盖和插入操作。不好描述,直接见代码:其中需要注意的地方都已标注出来。
1 /* 思路一:正常思路,循环左移
2 * 注意K的处理,K有可能比N大,K 等价于 K %= N;
3 * 算法的时间复杂度为O(N^2);
4 */
5 void RightShift(char * pArr, int N, int K)
6 {
7 assert(NULL != pArr); //断言判断
8 if(NULL == pArr)
9 return;
10
11 K %= N; //K有可能比N大,考虑周到了
12 while(K--){
13 char pTemp = pArr[0];
14 for(int i = 0; i < N; i ++){
15 pArr[i] = pArr[i + 1];
16 }
17 pArr[N - 1] = pTemp;
18 }
19 }
当然你也可以C++的String库来写,建议以后编程多用C++的string库,至少不会出现(char *)中出现的很多令人蛋疼的指针问题,不过各有各的好处,因人而异。
上面的思路最简单,但时间复杂度却不是很理想。下面是改进的算法,实现三次交换,而不是双重循环。交换的时间复杂度是线性的。
思路二:
这个也是比较容易想到的,E.g:"abcd1234" ,将之分为两部分,"abcd"和"1234",将两者交换-->"dcba"和"4321",在对整体交换-->"1234abcd",OK!是不是很简单,大部分人想到这里就应该会放弃了,包括我也是这样,但解决问题的方式永远不止一两种,只有少部分人相信了这种话,所以,相信的现在都变大神了,大神July就是这样的,下面的几种思路保证让你大开眼界,所以,以后思考问题应该多多抱着一种批判的思想,层层深入,如此方能凿到金子。看思路二的代码:
1 /* 思路二:三次反转
2 * e.g: "abcd1234"
3 * 第一次反转:"dcba",第二次反转:"4321",第三次反转:“1234abcd”
4 * 算法的时间复杂度降到线性级为O(N);
5 */
6 void Reverse(char *pArr, int M, int N) //反转函数
7 {
8 //M、N代表字符串区域边界上的两个点
9 while(M < N){
10 char pTemp = pArr[N];
11 pArr[N] = pArr[M];
12 pArr[M] = pTemp;
13 ++ M;
14 -- N;
15 }
16 }
17 //三次反转
18 char * ThreeReverse(char * pArr, int N, int K)
19 {
20 K %= N; //同样对K进行处理
21 Reverse(pArr, 0, K - 1);
22 Reverse(pArr, N - K, N - 1);
23 Reverse(pArr, 0, N - 1);
24 return pArr;
25 }
上面N表示字符串的长度,K表示要循环移动的位数,注意对K的处理上,K有可能比N大,如果K == N,刚好回到原来的字符串,即没有移动,所以,我们可以用K %= N来代替K,效果是一样的。
思路三:
将所要旋转的字符串当做一个整体,然后集体移动,如果是左循环,就进行右移动,右循环就左移动。举个例子,E.g:“abcdefghijk”实行左循环,将“abc”移动最后,则有:
“abcdefghijk” --> "defabcghijk" --> "defghiabcjk",到这里,就没法再移动了,这个时候,刚好反过来,将"jk"前移 --> "defghijkabc",这其中会用到交换Swap函数,如下:
1 void Swap(char *pArr, int M, int N) //交换函数
2 {
3 char pTemp = pArr[N];
4 pArr[N] = pArr[M];
5 pArr[M] = pTemp;
6 }
那么如何来控制待处理的串(如"abc")的移动呢?用两个临界指针不久解决了吗,保证P2 - P1 = K即可,移动中要对P2进行判断,如果(P2 + K - 1)超过了 N(串长),就停止。对于"abcdefghijk",停止时 P1-->'a' , P2 --> 'j',因为这个时候(P2 + K1 - 1)> N,控制P2的停止,这个地方有个小技巧,就是设一个变量 Index = (N - K) - (N % K),当Index == 0时,P2不在移动。这个很好理解,比判断P2是否越界要好处理得多。见代码:
1 /* 思路三:将要循环左移的字符串当做一个整体(两个指针控制),依次右移
2 * e.g:“abcdefghijk”,将abc移到最右边-->"defghijkabc"
3 * 第一次移动-->"defabcghijk",第二次移动-->"defghiabcjk"
4 * 再将jk往前移K位-->"defghijkabc"
5 * 算法的时间复杂度也是线性的
6 */
7 void pConReverseFirst(char *pArr, int N, int K)
8 {
9 assert(NULL != pArr); //断言判断
10 if(NULL == pArr)
11 return;
12
13 K %= N;
14 if(K == 0)
15 return;
16
17 //将待处理的串往后移
18 int p1 = 0, p2 = K;
19 int pIndex = (N - K) - (N % K); //小技巧:pIndex表示p2所能指示的最大区域
20
21 while(pIndex --){
22 Swap(pArr, p1, p2);
23 ++ p1;
24 ++ p2;
25 }
26
27 //将剩余的串往前移
28 int pR = N % K; //计算剩余的单出来的数,将这些数统一向前移,pR也可以= N - p2;
29 while(pR --){
30 char pTemp = pArr[p2];
31 for(int i = p2; i > p1; i --)
32 pArr[i] = pArr[i - 1];
33 pArr[p1] = pTemp;
34 ++ p2;
35 ++ p1;
36 }
37 }
思路四:
前面部分的算法和思路三一样,在后面剩余串的处理上,本思路是将待处理串中剩余的部分往后移,E.g:"abcdefghijk" -- > "defghiabcjk" -- > "defghi j bc a k" -- > "defghi j k c a b",将'c'往后移 -- > "defghijk abc"。见代码:
1 /* 思路四:和思路三一样,只在后面多余数据的处理上不一样,刚好和思路三相反
2 * 只要 *p2 != '\0',就交换p1和p2;然后将前面多余的数单独移到最后
3 * e.g:"defghiabcjk" --> "defghijkcab" --> "defghijkabc"
4 * 同样的时间复杂度为线性的
5 */
6 void pConReverseSecond(char * pArr, int N, int K)
7 {
8 assert(NULL != pArr); //断言判断
9 if(NULL == pArr)
10 return;
11
12 K %= N;
13 if(K == 0)
14 return;
15
16 int p1 = 0, p2 = K;
17 while(p2 < N){
18 Swap(pArr, p1,p2);
19 ++ p1;
20 ++ p2;
21 }
22
23 int pR = K - (N % K); //计算前面p1所指范围内剩余的数,e.g:"defghijkcab"剩余'c'
24 while(pR --){
25 for(int i = p1; i < p2 - 1; i ++)
26 Swap(pArr, i, i + 1);
27 }
28 }
思路五:
和思路三前面部分的算法也是一样的,后面的部分则采用递归处理。代码中有说明,相见代码:
1 /* 思路五:递归求解,前面的思路和思路三是一样的,只是对于后面的要递归处理
2 * e.g:"abcdefghijk" --> "defghiabcjk" 此时,对于"abcjk"
3 * N = K + N % K = 5; K = N % K = 2; 将"jk"左移 --> "ajkbc",此时,对于"ajk"
4 * N = K + N % K = 3; K = N % K = 1; 将'a' 右移 --> "jka";
5 * 算法的时间复杂度也是线性的
6 */
7 void RecurReverse(char * pArr, int N, int K, int pHead, int pTail, bool pFlag)
8 {
9 /* pHead = 待处理的头元素,pTail = 待处理的尾元素
10 * pFlag = 左循还是右循的标志
11 */
12 assert(NULL != pArr); //断言判断
13 if(NULL == pArr)
14 return;
15
16 K %= N;
17 if(pHead == pTail || K == 0) //递归出口
18 return;
19
20 //左循右移
21 if(pFlag == true){
22 int p1 = pHead, p2 = pHead + K;
23 int pLeft = N - K - (N % K);
24
25 for(; pLeft > 0; -- pLeft, ++ p1, ++p2)
26 Swap(pArr, p1, p2);
27
28 //递归,pFLag == FALSE
29 RecurReverse(pArr, K + N % K, N % K, p1, pTail, false);
30 }
31
32 //右循左移
33 //p2指向最右边第一个
34 else{
35 int p2 = pTail, p1 = pTail - K;
36 int pRight = N - K - (N % K);
37
38 for(; pRight > 0; -- pRight, -- p1, -- p2)
39 Swap(pArr, p1, p2);
40 //递归,pFLag == TRUE
41 RecurReverse(pArr, K + N % K, N % K, p1, p2, true); //"ajk" , p1指向'a',p2指向'k'
42 }
43 }
OK,以上所有代码都严格经过测试成立。
以上的算法思想,是非常低级的,一切没有涉及数据结构的算法都是非常低级的算法,但这些算法或多或少在不同的程度上打开了我们的思维,对以后的学习会有很多的帮助。以上的代码有好多种写法,每个人的写法都不一样,关键是懂得这种思想,学会层层深入地思考问题。