面试题之字符串

字符串面试题汇总如下：

1.字符串转化为整数，不得使用库函数

字符串转化为整数举例为：“12345”转化为整数即为：12345

转化思路为：将字符串的字符取出减去‘0’，得到该字符的数字，比如“12345”，逐个取出字符，先取出‘1’减去‘0’得到1

需要注意的几点：

（1）如果是空的字符串，则返回0

（2）如果字符串第一个字符为‘+’或者是‘-’，则需做处理，如果是‘+’，则说明是一个正数，如果是‘-’，则说明该数为负数，在对除‘-’之外的转化完成之后需加上符号；

（3）如果字符串是0~9的其他字符，比如a，b，c等等，返回0

（4）考虑溢出，如果字符串转化为整数后，超出了整数的范围，即正数超出了0x80000000，负数小于0x7FFFFFFFF，则返回0

代码如下：

int my_atoi(char *str)
{
	//如果字符串为空，返回0
	if (str == NULL)
	{
		return 0;
	}

	int num = 0; //最终转化为的数字
	bool minus = false;  //标志位，判断是否是负数
	//如果第一个字符是‘-’
	if (*str == '-')
	{
		minus = true;
		str ++;
	}
	//如果第一个字符是‘-’
	if (*str == '+')
	{
		str ++;
	}

	while (*str != '\0')
	{
		//如果是其他字符
		if (*str < '0' || *str > '9')
		{
			return 0;
		}
		num = num * 10 + (*str - '0');
		str ++;
	}
	if (minus)
	{
		num = -num;
	}
	return num;
}
           

2.整数转化为字符串

整数转化为字符串思路为，假设为12345，将每个数字取出加上‘0’即变为字符串，但是12345取出的顺序是54321，变成字符串后的顺序也是”54321“，因此需将转化完成后的字符串倒序。另外需要注意的是，如果数字为负数，则第一个字符为‘-’，即如果是-12345，则先转化为”54321-“，然后倒序为”-12345“

代码如下：

void my_itoa(const int num, char *str)
{
	int i = 0, j = 0;
	int tempnum = num;
	char tempstr[100];
	bool minus = false;
	if (tempnum < 0)
	{
		minus = true;
		tempnum = -tempnum;
	}

	while (tempnum > 0)
	{
		tempstr[i++] = tempnum % 10 + '0';
		tempnum = tempnum / 10;
	}
	if (minus)
	{
		tempstr[i] = '-';
		i++;
	}

	//倒序
	for (i = i-1; i >= 0; i--)
	{
		str[j ++] = tempstr[i];
	}
	str[j] = '\0';
	
}
           

3、字符串空格替换假设空间足够替换    如将一个字符串中空格替换为%20  举例为："a bcd e"替换为“a%20bcd%20e”

思路：从后往前替换，先计算出字符串中空格的数量，然后需加入的新字符数即为空格的数量*2，则替换后的字符串长度 = 替换之前字符串长度 + 空格数*2，然后从原字符串的末尾开始将字符添加到新字符串的末尾，遇到空格就替换为%20

需要注意：（1）留给替换字符串的空间应该是足够的，在替换函数的参数中是空间的长度，

                  （2）替换完成后字符串以‘\0’结尾

代码如下：

void replaceblank(char *str, int length)
{
	if (str == NULL)
	{
		return;
	}

	int count = 0; //记录空格数量
	int lenBeforeReplace = 0; //替换之前字符串长度
	int lenAfterReplace = 0; //替换之后字符串长度
	for(int i = 0; str[i] != '\0'; i++)
	{
		if (str[i] == ' ')
		{
			count ++;
		}
		lenBeforeReplace ++;
	}

	//计算替换后字符串长度
	lenAfterReplace = lenBeforeReplace + count * 2;
	if (lenAfterReplace + 1 > length)
	{
		return;
	}
	
	str[lenAfterReplace] = '\0';
	lenAfterReplace --;
	lenBeforeReplace --;

	//开始替换
	while (lenBeforeReplace >= 0)
	{
		if (str[lenBeforeReplace] == ' ')
		{
			str[lenAfterReplace --] = '%';
			str[lenAfterReplace --] = '0';
			str[lenAfterReplace --] = '2';
			lenBeforeReplace --;
		}
		str[lenAfterReplace --] = str[lenBeforeReplace --];
	}
}
           

4.字符串中第一次只出现一次的字符

思路：用哈希表，键为相应字符，值为字符出现的次数，因此字符数最多有256个，因此用特殊的哈希表---数组来记录，数组的下标为字符，数组的值为字符出现的次数。

代码如下：

char findoncechar(char *str)
{
	int tempstr[256] = {0};

	for (int i = 0; str[i] != '\0'; i++)
	{
		tempstr[(int)str[i]] ++;
	}

	for (int i = 0; i < 255; i++)
	{
		if (tempstr[i] == 1)
		{
			return i;
		}
	}
	return NULL;
}