个人可以做电视台网站吗,免费crm手机版,logo设计网页,江阴网站建设哪家好目录
77题. 组合
216.组合总和III
17.电话号码的字母组合
39. 组合总和
40.组合总和II
131.分割回文串 93.复原IP地址
78.子集
90.子集II
491.非递减子序列
46.全排列
47.全排列 II
332.重新安排行程
51. N皇后
37. 解数独 回溯的本质是穷举#xff0c;穷举所有…目录
77题. 组合
216.组合总和III
17.电话号码的字母组合
39. 组合总和
40.组合总和II
131.分割回文串 93.复原IP地址
78.子集
90.子集II
491.非递减子序列
46.全排列
47.全排列 II
332.重新安排行程
51. N皇后
37. 解数独 回溯的本质是穷举穷举所有可能然后选出我们想要的答案
回溯三部曲。
回溯函数模板返回值以及参数回溯函数终止条件回溯搜索的遍历过程
回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}77题. 组合
力扣题目链接(opens new window)
给定两个整数 n 和 k返回 1 ... n 中所有可能的 k 个数的组合。
示例: 输入: n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
剪纸如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了那么就没有必要搜索了。 已经选择的元素个数path.size(); 还需要的元素个数为: k - path.size(); 在集合n中至多要从该起始位置 : n - (k - path.size()) 1开始遍历
class Solution {//有序集合List add addAll remove removeall contains isEmpty get set size indexOf clear//arraylist构造方法可以直接传入集合ListListInteger resnew ArrayList();ListInteger temnew ArrayList();public ListListInteger combine(int n, int k) { back(n,k,1);return res;}public void back(int n , int k,int begin){if(tem.size()k){res.add(new ArrayList(tem));return;}for(int ibegin;in-(k-tem.size())1;i){tem.add(i);back(n,k,i1);tem.remove(tem.size()-1);}}
}
216.组合总和III
力扣题目链接(opens new window)
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数并且每种组合中不存在重复的数字。
说明
所有数字都是正整数。解集不能包含重复的组合。
示例 1: 输入: k 3, n 7 输出: [[1,2,4]]
示例 2: 输入: k 3, n 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
class Solution {public ListListInteger resnew ArrayList();public LinkedListInteger temnew LinkedList();//双链表实现了List和Deque接口。 实现所有可选列表操作并允许所有元素包括null 构造方法可以传入集合//addFirst addLast removeFirst getFirst set//offer offerFirst peek peekFirst poll pollFirstpublic ListListInteger combinationSum3(int k, int n) {back(k,n,1);return res;}public void back(int k,int n,int begin){
//只要达到k个数字我们就判断剩下的n是为0 才添加进去否则就不加入并且都returnif(tem.size()k){if(n0) res.add(new LinkedList(tem));return;}for(int ibegin;i9-(k-tem.size())1;i){tem.add(i);back(k,n-i,i1);tem.removeLast();}}
}
17.电话号码的字母组合
力扣题目链接(opens new window)
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
本题每一个数字代表的是不同集合也就是求不同集合之间的组合不需要控制索引起始位置
前面2道题目 都是求同一个集合中的组合需要控制起始元素保证不重复
这里注意一下输入按键不是2-9的情况
class Solution {public String[] ss{abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};public ListString resnew ArrayList();public StringBuilder temnew StringBuilder();public ListString letterCombinations(String digits) {if(digitsnull||digits.length()0) return res;back(0,digits);return res;}public void back(int begin,String digits){//digits长度就是搜索的深度if(tem.length()digits.length()){res.add(new String(tem));return;}int indexdigits.charAt(begin)-0-2;String strss[index];for(int i0;istr.length();i){tem.append(str.charAt(i));back(begin1,digits);tem.deleteCharAt(tem.length()-1);}}
}
39. 组合总和
力扣题目链接(opens new window)
给定一个无重复元素的数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明
所有数字包括 target都是正整数。解集不能包含重复的组合。
示例 1
输入candidates [2,3,6,7], target 7,所求解集为 [ [7], [2,2,3] ]
示例 2
输入candidates [2,3,5], target 8,所求解集为 [ [2,2,2,2], [2,3,3], [3,5] ]
class Solution {public ListListInteger resnew ArrayList();ListInteger temnew ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {back(candidates,target,0);return res;}public void back(int[] candidates, int target,int begin){if(target0){res.add(new ArrayList(tem));return;}// if(target0) return; for(int ibegin;icandidates.length;i){if(target-candidates[i]0) continue;//剪纸tem.add(candidates[i]);//这里设置起始点在i 下次搜索还是可以取值i位置的数字//从而实现重复利用数字back(candidates,target-candidates[i],i);tem.remove(tem.size()-1);}}
}
40.组合总和II
力扣题目链接(opens new window)
给定一个数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明 所有数字包括目标数都是正整数。解集不能包含重复的组合。
class Solution {public ListListInteger res new ArrayList();public ListInteger temnew ArrayList();public ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);back(candidates,target,0);return res;}public void back(int[] candidates, int target,int begin){if(target0){res.add(new ArrayList(tem));return;}for(int ibegin;icandidates.lengthtarget-candidates[i]0;i){//这里限制同一层中 从第二个节点开始 如果当前节点和上一个节点相同 那就不继续添加,//从而阻止重复if(i!begincandidates[i]candidates[i-1]) continue;tem.add(candidates[i]);back(candidates,target-candidates[i],i1);tem.remove(tem.size()-1);}}
} 131.分割回文串
力扣题目链接(opens new window)
给定一个字符串 s将 s 分割成一些子串使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: aab 输出: [ [aa,b], [a,a,b] ] class Solution {public ListListString res new ArrayList();public ListString temnew ArrayList();public ListListString partition(String s) {back(s,0);return res;}//解题思路每一层切割的遍历逻辑是 切割12...n个字符//到下一层又继续从左到右切割 例如 abcd 第一层 a ab abc abcd 第二层 a,b/bc/bcd) (ab,c/cd) (abc,d)public void back(String s,int begin){if(begins.length()){res.add(new ArrayList(tem));return;}StringBuilder sbnew StringBuilder();for(int ibegin;is.length();i){//第一种方法 逐步添加字符到sb sb.append(s.charAt(i));if(!isPalindrome(sb.toString())) continue;//第二种方法 直接利用子字符串判断s.substring(begin,i1)// if(!isPalindrome(s.substring(begin,i1))) continue;tem.add(sb.toString());back(s,i1);tem.remove(tem.size()-1);}}public boolean isPalindrome(String s){for(int i0;is.length()/2;i){if(s.charAt(i)!s.charAt(s.length()-i-1)) return false;}return true;}
}
93.复原IP地址
力扣题目链接(opens new window)
给定一个只包含数字的字符串复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 . 分隔。
例如0.1.2.201 和 192.168.1.1 是 有效的 IP 地址但是 0.011.255.245、192.168.1.312 和 192.1681.1 是 无效的 IP 地址。
示例 1
输入s 25525511135输出[255.255.11.135,255.255.111.35]
class Solution {public ListString resnew ArrayList();public ListInteger temnew ArrayList();public ListString restoreIpAddresses(String s) {if(s.length()4||s.length()12) return res;back(s,0);return res;}public void back(String s,int begin){if(tem.size()4){StringBuilder strnew StringBuilder();if(begins.length()){for(Integer ss:tem){str.append(ss.);}str.deleteCharAt(str.length()-1);res.add(str.toString());} return;}StringBuilder sbnew StringBuilder();//每次只会最多分割3个数字for(int ibegin;ibegin3 is.length();i){sb.append(s.charAt(i));//如果数字位数超过1且第一位为0 不合法if(sb.length()1sb.charAt(0)0) continue;Integer numInteger.parseInt(sb.toString());if(num0num255){tem.add(num);back(s,i1);tem.remove(tem.size()-1);}}}
}
78.子集
力扣题目链接(opens new window)
给定一组不含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明解集不能包含重复的子集。
示例: 输入: nums [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
class Solution {public ListListInteger resnew ArrayList();public ListInteger temnew ArrayList();public ListListInteger subsets(int[] nums) {back(nums,0);return res;}public void back(int[] nums,int begin){res.add(new ArrayList(tem));if(beginnums.length) return;for(int ibegin;inums.length;i){tem.add(nums[i]);back(nums,i1);tem.remove(tem.size()-1);}}
}
90.子集II
力扣题目链接(opens new window)
给定一个可能包含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明解集不能包含重复的子集。
示例:
输入: [1,2,2]输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
这道题目类似之前那个集合里面有重复数字的那就需要在当前层判断
如果有相同的节点就只是处理一次
所以本道题目和上题基本一致只不过需要先对数组排序然后判断
class Solution {public ListListInteger resnew ArrayList();public ListInteger temnew ArrayList();public ListListInteger subsetsWithDup(int[] nums) {//改动1 对数组排序Arrays.sort(nums);back(nums,0);return res;}public void back(int[] nums,int begin){res.add(new ArrayList(tem));if(beginnums.length) return;for(int ibegin;inums.length;i){//改动2 判断当前节点和上一个是否相同注意第一个节点不做判断if(i!beginnums[i]nums[i-1]) continue;tem.add(nums[i]);back(nums,i1);tem.remove(tem.size()-1);}}
}
491.非递减子序列
力扣题目链接(opens new window)
给定一个整型数组, 你的任务是找到所有该数组的递增子序列递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7]输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
说明:
给定数组的长度不会超过15。数组中的整数范围是 [-100,100]。给定数组中可能包含重复数字相等的数字应该被视为递增的一种情况。
class Solution {public ListListInteger res new ArrayList();public ListInteger tem new ArrayList();public ListListInteger findSubsequences(int[] nums) {back(nums, 0);return res;}public void back(int[] nums, int begin) {if (tem.size() 1)res.add(new ArrayList(tem));// hashset方法 clear add removeif (begin nums.length)return;HashSetInteger map new HashSet();for (int i begin; i nums.length; i) {if (map.contains(nums[i]))continue;if (tem.size() ! 0 nums[i] tem.get(tem.size() - 1))continue;map.add(nums[i]);tem.add(nums[i]);back(nums, i 1);tem.remove(tem.size() - 1);}}
}
46.全排列
力扣题目链接(opens new window)
给定一个 没有重复 数字的序列返回其所有可能的全排列。
示例:
输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
//第一种方法
class Solution {public ListListInteger resnew ArrayList();public ListInteger temnew ArrayList();HashSetInteger setnew HashSet();public ListListInteger permute(int[] nums) {for(int i0;inums.length;i){set.add(nums[i]);}back();return res;}public void back(){if(set.size()0) {res.add(new ArrayList(tem));return;}HashSetInteger ssetnew HashSet(set);for(Integer num:sset){tem.add(num);set.remove(num);back();tem.remove(tem.size()-1);set.add(num);}}
}//第二种方法
class Solution {public ListListInteger res new ArrayList();public ListInteger tem new ArrayList();boolean[] used;public ListListInteger permute(int[] nums) {used new boolean[nums.length];back(nums);return res;}public void back(int[] nums) {if (tem.size() nums.length) {res.add(new ArrayList(tem));return;}for (int i 0; i nums.length; i) {if (used[i])continue;used[i] true;tem.add(nums[i]);back(nums);tem.remove(tem.size() - 1);used[i] false;}}
}
47.全排列 II
力扣题目链接(opens new window)
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。
示例 1
输入nums [1,1,2]输出 [[1,1,2], [1,2,1], [2,1,1]]
示例 2
输入nums [1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
这道题就需要控制每一层中不能重复回溯节点 利用used数组
关键biguse是为了记录集合的数字只能使用一次同一树枝只能用一次数字所以是全局变量需要回溯退回标记
used数组是用在每一层的for遍历中所以每层都有一个局部变量used数组标注当前层使用过的节点不能再继续使用
class Solution {public ListListInteger resnew ArrayList();public ListInteger temnew ArrayList();boolean[] bigUse;public ListListInteger permuteUnique(int[] nums) {bigUsenew boolean[nums.length];back(nums);return res;}public void back(int[] nums){if(tem.size()nums.length) {res.add(new ArrayList(tem));return;}int[] usednew int[21];for (int i 0; i nums.length; i) {if (used[nums[i]10]1||bigUse[i])continue;bigUse[i]true;used[nums[i]10] 1;tem.add(nums[i]);back(nums);tem.remove(tem.size() - 1);bigUse[i]false;}}
}
332.重新安排行程
力扣题目链接(opens new window)
给定一个机票的字符串二维数组 [from, to]子数组中的两个成员分别表示飞机出发和降落的机场地点对该行程进行重新规划排序。所有这些机票都属于一个从 JFK肯尼迪国际机场出发的先生所以该行程必须从 JFK 开始 思路 利用一个map存储一个起点对应的多个终点的集合map的key就是起点val是又一个treemap有序数组存储多个终点作为tmap的key value是该终点的次数
因为会存在多个起点和终点都相同的情况。
首先遍历所有的数组把数据存入map,再进行back回溯
终止条件就是res的长度等于ticket数量1
先取出res的最后一个元素作为key 去map搜索对应的全部终点作为for循环的集合
如果map不存在这个key就代表这个路径不可选退回
如果存在就进行for遍历 遍历过程中判断tmap的val是否为00代表该航班已经用完跳过
定义新的treemap把该终点的val减一 map也需要重新添加这个key,为了下一层循环控制使用次数
回溯需要注意
判断res的大小是否满足满足就直接退出循环
不满足就恢复之前的情况继续遍历for
恢复之前的情况需要注意重新添加tmap和map
class Solution {public ListString res new ArrayList();MapString, TreeMapString, Integer map new HashMap();public ListString findItinerary(ListListString tickets) {for (ListString ss : tickets) {String key ss.get(0);TreeMapString, Integer tmap map.getOrDefault(key, new TreeMapString, Integer());Integer tmapVal tmap.getOrDefault(ss.get(1), 0);tmap.put(ss.get(1), tmapVal 1);map.put(key, tmap);}res.add(JFK);back(tickets.size() 1);return res;}public void back(int airLength) {if (res.size() airLength)return;String key res.get(res.size() - 1);if (!map.containsKey(key))return;MapString, Integer vals map.get(key);for (Map.EntryString, Integer destination : vals.entrySet()) {String desKey destination.getKey();Integer desVal destination.getValue();if (desVal 0)continue;// 定义新的tmap put key, 并且map重新 put keyTreeMapString, Integer newVal new TreeMap(vals);newVal.put(desKey, desVal - 1);map.put(key, newVal);res.add(desKey);back(airLength);if (res.size() ! airLength) {res.remove(res.size() - 1);// 回溯恢复tmap和map的原来的keynewVal.put(desKey, desVal);map.put(key, newVal);} elsebreak;}}
}
51. N皇后
力扣题目链接(opens new window)
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。
used二维数组记录每个位置使用情况
used2一维数组记得每一列的使用情况用于检查不同一列
back回溯中是一行一行放置Q的所以已经控制一行中只有一个Q
回溯时需要判断是否满足对角线是否有Q不仅仅是相邻的对角线元素整个对角线都需要判断
并且我们只需要判断左上角和右上角下面的行不用判断因为我们是从第一行到最后一行放置的后面的还没放不用理会
每一行用stringbuilder添加字符串利用setCharAt改变Q的位置
这道题还可以直接创建二维数组放置Q的位置最后再用String.copyValueOf(char[])创建string class Solution {public ListListString res new ArrayList();public ListString tem new ArrayList();public boolean[][] used;public boolean[] used2;public ListListString solveNQueens(int n) {used new boolean[n][n];used2new boolean[n];back(n, 0);return res;}public void back(int n, int j) {if (tem.size() n) {res.add(new ArrayList(tem));return;}StringBuilder sb new StringBuilder();for (int i 0; i n; i) {sb.append(.);}for (int i 0; i n; i) {if(diag(j,i)) continue;if (used2[i])continue;sb.setCharAt(i, Q);used2[i] true;used[j][i] true;tem.add(sb.toString());back(n, j 1);tem.remove(tem.size() - 1);used2[i] false;used[j][i] false;sb.setCharAt(i, .);}}public boolean diag(int j,int i){//只需要检查左上角45度和右上角45度for(int jjj-1,iii-1;jj0ii0;ii--,jj--){if(used[jj][ii]) return true;}for(int jjj-1,iii1;jj0ii0iiused.length;ii,jj--){if(used[jj][ii]) return true;}return false;}
}第二种方法
class Solution {public ListListString res new ArrayList();public char[][] chessboard;public boolean[] used2;public ListListString solveNQueens(int n) {used2 new boolean[n];chessboard new char[n][n];for (int i 0; i n; i) {for (int j 0; j n; j) {chessboard[i][j] .;}}back(n, 0);return res;}public void back(int n, int j) {if (j n) {ListString tem new ArrayList();for (char[] ss : chessboard) {tem.add(String.copyValueOf(ss));}res.add(new ArrayList(tem));return;}for (int i 0; i n; i) {if (diag(j, i))continue;if (used2[i])continue;chessboard[j][i] Q;used2[i] true;back(n, j 1);used2[i] false;chessboard[j][i] .;}}public boolean diag(int j, int i) {// 只需要检查左上角45度和右上角45度for (int jj j - 1, ii i - 1; jj 0 ii 0; ii--, jj--) {if (chessboard[jj][ii] Q)return true;}for (int jj j - 1, ii i 1; jj 0 ii 0 ii chessboard.length; ii, jj--) {if (chessboard[jj][ii] Q)return true;}return false;}
}
37. 解数独
力扣题目链接(opens new window)
编写一个程序通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 . 表示。
思路逐个遍历二维数组填入数据每次填写一个都需要递归进入下一层重复填充所有的二维数组空格数据如果在填充过程中冲突就返回false并且恢复数据为空值层层回溯到最上面更改数字填充注意填充过程会出现1-9个数字都出现冲突的情况返回false
class Solution { public void solveSudoku(char[][] board) {back(board);}public boolean back(char[][] board) {for (int r 0; r board.length; r) {for (int c 0; c board[0].length; c) {if (board[r][c] ! .)continue;for (char i 1; i 9; i) {if (isValid(r, c, i, board)) {board[r][c] i;if (back(board))return true;// 这一步不能省略因为可能会存在当前空格9个数字都不能填写那就需要保持为空board[r][c] .;}}// 这一步不能省略因为会存在当前空格9个数字都不能填写说明需要回溯上上层返回falsereturn false;}}return true;}public boolean isValid(int row, int col, char num, char[][] board) {for (int i 0; i board.length; i) {if (board[row][i] num)return false;}for (int j 0; j board.length; j) {if (board[j][col] num)return false;}int rr row / 3;int cc col / 3;for (int ii rr * 3; ii rr * 3 3; ii) {for (int jj cc * 3; jj cc * 3 3; jj) {if (board[ii][jj] num)return false;}}return true;}
}
回溯算法完结*★,°*:.☆(▽)/$:*.°★* 。
