保定网站seo服务,做自适应网站注意事项,宣城网站建设jidela,如何优化wordpress网站目录
第一题
题目来源
题目内容
解决方法
方法一#xff1a;动态规划
第二题
题目来源
题目内容
解决方法
方法一#xff1a;有限状态自动机
方法二#xff1a;正则表达式
第三题
题目来源
题目内容
解决方法
方法一#xff1a;从最后一位向前遍历
方法二…目录
第一题
题目来源
题目内容
解决方法
方法一动态规划
第二题
题目来源
题目内容
解决方法
方法一有限状态自动机
方法二正则表达式
第三题
题目来源
题目内容
解决方法
方法一从最后一位向前遍历
方法二数学运算 第一题
题目来源
64. 最小路径和 - 力扣LeetCode
题目内容 解决方法
方法一动态规划
可以使用动态规划来解决这个问题。
首先创建一个与网格大小相同的二维数组dp用于存储从起点到每个位置的最小路径和。然后初始化dp[0][0] grid[0][0]表示起点的最小路径和为起点的值。接下来进行动态规划的遍历遍历顺序可从起点开始按行或按列遍历。对于每个位置dp[i][j]其最小路径和为grid[i][j]加上它左边或上边位置的最小路径和的较小值。
复杂度分析
时间复杂度
遍历网格中的每个元素所以需要进行两层嵌套循环总共遍历次数为m * n其中m为网格的行数n为网格的列数。在每次循环中执行常数时间的操作将上方和左方的最小路径和与当前位置的值相加然后取最小值。因此整体的时间复杂度为O(m * n)。
空间复杂度
创建了一个与网格大小相同的二维数组dp用于存储从起点到每个位置的最小路径和。因此需要额外的空间来存储这些最小路径和。dp数组的大小为m * n与原始网格的大小相同。所以空间复杂度为O(m * n)。
综上所述该算法的时间复杂度为O(m * n)空间复杂度为O(m * n)。
LeetCode运行结果 第二题
题目来源
65. 有效数字 - 力扣LeetCode
题目内容 解决方法
方法一有限状态自动机
可以使用有限状态自动机DFA来解决该问题。我们需要设计合适的状态集合以及状态转移规则。其中状态包括以下几种
起始空格状态在这个状态下前面的空格已经被忽略。 符号位状态在这个状态下可能出现 或 -。 整数状态在这个状态下输入了数字 0-9。 小数点状态在这个状态下已经输入了小数点。 小数状态在这个状态下已经输入了数字并带有小数点。 幂符号状态在这个状态下出现了字符 e 或 E。 幂符号后的符号位状态在这个状态下出现了符号位 或 -。 幂符号后的整数状态在这个状态下输入了数字 0-9。 终止状态如果当前输入的字符不合法或者最后一步能够到达终止状态则说明输入是一个合法的数字。
class Solution {
public boolean isNumber(String s) {// 定义有限状态自动机MapState, MapCharType, State transfer new HashMap(); transfer.put(State.STATE_INITIAL, new HashMap() {{put(CharType.CHAR_SPACE, State.STATE_INITIAL); // 起始空格状态put(CharType.CHAR_NUMBER, State.STATE_INTEGER); // 整数状态put(CharType.CHAR_SIGN, State.STATE_SIGN); // 符号位状态put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT); // 小数点状态前面没有数字}});transfer.put(State.STATE_SIGN, new HashMap() {{put(CharType.CHAR_NUMBER, State.STATE_INTEGER); // 整数状态put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT); // 小数点状态前面没有数字}});transfer.put(State.STATE_INTEGER, new HashMap() {{put(CharType.CHAR_NUMBER, State.STATE_INTEGER); // 整数状态put(CharType.CHAR_EXP, State.STATE_EXP); // 幂符号状态put(CharType.CHAR_POINT, State.STATE_POINT); // 小数状态put(CharType.CHAR_SPACE, State.STATE_END); // 终止状态}});transfer.put(State.STATE_POINT, new HashMap() {{put(CharType.CHAR_NUMBER, State.STATE_FRACTION); // 小数状态put(CharType.CHAR_EXP, State.STATE_EXP); // 幂符号状态put(CharType.CHAR_SPACE, State.STATE_END); // 终止状态}});transfer.put(State.STATE_POINT_WITHOUT_INT, new HashMap() {{put(CharType.CHAR_NUMBER, State.STATE_FRACTION); // 小数状态}});transfer.put(State.STATE_FRACTION, new HashMap() {{put(CharType.CHAR_NUMBER, State.STATE_FRACTION); // 小数状态put(CharType.CHAR_EXP, State.STATE_EXP); // 幂符号状态put(CharType.CHAR_SPACE, State.STATE_END); // 终止状态}});transfer.put(State.STATE_EXP, new HashMap() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER); // 幂符号后的整数状态put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN); // 幂符号后的符号位状态}});transfer.put(State.STATE_EXP_SIGN, new HashMap() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER); // 幂符号后的整数状态}});transfer.put(State.STATE_EXP_NUMBER, new HashMap() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER); // 幂符号后的整数状态put(CharType.CHAR_SPACE, State.STATE_END); // 终止状态}});transfer.put(State.STATE_END, new HashMap() {{put(CharType.CHAR_SPACE, State.STATE_END); // 终止状态}});// 根据定义的状态转移规则判断该字符串是否为有效数字int length s.length();State state State.STATE_INITIAL;for (int i 0; i length; i) {CharType type toCharType(s.charAt(i));if (!transfer.get(state).containsKey(type)) { // 当前输入不合法return false;}state transfer.get(state).get(type); // 进入下一个状态}// 最后一步能够到达终止状态说明该字符串是一个有效数字return state State.STATE_INTEGER || state State.STATE_POINT ||state State.STATE_FRACTION || state State.STATE_EXP_NUMBER ||state State.STATE_END;
}// 定义字符类型枚举类
enum CharType {CHAR_NUMBER,CHAR_EXP,CHAR_POINT,CHAR_SIGN,CHAR_SPACE,CHAR_ILLEGAL
}// 判断字符类型
private CharType toCharType(char ch) {if (ch 0 ch 9) {return CharType.CHAR_NUMBER;} else if (ch e || ch E) {return CharType.CHAR_EXP;} else if (ch .) {return CharType.CHAR_POINT;} else if (ch || ch -) {return CharType.CHAR_SIGN;} else if (ch ) {return CharType.CHAR_SPACE;} else {return CharType.CHAR_ILLEGAL;}
}// 定义状态枚举类
enum State {STATE_INITIAL,STATE_INTEGER,STATE_POINT,STATE_POINT_WITHOUT_INT,STATE_FRACTION,STATE_EXP,STATE_EXP_SIGN,STATE_EXP_NUMBER,STATE_SIGN,STATE_END
}
}
复杂度分析
时间复杂度为O(n)其中n表示字符串的长度。算法需要对字符串中的每个字符进行遍历因此时间复杂度与字符串的长度成正比。空间复杂度为O(1)因为算法只使用了常数个变量和一个固定大小的哈希表状态转移规则不随输入规模的增加而增加额外的空间消耗。因此算法的空间复杂度是常数级别的。
LeetCode运行结果 方法二正则表达式
除了有限状态自动机还可以使用正则表达式来判断一个字符串是否为有效数字。Java中提供了一个函数matches(String regex)来判断一个字符串是否能够匹配指定的正则表达式。
class Solution {
public boolean isNumber(String s) {// 使用正则表达式匹配字符串return s.trim().matches([-]?(?:\\d\\.?\\d*|\\.\\d)(?:[Ee][-]?\\d)?);
}
}
复杂度分析
该算法的时间复杂度为O(1)因为使用了Java内置函数时间复杂度是固定的。空间复杂度为O(1)因为没有使用额外的空间。
需要注意的是使用正则表达式虽然代码简单易懂但是性能可能不如有限状态自动机。正则表达式求解的时间复杂度是O(n)其中n是字符串长度适用于一些简单的模式匹配。对于复杂模式引擎会消耗非常多的时间和空间建议在使用时注意性能问题。
LeetCode运行结果 第三题
题目来源
66. 加一 - 力扣LeetCode
题目内容 解决方法
方法一从最后一位向前遍历
该方法从数组的最后一位开始向前遍历将当前位加一如果加一后不需要进位则直接返回结果。如果加一后需要进位则将当前位置为0并继续处理前一位。如果所有位都需要进位则返回新的结果数组长度为原数组长度加一首位为1其余位为0。
class Solution {
public int[] plusOne(int[] digits) {int n digits.length;// 从最后一位开始向前遍历for (int i n - 1; i 0; i--) {// 当前位加一digits[i];// 如果当前位加一后仍然小于10没有进位直接返回结果if (digits[i] 10) {return digits;}// 有进位当前位变为0继续处理前一位digits[i] 0;}// 若所有位都有进位则数组长度需要增加1首位为1后面全是0int[] result new int[n 1];result[0] 1;return result;
}}
复杂度分析
时间复杂度O(n)其中n为数组的长度。在最坏情况下需要遍历整个数组一次。空间复杂度O(n)需要创建一个新的结果数组长度可能为n1。
LeetCode运行结果 方法二数学运算
还可以使用数学运算来实现加一操作。
首先将数组最后一位加一记录进位carry。从数组倒数第二位开始将当前位加上进位carry并更新进位carry。如果进位carry为0则无需继续处理直接返回结果数组。如果进位carry不为0则继续向前处理前一位。如果处理完所有位后进位carry仍然不为0说明需要扩展结果数组的长度将原数组复制到新的结果数组中并在首位插入进位carry。
class Solution {
public int[] plusOne(int[] digits) {int n digits.length;int carry 1; // 进位初始化为1// 从数组最后一位开始计算for (int i n - 1; i 0; i--) {digits[i] carry; // 当前位加上进位carry digits[i] / 10; // 计算新的进位digits[i] % 10; // 当前位取模得到个位数// 如果进位为0说明不需要再进位直接返回结果数组if (carry 0) {return digits;}}// 若所有位都有进位则数组长度需要增加1首位为进位carry后面全是0int[] result new int[n 1];result[0] carry;System.arraycopy(digits, 0, result, 1, n);return result;
}}
复杂度分析
时间复杂度遍历数组需要线性时间O(n)其中每个元素只进行一次常数级别的数学运算所以总体时间复杂度也是O(n)。空间复杂度除了原数组外需要在进位的情况下创建一个新数组来存储结果所以空间复杂度为O(n)。
LeetCode运行结果
