好多人嘲笑程序员为码农，我个人认为码农应该是程序员的自嘲，毕竟人家创造了很多价值，只不过是因为技术的发展，使得编程越来越简单罢了。不过，话说回来程序员真应该深刻理解计算机科学的知识，NOT JUST CALL OTHER’S FUNCTION.以下记录一些字符串算法的问题。$ $

简单字符串算法问题

递归求一个字符串的长度

其实求一个字符串长度很简单，但是加上递归，小编认为还是有一人不会的。讲到递归，我觉得第一反应应该是这个公式：

\[ \begin{eqnarray}f(n)= \begin{cases} 1 &,&n=1\cr f(n)+3 &, &n>1 \cr\end{cases} \end{eqnarray} \]

比如求f(20),可以写如下的递归函数： 

1
2
3
4
5
6
int f(int n){
	if(n==1)
		return 1;
	else
		return f(n-1)+3;
}

可以看出重点就是结束的条件和递归表达式，下面直接贴出代码 

1
2
3
4
5
6
7
/*递归计算字符串长度*/
int RecurLength(char* str){
	if(str[0]=='\0')
		return 0;
	else
		return RecurLength(str+1)+1;
}

求字符串最后一个单词的长度。

第一种情况：不知道字符串长度

1
2
3
4
5
6
7
8
9
10
11
int LastWordLength(char* str){
	int len=0;
	while((*str)!='\0'){
		if((*str)==' ')
			len=0;
		else
			len++;
		str++;
	}
	return len;
}

第二种情况：知道字符串长度

1
2
3
4
5
6
7
8
9
int LastWordLength2(char* str,int length){
	int len=0;
	str=str+length-1;
	while((*str)!=' '){
		len++;
		str--;
	}
	return len;
}

实现memmove()函数

这个函数是c语言内置函数，功能：实现字符串的复制。

主要关注点：原字符串地址空间和目标字符串地址空间有重叠怎么办？ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
char* my_memmove(char* dst,char* src,int len){
	//保存目标的初始位置
	char* ret=dst;
	if(src==NULL||dst==NULL)
		return NULL;
	/*dst ≤ src；或者src+len ≤ dst,能够保证从前往后辅助不会冲突*/
	if(dst<=src||(src+len)<=dst)
		while(len>0){
			dst=src;
			dst++;
			src++;
			len--;
		}
	else{
		//从后往前复制。
		dst=dst+len-1;
		src=src+len-1;
		while(len>0){
			dst=src;
			dst--;
			src--;
			len--;
		}
	}
	return ret;
}

稍微复杂字符串算法问题

字符串排序

（1）一个包含着大小写的英文字符串，排序后使得大写在前，小写在后

（2）如果（1）中要求不变，且要求小写字符原来的相对位置不变。

这里说一种双指针法（小编自己起得名字，不要介意），一个指针依次遍历每个字符的位置，另一个指针指向新字符串的最后一个位置（当有满足条件的字符，将该字符赋值给该位置的下一个位置）。

（1）的代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
void  StrSort(char* str){
	int index=-1;
	int pos=0;
	char tmp;
	for(;str[pos]!='\0';pos++){
		if(str[pos]>='A'&&str[pos]<='Z'){
			index++;
			tmp=str[pos];
			str[pos]=str[index];
			str[index]=tmp;
		}
	}
}

小编在完成（1）后，觉得（2）没什么，再交换时，先做个标记，然后移动，最后在交换，那么相对位置就不变了啊，可是实现起来好痛苦。最后得高人点拨，发现（1）中大写字母的相对顺序是不变的。那么从后开始遍历而且以小写字母为基准，那么不是和（1）是同样的问题吗，哎，看来我的智商还是着实令人着急。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void StrSort2(char* str){
	int len=0;
	while(str[len]!='\0')
		len++;
	int index=len;
	int pos=len-1;
	char tmp;
	for(;pos>=0;pos--){
		if(str[pos]>='a'&&str[pos]<='z'){
			index--;
			tmp=str[pos];
			str[pos]=str[index];
			str[index]=tmp;
		}
	}
}

字符串去重

（1） 在一个排序好的字符串里，如何使得重复的字符串只保留一个

（2） 如何保留两个了？

（3） 如何全部却掉了？

小编看到这个问题，感觉要是可以申请新的地址空间就好了，那不是So easy的事。要是这样的话空间复杂度就是O（n）了。其实我们的最终结果的地址空间始终小于等于原字符串的地址空间大小的，我们无须另外开辟空间，其实还是用我们的双指针法就可以解决问题。

（1） 代码如下 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Remove(char* str)
{
	int index =0;
	int pos =1;
	for(;str[pos]!='\0';pos++)
	{
		if(str[pos] != str[index])
		{
			index++;
			str[index]= str[pos];
		}
	}
	str[index+1] ='\0';
}

（2）中要考虑到只要有重复字符,必然该字符出现了两次这个简单的道理。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void Remove2(char* str)
{
	int index =0;
	int pos =1;
	int flag =0;
	for(;str[pos]!='\0';pos++)
	{
		//如果当前位置的字符和已经保存的字符的最后一个位置的字符不同
		if(str[pos] != str[index])
		{
			index++;
			str[index] = str[pos];
			flag=0;
		}
		//如果当前位置的字符和已经保存的字符的最后一个位置的字符相同 
		else
		{
			if(flag == 0)
			{
				index++;
				str[index] = str[pos];
				flag =1;
			}
		}
	}
	str[index+1]='\0';
}

（3）有了前面的经验，我们多一个标记就可以了。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void Remove3(char* str)
{
	int flag =0;
	int index =-1;
	int pos;
	//遍历所有字符
	for(pos=0;str[pos]!='\0';)
	{
		//如果当前字符和下一个字符相同
		if(str[pos] == str[pos+1])
		{
			flag =1;
			pos++;
		}
	    //如果当前字符和下一个字符不同 
		else
		{
			if(flag == 1)
			{
				flag =0;
				pos++;
			}
			else
			{
				index++;
				str[index] = str[pos];
				pos++;
			}
		}
	}
	str[index+1] = '\0';
}

atoi()实现

atoi 是string类型转int类型的内置函数。

注意：考虑程序的健壮性 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int StringToInt(string& str)
{
	if(str.length() == 0)
		return 0;
	int i;
	int flag =1;
	int result =0;
	int digit;
	// 清空空格字符（字符串前面的空格）
	for(i=0;i<str.length();i++)
		if(str[i] !=' ')
			break;
	//查找正负号
	if(str[i] == '+')
		i++;
	if(str[i]== '-')
	{
		flag =0;
		i++;
	}
	//开始处理字符
	for(;i<str.length();i++)
	{
		if(str[i]<'0' || str[i] > '9')
			break;
		digit = str[i]-'0';
		//判断越界
		if(flag && (numeric_limits<int>::max() - result*10) <= digit)
			return numeric_limits<int>::max();
		else if(!flag && (numeric_limits<int>::min() + result*10) >= digit*-1)
			return numeric_limits<int>::min();
		result = result*10+digit;
	}
	return flag ==1? result:-result;
}