把字符串转换成整数

Wu Jun 2020-01-14 21:25:28
01 数据结构与算法 > 算法题 > 字符串

题目出处

把字符串转换成整数

1 题目描述

将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。 数值为 0 或者字符串不是一个合法的数值则返回 0。

Iuput:
+2147483647
1a33

Output:
2147483647
0

2 解题思路

//思路是 JDK8 的 Integer.parseInt 方法
public class Solution {
    public int StrToInt(String str) {
        if (str == null || str.length() == 0){
            return 0;
        }
        //是否负数
        boolean negative = false;
        //字符串遍历游标
        int i = 0;
        /**
         * limit 默认初始化为 负的 最大正整数 ,假如字符串表示的是正数
         * 那么 result (在返回之前一直是负数形式)就必须和这个最大正数的负数来比较,
         * 判断是否溢出
         */
        int limit = -Integer.MAX_VALUE;
        // 首先看第一位
        char firstChar = str.charAt(0);
        // 如果第一位不是数字,可能是 "+" 或者 "-"
        if (firstChar < '0' || firstChar > '9') {
            if (firstChar == '-') {
                //如果是负号,判断溢出的值就变成了 整数的 最小负数了
                negative = true;
                limit = Integer.MIN_VALUE;
            } else if (firstChar != '+'){
                //第一位不是数字和-只能是+
                return 0;
            }
            // 如果只有一位,并且不是数字,也非法
            if (str.length() == 1) {
                return 0;
            }
            //游标去掉非数字的第一位
            i++;
        }

        // 上线除以 10,用于提前判断,避免溢出
        int lastLimit = limit / 10;
        int result = 0;
        // 遍历字符串
        // 负累计可避免在 MAX_VALUE 附近出现意外
        while (i < str.length()) {
            // 当前字符转 int
            int digit = str.charAt(i++) - '0';
            // 当前字符不是数字,非法
            if (digit < 0 || digit > 9){
                return 0;
            }

            // 因为下一步要乘以 10,在乘之前提前判断,若已经小于 lastLimit,则乘 10 后肯定溢出
            if (result < lastLimit) {
                return 0;
            }
            // 字符串转数字:已有数字乘以 10,再加上当前数字
            result = result * 10;
            // 如果 result 比 limit 加上 digit 还小的话,那 result 减去 digit 肯定就溢出了
            if (result < limit + digit) {
                return 0;
            }
            // result = 已有数字加上 digit
            result = result - digit;
        }

        //因为 result 一直是负数,需要修正
        return negative ? result : -result;
    }
}