“摘要:本文主要讲述LeetCode字符串分类字符串转换整数 (atoi)解法。主要内容如下:
题目
示例
解题
”
01
—
题目
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
02
—
示例
示例 1:输入: "42"输出: 42示例 2:输入: " -42"输出: -42解释: 第一个非空白字符为 '-', 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。示例 3:输入: "4193 with words"输出: 4193解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。示例 4:输入: "words and 987"输出: 0解释: 第一个非空字符是 'w', 但它不是数字或正、负号。因此无法执行有效的转换。示例 5:输入: "-91283472332"输出: -2147483648解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。示例 6:输入: " -4193 with words"输出: -4193
03
—
解题思路
算法推演:
算法中还要注意一点，本题涉及整数的运算，我们需要注意溢出。对于溢出的处理方式通常可以转换为 INT_MAX 的逆操作。比如判断某数乘 10 是否会溢出，那么就把该数和 INT_MAX 除 10 进行比较。
实现代码
class Solution {public: int myAtoi(std::string s) {// 变量定义 long long ans = 0; int sign = 1; // 1.去掉前导空格 int spaceEndPos = (int)s.find_first_not_of(" "); int strLen = 0; char* sptr = nullptr; if (spaceEndPos == std::string::npos) {sptr = const_cast<char*>(s.c_str()); strLen = (int)s.length(); } else {sptr = const_cast<char*>(s.c_str()) + spaceEndPos; strLen = (int)s.length() - spaceEndPos; } if (strLen <= 0) {return 0; }// 2.判断第一个字符是否是符号位 if(sptr[0] == '-') {sign = -1; } else if (sptr[0] == '+') {sign = 1; } else if (!isdigit(sptr[0])) {return 0; } else {ans = ans * 10 + (sptr[0] - '0'); } ++sptr; --strLen;// 3.获取所有数字 for(int i = 0; i < strLen; ++i) {if(isdigit(sptr[i])) {long long temp = ans * 10 + (sptr[i] - '0');if (temp > INT_MAX) {temp = (sign == 1 ? INT_MAX : -((long long)INT_MIN));ans = temp;break;} else {ans = temp;} } else {break; } } return int(sign * ans); }};
复杂度分析
时间复杂度: O(n) ，要遍历整个字符串
空间复杂度: O(1)
