[Leetcode]8. 字符串转换整数 (atoi)

2019-01-24 本文已影响0人 LeeYunFeng

题目描述：
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 $[−2^{31}, 2^{31} − 1]$ 。如果数值超过这个范围，qing返回 INT_MAX $(2^{31} − 1)$ 或 INT_MIN $(−2^{31})$ 。

示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN $(−2^{31})$ 。

笨办法：
这是我第一反应方法：从左到右遍历字符串，记录下字符串的index和value（以下简称i和v），分别处理以下几种情况：

寻找第一个非空字符，记录下对应的i和v。此时的i记为start，如果v为+/-/数字则合法，否则为非法，并返回0。
start的初始值可以记为-1。
当i==start时，如果v为正负符号，记录op=1或-1。此时还不能判断数字合法，因为正负号后面可能跟着字母。
当i==start时，如果v为数字，则ans=ans*10+int(v)。ans的初始值为0.
当i>start时，随着i的增加，若v为非数字，则结束循环。

聪明办法：
看了别人的解法，发现至少有以下两个地方可以优化：

找第一个非空字符：无需使用循环，直接用str.strip()就可以了，应该会比用for循环快一点
判断是否超过上下限范围：可以不用放在for循环里面，放到最后再检测就行了。这样就只用检测一次，而非多次。

更简洁的方法：
python玩得更加熟练的一种方法：

将字符串去空格，并转换为数组ls。
判断ls[0]是否为正负符号，如果是，则记录下op同时del ls[0]（注意：只有数组才可用del()方法，字符串是没有del()方法的）。
处理后续数组中的数字，如果遇到非数字的字符，则停止。
判断是否超过上下限时，灵活使用min和max函数，max(-2**31,min(2**31-1,ans*op))。

笨办法：
显然这个办法不够简洁，用时52毫秒，仅击败28%的用户。

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        start=-1
        ans=0
        op=1
        hi,lo=2**31-1,-2**31
        for i,v in enumerate(str):
            #查找首个非空格字符的位置
            #注意不是非空，而是非空格
            if v!=' ' and start==-1:
                start=i
                if v in ('+','-'):
                    op=-1 if v=='-' else 1
                elif v>='0' and v<='9':
                    ans=ans*10+int(v)
                else:
                    return 0
            if start>=0 and i>start:
                if v>='0' and v<='9':
                    ans=ans*10+int(v)
                    if ans*op>=hi:
                        return hi
                    elif ans*op<=lo:
                        return lo
                else:
                    return ans*op
        return ans*op

聪明方法：
用时48ms，战胜49%的用户，看来还是不够简洁啊。

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        ans=0
        op=1
        str=str.strip()#剔除空格
        hi,lo=0x7FFFFFFF,-0x80000000#上下限
        # 处理首个字符
        if len(str)==0:
            return 0
        if str[0] in ('+','-'):
            op=-1 if str[0]=='-' else 1
        elif str[0]>='0' and str[0]<='9':
            ans=ans*10+int(str[0])
        else:
            return 0
        # 处理后续字符
        for i,v in enumerate(str[1:]):
            if v>='0' and v<='9':
                ans=ans*10+int(v)
            else:
                break
        # 判断合法性
        if ans*op>=hi:
            return hi
        elif ans*op<=lo:
            return lo
        return ans*op

更加简洁的方法：
虽然代码更简洁了，但是用时并没有减少，还是48ms，打败了49%的用户。

 class Solution(object):
    def myAtoi(self, s):
        """
        :type str: str
        :rtype: int
        """
        ls=list(s.strip())
        if len(ls)==0:
            return 0
        op=-1 if ls[0]=='-' else 1
        if ls[0] in ('+','-'):
            del ls[0]
        ans,i=0,0
        while i<len(ls) and ls[i].isdigit():
            ans=ans*10+int(ls[i])
            i+=1
        return min(2**31-1,max(-2**31,op*ans))

[Leetcode]8. 字符串转换整数 (atoi)

猜你喜欢

热点阅读