首页 > 代码库 > No.008:String to Integer (atoi)
No.008:String to Integer (atoi)
题目:
Implement atoi to convert a string to an integer.
Hint:
Carefully consider all possible input cases.
官方难度:
Easy
翻译:
实现atoi算法,将一个字符串转成整数。
提示:仔细考虑各种可能情况。
补充资料:
atoi函数是C语言库中的一个函数,百度了一下其实现的功能如下:
Requirements for atoi:
1.The function first discards as many whitespace characters as necessary until the first non-whitespace character is found.
Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible,
and interprets them as a numerical value.
2.The string can contain additional characters after those that form the integral number,
which are ignored and have no effect on the behavior of this function.
3.If the first sequence of non-whitespace characters in str is not a valid integral number,
or if no such sequence exists because either str is empty or it contains only whitespace characters,
no conversion is performed.
4.If no valid conversion could be performed, a zero value is returned.
If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
atoi函数要求:
1.丢弃所有的空白字符串,直到遇到第一个非空格字符串。从那个非空字符串开始,如果第一个是“+”或“-”,尽可能多的返回之后跟的数字。
2.字符串可以在之前的整数后包含其他字符,忽视它,对函数没有影响,立即结束函数。
3.如果遇到的第一个非空字符串,不是一个整数,甚至于,字符串根本就是空的或完全由空白键组成,返回0。
4.如果不能有效转化,返回0;如果超出整型的最大/最小值,返回整型数的最大/最小值。
思路:
1.用String.trim()方法完成去空格工作,使用String.toCharArray()方法将字符串拆成字符数组。
2.考虑,去空格字符串长度为0情况。
3.用标志位记录数组第一位可能是操作符"-"或"+"的情况,然后将操作符的位置置为0,便于以后赋值处理。
4.记录最高位数,开始循环累加,直到遇上非数字,由于考虑超过int表示范围的情况,sum被声明为long型。
5.特殊考虑超出范围的情况。
解题中可能遇到的困难:
1.比较或赋值的时候,时刻注意是char型的,带上‘‘。
2.char型的字符数字,转成数字计算array[i] - ‘0‘。
3.Integer.MAX_VALUE和Integer.MIN_VALUE不是相反数的关系。
解题代码:
1 private static int method(String str) { 2 // 先去空格 3 char[] array = str.trim().toCharArray(); 4 // 0特殊处理 5 if (array.length == 0) { 6 return 0; 7 } 8 // 正负号标志位 9 int operatorFlag = 1;10 // 记录返回数字,超过long表示范围不考虑11 long sum = 0;12 if (array[0] == ‘+‘ || array[0] == ‘-‘ || (array[0] >= ‘0‘ && array[0] <= ‘9‘)) {13 // 操作符置0,便于统一处理14 if (array[0] == ‘+‘) {15 // 这里赋值,注意是char型的16 array[0] = ‘0‘;17 operatorFlag = 1;18 } else if (array[0] == ‘-‘) {19 array[0] = ‘0‘;20 operatorFlag = -1;21 }22 // 最高位23 int maxLevel = 0;24 // 循环确定最高位25 for (int i = 0; i < array.length; i++) {26 if (array[i] >= ‘0‘ && array[i] <= ‘9‘) {27 maxLevel++;28 } else {29 // 遇到非数字退出30 break;31 }32 }33 // 需要一个maxLevel的副本来赋值34 int copyMaxLevel = maxLevel;35 // 累加赋值,注意其实位置的下标36 for (int i = 0; i < maxLevel; i++) {37 // 注意char型的数字,转成数字的处理38 sum += (array[i] - ‘0‘) * Math.pow(10, --copyMaxLevel);39 }40 // 超出范围处理41 long realNumber = sum * operatorFlag;42 if (realNumber > Integer.MAX_VALUE) {43 return Integer.MAX_VALUE;44 }45 if (realNumber < Integer.MIN_VALUE) {46 return Integer.MIN_VALUE;47 }48 return (int) realNumber;49 } else {50 return 0;51 }52 }
测试代码地址:
https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/easy/Q008.java
LeetCode题目地址:
https://leetcode.com/problems/string-to-integer-atoi/
PS:如有不正确或提高效率的方法,欢迎留言,谢谢!
No.008:String to Integer (atoi)