如何知道网站是否备案过,佛山外贸网站建设方案,免费的建站平台,评价中国建设银行网站转载自 LeetCode算法总结-回溯法与深度优先搜索
回溯法#xff08;探索与回溯法#xff09;是一种选优搜索法#xff0c;又称为试探法#xff0c;按选优条件向前搜索#xff0c;以达到目标。但当探索到某一步时#xff0c;发现原先选择并不优或达不到目标#xff0c;就…转载自 LeetCode算法总结-回溯法与深度优先搜索
回溯法探索与回溯法是一种选优搜索法又称为试探法按选优条件向前搜索以达到目标。但当探索到某一步时发现原先选择并不优或达不到目标就退回一步重新选择这种走不通就退回再走的技术为回溯法而满足回溯条件的某个状态的点称为“回溯点”。例题一牛客网-LeetCode148题之combinations问题 题目描述 给出两个整数n和k返回从1到n中取k个数字的所有可能的组合 例如 如果n4k2结果为 [↵ [2,4],↵ [3,4],↵ [2,3],↵ [1,2],↵ [1,3],↵ [1,4],↵] Given two integers n and k, return all possible combinations of k numbers out of 1 … n. For example, If n 4 and k 2, a solution is: [↵ [2,4],↵ [3,4],↵ [2,3],↵ [1,2],↵ [1,3],↵ [1,4],↵]↵ 先附带答案-再进行讲解
import java.util.*;
public class Solution {/*** * param n int整型 * param k int整型 * return int整型ArrayListArrayList*/public ArrayListArrayListInteger combine (int n, int k) {// write code hereArrayListArrayListInteger listsnew ArrayListArrayListInteger();ArrayListInteger listnew ArrayList();backTrack(n,k,1,lists,list);return lists;}public void backTrack(int n,int k,int start,ArrayListArrayListInteger lists,ArrayListInteger list){if(k0){return;}else if(k0){lists.add(new ArrayList(list));}else{for(int istart;in;i){list.add(i);backTrack(n,k-1,i1,lists,list);list.remove(list.size()-1);}}}
}要求返回的类型是ArrayListArrayList Integer 也就是说将所有可能的组合list由整数构成放入另一个list由list构成中。 现在进行套路教学要求返回ListList Intege r那我就给你一个ListList Intege r因此 (1) 定义一个全局ListList resultnew ArrayListList(); (2) 定义一个辅助的方法函数public void backtracking(int n,int k, Listlist){} n k 总是要有的吧加上这两个参数前面提到List 是数字的组合也是需要的吧这三个是必须的没问题吧。可以尝试性地写参数最后不需要的删除 (3) 接着就是我们的重头戏了如何实现这个算法对于n4k21,2,3,4中选2个数字我们可以做如下尝试加入先选择1那我们只需要再选择一个数字注意这时候k1了此时只需要选择1个数字啦。当然我们也可以先选择2,3 或者4通俗化一点我们可以选择1-n的所有数字这个是可以用一个循环来描述每次选择一个加入我们的链表list中下一次只要再选择k-1个数字。那什么时候结束呢当然是k0的时候啦这时候都选完了。
回溯法要注意回退例题二牛客网-LeetCode148题之combinations问题 题目描述 给出一组候选数C和一个目标数T找出候选数中加起来和等于T的所有组合。 C中的数字在组合中可以被无限次使用 注意 题目中所有的数字包括目标数T都是正整数 你给出的组合中的数字 (a 1, a 2, … , a k) 要按非递增排序 (ie, a 1 ≤ a 2 ≤ … ≤ a k). 结解集中不能包含重复的组合 例如给定的候选数集是[2,3,6,7]目标数是7 解集是 [7] [2, 2, 3]
import java.util.*;
public class Solution {public ArrayListArrayListInteger combinationSum(int[] candidates, int target) {ArrayListArrayListInteger listsnew ArrayListArrayListInteger();ArrayListInteger listnew ArrayList();Arrays.sort(candidates);backTrack(candidates,target,0,lists,list);return lists;}public void backTrack(int[] candidates,int target,int start,ArrayListArrayListInteger lists,ArrayListInteger list){if(target0){return;}else if(target0){ArrayListInteger tempnew ArrayList(list);Collections.sort(temp);lists.add(temp);}else{for(int istart;icandidates.length;i){list.add(candidates[i]);backTrack(candidates,target-candidates[i],i,lists,list);list.remove(list.size()-1);}}}
}例题三牛客网-LeetCode148题之subsets问题 题目描述 现在有一个没有重复元素的整数集合S求S的所有子集 注意 你给出的子集中的元素必须按不下降的顺序排列 给出的解集中不能出现重复的元素 例如 如果S[1,2,3], 给出的解集应为 [↵ [3],↵ [1],↵ [2],↵ [1,2,3],↵ [1,3],↵ [2,3],↵ [1,2],↵ []↵] 方法一其实这种方法完全可以输出正确内容但是顺序与oj不同不能通过也没能找到合适的比较器策略。
import java.util.*;
public class Solution {public ArrayListArrayListInteger subsets(int[] S) {ArrayListArrayListInteger list new ArrayListArrayListInteger();Arrays.sort(S);backtrack(list, new ArrayList(),S, 0);// Collections.sort(list);return list;}private void backtrack(ArrayListArrayListInteger list , ArrayListInteger tempList, int [] nums, int start){list.add(new ArrayList(tempList));for(int i start; i nums.length; i){tempList.add(nums[i]);backtrack(list, tempList, nums, i 1);tempList.remove(tempList.size() - 1);}}
}方法二
import java.util.*;
public class Solution {public ArrayListArrayListInteger subsets(int[] S) {ArrayListArrayListInteger lists new ArrayListArrayListInteger();ArrayListInteger listnew ArrayList();Arrays.sort(S);for(int i0;iS.length;i){backtrack(S,i,0,lists,list);}// Collections.sort(list);return lists;}//这里的K其实就是要获取多长的子序列private void backtrack(int[] S,int k,int start,ArrayListArrayListInteger lists , ArrayListInteger list){if(k0){return;}else if(k0){ArrayListInteger tempnew ArrayList(list);Collections.sort(temp);lists.add(temp);}else{for(int i start; i S.length; i){list.add(S[i]);backtrack(S,k-1,i1,lists,list);list.remove(list.size()-1);}}}
}例题四牛客网-LeetCode148题之subsets进阶问题 题目描述 给出一个可能包含重复元素的整数集合S返回该整数集合的所有子集。 注意 你给出的子集中的元素要按非递减的顺序排列 给出的解集中不能包含重复的子集 例如 如果S [1,2,2], 给出的解集应该是 [↵ [2],↵ [1],↵ [1,2,2],↵ [2,2],↵ [1,2],↵ []↵]
import java.util.ArrayList;
import java.util.ArrayList;
import java.util.Arrays;public class Solution {public ArrayListArrayListInteger subsetsWithDup(int[] num) {ArrayListArrayListInteger lists new ArrayListArrayListInteger();ArrayListInteger listnew ArrayList();if(num.length 0){return lists;}Arrays.sort(num);backTrack(num,0,lists,list);return lists;}private void backTrack(int[] num, int start,ArrayListArrayListInteger lists, ArrayListInteger list) {lists.add(new ArrayList(list));for(int i start ; i num.length ; i){if( i ! start num[i] num[i-1]){continue;}list.add(num[i]);backTrack(num,i1,lists,list);list.remove(list.size()-1);}}
}例题五牛客网-LeetCode148题之permutations问题 题目描述 给出一组数字返回该组数字的所有排列 例如 [1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
import java.util.*;
public class Solution {public ArrayListArrayListInteger permute(int[] num) {ArrayListArrayListInteger lists new ArrayList();// Arrays.sort(nums); // not necessaryArrayListInteger listnew ArrayList();backtrack(lists,list, num,0);return lists;}private void backtrack(ArrayListArrayListInteger lists, ArrayListInteger list, int [] nums,int k){if(k nums.length){lists.add(new ArrayList(list));return;} else{for(int i 0; i nums.length; i){ if(list.contains(nums[i])) continue; // element already exists, skiplist.add(nums[i]);backtrack(lists, list, nums,k1);list.remove(list.size() - 1);}}}
}例题六牛客网-LeetCode148题之permutations进阶问题 给出一组可能包含重复项的数字返回该组数字的所有排列 例如 [1,1,2]的排列如下 [1,1,2],[1,2,1], [2,1,1].
import java.util.*;
public class Solution {public ArrayListArrayListInteger permuteUnique(int[] num) {ArrayListArrayListInteger list new ArrayList();Arrays.sort(num);backtrack(list, new ArrayList(), num, new boolean[num.length]);return list;}private void backtrack(ArrayListArrayListInteger lists, ArrayListInteger list, int [] nums, boolean [] used){if(list.size() nums.length){lists.add(new ArrayList(list));} else{for(int i 0; i nums.length; i){if(used[i] || i 0 nums[i] nums[i-1] !used[i - 1]) continue;used[i] true; list.add(nums[i]);backtrack(lists, list, nums, used);used[i] false; list.remove(list.size() - 1);}}}
}例题七牛客网-LeetCode148题之letter-combination-of-phone问题 给出一个仅包含数字的字符串给出所有可能的字母组合。 数字到字母的映射方式如下:(就像电话上数字和字母的映射一样) import java.util.*;
public class Solution {/*** * param digits string字符串 * return string字符串ArrayList*/public ArrayListString letterCombinations (String digits) {// write code hereArrayListString listnew ArrayList();String[] str{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};StringBuilder resnew StringBuilder();backTrack(digits,str,res,0,list);return list;}//k表示的是到了第几个数字public void backTrack(String digits,String[] strs,StringBuilder sb,int k,ArrayListString list){if(kdigits.length()){String ssb.toString();list.add(s);return;}for(int i0;istrs[digits.charAt(k)-0].length();i){sb.append(strs[digits.charAt(k)-0].charAt(i));backTrack(digits,strs,sb,k1,list);sb.delete(sb.length()-1,sb.length());}}
}https://www.nowcoder.com/practice/f0069cfcd42649e3b6b0c759fae8cde6?tpId46tagstitlediffculty0judgeStatus0rp1ru/ta/leetcodeqru/ta/leetcode/question-ranking
剑指 Offer 12. 矩阵中的路径 请设计一个函数用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格那么该路径不能再次进入该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径路径中的字母用加粗标出。 [[“a”,“b”,“c”,“e”], [“s”,“f”,“c”,“s”], [“a”,“d”,“e”,“e”]] 但矩阵中不包含字符串“abfb”的路径因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后路径不能再次进入这个格子。 示例 1 输入board [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word “ABCCED” 输出true 示例 2 输入board [[“a”,“b”],[“c”,“d”]], word “abcd” 输出false
class Solution {public boolean exist(char[][] board, String word) {char[] words word.toCharArray();boolean[][] flagnew boolean[board.length][board[0].length];for(int i 0; i board.length; i) {for(int j 0; j board[0].length; j) {if(dfs(board, words, flag,i, j, 0)) return true;}}return false;}boolean dfs(char[][] board, char[] word,boolean[][] flag, int i, int j, int k) {if(i board.length || i 0 || j board[0].length || j 0 || board[i][j] ! word[k]||flag[i][j]) return false;if(k word.length - 1) return true;// char tmp board[i][j];//board[i][j] /;flag[i][j]true;boolean res dfs(board, word,flag, i 1, j, k 1) || dfs(board, word,flag, i - 1, j, k 1) || dfs(board, word,flag, i, j 1, k 1) || dfs(board, word,flag, i , j - 1, k 1);// board[i][j] tmp;flag[i][j]false;return res;}
}题目描述:(这题其实不是回溯法 但是跟上道题很像) 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动每一次只能向左右上下四个方向移动一格但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如当k为18时机器人能够进入方格35,37因为3537 18。但是它不能进入方格35,38因为3538 19。请问该机器人能够达到多少个格子
public class Solution {public int movingCount(int threshold, int rows, int cols){boolean move[][] new boolean[rows][cols];return help(0,0,threshold,rows,cols,move);}public int help(int i, int j, int threshold, int rows, int cols, boolean[][] move){if(i0||j0||irows||jcols||bitNum(i)bitNum(j)threshold||move[i][j] true)return 0;move[i][j] true;return help(i-1,j,threshold,rows,cols,move)help(i1,j,threshold,rows,cols,move)help(i,j-1,threshold,rows,cols,move)help(i,j1,threshold,rows,cols,move)1;}public int bitNum(int i){int sum 0;do{sum i%10;}while((i i/10) 0);return sum;}
}LeetCode 200. 岛屿数量 给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。 岛屿总是被水包围并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。 此外你可以假设该网格的四条边均被水包围。
class Solution {void dfs(char[][] grid, int r, int c) {int nr grid.length;int nc grid[0].length;if (r 0 || c 0 || r nr || c nc || grid[r][c] 0) {return;}grid[r][c] 0;dfs(grid, r - 1, c);dfs(grid, r 1, c);dfs(grid, r, c - 1);dfs(grid, r, c 1);}public int numIslands(char[][] grid) {if (grid null || grid.length 0) {return 0;}int nr grid.length;int nc grid[0].length;int num_islands 0;for (int r 0; r nr; r) {for (int c 0; c nc; c) {if (grid[r][c] 1) {num_islands;dfs(grid, r, c);}}}return num_islands;}
}矩阵中的单词匹配单词匹配 题目描述 给出一个二维字符数组和一个单词判断单词是否在数组中出现 单词由相邻单元格的字母连接而成相邻单元指的是上下左右相邻。同一单元格的字母不能多次使用。 例如 给出的字符数组 [↵ [“ABCE”],↵ [“SFCS”],↵ [“ADEE”]↵] 单词 “ABCCED”, - 返回 true, 单词 “SEE”, -返回 true, 单词 “ABCB”, - 返回 false.
public class Solution {public boolean exist(char[][] board, String word){if(word null || word || board null || board.length 0){return false;}int wordLengh word.length();int row board.length ;int colum board[0].length;int flag[][] new int[row][colum];for(int i 0 ; i row ; i ){for(int j 0; j colum ; j ){if(dfs(i,j,row,colum,word,board,flag,0)){return true;}}}return false;}public boolean dfs(int i ,int j ,int rowMax,int columMax,String word,char[][] board,int flag[][],int count){if(i rowMax || j columMax || i 0 || j 0 || flag[i][j] 1 || word.charAt(count) ! board[i][j]){return false;}flag[i][j] 1;if(count word.length() -1 ){return true;}if( dfs(i 1, j,rowMax,columMax,word,board,flag,count1) ||dfs(i - 1, j,rowMax,columMax,word,board,flag,count1)|| dfs(i , j 1,rowMax,columMax,word,board,flag,count1) ||dfs(i , j -1,rowMax,columMax,word,board,flag,count1)){return true;}flag[i][j] 0;return false;}
}LeetCode679. 24 点游戏24点 你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 */-() 的运算得到 24。
示例 1:
输入: [4, 1, 8, 7] 输出: True 解释: (8-4) * (7-1) 24 示例 2:
输入: [1, 2, 1, 2] 输出: False 注意:
除法运算符 / 表示实数除法而不是整数除法。例如 4 / (1 - 2/3) 12 。 每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如[1, 1, 1, 1] 作为输入时表达式 -1 - 1 - 1 - 1 是不允许的。 你不能将数字连接在一起。例如输入为 [1, 2, 1, 2] 时不能写成 12 12 。
import java.util.*;public class Solution {public boolean judgePoint24(int[] nums) {ListDouble numbers new ArrayListDouble();for (int num : nums) {numbers.add((double) num);}return solve(numbers);}/*** description 回溯法从数组中选出两个数把运算结果加到数组中*/private boolean solve(ListDouble numbers) {if (numbers.size() 1) {//数组中只剩下一个数的时候判断结果return Math.abs(numbers.get(0) - 24) 1e-6;//看是否与24相等}//从numbers中取出两个数把结果放入数组中for (int i 0; i numbers.size(); i) {for (int j 0; j numbers.size(); j) {if (i ! j) {//取不同的两个数//如果回溯的话还要恢复现场把数插回原位置所以不如直接生成一个新数组ListDouble nums new ArrayListDouble();for (int k 0; k numbers.size(); k) {if (k ! i k ! j) {//把剩下的数加入到新数组nums.add(numbers.get(k));}}SetDouble doubles calculate(numbers.get(i), numbers.get(j));//获取两个数运算的结果集for (Double aDouble : doubles) {nums.add(aDouble);//把两个数运算的结果分别加入到新数组中if (solve(nums)) {//找到一个结果立即返回return true;}nums.remove(nums.size() - 1);//恢复现场}}}}return false;//如果没有找到结果返回false}/*** description 返回两个数计算得到的结果集*/private SetDouble calculate(double a, double b) {SetDouble res new HashSetDouble();res.add(a - b);res.add(b - a);res.add(a b);res.add(a * b);if (a ! 0) {res.add(b / a);}if (b ! 0) {res.add(a / b);}return res;}
}95. 不同的二叉搜索树 II 给定一个整数 n生成所有由 1 … n 为节点所组成的 二叉搜索树 。
class Solution {public ListTreeNode generateTrees(int n) {if (n 0) {return new LinkedListTreeNode();}return generateTrees(1, n);}public ListTreeNode generateTrees(int start, int end) {ListTreeNode allTrees new LinkedListTreeNode();if (start end) {allTrees.add(null);return allTrees;}// 枚举可行根节点for (int i start; i end; i) {// 获得所有可行的左子树集合ListTreeNode leftTrees generateTrees(start, i - 1);// 获得所有可行的右子树集合ListTreeNode rightTrees generateTrees(i 1, end);// 从左子树集合中选出一棵左子树从右子树集合中选出一棵右子树拼接到根节点上for (TreeNode left : leftTrees) {for (TreeNode right : rightTrees) {TreeNode currTree new TreeNode(i);currTree.left left;currTree.right right;allTrees.add(currTree);}}}return allTrees;}
}
class Solution {public int numTrees(int n) {if(n2)return n;//防止溢出long cn1;//卡特兰数for(int i0;in;i){cncn*2*(2*i1)/(i2);}return (int)cn;}
}马走日判断能否从一个点到另一个点并返回路径感觉这个问题应该也是回溯法但是没有OJ平台可以测试。
leetcode 130. 被围绕的区域
https://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83?tpId46tagstitlediffculty0judgeStatus0rp1https://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83?tpId46tagstitlediffculty0judgeStatus0rp1
