恋爱网站建设,浙江网站建设价格,铜仁做网站的公司,安徽全过程网站搭建案例❝每天 3 分钟#xff0c;走上算法的逆袭之路。❞前文合集每日一道 LeetCode 前文合集代码仓库GitHub#xff1a;https://github.com/meteor1993/LeetCodeGitee#xff1a;https://gitee.com/inwsy/LeetCode题目#xff1a;最长回文子串难度#xff1a;「中等」题目来源走上算法的逆袭之路。❞前文合集每日一道 LeetCode 前文合集代码仓库GitHubhttps://github.com/meteor1993/LeetCodeGiteehttps://gitee.com/inwsy/LeetCode题目最长回文子串难度「中等」题目来源https://leetcode-cn.com/problems/string-to-integer-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 (−231) 。解题方案有限状态机这道题单纯的做出来并不是很难纯暴力的解法肯定搞得定除了逻辑复杂一点判断多一点各种 flag 多立几个做肯定是做得出来的。这道题的难度定成中等肯定不是要我们用暴力解法把它解出来的不然没必要搞成中等难度简单难度就够了除了逻辑复杂点这种方案找不到任何难点这不符合力扣的尿性一定有我不知道的解法。果然在答案中我看到了一个新名词叫做「状态机」。状态机的基本定义状态机是有限状态自动机的简称是现实事物运行规则抽象而成的一个数学模型。状态机里面有 4 个概念第一个是 State 状态。一个状态机至少要包含两个状态。第二个是 Event 事件。事件就是执行某个操作的触发条件或者口令。第三个是 Action 动作。事件发生以后要执行动作。第四个是 Transition 变换。也就是从一个状态变化为另一个状态。套到这道题里就是我们的程序在每个时刻有一个状态 s 每次从序列中输入一个字符 c 并根据字符 c 转移到下一个状态 s 。这样我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s 的表格即可解决题目中的问题。答案中给出的示例图是这样的/-numberotherstartstartsignedin_numberendsignedendendin_numberendin_numberendendin_numberendendendendendend接下来就是把这一个构件的状态机写成代码public class Automaton { // 正负 public int sign 1; // 数值 public long ans 0; private String state start; private Map table new HashMap() {{ put(start, new String[]{start, signed, in_number, end}); put(signed, new String[]{end, end, in_number, end}); put(in_number, new String[]{end, end, in_number, end}); put(end, new String[]{end, end, end, end}); }};public void get(char c) { state table.get(state)[get_col(c)];if (in_number.equals(state)) { ans ans * 10 c - 0; ans sign 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE); } else if (signed.equals(state)){ sign c ? 1 : -1; } }private int get_col(char c) {if (c ) {return 0; }if (c || c -) {return 1; }if (Character.isDigit(c)) {return 2; }return 3; }}然后我们在主方法里面调用这个状态机public int myAtoi(String str) { Automaton automaton new Automaton(); char[] c str.toCharArray(); for (int i 0; i automaton.get(c[i]); } return (int) (automaton.sign * automaton.ans);}参考https://zhuanlan.zhihu.com/p/47434856感谢阅读
