题目:输入一个表示整数的字符串,把该字符串转换成整数并输出。例如输入字符串"345",则输出整数345。
分析:这道题尽管不是很难,学过C/C++语言一般都能实现基本功能,但不同程序员就这道题写出的代码有很大区别,可以说这道题能够很好地反应出程序员的思维和编程习惯,因此已经被包括微软在内的多家公司用作面试题。建议读者在往下看之前自己先编写代码,再比较自己写的代码和下面的参考代码有哪些不同。 首先我们分析如何完成基本功能,即如何把表示整数的字符串正确地转换成整数。还是以"345"作为例子。当我们扫描到字符串的第一个字符'3'时,我们不知道后面还有多少位,仅仅知道这是第一位,因此此时得到的数字是3。当扫描到第二个数字'4'时,此时我们已经知道前面已经一个3了,再在后面加上一个数字4,那前面的3相当于30,因此得到的数字是3*10+4=34。接着我们又扫描到字符'5',我们已经知道了'5'的前面已经有了34,由于后面要加上一个5,前面的34就相当于340了,因此得到的数字就是34*10+5=345。 分析到这里,我们不能得出一个转换的思路:每扫描到一个字符,我们把在之前得到的数字乘以10再加上当前字符表示的数字。这个思路用循环不难实现。 由于整数可能不仅仅之含有数字,还有可能以'+'或者'-'开头,表示整数的正负。因此我们需要把这个字符串的第一个字符做特殊处理。如果第一个字符是'+'号,则不需要做任何操作;如果第一个字符是'-'号,则表明这个整数是个负数,在最后的时候我们要把得到的数值变成负数。 接着我们试着处理非法输入。由于输入的是指针,在使用指针之前,我们要做的第一件是判断这个指针是不是为空。如果试着去访问空指针,将不可避免地导致程序崩溃。另外,输入的字符串中可能含有不是数字的字符。每当碰到这些非法的字符,我们就没有必要再继续转换。最后一个需要考虑的问题是溢出问题。由于输入的数字是以字符串的形式输入,因此有可能输入一个很大的数字转换之后会超过能够表示的最大的整数而溢出。 现在已经分析的差不多了,开始考虑编写代码。首先我们考虑如何声明这个函数。由于是把字符串转换成整数,很自然我们想到: int StrToInt(const char* str); 这样声明看起来没有问题。但当输入的字符串是一个空指针或者含有非法的字符时,应该返回什么值呢?0怎么样?那怎么区分非法输入和字符串本身就是”0”这两种情况呢? 接下来我们考虑另外一种思路。我们可以返回一个布尔值来指示输入是否有效,而把转换后的整数放到参数列表中以引用或者指针的形式传入。于是我们就可以声明如下: bool StrToInt(const char *str, int& num); 这种思路解决了前面的问题。但是这个函数的用户使用这个函数的时候会觉得不是很方便,因为他不能直接把得到的整数赋值给其他整形变量,显得不够直观。 前面的第一种声明就很直观。如何在保证直观的前提下当碰到非法输入的时候通知用户呢?一种解决方案就是定义一个全局变量,每当碰到非法输入的时候,就标记该全局变量。用户在调用这个函数之后,就可以检验该全局变量来判断转换是不是成功。 下面我们写出完整的实现代码。参考代码: enum Status {kValid = 0, kInvalid};//是否存在非法状况 讨论:在参考代码中,我选用的是第一种声明方式。不过在面试时,我们可以选用任意一种声明方式进行实现。但当面试官问我们选择的理由时,我们要对两者的优缺点进行评价。第一种声明方式对用户而言非常直观,但使用了全局变量,不够优雅;而第二种思路是用返回值来表明输入是否合法,在很多API中都用这种方法,但该方法声明的函数使用起来不够直观。 最后值得一提的是,在C语言提供的库函数中,函数atoi能够把字符串转换整数。它的声明是int atoi(const char*str)。该函数就是用一个全局变量来标志输入是否合法的。
int g_nStatus = kValid;
///////////////////////////////////////////////////////////////////////
// Convert a string into an integer
///////////////////////////////////////////////////////////////////////
int StrToInt(const char* str)
{
g_nStatus = kInvalid;
long long num = 0;
if(str != NULL) //判断是否为空
{
const char* digit = str;
// the first char in the string maybe '+' or '-'
bool minus = false;
if(*digit == '+')
digit ++;
else if(*digit == '-')
{
digit ++;
minus = true;
}
// the remaining chars in the string
while(*digit != '\0')//循环截止条件
{
if(*digit >= '0' && *digit <= '9')//判断字符串是否为数字
{
num = num * 10 + (*digit - '0');//核心转换公式
// overflow
if(num > std::numeric_limits<int>::max())//判断是否溢出
{
num = 0;
break;
}
digit ++;
}
// if the char is not a digit, invalid input
else //是否含有非数字字符
{
num = 0;
break;
}
}
if(*digit == '\0')//判断字符串是否转换完毕
{
g_nStatus = kValid;
if(minus)
num = 0 - num;
}
}
return static_cast<int>(num);
}
发表评论
-
析构函数为虚函数的原因
2012-09-09 11:42 786我们知道,用C++开发的时候,用来做基类的类的析构函数 ... -
hash的应用
2012-08-31 23:02 925第一部分为一道百度面试题Top K算法的详解;第二部分为关 ... -
微软智力题
2012-08-29 19:59 538第一组1.烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有 ... -
C++不能被继承的类
2012-08-27 20:16 997一个类不能被继承, ... -
括号对齐问题
2012-08-27 10:47 1352解法一:左右括号成一对则抵消 可以 ... -
树的遍历
2012-08-19 10:43 679/****************************** ... -
堆排序
2012-08-16 14:24 844堆:(二叉)堆数据结构是一种数组对象。它可以被视为一棵完全 ... -
多态赋值
2012-08-14 16:16 777#include <iostream> usi ... -
static变量与static函数(转)
2012-08-13 10:15 702一、 static 变量 static变量大致分为三种用法 ... -
不用sizeof判断16位32位
2012-08-10 15:21 1663用C++写个程序,如何判断一个操作系统是16位还是3 ... -
找出连续最长的数字串(百度面试)
2012-08-09 15:15 1111int maxContinuNum(const char*in ... -
顺序栈和链栈
2012-08-06 10:01 767顺序栈:话不多说直接上代码 #include ... -
队列的数组实现和链表实现
2012-08-05 16:20 995话不多少,数组实现上代码: #include<i ... -
KMP算法详解
2012-08-02 21:40 850KMP算法: 是在一个“主文本字符串” ... -
字符串的最长连续重复子串
2012-08-01 15:05 9700两种方法: 循环两次寻找最长的子串: <方法一> ... -
寻找一个字符串连续出现最多的子串的方法(转)
2012-07-31 21:19 917算法描述首先获得后缀数组,然后1.第一行第一个字符a,与第二行 ... -
字符串的循环移位
2012-07-31 16:52 935假设字符串:abcdefg 左循环两位:cdefgab 右 ... -
一次谷歌面试趣事(转)
2012-07-31 15:26 726很多年前我进入硅谷 ... -
约瑟夫环问题(循环链表)
2012-07-30 21:31 1242题目描述:n只猴子要选大王,选举方法如下:所有猴子按 1, ... -
面试之单链表
2012-07-30 20:18 6911、编程实现一个单链表的建立/测长/打印。 ...
相关推荐
程序员面试题精选100题
程序员面试题精选100题
程序员面试题精选程序员面试题精选程序员面试题程序员面试题精选精选
程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试...
程序员面试题精选100题-何海涛 程序员 面试题 算法 数据结构
程序员面试题精选100题(2008)程序员面试题精选100题(2008)
程序员面试题精选100题
一份可以让大家在求职时更能自信的题解,经典的100题,让大家可以感受到算法的经典,当然,自己要更加努力,要懂得举一反三才能更上一层楼!
程序员面试题精选100题
------------------------------------- java程序员早期面试题汇总 BAT经典面试题汇总.pdf Java常考面试题.pdf java面试题(题库全)....程序员面试题精选100题.pdf ... -------------------------------------
程序员面试题精选100题,以前下过的不全,自己在网上搜了搜,整理了一下。