点击上方“蓝色字体”,选择“设为星标”
每天复习一道面试题,轻松拿大厂Offer~
题目描述:
请你来实现一个atoi
函数,使其能将字符串转换成整数。
首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下:
如果第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字字符组合起来,形成一个有符号整数。假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成一个整数。该字符串在有效的整数部分之后也可能会存在多余的字符,那么这些字符可以被忽略,它们对函数不应该造成影响。
注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换,即无法进行有效转换。
在任何情况下,若函数不能进行有效的转换时,请返回 0 。
提示:
本题中的空白字符只包括空格字符' '
。假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例1:
输出:42输入:"42"
示例2:
输出:-42 解释:第一个非空白字符为'-', 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到-42 。输入:"-42"
示例3:
输出:4193 解释:转换截止于数字'3',因为它的下一个字符不为数字。输入:"4193withwords"
示例4:
输出:0 解释:第一个非空字符是'w', 但它不是数字或正、负号。 因此无法执行有效的转换。输入:"wordsand987"
示例5:
输出:-2147483648 解释:数字"-91283472332"超过 32 位有符号整数范围。 因此返回 INT_MIN (−231)。输入:"-91283472332"
难度:
难度:中等支持语言:JavaScript、Java、Python相关标签
字符串数学相关企业
阿里大疆腾讯思路 1(javascript):
这道题涉及的情况有4种,因此需要先完全考虑清楚它们的关系,否则会容易漏掉一些规则出错。
空格:空格只有在前面没有任何字符的情况下才能继续处理,如果前面存在任何字符,遇到空格直接跳出。字母:遇到字母直接跳出。正负号:只有在还没有出现正负号或者数字的情况,正负号才有效,否则跳出。数字:遇到数字如果前面无zhengfuhao正负号,说明是正号。
思路 2:
字符串处理的题目往往涉及复杂的流程以及条件情况,如果直接上手写程序,一不小心就会写出极其臃肿的代码。
因此,为了有条理地分析每个输入字符的处理方法,我们可以使用自动机这个概念:
我们的程序在每个时刻有一个状态s
,每次从序列中输入一个字符c
,并根据字符c
转移到下一个状态s
'。这样,我们只需要建立一个覆盖所有情况的从s
与c
映射到s
' 的表格即可解决题目中的问题。
思路 3:
使用正则表达式:[\+\-]:代表一个+字符或-字符 ?:前面一个字符可有可无 \d:一个数字 +:前面一个字符的一个或多个 \D:一个非数字字符 *:前面一个字符的0个或多个^:匹配字符串开头
max(min(数字, 231 - 1), -231) 用来防止结果越界
为什么可以使用正则表达式?如果整数过大溢出怎么办?
首先,这个假设对于 Python 不成立,Python 不存在 32 位的 int 类型。其次,即使搜索到的字符串转32位整数可能导致溢出,我们也可以直接通过字符串判断是否存在溢出的情况(比如 try 函数 或 判断字符串长度 + 字符串比较)~
复杂度分析
时间复杂度:O(N)O(N),这里 NN 为字符串的长度;空间复杂度:O(1)O(1)。代码
JavaScript 实现
*@来源:Javascript中文网-前端进阶资源教程 / *@介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容 *@param{string}str *@return{number} */ varmyAtoi=function(str){ letisNeg=null letfirst=false letnumS=0 for(leti=0;iif(!first&&str[i]==='')continue first=true if(isNeg==null&&str[i]==="+"){ isNeg=false }elseif(isNeg==null&&str[i]==="-"){ isNeg=true }elseif(/\d/.test(str[i])){ isNeg=!!isNeg numS=numS*10+str[i]*1 }else{ break } } letres=isNeg?-numS:numS, limit=Math.pow(2,31) if(res>limit-1)res=limit-1 if(resreturnres };/**
*@作者:gatsby-23 *@链接:https://leetcode-/problems/string-to-integer-atoi/solution/javascripttou-ji-qu-qiao-wu-xu-si-kao-yi-kan-jiu-h/ *@param{string}str *@return{number} */ varmyAtoi=function(str){ constnumber=parseInt(str,10); if(isNaN(number)){ return0; }elseif(numberMath.pow(-2,31)||number>Math.pow(2,31)-1){ returnnumberMath.pow(-2,31)?Math.pow(-2,31):Math.pow(2,31)-1; }else{ returnnumber; } };/**
*@作者:liu-zi-qian-2 *@链接:https://leetcode-/problems/string-to-integer-atoi/solution/8-zi-fu-chuan-zhuan-huan-zheng-shu-atoi-by-liu-zi-/ *@param{string}str *@return{number} */ varmyAtoi=function(str){ str=str.trim(); if(!/^[+|-]?\d+/.test(str))return0; letval=parseInt(str.match(/^[+|-]?\d+/)); letbase=Math.pow(2,31) letmin=-base; letmax=base-1; returnMath.max(Math.min(val,max),min) };/**
Java 实现
*@作者:liweiwei1419 *@链接:https://leetcode-/problems/string-to-integer-atoi/solution/jin-liang-bu-shi-yong-ku-han-shu-nai-xin-diao-shi-/ */ publicclassSolution{ publicintmyAtoi(Stringstr){ intlen=str.length(); //str.charAt(i)方法回去检查下标的合法性,一般先转换成字符数组 char[]charArray=str.toCharArray(); //1、去除前导空格 intindex=0; while(index''){ index++; } //2、如果已经遍历完成(针对极端用例"") if(index==len){ return0; } //3、如果出现符号字符,仅第1个有效,并记录正负 intsign=1; charfirstChar=charArray[index]; if(firstChar=='+'){ index++; }elseif(firstChar=='-'){ index++; sign=-1; } //4、将后续出现的数字字符进行转换 //不能使用long类型,这是题目说的 intres=0; while(indexcharcurrChar=charArray[index]; //4.1先判断不合法的情况 if(currChar>'9'||currChar'0'){ break; } //题目中说:环境只能存储 32 位大小的有符号整数,因此,需要提前判:断乘以 10以后是否越界 if(res>Integer.MAX_VALUE/10||(res==Integer.MAX_VALUE/10&&(currChar-'0')>Integer.MAX_VALUE%10)){ returnInteger.MAX_VALUE; } if(res10||(res==Integer.MIN_VALUE/10&&(currChar-'0')>-(Integer.MIN_VALUE%10))){ returnInteger.MIN_VALUE; } //4.2合法的情况下,才考虑转换,每一步都把符号位乘进去 res=res*10+sign*(currChar-'0'); index++; } returnres; } publicstaticvoidmain(String[]args){ Solutionsolution=newSolution(); Stringstr="2147483646"; intres=solution.myAtoi(str); System.out.println(res); System.out.println(Integer.MAX_VALUE); System.out.println(Integer.MIN_VALUE); } }/**
classSolution{ publicintmyAtoi(Stringstr){ //清空字符串开头和末尾空格(这是trim方法功能,事实上我们只需清空开头空格) str=str.trim(); //java正则表达式 Patternp=pile("^[\\+\\-]?\\d+"); Matcherm=p.matcher(str); intvalue=0; //判断是否能匹配 if(m.find()){ //字符串转整数,溢出 try{ value=Integer.parseInt(str.substring(m.start(),m.end())); }catch(Exceptione){ //由于有的字符串"42"没有正号,所以我们判断'-' value=str.charAt(0)=='-'?Integer.MIN_VALUE:Integer.MAX_VALUE; } } returnvalue; } }importjava.util.regex.*;
*@作者:sweetiee *@链接:https://leetcode-/problems/string-to-integer-atoi/solution/java-zi-fu-chuan-zhuan-zheng-shu-hao-dong-by-sweet/ */ publicclassSolution{ publicintmyAtoi(Stringstr){ char[]chars=str.toCharArray(); intn=chars.length; intidx=0; while(idx''){ //去掉前导空格 idx++; } if(idx==n){ //去掉前导空格以后到了末尾了 return0; } booleannegative=false; if(chars[idx]=='-'){ //遇到负号 negative=true; idx++; }elseif(chars[idx]=='+'){ //遇到正号 idx++; }elseif(!Character.isDigit(chars[idx])){ //其他符号 return0; } intans=0; while(idxintdigit=chars[idx]-'0'; if(ans>(Integer.MAX_VALUE-digit)/10){ //本来应该是ans*10+digit>Integer.MAX_VALUE //但是*10和+ digit 都有可能越界,所有都移动到右边去就可以了。 returnnegative?Integer.MIN_VALUE:Integer.MAX_VALUE; } ans=ans*10+digit; idx++; } returnnegative?-ans:ans; } }/**
Python 实现
#链接:https://leetcode-/problems/string-to-integer-atoi/solution/python-1xing-zheng-ze-biao-da-shi-by-knifezhu/ classSolution: defmyAtoi(self,s:str)->int: returnmax(min(int(*re.findall('^[\+\-]?\d+',s.lstrip())),2**31-1),-2**31)#作者:QQqun902025048
#@链接:https://leetcode-/problems/string-to-integer-atoi/solution/san-chong-fang-fa-zheng-chang-bian-li-you-xian-zhu/ classSolution: defmyAtoi(self,str:str)->int: i=0 n=len(str) whileiandstr[i]=='': i=i+1ifn==0ori==n:return0 flag=1ifstr[i]=='-': flag=-1ifstr[i]=='+'orstr[i]=='-': i=i+1 INT_MAX=2**31-1 INT_MIN=-2**31 ans=0whileiand'0'<=str[i]<='9': ans=ans*10+int(str[i])-int('0') i+=1if(ans-1>INT_MAX):break ans=ans*flagifans>INT_MAX:returnINT_MAXreturnINT_MINifanselseans#@作者:yun-yu-chen
#@链接:https://leetcode-/problems/string-to-integer-atoi/solution/wo-shi-liao-19ci-ni-men-ni-by-yi-wen-statistics/ classSolution: defmyAtoi(self,s:str)->int: ''' 自定义匹配规则(自上而下,按顺序排除特殊情况): 1.将第一个字符为非有效字符的字符串、空白字符串、不含数字的字符串以及空字符串排除 2.如果第一位是正负号,此时它后面必须为数字,否则一定无效 3.如果第一位是正负号,那么扫描出有效整数 4.如果第一位是数字,那么同样扫描出有效整数 5.得出有效整数以后,需要排除前置0 6.输出结果 ''' #第一步 countInvalidChar=0 judgeFirstChar=False firstChar=''; firstCharIndex=-1; forcharIndexinrange(len(s)): ifs[charIndex]!=''ands[charIndex]in"-+0123456789"andnotjudgeFirstChar: firstChar=s[charIndex] firstCharIndex=charIndex judgeFirstChar=True ifs[charIndex]!=''ands[charIndex]notin"-+0123456789"andnotjudgeFirstChar: judgeFirstChar=True return0 ifs[charIndex]in"-+0123456789": countInvalidChar+=1 ifcountInvalidChar==0: return0 #第二步 iffirstCharin"-+": iffirstCharIndex+1==len(s): return0 else: ifs[firstCharIndex+1]notin"0123456789": return0 else:#第三步 i=firstCharIndex+1#设定指针,扫描charIndex后的数据 invalidInteger=firstChar whileiands[i]in"0123456789": invalidInteger+=s[i] i+=1 else:#第四步 j=firstCharIndex+1 invalidInteger=firstChar whilejands[j]in"0123456789": invalidInteger+=s[j] j+=1 #第六步 returnself.outputFinalInteger(invalidInteger) #第五步 defoutputFinalInteger(self,invalidInteger): ifinvalidInteger[0]in"-+": finalInteger=invalidInteger[0] i=1#设置指针,扫描出不含前置0的整数 whileiandinvalidInteger[i]==0: i+=1 finalInteger+=invalidInteger[i:] returnmin(max(int(finalInteger),-2**31),2**31-1) else: returnmin(max(int(invalidInteger),-2**31),2**31-1)#@作者:yi-wen-statistics
其他
原题leetcode链接:https://leetcode-/problems/string-to-integer-atoi/合作方:JavaScript中文网 – 全球极客挚爱的技术成长平台说明:leetcode 题解 | 每日一题? 所有题目并非全部为本人解答,部分为在复习学习中整理提取其他解题作者的优秀笔记,便于大家学习共同进步,如有侵权,请联系删除。-完-关注公众号「IT平头哥联盟」,一起进步,一起成长!006. Z 字形变换 | Leetcode题解
005. 最长回文子串
004.寻找两个正序数组的中位数
003. 无重复字符的最长子串