菜鸡每日一题系列打卡8天
每天一道算法题目
小伙伴们一起留言打卡
坚持就是胜利,我们一起努力!
题目描述(引自LeetCode)
请你来实现一个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)。
题目分析
本题的难点在于如何确保各种可能的情况不重不漏的同时,尽可能保持代码的干净整洁。官方给出的解答是采用了自动机的概念。什么是自动机呢?自动机是有限状态机(FSM)的数学模型。FSM 是给定符号输入,依据(可表达为一个表格的)转移函数“跳转”过一系列状态的一种机器。自动机与一般机器的重要区别在于自动机具有固定的内在状态,即具有记忆能力和识别判断能力或决策能力。确切来说,本题符合的模型是确定有限状态自动机。参考官方解答中建立的自动机,得到如下表格。
' ' | +/- | number | other | |
START | START | SIGNED | NUMBER | END |
SIGNED | END | END | NUMBER | END |
NUMBER | END | END | NUMBER | END |
END | END | END | END | END |
在代码实现过程中,要注意溢出判断,并注意在state为END时,及时终止循环。
代码实现
class Solution {
// 确定有限状态自动机,状态枚举
enum DFA {
START,
SIGNED,
NUMBER,
END;
}
class Automaton {
// 自动机初始状态
private DFA state = DFA.START;
// 记录状态流转
private Map<DFA, DFA[]> map;
// 记录符号位
private char sign = '+';
// 记录结果
private int result = 0;
// 判断终止条件
private boolean flag = true;
public Automaton() {
map = new HashMap<>();
map.put(DFA.START, new DFA[]{DFA.START, DFA.SIGNED, DFA.NUMBER, DFA.END});
map.put(DFA.SIGNED, new DFA[]{DFA.END, DFA.END, DFA.NUMBER, DFA.END});
map.put(DFA.NUMBER, new DFA[]{DFA.END, DFA.END, DFA.NUMBER, DFA.END});
map.put(DFA.END, new DFA[]{DFA.END, DFA.END, DFA.END, DFA.END});
}
public int getResult() {
return result;
}
public boolean getFlag() {
return flag;
}
// 处理状态变化
public int getIndex(char c) {
if (c == ' ') return 0;
if (c == '+' || c == '-') return 1;
if (c >= '0' && c <= '9') return 2;
return 3;
}
// 计算当前结果
public void getInteger(char c) {
// 跟踪当前状态
state = map.get(state)[getIndex(c)];
switch (state) {
// 注意溢出判断
case NUMBER:
if (sign == '+' && (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && c - '0' > 7))) {
result = Integer.MAX_VALUE;
flag = false;
break;
} else if (sign == '-' && (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && c - '0' > 8))) {
result = Integer.MIN_VALUE;
flag = false;
break;
}
result = (sign == '+') ? (result * 10 + c - '0') : (result * 10 - (c - '0'));
break;
case SIGNED:
sign = c;
break;
case END:
flag = false;
break;
default:
break;
}
}
}
// 字符串转换整数
public int myAtoi(String str) {
// 特殊情况处理
if (str == null || str.length() == 0) {
return 0;
}
Automaton automaton = new Automaton();
for (int i = 0; i < str.length(); i++) {
if (automaton.getFlag()) {
automaton.getInteger(str.charAt(i));
} else {
break;
}
}
return automaton.getResult();
}
}
代码分析
对代码进行分析,时间复杂度与字符串的被处理长度有关,因此时间复杂度为O(n),而就空间而言,仅使用了固定的几个变量,因此空间复杂度为O(1)。
执行结果
学习 | 工作 | 分享