找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1243|回复: 2
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【String to Integer (atoi)】-【刷题第一弹2014]

[复制链接]

21

主题

4

精华

481

积分

高级会员

Rank: 3Rank: 3

积分
481
发表于 10-22-2014 04:59 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-5-2014 10:42 PM 编辑

快速通道:
https://oj.leetcode.com/problems/string-to-integer-atoi/

题目:

Implement atoi 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.


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.


建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)

=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================

思路:

按照spoiler的规则做即可。重点是溢出的判断。我的判断方法是在新一个数字到来之前先将已经转换的数(result) 与INT_MAX的十分之一判断

代码:

  1.     int atoi(const char *str) {
  2.         bool isNegative = false;
  3.         const char* p = str;
  4.         int result = 0;
  5.         while (*p && (*p == ' '))
  6.             p++;
  7.         
  8.         if (!*p)
  9.             return result;
  10.         
  11.         if (*p == '-') {
  12.             isNegative = true;
  13.             p++;
  14.         } else if (*p == '+')
  15.             p++;
  16.         
  17.         for (;*p && isdigit(*p); p++)
  18.         {
  19.             if ((result > INT_MAX / 10)
  20.                 || ((result == INT_MAX / 10) && (((*p - '0') > 7)))){
  21.                return isNegative ? INT_MIN : INT_MAX;
  22.             } else {
  23.                 result = result * 10 + (*p - '0');
  24.             }
  25.         }
  26.         
  27.         return isNegative ? -result : result;
  28.         
  29.     }
复制代码

时间复杂度: O(n)

空间复杂度:O(1)



本帖被以下淘专辑推荐:

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-4-2014 12:08 AM | 显示全部楼层
思路和楼主很像。数值操作需要注意溢出的判断。

- res * 10 - digit < min
res * 10 + digit > max

代码如下:
  1. public class Solution {
  2.     public int atoi(String str) {
  3.         if(str == null||str.length() == 0 || str.trim().length() == 0) return 0;
  4.         str = str.trim();
  5.         boolean isNeg = false;
  6.         int i = 0;
  7.         int res = 0;
  8.         if(str.charAt(0) == '+' || str.charAt(0) == '-')
  9.         {
  10.             i++;
  11.             isNeg = str.charAt(0) != '+' ? true : false;
  12.         }
  13.         while(i < str.length())
  14.         {
  15.             if(str.charAt(i) < '0' || str.charAt(i) > '9') break;
  16.             int digit = (int) (str.charAt(i) - '0');
  17.             if(isNeg && res > -((Integer.MIN_VALUE+digit)/10))
  18.                 return Integer.MIN_VALUE;
  19.             else if (!isNeg && res > (Integer.MAX_VALUE - digit)/10)
  20.                 return Integer.MAX_VALUE;
  21.             res = res*10 + digit;
  22.             i++;
  23.         }
  24.         return isNeg ? - res : res;
  25.     }
  26. }
复制代码
回复 支持 1 反对 0

使用道具 举报

15

主题

1

精华

126

积分

资深会员

Rank: 2

积分
126
发表于 2-9-2015 10:54 AM | 显示全部楼层
我提交的时候 看到如果输入是+-2 应该得到0 可是我觉得常识告诉我应该是-2啊。。。还是说就应该只能第一位是符号   然后多的都是不对的
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表