最近在看算法的书，介绍的算法面试题都没有之前的几篇那么难懂，所以一直没有更新，今天更新字符串系列的最后两个算法面试题，两个算法题的篇幅都不长，所以合并到一起了。
- 字符串转整数 eg:"123"-->123
- 反转字符串 eg:"123"-->"321"
- 字符串的左旋转（和反转字符串是一个类型的题目）
1.字符串转整数
字符转数字本身并不难，当时我们需要考虑到很多特殊输入。比如说输入NULL，空字符串""，正负号，溢出等问题。把这些都考虑进去，就不是10几行代码能搞定的了。
核心转换代码：
下面是字符串转数字的核心代码，很简单，不用多解释。
int num = 0;
while(*str != '\0'){
num = num*10 + *str - '0';
str++;
}
代码：
思想：针对输入合法和输入不合法两个情况，设置一个全局的状态标志g_nStatus,非法输入的情况下，该值置为kInvalid，返回0。考虑以下输入：
1.输入NULL，""。
2.输入带有正负号的数字。
3.输入正负号，后面不带数字。
4.最大和最小整数，溢出问题。
直接上代码，看了代码自然就明白了。
/*输入字符串，minus是否为负数*/
long long StrToIntCore(const char* str, bool minus);
enum Status { kValid = 0, kInvalid };
int g_nStatus = kValid;//标记输入是否合法
int StrToInt(const char* str)
{
g_nStatus = kInvalid;
long long num = 0;//用long long类型的变量来保存结果
/*解决了输入NULL和空字符串""的问题*/
if (str != NULL && *str != '\0')
{
bool minus = false;
if (*str == '+')
str++;
else if (*str == '-')
{
str++;
minus = true;
}
/*处理了只输入正负号的情况*/
if (*str != '\0')
{
num = StrToIntCore(str, minus);
}
}
return (int)num;
}
long long StrToIntCore(const char* digit, bool minus)
{
long long num = 0;
while (*digit != '\0')
{
/*是否在0~9之间，0~9之外的是非法输入*/
if (*digit >= '0' && *digit <= '9')
{
int flag = minus ? -1 : 1;
num = num * 10 + flag * (*digit - '0');
/*判断是否超过了最大正整数，或小于最小负整数*/
if ((!minus && num > 0x7FFFFFFF)
|| (minus && num < (signed int)0x80000000))
{
num = 0;
break;
}
digit++;
}
else/*非法输入*/
{
num = 0;
break;
}
}
/*任何一个break退出的都一定是kInvalid*/
if (*digit == '\0')
{
g_nStatus = kValid;
}
return num;
}
void Test(char* string)
{
int result = StrToInt(string);
if (result == 0 && g_nStatus == kInvalid)
printf("the input %s is invalid.\n", string);
else
printf("number for %s is: %d.\n", string, result);
}
int main(int argc, char const *argv[])
{
Test(NULL);
Test("");
Test("123");
Test("+123");
Test("-123");
Test("1a33");
Test("+0");
Test("-0");
//有效的最大正整数, 0x7FFFFFFF
Test("+2147483647");
Test("-2147483647");
Test("+2147483648");
//有效的最小负整数, 0x80000000
Test("-2147483648");
Test("+2147483649");
Test("-2147483649");
Test("+");
Test("-");
return 0;
}
结果
字符串转整数
2.反转字符串
例1：给出一个单词序列，反转字符串中的单词的顺序，但是单词内字符串的顺序不变。eg:I am a student.==>sudent. a am I。
关于反转字符串的面试题，这个就很典型。基本思路就是先对整个字符串进行反转，得到.tneduts a ma I，然后针对每个单词进行反转。两次反转的结果就是题目要求了。
这种思想的关键就是实现一个在任意范围内反转字符串的函数：
/*反转pBegin~pEnd之间的单词序列*/
void Reverse(char *pBegin, char *pEnd){
if (pBegin == NULL || pEnd == NULL)
return;
while (pBegin < pEnd){
char temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
pBegin++;
pEnd--;
}
}
先反转整个句子，再反转句子中的单词。单词间以空格来分隔，所以我们可以根据空格，确定pBegin,pEnd，使得它们分别指向一个单词的开头和结尾。
char* ReverseSentence(char *pStr)
{
if (pStr == NULL)
return NULL;
char *pBegin = pStr;
char *pEnd = pStr;
while (*pEnd != '\0')
pEnd++;
pEnd--;//上一步结束之后，pEnd指向'\0'的位置，现在要前移一位，指向最后一个字符
/*反转整个字符串*/
Reverse(pBegin, pEnd);
//反转单词,pBegin和pEnd分别指向一个单词的开头个结尾
pBegin = pEnd = pStr;
while (*pBegin != '\0'){
/*单词间以空格区分*/
if (*pBegin == ' ')
{
pBegin++;
pEnd++;
}
else if (*pEnd == ' ' || *pEnd == '\0')//说明pEnd已经指向了一个单词的结尾
{
Reverse(pBegin, --pEnd);
pBegin = ++pEnd;
}
else
pEnd++;
}
return pStr;
}
结果：
第4，5个测试可以输入一个空格，多个空格。
反转字符串
例2：字符串的左旋转就是把字符串左边的若干个字符旋转到字符串的尾部。请定义一个函数，实现字符串左旋转的功能。eg:abcdef 左旋转2位==> cdefab
这个题可以用上面的方法来解，就是反转字符串。比如hello world==>world hello，就是把前后的部分反转到了后面。
下面以str = "ABCDE"为例，对前2个字符进行左旋转。
- 先对str[0...1]进行反转；ABCDE-->BACDE
- 对str[2...n-1]进行反转；BACDE-->BAEDC
- 全局范围内反转。BAEDC-->CDEAB
其实做旋转问题就是把字符串分为两部分，旋转的部分和旋转后面的部分，分别对其进行反转，再在全局范围上反转就可以得到。这样的题主要是找规律。
代码：
理清了思路就比较简单了，但是要注意针对输入为NULL的情况和越界的情况，代码中用n<nLength对越界的情况进行了处理，这些都是写代码的过程中容易忽略的。
//左旋转字符串，n是旋转位数
char* LeftRotateString(char* pStr, int n)
{
if (pStr != NULL)
{
int nLength = strlen(pStr);
if (nLength > 0 && n > 0 && n < nLength)
{
char* pFirstStart = pStr;
char* pFirstEnd = pStr + n - 1;
char* pSecondStart = pStr + n;
char* pSecondEnd = pStr + nLength - 1;
// 翻转字符串的前面n个字符
Reverse(pFirstStart, pFirstEnd);
// 翻转字符串的后面部分
Reverse(pSecondStart, pSecondEnd);
// 翻转整个字符串
Reverse(pFirstStart, pSecondEnd);
}
}
return pStr;
}
网友评论