长网址转短网址网站,网站源码网,域名抢注网站,佛山网站定制一)单词搜索: 直接在矩阵中依次找到特定字符串 79. 单词搜索 - 力扣#xff08;LeetCode#xff09; 画出决策树#xff0c;只需要做一个深度优先遍历: 1)设计dfs函数:只需要关心每一层在做什么即可#xff0c;从这个节点开始#xff0c;开始去尝试匹配字符串的下一个字符… 一)单词搜索: 直接在矩阵中依次找到特定字符串 79. 单词搜索 - 力扣LeetCode 画出决策树只需要做一个深度优先遍历: 1)设计dfs函数:只需要关心每一层在做什么即可从这个节点开始开始去尝试匹配字符串的下一个字符就是从某一个位置的字符开始上下左右下标看看能不能匹配下一个字符给定一个节点的位置上下左右去匹配一个结点的位置dfs(char[][] boardijspos)把原始的矩阵给定把这个字符的位置把要匹配字符串字符串匹配到哪一个位置 2)从ij位置开始上下左右去搜索word的哪一个字符就可以了 3)boolean返回值代表此次路径的选择是成功还是失败 2)二维矩阵中要注意的细节问题: 在二维矩阵搜索的过程中不能走重复的路要想解决这个问题可以有两种方法: 2.1)使用一个和原始矩阵相同规模大小的布尔数组如果这个字符已经被路径走过了那么直接修改成true 2.2)直接修改原始矩阵的值如果某一个字符被走过了那么直接修改字符为.或者其他标记字符 假设在下面的这个例子中给定我们一个矩阵给定一个字符串AAAAA判断是否可以匹配成功 2.3)当我们第一次成功的匹配到了A字符的时候将这个A字符标记成true表示这个字符已经被使用过了此时想左匹配第二个A字符当尝试在第二个A字符中匹配第三个A字符的时候此时是不能再继续想左找第一个A字符了此时因为第一个A字符已经被使用过了 class Solution {public boolean[][] check;int row;int col;
//利用向量数组一个for循环搞定上下左右四个方向int[] dx{0,0,1,-1};int[] dy{1,-1,0,0};public boolean dfs(char[][] board,String word,int i,int j,int pos){if(posword.length()) return true;//当匹配到最后一个字符之后直接返回//接下来向上下走有去匹配word[pos];for(int k0;k4;k){
//从这里面开始左每一层所做的事情,从(i,j)下标开始上下左右去匹配pos位置的字符int xidx[k];int yjdy[k];
if(x0xrowy0ycolcheck[x][y]falseboard[x][y]word.charAt(pos))
{check[x][y]true;if(dfs(board,word,x,y,pos1)) return true;check[x][y]false;
}}return false;//匹配失败在这里面返回说明上下左右都匹配不到想要的字符}
//此时如果不加上返回值的话,那么匹配成功也是返回return;
//此时匹配失败也就是说上下左右找不到特定字符也是返回return;此时主函数就不知道最终是返回true还是false的public boolean exist(char[][] board, String word) {
//1.先进行计算二维数组的行和列,初始化布尔数组this.rowboard.length;this.colboard[0].length;this.checknew boolean[row][col];
//2.现在整个数组中找到字符串中第一个字符出现的位置,然后去尝试匹配下一个字符for(int i0;irow;i){for(int j0;jcol;j){if(board[i][j]word.charAt(0)){
//先进行遍历整个矩阵直到我们找到第一个位置的时候才会向下进行搜索check[i][j]true;if(dfs(board,word,i,j,1)true) return true;
//判断从这个位置开始尝试是否正确check[i][j]false;}}}
//3.代码走到这里说明所有枚举的第一个位置都无法匹配s这个字符串,所以直接返回falsereturn false;}
} 二)黄金矿工: 算法原理: 1)这个题和上一个题的起始dfs位置是存在着差别的上一道题必须是从字符串的第一个位置开始才可以进行向下dfs而这个题从上下左右边界任意位置开始进行dfs都可以 2)开采过的位置不能再挖0号位置不能再挖 3)枚举所有位置为起点进行爆搜 1219. 黄金矿工 - 力扣LeetCode class Solution {int ret0;int row0;int col0;public boolean[][] check;int[] dx{0,0,1,-1};int[] dy{1,-1,0,0};public void dfs(int[][] array,int i,int j,int glod){glodarray[i][j];retMath.max(glod,ret);for(int k0;k4;k){int xidx[k];int yjdy[k];
if(x0xrowy0ycol!check[x][y]array[x][y]!0){check[x][y]true;dfs(array,x,y,glod);check[x][y]false;
}}}public int getMaximumGold(int[][] array) {this.rowarray.length;this.colarray[0].length;this.checknew boolean[row][col];for(int i0;iarray.length;i){for(int j0;jarray[0].length;j){if(array[i][j]0) continue;else{check[i][j]true;dfs(array,i,j,0);//这个二层循环的目的就是从每一个位置开始开始挖此时能获取到的最大黄金数check[i][j]false;}}}return ret;}
} 三)不同路径 算法原理:在矩阵中进行搜索先找到1的位置从这个起始位置开始进行深度优先遍历然后进行判断这条路径是否合法即可解决方法就是在进行向下递归的过程中使用count变量来记录一下从起始位置开始记录一下行走步数到达最终结果之后再进行对比和实际要走的步数是否相同(整个数组0的个数) 980. 不同路径 III - 力扣LeetCode class Solution {//这样处理的目的就是我所走的所有路径的格子数等于总的格子数public int step2;//表示处理第一个数和最后一个数public boolean[][] check;public int row0;public int col0;public int count1;//表示处理第一个数public int ret0;int[] dx{0,0,1,-1};int[] dy{1,-1,0,0};public void dfs(int[][] array,int i,int j){if(array[i][j]2){if(stepcount){System.out.println(ret);ret;}return;}for(int k0;k4;k){int xidx[k];int yjdy[k];
if(x0xrowy0ycol!check[x][y]array[x][y]!-1){check[x][y]true;count;dfs(array,x,y);count--;check[x][y]false;
}}}public int uniquePathsIII(int[][] array) {this.rowarray.length;this.colarray[0].length;this.checknew boolean[row][col];
//1.先进行处理整个方形格子中的0的个数int dx0;int dy0;for(int i0;irow;i){for(int j0;jcol;j){if(array[i][j]0) step;else if(array[i][j]1){dxi;dyj;}}}
//2.先找到1的位置check[dx][dy]true;dfs(array,dx,dy);return ret;}
} 四)递增子序列 算法原理: 1)这个题的剪枝策略一共有两步: 1.2)在同一层内相同的元素重复出现的要剪掉 1.3)在每一层内进行枚举从pos1的位置开始进行枚举防止使用到上一层已经使用过的元素 1.3)在本层进行枚举元素的时候一定要比上一层的最后一个元素要大但是如果path中没有任何元素那么就可以放心地向里面添加元素 491. 递增子序列 - 力扣LeetCode class Solution {ListListInteger retnew ArrayList();ListInteger pathnew ArrayList();public void dfs(int[] nums,int pos){if(path.size()2){ret.add(new ArrayList(path));}
HashSetInteger setnew HashSet();
//将本层的所有元素保存起来,防止重复for(int ipos;inums.length;i){
if((path.size()0||path.get(path.size()-1)nums[i])!set.contains(nums[i])){path.add(nums[i]);set.add(nums[i]);dfs(nums,i1);path.remove(path.size()-1);
}}}public ListListInteger findSubsequences(int[] nums) {dfs(nums,0);return ret;}
} 五)分割回文串 131. 分割回文串 - 力扣LeetCode 1)什么是切割线startIndex后面应该被切割的字符串的第一个位置第一个分割线就是在startIndex第一个字符后面的 2)如何表示切割的子串的范围[startIndexi]i一开始等于startIndex此时切割线在i所指向的字符的后面 class Solution {ListListString retnew ArrayList();boolean[][] dpnull;ListString pathnew ArrayList();public void dfs(String s,int startIndex){if(startIndexs.length()){ret.add(new ArrayList(path));return;}
//注意单层递归的逻辑for(int istartIndex;is.length();i){if(dp[startIndex][i]true){
//判断当前选择切割的这一段部分是否是回文串,如果不是回文串,那么当前位置作废,直接进行剪枝操作path.add(s.substring(startIndex,i1));
//此时这个分割线在i1这个字符的后面dfs(s,i1);path.remove(path.size()-1);}else{continue;}}}public ListListString partition(String s) {
//1.首先创建一个dp表,dp[i][j]表示以i位置元素为起点,j位置字符为终点,是否这个子串是一个回文串
this.dpnew boolean[s.length()][s.length()];//从下到上,从走向右进行填表for(int is.length()-1;i0;i--){for(int ji;js.length();j){if(s.charAt(i)s.charAt(j)){if(ij) dp[i][j]true;else if(i1j) dp[i][j]true;else{dp[i][j]dp[i1][j-1];}}else{dp[i][j]false;}}}//2.然后进行回溯操作dfs(s,0);return ret;}
} 六)复原IP地址 93. 复原 IP 地址 - 力扣LeetCode 一)题目解析: 1)什么是有效的IP地址呢 1.1)首先这个IP地址的经过逗号分割的单独一个部分可以包含一个0但是一个数字前面不能出现前导0就比如说0.011.122.32 1.2)还有经过逗号分割的每一个部分的值都是小于255的例如192.168.1.455 1.3)如果给定的字符串中出现了非正整数字符的话那么它本身也是一个非法的IP地址 所以本题我们不光要对字符串进行切割处理还需要针对切割出来的每一个字符串要做一个合法性的判断 二)算法原理: dfs参数的设计: 1)在我们的dfs函数的参数里面有一个变量叫做startIndex主要作用就是从本层开始当进入到下一层递归的时候要从剩下的字符串的哪一个位置开始进行切割 2)传入应该被切割的字符串 3)要加入的IP地址的点的数量其实这个IP地址的点的数量就决定了这颗决策树的深度决策树的高度其实就是三就可以了也没有必要向下进行切割了如果你继续向下切割那么只能会多增加逗点此时这个IP地址固定不是一个合法的IP地址了 返回值: 还有当进入到递归出口的时候要对最后一个字符串做合法性的判断如果这个最后一个字符串也合法最后才可以加入到最终的结果集里面这个判断函数数字前面不能有0区间长度不能超过255不能出现除了数字外的字符 dfs函数有就是每一层要做的事: 1)枚举每一个切割线的位置进行切割如果发现切割线切除的字符串不是一个合法的字符串就没有必要继续向下进行深度优先遍历了直接向上返回就可以了 2)如果发现被这个切割线的子串是一个合法的字符串(s.substring(startIndexi1)那么就将这个字符串加入到path里面同时开始进行枚举下一层最后回到本层的时候别忘了恢复现场 3)注意本体有一道坑这个num这个数应该写在for循环的里面因为num所传递的数可能已经超过了整数可以表示的最大范围 class Solution {ListString retnew ArrayList();StringBuilder pathnew StringBuilder();public int pointNum0;//判断字符串s在左闭右闭区间[start,end]区间内是否合法public boolean isValid(String s,int start,int end){if(s.equals()) return false;if(startend) return false;//以0为开始的字符不合法if(s.charAt(start)0start!end) return false;int num0;for(int istart;iend;i){if(s.charAt(i)9||s.charAt(i)0) return false;numnum*10(s.charAt(i)-0);}if(num255) return false;return true;}public void dfs(String s,int startIndex){
//1.处理递归出口if(pointNum3){
//说明此时逗号数量是3,分割结束,此时判断第四段字符串是否合法,如果合法就加入到result中
if(isValid(s,startIndex,s.length()-1)){
//将最后一个字符串加入到path中path.append(s.substring(startIndex,s.length()));ret.add(path.toString());
//恢复现场,注意这里面不是s.length()-1path.delete(startIndex2,path.length()-1);}return; }
//2.处理每一层所干的事for(int istartIndex;is.length();i){if(isValid(s,startIndex,i)){path.append(s.substring(startIndex,i1));pointNum;path.append(.);dfs(s,i1);pointNum--;path.delete(startIndexpointNum,ipointNum2);}}}public ListString restoreIpAddresses(String s) {// if(s.length()12) return ret;dfs(s,0);return ret;}
} 七)不同的二叉搜索树 95. 不同的二叉搜索树 II - 力扣LeetCode 算法原理:
