【算法】字符串转int类型思路及代码

忘是亡心i 2024-03-17 11:08 37阅读 0赞

#### 文章目录 ####

*  题目
 *  分析
 *  思路
 *  完整代码

## 题目 ##

给你一个字符串，如何这个字符串符合日常的整形的书写规范，那么我们需要写出将其转化为int类型的方法，并且不能使用Java提供的API，比如parseInt方法。

## 分析 ##

这道题考察的其实就是parseInt的底层思路实现，相当于是你自己要学会写出一个parseInt方法。  
并且考虑到需要将字符串转换为int，那么首先我们要保证，这个字符串符合int类型的格式，并且不会发生溢出。  
有如下几种情况需要保证：  
1：这个字符串可以为 ‘ - ’开头，但是不能只有一个 ‘ - ’  
2：这个字符串开头为0时字符串长度必须也为1  
3：不能发生溢出，也就是字符串的值不能大于 2147483647，不能小于 - 2147483648  
4：字符串中不能出现除了 ‘ - ’，‘0’ - ‘9’的任何其他非法字符，比如 ‘A’

## 思路 ##

1：我们可以先编写一个方法，判断这个字符串对应的数据是否符合它是一个数字类型的要求。  
方法如下：

public static boolean isValid(String str) {
        
            char[] chars = str.toCharArray();
            //1:判断字符串不以 ‘ - ’开头并且也不是数字开头
            if (chars[0] != '-' && (chars[0] < '0' || chars[0] > '9') {
        
                return false;
            }
            //2:字符串以'-'开头,但是长度为1,或长度不为1,但是chars[1]='0'
            if (chars[0] == '-' && (chars.length == 1 || chars[1] == '0')) {
        
                return false;
            }
            //3:字符串以0开头,但是长度不为1
            if (chars[0] == '0' && chars.length != 1) {
        
                return false;
            }
            //4:判断字符串中是否有非法字符
            for (int i = 1; i < chars.length; i++) {
        
                if (chars[i] > '9' || chars[i] < '0') {
        
                    return false;
                }
            }
            return true;
        }

2：成功判断当前字符串是否是一个合格的整形之后，我们开始具体的转换思路。  
首先，根据字符串的正负进行判断，如果是以 ‘ - ’开头，那么从字符串的下标1处开始遍历，否则从0开始遍历。  
然后，得到数据的方式其实就是，我们从字符串的左边开始遍历，当前值（初始为0）乘\*10+当前位的值即可。  
先看下面一段不考虑溢出的代码，你可能会这么写。

public static int parseInt(String str) {
        
            int cur = 0;
            int res = 0;
            boolean negative = str.charAt(0) == '-' ? true : false;
            for (int i = negative ? 1 : 0; i < str.length(); i++) {
        
                cur = str.charAt(i)-'0';
                res = res * 10+cur;
            }
            return negative?-1*res : res;
        }
    
        public static void main(String[] args) {
        
            System.out.println(parseInt("-123123"));
        }

对于不考虑溢出的情况，当然可以怎么写，答案也是对的，但是如果我们输入的字符串会溢出，那么我们处理起来会比较棘手，原因如下：  
我们输入一个超出int范围的数据，那么就会溢出，从而导致数据的不准确。  
![在这里插入图片描述][5e27db7290294dec91cfb88fe594736b.png]  
可能你会认为加一个判断即可，但是很明显，在这里，如果我们在已经得到了最后的res之后进行判断，明显是不合理的，因为此时要么已经溢出，要么就是需要将long类型和int类型去比较，不太合理。  
因此我们的解决思路是，得到 Integer.MAX\_VALUE除以10的哪一个数据，然后这样子就能做到提前比较是否溢出。  
代码如下：

public static int parseInt(String str) {
        
            int cur = 0;
            int res = 0;
            int maxQ = Integer.MAX_VALUE / 10;
            int maxP = Integer.MAX_VALUE % 10;
    
            boolean negative = str.charAt(0) == '-' ? true : false;
            for (int i = negative ? 1 : 0; i < str.length(); i++) {
        
                cur = str.charAt(i) - '0';
                //如果此时res已经大于了int最大值/10，并且此时cur还没有加上去就已经大于了，那么说明肯定溢出，直接返回0
                //如果等于，但是cur大于最后一位，那么也是溢出，也返回
                if (res > maxQ || (res == maxQ && cur > maxP) ||
                        (res == maxQ && negative && cur > maxP + 1)){
        
                    return 0;
                }
                res = res * 10 + cur;
            }
            return negative ? -1 * res : res;
        }
    
        public static void main(String[] args) {
        
            System.out.println(parseInt("-2147483649")); // 0 
            System.out.println(parseInt("2147483649")); // 0 
        }

如下代码是Java的Integer提供的字符串转int类型的方法

public static int parseInt(String s, int radix)
                    throws NumberFormatException
        {
        
            /*
             * WARNING: This method may be invoked early during VM initialization
             * before IntegerCache is initialized. Care must be taken to not use
             * the valueOf method.
             */
    
            if (s == null) {
        
                throw new NumberFormatException("null");
            }
    
            if (radix < Character.MIN_RADIX) {
        
                throw new NumberFormatException("radix " + radix +
                                                " less than Character.MIN_RADIX");
            }
    
            if (radix > Character.MAX_RADIX) {
        
                throw new NumberFormatException("radix " + radix +
                                                " greater than Character.MAX_RADIX");
            }
    
            int result = 0;
            boolean negative = false;
            int i = 0, len = s.length();
            int limit = -Integer.MAX_VALUE;
            int multmin;
            int digit;
    
            if (len > 0) {
        
                char firstChar = s.charAt(0);
                if (firstChar < '0') {
         // Possible leading "+" or "-"
                    if (firstChar == '-') {
        
                        negative = true;
                        limit = Integer.MIN_VALUE;
                    } else if (firstChar != '+')
                        throw NumberFormatException.forInputString(s);
    
                    if (len == 1) // Cannot have lone "+" or "-"
                        throw NumberFormatException.forInputString(s);
                    i++;
                }
                multmin = limit / radix;
                while (i < len) {
        
                    // Accumulating negatively avoids surprises near MAX_VALUE
                    digit = Character.digit(s.charAt(i++),radix);
                    if (digit < 0) {
        
                        throw NumberFormatException.forInputString(s);
                    }
                    if (result < multmin) {
        
                        throw NumberFormatException.forInputString(s);
                    }
                    result *= radix;
                    if (result < limit + digit) {
        
                        throw NumberFormatException.forInputString(s);
                    }
                    result -= digit;
                }
            } else {
        
                throw NumberFormatException.forInputString(s);
            }
            return negative ? result : -result;
        }

## 完整代码 ##

package com.base.learn.string;
    
    /**
     * @author: 张锦标
     * @date: 2023/5/25 9:57
     * ParseInt类
     */
    public class ParseInt {
        
        public static boolean isValid(String str) {
        
            char[] chars = str.toCharArray();
            //1:判断字符串不以 ‘ - ’开头并且也不是数字开头
            if (chars[0] != '-' && (chars[0] < '0' || chars[0] > '9')) {
        
                return false;
            }
            //2:字符串以'-'开头,但是长度为1,或长度不为1,但是chars[1]='0'
            if (chars[0] == '-' && (chars.length == 1 || chars[1] == '0')) {
        
                return false;
            }
            //3:字符串以0开头,但是长度不为1
            if (chars[0] == '0' && chars.length != 1) {
        
                return false;
            }
            //4:判断字符串中是否有非法字符
            for (int i = 1; i < chars.length; i++) {
        
                if (chars[i] > '9' || chars[i] < '0') {
        
                    return false;
                }
            }
            return true;
        }
    
        public static int parseInt(String str) {
        
            int cur = 0;
            int res = 0;
            int maxQ = Integer.MAX_VALUE / 10;
            int maxP = Integer.MAX_VALUE % 10;
            //如果此时res已经大于了int最大值/10，并且此时cur还没有加上去就已经大于了，
            // 那么说明肯定溢出，直接返回0
            //如果等于，但是cur大于最后一位，那么也是溢出，也返回
            boolean negative = str.charAt(0) == '-' ? true : false;
            for (int i = negative ? 1 : 0; i < str.length(); i++) {
        
                cur = str.charAt(i) - '0';
                if (res > maxQ || (res == maxQ && cur > maxP) ||
                        (res == maxQ && negative && cur > maxP + 1)){
        
                    return 0;
                }
                res = res * 10 + cur;
            }
            return negative ? -1 * res : res;
        }
    
        public static void main(String[] args) {
        
            String s = "123asd";
            if (!isValid(s)){
        
                //do something
            }else{
        
                parseInt(s);
            }
        }
    }

[5e27db7290294dec91cfb88fe594736b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/105496a123df408dbc83ad4fa3f269d1.png