专栏首页大白技术控的技术自留地C++版 - Leetcode 8: String to Integer (myAtoi,C库函数atoi模拟) (剑指offer 面试题49) 解题报告

C++版 - Leetcode 8: String to Integer (myAtoi,C库函数atoi模拟) (剑指offer 面试题49) 解题报告

leetcode 8:  (剑指offer 面试题49)

8. String to Integer (atoi)

提交网址: https://leetcode.com/problems/string-to-integer-atoi/

Total Accepted: 100027 Total Submissions: 741432 Difficulty: Easy     ACrate: 13.5%

Implement atoi (myAtoi) to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10): The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button  to reset your code definition.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

中文题来自于《剑指offer》2014版

面试官:能不能介绍一下C语言的库函数中atoi的作用?

应聘者:atoi用来把一个字符串转换成一个整数。比如输入字符串 "123",它的输出是数字123。 面试官:对的。现在就请你写一个函数StrTolnt(或 myAtoi),实现把字符串转换成整数这个功能。当然,不能使用atoi或者其他类似的库函数...

提交网址:  http://www.nowcoder.com/practice/1277c681251b4372bdef344468e4f26e?tpId=13&tqId=11202

参与人数:2008   时间限制:1秒  空间限制:32768K 本题知识点: 字符串

题目描述:将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数atoi()。 输入:输入可能包含多个测试样例。对于每个测试案例,输入为一个合法或者非法的字符串,代表一个整数n(1<= n<=18446744073709551617)。 输出:对应每个测试案例,若输入为一个格式合法的字符串(即恰好表示一个整数),则输出这个整数;若输入为一个合法的字符串,但中间出现了数字、+、-以外的特殊字符,则输出第一个特殊字符之前的整数;若输入为一个格式非法的字符串,则输出0;若输入的数格式合法,但超出INT_MIN或INT_MAX,如果为正数输出INT_MAX,如果为负数则输出INT_MIN . 样例输入:"+8""1314" "-123456" "1ab3" "    010"; "13  456" "-66666666666""9223372036854775807" "18446744073709551617" "- +899999" "   - 321" "   +0 123" 样例输出:81314 -123456 1 10 13 -2147483648 21474836472147483647000

注: 费马质数(Fermat number) F(n) = 2^(2^n) + 1,F(6)=18446744073709551617=2^64+1 (65位的数),9223372036854775807=2^63-1. 测试用例中的部分数来源于此。可以顺便记录转换后的长度newlen,如果值越出[INT_MIN, INT_MAX](或 长度newlen超过11),提前输出INT_MAX,如果为负数则输出INT_MIN.

leetcode AC代码:

#include<iostream>
#include<string>
using namespace std;

class Solution {
public:
    int myAtoi(string str)
	{
        if(str=="") return 0;  // str.length()==0 等价于 str=="",故条件不必写为if(str=="" || str.length()==0) 
        long long final, res=0;
        int len=str.length();
        int sign=1;
        int sign_count=0;
		for(int i=0; i<len; i++)
        {
        	char ch=str[i];
			if(ch=='-' || ch=='+') sign_count++;
			if(sign_count<=1)			
			{
			if(ch<='9' && ch>='0')
			{
				res = res*10+ch-'0';
	if(res> INT_MAX && sign==1) return INT_MAX;   // 当输入数超过INT_MAX或INT_MIN时,需及时退出,如果等计算完再返回,final会变为1(存储越界)
	if(res< INT_MIN && sign==-1) return INT_MIN;
				if(i+1<len && str[i+1]==' ') break;
			}
			else if(ch=='-' || ch=='+') 
			{
				if(ch=='-') sign=-1;
				if(i+1<len && str[i+1]==' ') break;
			}
				else if(ch==' ') ;  // 开头的空格忽略掉
					else break;  // 输入不合法,退出循环				
			}  	
			else return 0;
		}		
        if(res>= INT_MIN && res <= INT_MAX) final=res*sign;
        else if(sign==1) final = INT_MAX;
        	else if(sign==-1) final = INT_MIN;  // 如果越出整数边界,返回相应的值 
		return final; // -2147483648[(signed int)0x80000000] ~ 2147483647(0x7FFFFFFF)
    }   
};

// 以下为测试
int main()
{
	string str0; //	str0.size() == 0; // 后面的半句:可写可不写,字符串默认初始化为空串 
	string str1="1ab3";  // 应返回1
	string str2="18446744073709551617";	
	string str3="- +899999 ";
	string str4="    010"; // 应返回10
	string str5="   +0 123";
	string str6="13  456"; // 123
	string str7="   - 321";

	Solution sol;
	cout<<sol.myAtoi(str0)<<endl;	
	cout<<sol.myAtoi(str1)<<endl;
	cout<<sol.myAtoi(str2)<<endl;		
	cout<<sol.myAtoi(str3)<<endl;	
	cout<<sol.myAtoi(str4)<<endl;
	cout<<sol.myAtoi(str5)<<endl;
	cout<<sol.myAtoi(str6)<<endl;	
	cout<<sol.myAtoi(str7)<<endl;	
	return 0;
} 

