网站模板内容怎么添加图片不显示,网站建设 万户建站,网站建设选择题题库,策划书怎么写文章目录 矩阵中的路径题目思路代码实现 机器人的运动范围题目思路代码实现 矩阵中的路径
题目
请设计一个函数#xff0c;用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始#xff0c;每一步可以在矩阵… 文章目录 矩阵中的路径题目思路代码实现 机器人的运动范围题目思路代码实现 矩阵中的路径
题目
请设计一个函数用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始每一步可以在矩阵中向左向右向上向下移动一个格子。如果一条路径经过了矩阵中的某一个格子则该路径不能再进入该格子。 例如 [a b c e] [s f c s] [a d e e] 矩阵中包含一条字符串bcced的路径但是矩阵中不包含abcb路径因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后路径不能再次进入该格子。
思路
采用回溯法思想对于矩阵中各个坐标一个个尝试并递归查找对应位置上下左右位置直到查找完毕 牛客链接以及题解
代码实现 public boolean hasPath (char[][] matrix, String word) {char[] words word.toCharArray();//遍历查找矩阵各个位置是否满足for(int i 0 ; i matrix.length ; i){for(int j 0; j matrix[0].length;j){if(dfs(matrix,words,i,j,0)){return true;}}}return false;}/*** matrix 表示二维查找矩阵* 目标字符串* i 表示 行号* j 表示 列号* index 表示字符当前下标*/private boolean dfs(char[][] matrix,char[] words,int i,int j,int index){//边界判断if(i 0 || i matrix.length || j 0 || j matrix[0].length || words[index] ! matrix[i][j]){return false;}//匹配结束直接返回trueif(index words.length -1){return true;}//记录下当前字符用于后续还原char temp matrix[i][j];//使用过的字符设置为特殊符号标记为已使用后续无法再次匹配成功matrix[i][j] ;//递归查找上下左右字符是否匹配成功boolean res dfs(matrix,words,i-1,j,index1) || dfs(matrix,words,i1,j,index1) ||dfs(matrix,words,i,j-1,index1) || dfs(matrix,words,i,j1,index1);//还原字符用于再次匹配matrix[i][j] temp;return res;}机器人的运动范围
题目
地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动每一次只能向左右上下四个方向移动一格但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如当 threshold 为 18 时机器人能够进入方格 [35,37] 因为 3537 18。但是它不能进入方格 [35,38] 因为 3538 19 。请问该机器人能够达到多少个格子 牛客链接
思路
同样是采用回溯法进行解题我们只需要正确的处理边界判断逻辑然后套用通用模板即可
代码实现 public int movingCount(int threshold, int rows, int cols) {//用于记录当前下标是否被访问过boolean[][] isVisited new boolean[rows][cols];//从 0,0下标开始访问return dfs(threshold,isVisited,rows,cols,0,0);}private int dfs(int threshold,boolean[][] isVisited,int rows,int cols, int i,int j){//处理访问边界if(i0 || irows || j0 || jcols){return 0;}//访问过的 或者不满足threshold阈值的过滤掉if(isVisited[i][j] || sum(i,j) threshold){return 0;} //标记已访问过isVisited[i][j] true;//上下左右运动return 1 dfs(threshold,isVisited,rows,cols,i-1,j) dfs(threshold,isVisited,rows,cols,i1,j) dfs(threshold,isVisited,rows,cols,i,j-1) dfs(threshold,isVisited,rows,cols,i,j1);}
