织梦网网站建设,上海加盟网站建设,建一个网站做cpa联盟,网络教育室内设计专业剑指 Offer第二版 13. 机器人的运动范围19. 正则表达式匹配20. 表示数值的字符串 13. 机器人的运动范围 题目#xff1a;地上有一个m行n列的方格#xff0c;从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动#xff0c;它每次可以向左、右、上、下移… 剑指 Offer第二版 13. 机器人的运动范围19. 正则表达式匹配20. 表示数值的字符串 13. 机器人的运动范围 题目地上有一个m行n列的方格从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动它每次可以向左、右、上、下移动一格不能移动到方格外也不能进入行坐标和列坐标的数位之和大于k的格子。例如当k为18时机器人能够进入方格 [35, 37] 因为353718。但它不能进入方格 [35, 38]因为353819。请问该机器人能够到达多少个格子 示例 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”, “12e5.4”] 示例 1 输入s “0” 输出true 思路分析 使用三个布尔变量isNum、isDot和isE来记录字符串中是否有数字、小数点和指数符号。具体来说当遍历到一个字符时如果它是数字则将isNum设置为true如果它是小数点并且之前没有出现过小数点和指数符号则将isDot设置为true如果它是指数符号并且之前出现过数字但没有出现过指数符号则将isE设置为true并将isNum设置为false如果它是加号或减号则它必须出现在字符串的开头或紧接着指数符号之后如果它不是数字、小数点、指数符号或加减号则返回false。最后返回isNum的值表示字符串中是否有数字。 时间复杂度 O ( n ) O(n) O(n)其中 n n n是字符串的长度因为算法需要遍历字符串中的每个字符。 空间复杂度 O ( 1 ) O(1) 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;}
}
