剑指 Offer第二版：机器人的运动范围、正则表达式匹配、表示数值的字符串

13. 机器人的运动范围

题目：地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3

class Solution {boolean[][] visited;  // 存储每个格子是否被访问过int res = 0;  // 记录可到达的格子数int m;  // 行数int n;  // 列数public int movingCount(int m, int n, int k) {if (m == 0) {  // 如果行数为0，返回0return 0;}this.m = m;this.n = n;visited = new boolean[m][n];  // 初始化visited数组dfs(0, 0, k);  // 从(0, 0)开始dfs搜索return res;  // 返回可到达的格子数}private void dfs(int i, int j, int k) {if (i < 0 || j < 0 || i >= m || j >= n || check(i, j, k) || visited[i][j]) {  // 如果i或j越界、格子的数字和大于k、或者格子已经被访问过，返回return;}res++;  // 可到达的格子数加1visited[i][j] = true;  // 标记格子(i, j)已经被访问过dfs(i + 1, j, k);  // 向下搜索dfs(i - 1, j, k);  // 向上搜索dfs(i, j + 1, k);  // 向右搜索dfs(i, j - 1, k);  // 向左搜索//不能回头//visited[i][j] = false;}private boolean check(int i, int j, int k) {  // 判断格子(i, j)的数字和是否大于kint res = 0;while (i != 0) {res += i % 10;i /= 10;}while (j != 0) {res += j % 10;j /= 10;}if (res > k) {return true;} else {return false;}}
}

19. 正则表达式匹配

题目：请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。
示例 1：
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

class Solution {public boolean isMatch(String s, String p) {// 获取字符串s和p的长度。int m = s.length();int n = p.length();// 创建一个二维布尔数组来存储子问题的结果。boolean[][] dp = new boolean[m + 1][n + 1];// 设置第一个元素的初始值为true。dp[0][0] = true;// 当p为空时，设置第一行的初始值。for (int i = 2; i <= p.length(); i++) {if (p.charAt(i - 1) == '*') {dp[0][i] = dp[0][i - 2];}}// 遍历整个dp数组，并根据递推关系填充它。for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 如果p中的当前字符不是'*'，我们需要检查s和p中的当前字符是否匹配。if (p.charAt(j - 1) != '*') {if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {dp[i][j] = dp[i - 1][j - 1];}} // 如果p中的当前字符是'*'，有两种情况需要考虑。else {// 如果p中的前一个字符不匹配s中的当前字符且不是'.'，则可以跳过p中的最后两个字符。if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {dp[i][j] = dp[i][j - 2];} // 如果p中的前一个字符匹配s中的当前字符或是'.'，则有三种可能的情况需要考虑。else {dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j];}}}}// 返回最后一个子问题的结果。return dp[m][n];}
}

20. 表示数值的字符串

题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
若干空格
一个 小数 或者 整数
（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
若干空格
小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（‘+’ 或 ‘-’）
下述格式之一：
至少一位数字，后面跟着一个点 ‘.’
至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（‘+’ 或 ‘-’）
至少一位数字
部分数值列举如下：
[“+100”, “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]
部分非数值列举如下：
[“12e”, “1a3.14”, “1.2.3”, “±5”, “12e+5.4”]
示例 1：
输入：s = “0”
输出：true

思路分析： 使用三个布尔变量isNum、isDot和isE来记录字符串中是否有数字、小数点和指数符号。具体来说，当遍历到一个字符时，如果它是数字，则将isNum设置为true；如果它是小数点，并且之前没有出现过小数点和指数符号，则将isDot设置为true；如果它是指数符号，并且之前出现过数字但没有出现过指数符号，则将isE设置为true，并将isNum设置为false；如果它是加号或减号，则它必须出现在字符串的开头或紧接着指数符号之后；如果它不是数字、小数点、指数符号或加减号，则返回false。最后，返回isNum的值，表示字符串中是否有数字。
时间复杂度：$O(n)$，其中$n$是字符串的长度，因为算法需要遍历字符串中的每个字符。
空间复杂度：$O(1)$，因为算法只使用了固定数量的额外空间来存储三个布尔变量。

class Solution {public boolean isNumber(String s) {// 去除字符串两端的空格。s = s.trim();// 如果字符串为空或长度为0，则返回false。if (s == null || s.length() == 0) {return false;}// 初始化三个布尔变量，用于记录字符串中是否有数字、小数点和指数符号。boolean isNum = false;boolean isDot = false;boolean isE = false;// 遍历字符串中的每个字符。for (int i = 0; i < s.length(); i++) {// 如果当前字符是数字，则将isNum设置为true。if (Character.isDigit(s.charAt(i))) {isNum = true;} // 如果当前字符是小数点，并且之前没有出现过小数点和指数符号，则将isDot设置为true。else if (s.charAt(i) == '.' && !isDot && !isE) {isDot = true;} // 如果当前字符是指数符号，并且之前出现过数字但没有出现过指数符号，则将isE设置为true，并将isNum设置为false（因为指数符号的出现意味着当前数字已经结束了）。else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && isNum && !isE) {isE = true;isNum = false;} // 如果当前字符是加号或减号，则它必须出现在字符串的开头或紧接着指数符号之后。else if (s.charAt(i) == '+' || s.charAt(i) == '-') {if (i != 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') {return false;}} // 如果当前字符不是数字、小数点、指数符号或加减号，则返回false。else {return false;}}// 返回isNum的值，表示字符串中是否有数字。return isNum;}
}