Submission Details:

Accepted 1047 / 1047 test cases passed.

ps: 在leetcode中提交代码的过程中遇到了下面这个error: control reaches end of non-void function [-Werror=return-type],而本地的visual studio和Dev C++上没报错,这是由于所提交的代码中带返回值的函数不一定能return而导致的错误。比如将return放进了if else判断语句里面,如果那个判断语句一直不执行那么就没有返回值了,就会报此错。于是可将需要返回的值都放进同一个变量final中,最后return final即可.

相关链接: http://stackoverflow.com/questions/30402164/control-reaches-end-of-non-void-function-werror-return-type

牛客网中文版 AC代码:

class Solution {
public:
    int StrToInt(string str)
    {
        if(str=="") return 0;
        long long res=0;
        int len=str.length();
        int isPositive=1;
         
        for(int i=0; i<len; i++)
        {
            char ch=str[i];
            if(ch<='9' && ch>='0')  res = res*10+ch-'0';
            else if(ch=='-') isPositive=-1;
                else if(ch=='+') ;  // 不处理,继续往后扫
                    else return 0;
        }
        return res*isPositive;
    }
};

牛客网上测试用例只有10个左右,因而要求比较低...

严格参考《剑指offer》2014版 原书的写法:

1、设置输入合法标志,默认为false,当第一个字符为空或者\0的时候直接诶返回0,输入合法标志为false。反之进入下一步。 2、设置符号位,判断是+还是-还是不带符号位,只有为-才置为true,否则均为false。 3、区分除了符号位之外第一位时候合法输入。非法时返回0,输入合法位为false。合法时判断有无越界,若越界返回0,输入合法位为false,无越界计算num返回,输入合法位为true。

总结:只有在顺利走到字符串尾部的时候输入合法标志位才为true,其余情况均为false。这样就能区分开返回0时究竟是非法输入还是确实输入的就是0。只有一个+号或-号也被考虑进来了,直接返回0且输入合法标志位为false。

class Solution {
public:
    enum Status{kValid = 0,kInvalid};
    int g_nStatus = kValid;
    int StrToInt(string str) {
        g_nStatus = kInvalid;
        long long num = 0;
        int index=0;
        if((!str.empty())&&str[index]!='\0')
        {
            bool minus = false;
            if(str[index]=='+')
                index++;
            else if(str[index]=='-')
            {
                index++;
                minus = true;
            }
            if(str[index]!='\0')
            {
                int length=str.size();
                num = StrToIntCore(str.substr(index,length-index),minus);  
            }
        }
        return (int)num;
    }
         
    long long StrToIntCore(const string& digit,bool minus)
    {
        long long num=0;
        int i=0;
        while(digit[i]!='\0')
        {   //合法情况
            //if(digit[i]=='+'||digit[i]=='-')
                //i++;
            if(digit[i]>='0'&&digit[i]<='9')
            {
                int flag = minus?-1:1;
                num = num*10+ flag*(digit[i]-'0');
                //越界情况
                if((!minus&&num>0x7FFFFFFF)||(minus&&num<(signed int)0x80000000))
                {
                    num = 0;
                    break;
                }
                i++; 
            }
            else//非法情况
            {
                num = 0;
                break;
            }
        }
        if(digit[i]=='\0')
            g_nStatus = kValid;
        return num;
    }
}; 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C#版(击败96.64%的提交) - Leetcode 728. 自除数 - 题解

    Leetcode 728 - Self Dividing Numbers 在线提交: https://leetcode-cn.com/problems/se...

    Enjoy233
  • C#刷遍Leetcode面试题系列连载(4): No.633 - 平方数之和

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    Enjoy233
  • C++版 - 剑指Offer 面试题45:圆圈中最后剩下的数字(约瑟夫环问题,ZOJ 1088:System Overload类似)题解

    提交网址: http://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&...

    Enjoy233
  • 剑指offer【60~68】

    动态规划。令 dp[n][6*n],其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。则 dp[-1][1...6*n] 就是每一种点数的次数。点...

    echobingo
  • 聊聊HystrixCircuitBreaker

    hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixCircuitBreaker.java

    codecraft
  • Android Architecture Component之Lifecycle解析HeaderLifecyclePart 1Part 2Part 3Footer

    终于到了最后的关头,Android Architecture Component 系列的最后一节内容。今天给大家带来的就是 Lifecycle 的解析。

    俞其荣
  • Leetcode【319、672】

    灯泡开关。初始时有 n 个灯泡关闭,第 i 轮,每 i 个灯泡切换一次开关。找出 n 轮后有多少个亮着的灯泡。

    echobingo
  • Golang Leetcode 868. Binary Gap.go

    https://blog.csdn.net/anakinsun/article/details/89578355

    anakinsun
  • Golang Leetcode 868. Binary Gap.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/arti...

    anakinsun
  • R 语言根据条件判断返回ABCD状态

    有朋友给我写信,问我R语言的问题,与其回复代码,不如写篇博客,顺便试试CSDN的新模板。

    邓飞

扫码关注云+社区

领取腾讯云代金券