【CareerCup】 Arrays and Strings—Q1.3

전재 출처 를 밝 혀 주 십시오:http://blog.csdn.net/ns_code/article/details/21328151
    제목:    
    Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not.
FOLLOW UP
    Write the test cases for this method.
    번역:    
    문자열 에서 중 복 된 문 자 를 제거 합 니 다. 예 를 들 어 abcadc 를 제거 한 후 abcd 로 변 하면 한두 개의 변 수 를 추가 로 정의 할 수 있 지만, 하나의 배열 을 추가 로 만 드 는 것 은 허용 되 지 않 습 니 다.이 알고리즘 을 위해 테스트 용례 를 쓴다.
    생각:
    이 문 제 는 주로 공간의 복잡 도 를 제한 하 는 것 입 니 다. 만약 에 이런 요구 가 없 으 면 우 리 는 좋 은 해법 을 가 질 수 있 습 니 다. (문자열 의 자모 가 모두 소문 자 라 고 가정 합 니 다)
    예 를 들 어 문자열 이 길 었 을 때 우 리 는 Q. 1. 1 문제 와 같은 방향 으로 26 크기 의 bool 배열 을 개설 할 수 있 습 니 다. 초기 값 은 false 이 고 문자열 을 옮 겨 다 니 며 처음으로 특정한 문 자 를 만 났 습 니 다. 이 문 자 를 bool 배열 에서 해당 하 는 위치 에 있 는 요 소 를 true 로 설정 할 수 있 습 니 다. 다시 만 났 을 때 중복 문자 가 나 타 났 음 을 설명 하고 이 문 자 를 제거 하면 됩 니 다.
    예 를 들 어 문자열 이 길지 않 으 면 KMP 알고리즘 의 접두사 배열 을 사용 하여 문자열 의 길이 보다 1 큰 배열 (마지막 문자 '\0' 에 대해 접두사 값 을 요구 함) 을 만 드 는 것 을 고려 할 수 있 습 니 다. 접두사 배열 의 값 next [i] > 0 이면 이 위치 앞 에 연속 next [i] 를 설명 합 니 다.위치 에 있 는 문 자 는 앞의 문자 와 중복 되 며 이 문 자 를 제거 할 수 있 습 니 다.
    그러나 여기 서 공간 복잡 도 를 O (1) 로 요구 했다. 그러면 우 리 는 가장 간단 한 옮 겨 다 니 는 방법 으로 첫 번 째 문자 와 뒤의 문 자 를 일일이 비교 할 수 밖 에 없다. 중복 되 는 문 자 를 만나면 중복 되 는 문 자 를 '\0' 으로 교체 한 다음 에 두 번 째 문자 와 오른쪽 문 자 를 일일이 비교 하고 중복 되 는 문 자 를 '\0' 으로 대체 하여 이렇게 순환 할 수 있다.마지막 문자 까지 '\0' 을 만 날 때마다 (반복 문자 가 나타 나 는 위 치 는 '\0' 으로 채 워 졌 습 니 다) 뒤의 문 자 를 앞으로 옮 겨 '\0' 으로 바 꾸 고 마지막 으로 자 리 를 옮 긴 후의 마지막 위 치 를 '\0' 으로 설정 하여 이 문자열 의 묶음 을 표시 합 니 다.시간 복잡 도 는 O (n * n) 이다.
    테스트 용례 우 리 는 다음 과 같은 몇 가지 상황 을 고려 해 야 한다.
    char str1[] = "abcdfbdk";//무 작위 문자열    char str2[] = "abababab";//반복 문자 교체 출현    char str3[] = "aaaabbbb";//반복 문자 연속 출현    char str4[] = "aaaaaaaa";  //모두 중복 문자 입 니 다.    char str5[] = "abcdefgh";  //중복 문자 없 음    char str6[] = "";        //빈 문자열
    구현 코드:

/***********************************************
题目描述：
移除字符串中重复的字符，如abcadc移除后变为abcd，
可以额外定义一两个变量，但不允许额外开辟一个数组,
并为该算法写测试用例
Date:2014-03-16
************************************************/
#include<stdio.h>
#include<string.h>

void remove(char *str)
{
	int len = strlen(str);
	if(len<2)
		return;
	int i,j;
	int p = 0;	//p的初值与i相等，均为0
	for(i=0;i<len;i++)
	{
		//如果该字符不为'\0'，则与下面的字符比较
		if(str[i])
		{
			//如果当前字符不为'\0'时，p一直与i相等，
			//如果当前字符为'\0'，则p会小于i，从而用后面的字符来填充前面'\0'字符的位置
			str[p++] = str[i];
			//每个字符与其后面的字符比较，
			//如果出现重复字符，则将后面的重复字符用'\0'代替
			for(j=i+1;j<len;j++)
				if(str[i] == str[j])
					str[j] = '\0';
		}
	}
	str[p] = '\0';
}

int main()
{
	char str1[] = "abcdfbdk";	//随机字符串
	char str2[] = "abababab";	//重复字符交替出现
	char str3[] = "aaaabbbb";	//重复字符连续出现
	char str4[] = "aaaaaaaa";   //全是重复字符
	char str5[] = "abcdefgh";   //没有重复字符
	char str6[] = "";			//空字符串

	remove(str1);
	remove(str2);
	remove(str3);
	remove(str4);
	remove(str5);
	remove(str6);

	puts(str1);
	puts(str2);
	puts(str3);
	puts(str4);
	puts(str5);
	puts(str6);

	return 0;
}

    다음은 고정 크기 의 bool 배열 을 개척 하 는 방법 을 제시 합 니 다. 즉, 우리 가 분석 한 첫 번 째 방법 입 니 다. 코드 는 다음 과 같 습 니 다.

/*
开辟长为26的bool数组的方法
*/
void remove1(char *str)
{
	int len = strlen(str);
	if(len < 2)
		return ;
	int i;
	int p = 0;
	bool A[MAX];
	memset(A,0,sizeof(A));
	for(i=0;i<len;i++)
	{
		int index = str[i] - 'a';
		if(!A[index])
		{
			str[p++] = str[i];
			A[index] = true;
		}
	}
	str[p] = '\0';
}

    테스트 결과: