专栏首页测试开发架构之路程序员面试50题(4)—把字符串转换成整数[算法]

程序员面试50题(4)—把字符串转换成整数[算法]

题目:输入一个表示整数的字符串,把该字符串转换成整数并输出。例如输入字符串"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};
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);
}

原文:http://zhedahht.blog.163.com/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • nginx配置文件nginx.conf超详细讲解

    #nginx进程,一般设置为和cpu核数一样 worker_processes 4;                         #错误日志存放目录 er...

    互联网金融打杂
  • Android软件测试Monkey测试工具

    前言: 最近开始研究Android自动化测试方法,对其中的一些工具、方法和框架做了一些简单的整理,其中包括android测试框架、CTS、Monkey、Monk...

    互联网金融打杂
  • C语言之Sleep函数

    Sleep函数: 功 能: 执行挂起一段时间   用 法: unsigned sleep(unsigned seconds);   注意:   在VC中使用带上...

    互联网金融打杂
  • Python的基本数据类型之Number

    Python下载地址: https://www.python.org/downloads/

    py3study
  • Python编程思想(4):字符串类型

    字符串的意思就是“一串字符”,也可以看做是字符的序列。比如“Helo, Mike”是一个字符串,“How are you?”也是一个字符串。Python要求字符...

    蒙娜丽宁
  • Linux磁盘及文件系统管理

    磁盘(Hard Disk Drive,简称HDD)是一种存储介质,传统的机械硬盘由一个或多个铝制或玻璃制的碟片组成,碟片外覆盖有铁磁性材料。 磁盘的物...

    小小科
  • VAIN:Attentional Multi-agent Predictive Modeling

    Hoshen Y. VAIN: Attentional Multi-agent Predictive Modeling[J]. arXiv preprint a...

    企鹅号小编
  • 移动端布局伸缩、设置div高度等比例缩放

    随着移动端的屏幕大小,div的布局宽度是设置100%,所以可以跟着变化。但是高度是固定写了10rem的高度,这样是无法随着宽度变化进行等比例变化的。

    Devops海洋的渔夫
  • JavaWEB+Ajax实现文件上传

    准备:我们需要找一张绿色或者其它颜色的背景图,放在photo文件夹里就好哈,然后加jar:common-io和commo-fileupload就可以哈

    SmileNicky
  • javascript读写本机文本文件

    近日在工作中遇到了一个情况:一张纯html的网页,用它一条一条输入数据,然后由JS运算出结果(这些数据多半都是临时的,所以也没考虑保存到数据库),每次用完后换台...

    菩提树下的杨过

扫码关注云+社区

领取腾讯云代金券