原题地址：字符串转换整数 (atoi)
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [$-2^{31}$, $2^{31} - 1$]。如果数值超过这个范围，请返回 INT_MAX ($2^{31}$ − 1) 或 INT_MIN ($-2^{31}$) 。
示例 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 ($-2^{31}$) 。
常规解法
本题中的条件已经给得很明确了，所以只需要按照给定的条件依次判断即可：
/**
* @param {string} str
* @return {number}
*/
let myAtoi2 = function(str) {
str = str.trimLeft(); // 去除两边的空格
if (str.length === 0) {
return 0;
}
const chars = ['0','1','2','3','4','5','6','7','8','9'];
let multiple = 1; // 保存正号和负号
// 取出正号和负号
if (str[0] === '+') {
str = str.substr(1)
} else if (str[0] === '-') {
multiple = -1;
str = str.substr(1);
}
if (str.length === 0 || !chars.includes(str[0])) {
return 0;
}
let result = 0;
for (let i = 0; i < str.length; i ++) {
let index = chars.indexOf(str[i]);
if (index < 0) { // 不是数字
break;
}
result = result * 10 + index;
}
// 以max和min函数来防止溢出
return Math.max(-0x80000000, Math.min(0x7fffffff, result * multiple));
};
测试：
let start = new Date();
const test = myAtoi2;
console.log(test('42')); // 42
console.log(test(' -42')); // -42
console.log(test('4193 with words')); // 4193
console.log(test('words and 987')); // 0
console.log(test('-91283472332')); // -2147483648
console.log(new Date().getTime() - start.getTime()); // 6
时间复杂度： 单次遍历，时间复杂度为O(n)
空间复杂度： 只需要固定数量的额外参数，空间复杂度为O(1)
正则表达式
除了常规解法外，我们还可以利用正则表达式，按照题目的要求去除干扰字符。再直接强转为数字即可：
/**
* @param {string} str
* @return {number}
*/
let myAtoi3 = function(str) {
str = str.trimLeft();
// [+\-]? 有一个或零为+或-号
// \d+ 匹配数字
let reg = new RegExp('^[+\\-]?\\d+');
let array = reg.exec(str); // 匹配一次并以数组形式返回
let result = array ? Number(array[0]) : 0; // 没有匹配到就返回0，否则转换为数字
return Math.max(-0x80000000, Math.min(0x7fffffff, result));
};
测试：
let start = new Date();
const test = myAtoi3;
console.log(test('42')); // 42
console.log(test(' -42')); // -42
console.log(test('4193 with words')); // 4193
console.log(test('words and 987')); // 0
console.log(test('-91283472332')); // -2147483648
console.log(new Date().getTime() - start.getTime()); // 6
时间复杂度： 单次遍历，时间复杂度为O(n)
空间复杂度： 只需要固定数量的额外参数，空间复杂度为O(1)
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 27,2019