菜鸡每日一题系列打卡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)。
执行结果
学习 | 工作 | 分享
