NO.8 字符串转换整数 (atoi) 中等
思路一:三步串行法 瞎起了一个名字,其实就是简单的三个步骤逐一进行即可:1.跳过所有空格。2.确定正负号。3.找出连续的数字并进行溢出判断。
判断每个字符是否是数字时,.第一个字符可以是‘+’或‘-’,其余字符都必须是数字,循环才能继续。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| public int myAtoi(String str) {
if(str==null)return 0;
String s = str.trim();
if (s.equals(""))return 0;
int flag=1; if (s.charAt(0)=='-')flag=-1;
int ans=0; for (int i=0;i<s.length();i++){ char c=s.charAt(i); if (c>='0'&&c<='9'){ if (flag==1){ if (ans>Integer.MAX_VALUE/10||(ans==Integer.MAX_VALUE/10&&c-'0'>7)) return Integer.MAX_VALUE; }else { if (ans*flag<Integer.MIN_VALUE/10||(ans*flag==Integer.MIN_VALUE/10&&c-'0'>8)) return Integer.MIN_VALUE; } ans=ans*10+c-'0'; }else if ((c=='-'||c=='+')&&i<1){
}else{ break; } } return ans*flag; }
|
最坏情况每个字符访问一次,所以时间复杂度是:O(n)
思路二:正则表达式法 这道题在leetcode上解答很少,因为题比较简单,大神都不屑于留恋。。
最简单的方法直接用正则,贴一个别人的python解法,一行代码:
1 2 3
| class Solution: def myAtoi(self, s: str) -> int: return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)
|
本人菜鸟,有错误请告知,感激不尽!
更多题解和学习记录博客:博客、github