[LeetCode] String to Integer (atoi)

题意

给出一个字符串，trim 之后，按照 PHP 的方式将其转成 int。

题解

好吧……“按照 PHP 的方式”……

首先，可以以 + 或者 - 开头。其次，转换不下去的话就停止。

最后，把结果限定在 int 范围内。

第一次尝试

正则表达式大法好啊，写起来简单啊！

先做 trim，然后正则出来第一个结果，然后 int() 一下就好了。如果没有结果，pass。

这种做法呢，还有一个好处：如果说让你把串中所有的数字都转换出来，也是超级简单的：match 改为 findall 就好了。超级省心。

缺点么…… 时间，时间。

代码

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        import re

        INT_MAX = 2147483647
        INT_MIN = -2147483648

        ans = 0
        match = re.match(r'(^[\-\+]?\d+)', str.strip())

        if match:
            ans = int(match.group(0))

        ans = min(ans, INT_MAX)
        ans = max(ans, INT_MIN)

        return ans

运行结果

1047 / 1047 test cases passed.
Status: Accepted
Runtime: 159 ms

Your runtime beats 1.08% of pythonsubmissions.

OK 我不是最慢的～

第二次尝试

没啥技巧…… 最最传统的做法。

代码

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """

        INT_MAX = 2147483647
        INT_MIN = -2147483648

        sym = 1
        ans = 0
        str = str.strip()
        if len(str) == 0:
            return 0
        if str[0] in ['-', '+']:
            if str[0] == '-':
                sym = -1
            elif str[0] == '+':
                sym = 1
            str = str[1:]

        for x in str:
            if '0' <= x <= '9':
                ans = ans * 10 + int(x)
            else:
                break
        ans *= sym

        ans = min(ans, INT_MAX)
        ans = max(ans, INT_MIN)

        return ans

运行结果

1047 / 1047 test cases passed.
Status: Accepted
Runtime: 92 ms

其他想法

虽然传统办法比第一次正则表达式的办法快了不少，但是还是很慢啊。所以呢，可以用一个 ptr 记录当前最后位置，这样能少做一些乘法。

桩程序

if __name__ == '__main__':
    cases = [
        {'x': '123', 'ans': 123},
        {'x': '+123', 'ans': 123},
        {'x': '-123', 'ans': -123},
        {'x': '-123 123', 'ans': -123},
        {'x': '123', 'ans': 123},
        {'x': 'aa123aa', 'ans': 0},
        {'x': 'aa-123aa', 'ans': 0},
        {'x': '2147463847', 'ans': 2147463847},
        {'x': '2147483648', 'ans': 2147483647},
        {'x': 'aa123bb-456', 'ans': 0},
    ]

    for item in cases:
        ans = (Solution()).myAtoi(str=item['x'])
        print(str(ans == item['ans']) + "\t=>" + str(ans) + ":" + str(item['ans']))