【笔试题集合】字符串问题

1. 实现字符串移位操作，要求时间复杂度为O(n)，空间复杂度为O(1)。

思路：由于空间复杂度为O(1)，可以知道移位操作只在原字符串上面完成。

假设c1 c2 c3 c4 ... ci-1, ci, ci+1 ... cn字符串，low=1，high=n，shift=i，需要移位的字符串长度为high-low+1;

向左移位i位时，有三种情况：

1）当i>n-i时，将c[1...n-i]与c[i+1...n]进行对调，此时c[i+1...n]到达正确位置，修改low=n-i+1，shift=(high-low+1)-2*(n-i)；

2）当i=n-i时，将c[1...i]与c[i+1...n]进行对调，此时刚好完成移位，退出移位循环体；

3）当i<n-i时，将c[i...i]与c[n-i+1...n]进行对调，此时c[1...i]到达正确位置，修改high=high-i即可。

比如有字符串“abcdefghi”左移7位的顺序如下：

第一步：“<abcdefghi>”的low=1，high=9，i=7，因为i>high-i，所以对调c[1...high-i]和c[i+1...high]，得到“hi<cdefg ab>”，low=high-i+1=3，i=(high-low+1)-2*(high-low+1-i)=5；

第二步：类似于第一步，得到“hiab<efg cd>”，low=high-i+1=5，i=(high-low+1)-2*(high-low+1-i)=3；

往后继续可得“hiabcd<g ef>"，"hiabcd<f e>g"，”hiabcdefg"结束。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(char *a, char *b){
	char temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

void shift_str(char *s, int n){
	int slen;
	int k;
	int low, high, ntemp;

	slen = strlen(s);
	low=0; high=slen;
	while(high>low){
		if(n>high-low-n){
			for(k=0; k<high-low-n; k++){
				swap(s+low+k, s+low+n+k);
			}
			ntemp = n;
			n=n+n+low-high;     //(high-low)-2*(high-low-n)
			low=high-ntemp;  //low+(high-low-n)
		}
		else if(n==high-low-n){
			for(k=0; k<n; k++){
				swap(s+low+k, s+high-n+k);
			}
			break;
		}
		else{
			for(k=0; k<n; k++){
				swap(s+low+k, s+high-n+k);
			}
			high=high-n;
		}
	}
}

int main(void){
	char s[100];
	int n;

	gets(s);
	scanf("%d", &n);
	shift_str(s, n);
	printf("%s", s);

	system("pause");
	return 0;
}

感谢网友hzdgyl01给出的递归思路，

int leftWeiYiChar(char str[], int length, int k){
    int i;
    static int cnt=0;
    if(k%length==0)
        return cnt;
    k=k%length;
    i=k-1;
    cnt++;
    while(i>=0){
        str[i]=str[i]^str[length-k+i];
        str[length-k+i]=str[i]^str[length-k+i];
        str[i]=str[i]^str[length-k+i];
        i--;
    }
    leftWeiYiChar(str, length-k, k);
    return cnt;
}

使用了递归，代码显得非常简洁。

但是，这里可能与题目条件空间复杂度O(1)产生冲突。因为，递归调用函数是需要压栈的，在这里可以加入static int cnt来记录递归的次数进行测试；同样我们来分析最好情况和最坏的情况：最好情况是函数只运行一次，就是在k%length==0直接返回；最坏的情况需要递归n-1次(移一位的情况下)。所以在移位位数概率一致的情况下，平均空间复杂度为n/2，即O(n)。