专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
据每日经济网报道英伟达员工有一半的人净资产已达到2500万美元，约合人民币1.83亿。不少英伟达员工反映为了支撑英伟达的高市值，他们经常每周工作 7 天，经常加班到凌晨 2 点。这工作量比起996严重多了，不过收入也确实很诱人。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第8题：字符串转换整数 (atoi)
问题描述
来源：LeetCode第8题
难度：中等
把一个字符串s转化为整数，前面如果有空格要去掉，还要注意正负号，读入下一个字符，直到到达 下一个非数字字符或到达输入的结尾 ，字符串的其余部分将被忽略。
如果整数超过 32 位有符号整数范围 [−2^31, 2^31 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2^31 的整数应该被固定为 −2^31 ，大于 2^31 − 1 的整数应该被固定为 2^31 − 1 。
示例1：
输入：s = " -42" 输出：-42 解释：" -42"（读入前导空格，但忽视掉）
示例2：
输入：s = "4193 with words" 输出：4193 解释："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止），解析得到整数 4193 。
0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成
问题分析
这题是让把一个字符串转成一个整数，难度不是很大，但细节挺多，一不小心有可能就会做错。
首先如果字符串前面有空格要去掉，去掉最前面的空格之后如果遇到符号，还要记录符号，如果没有遇到符号就默认是正数。后面开始把字符串转成数字，如果遇到不是数字的直接停止，后面的忽略掉，就不要再转了。还有一点就是转成的数字不能超出int的范围，如果超出了直接截取。
我们需要使用一个变量sign来记录符号位， 1 表示正数， -1 表示负数，转的时候就不需要在考虑符号了，但最后返回的时候还要注意符号不能漏掉。
java：
public int myAtoi(String str) { str = str.trim();// 去掉前后的空格 if (str.length() == 0) return 0; int num = 0;// 最终结果 int index = 0;// 遍历字符串中字符的位置 int sign = 1;// 符号，1是正数，-1是负数，默认为正数 int length = str.length(); // 判断符号 if (str.charAt(index) == '-' || str.charAt(index) == '+') sign = str.charAt(index++) == '+' ? 1 : -1; for (; index < length; ++index) { // 取出字符串中字符，然后转化为数字 int digit = str.charAt(index) - '0'; // 按照题中的要求，读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。 // 字符串的其余部分将被忽略。如果读取了非数字，后面的都要忽略。 if (digit < 0 || digit > 9) break; // 越界处理 if (num > Integer.MAX_VALUE / 10 || (num == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; else num = num * 10 + digit; } return sign * num; }C++：
public: int myAtoi(string str) { if (str.empty()) return 0; int length = str.size(); int index = 0;// 遍历字符串中字符的位置 while (str[index] == ' ')// 去掉前面的空格 if (++index == length) return 0; int num = 0;// 最终结果 int sign = 1;// 符号，1是正数，-1是负数，默认为正数 // 判断符号 if (str[index] == '-' || str[index] == '+') sign = str[index++] == '+' ? 1 : -1; for (; index < length; ++index) { // 取出字符串中字符，然后转化为数字 int digit = str[index] - '0'; // 按照题中的要求，读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。 // 字符串的其余部分将被忽略。如果读取了非数字，后面的都要忽略。 if (digit < 0 || digit > 9) break; // 越界处理 if (num > INT_MAX / 10 || (num == INT_MAX / 10 && digit > INT_MAX % 10)) return sign == 1 ? INT_MAX : INT_MIN; else num = num * 10 + digit; } return sign * num; }python：
def myAtoi(self, s: str) -> int: s = s.strip() # 删除首尾空格 if not s: return 0 # 字符串为空则直接返回 num = 0 # 最终结果 index = 0 # 遍历字符串中字符的位置 sign = 1 # 符号，1是正数，-1是负数，默认为正数 int_max, int_min = 2 ** 31 - 1, -2 ** 31 if s[index] == '-' or s[index] == '+': sign = 1 if s[index] == '+' else -1 index += 1 for c in s[index:]: digit = ord(c) - ord('0') if digit < 0 or digit > 9: break # 遇到非数字的字符则跳出 # 越界处理 if num > int_max // 10 or (num == int_max // 10 and digit > int_max % 10): return int_max if sign == 1 else int_min num = 10 * num + digit return sign * num笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