Kotlin算法宝典：判断字符串是否是整数

【出自HW笔试题】

难度系数：★★★☆☆ 被考察系数：★★★☆☆

题目描述

写一个方法，检查字符串是否是整数，如果是，则返回其整数值。

分析与解答：

整数分为负数与非负数，负数只有一种表示方法，而整数可以有两种表示方法。例如：-123，123，+123。因此在判断字符串是否为整数的时候，需要把这几个问题都考虑到。下面主要介绍两种方法。

方法一：递归法

对于整数而言，例如123，可以看成12*10+3，而12又可以看成1*10+2。而-123可以看成（-12）*10-3，-12可以被看成（-1）*10-2。根据这个特点，可以采用递归的方法来求解，可以首先根据字符串的第一个字符确定整数的正负，接着对字符串从右往左遍历，假设字符串为“c₁c₂c₃c_n”，如果cn不是整数，那么这个字符串不能表示成整数；如果这个数是非负数（c1！=‘-’），那么这个整数的值为“c₁c₂c₃…c_n-1”对应的整数值乘以10加上cn对应的整数值，如果这个数是负数（c1==‘-’），那么这个整数的值为c₁c₂c₃…c_n-1对应的整数值乘以10减去cn对应的整数值。而求解子字符串“c1c2c3…sc-1”对应的整数的时候，可以用相同的方法来求解，因此可以采用递归的方法来求解。对于“+123”，可以首先去掉“+”，然后处理方法与“123”相同。由此可以得到递归表达式为

c1==‘-’？toint（“c1c2c3cn-1”）*10-（cn-'0'）：toint（“c1c2c3cn-1”）*10+（cn-'0'）。

递归的结束条件是：当字符串长度为1时，直接返回字符对应的整数的值。实现代码如下：

程序的运行结果如下：(www.xing528.com)

-543

543

543

不是数字

算法性能分析：

由于这种方法对字符串进行了一次遍历，因此时间复杂度为O（N）（其中，N是字符串的长度）。

方法二：非递归法

首先通过第一个字符的值确定整数的正负性，然后去掉符号位，把后面的字符串当作正数来处理，处理完成后再根据正负性返回正确的结果。实现方法为从左到右遍历字符串计算整数的值，以“123”为例，遍历到‘1’的时候结果为1，遍历到‘2’的时候结果为1*10+2=12，遍历到‘3’的时候结果为12*10+3=123。其本质思路与方法一类似，根据这个思路实现代码如下：

算法性能分析：

由于这种方法对字符串进行了一次遍历，因此，算法的时间复杂度为O（N）（其中，N是指字符串的长度）。但是由于方法一采用了递归法，而递归法需要大量的函数调用，也就有大量的压栈与弹栈操作（函数调用都是通过压栈与弹栈操作来完成的）。因此，虽然这两个方法有相同的时间复杂度，但是方法二的运行速度会比方法一更快，效率更高。