网站备案核验系统,wordpress获取浏览人信息,网站制作售后,品牌设计开题报告文章目录 组合组合总和 III电话号码的字母组合组合总和组合总和II思路代码实现 分割回文串※思路字符串分割回文串判断效率优化※ 复原 IP 地址优化版本 子集子集 II使用usedArr辅助去重不使用usedArr辅助去重 递增子序列※全排列全排列 II重新安排行程题意代码 N 皇后解数独直… 文章目录 组合组合总和 III电话号码的字母组合组合总和组合总和II思路代码实现 分割回文串※思路字符串分割回文串判断效率优化※ 复原 IP 地址优化版本 子集子集 II使用usedArr辅助去重不使用usedArr辅助去重 递增子序列※全排列全排列 II重新安排行程题意代码 N 皇后解数独直接遍历优化 组合
https://leetcode.cn/problems/combinations/description/ public ListListInteger combine(int n, int k) {ListListInteger result new ArrayList();// 存储搜索路径ListInteger path new ArrayList();// 从1开始递归backtrack(n, k, 1, path, result);return result;
}void backtrack(int n, int k, int startNum, ListInteger path, ListListInteger result) {if (path.size() k) {// --if-- 组合的元素个数k说明找到了新的解存储到result中ListInteger clone new ArrayList(k);for (Integer num : path) {clone.add(num);}result.add(clone);return;}for (int num startNum; num n; num) {// --for--遍历加下来的元素// 将遍历到的元素添加到搜索路径中path.add(num);// 递归开始数量1backtrack(n, k, num 1, path, result);// 移除刚刚添加的数量path.remove(path.size() - 1);}
}ListInteger clone new ArrayList(k);
for (Integer num : path) {clone.add(num);
}
result.add(clone);上面的实现可以简化为
result.add(new ArrayList(path));通过查看源码可以发现构造方法传入集合的时候JDK会自动帮我们做克隆操作
/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collections* iterator.** param c the collection whose elements are to be placed into this list* throws NullPointerException if the specified collection is null*/
public ArrayList(Collection? extends E c) {Object[] a c.toArray();if ((size a.length) ! 0) {if (c.getClass() ArrayList.class) {elementData a;} else {elementData Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData EMPTY_ELEMENTDATA;}
}通过提交运行结果可以发现上面的实现执行用时比较长这是为什么呢
假设n5,k3组合可选元素为1,2,3,4,5
当path[]时组合的第一个元素为4后面只有一个5继续递归遍历也只能找到两个元素的组合无法找找到达到长度要求的组合4、5无需遍历当path[1]时组合的第二个元素为5后面没有元素无法找找到达到长度要求的组合5无需遍历
因此通过减少部分遍历来加快代码速度
public ListListInteger combine(int n, int k) {ListListInteger result new ArrayList();// 存储搜索路径ListInteger path new ArrayList();// 从1开始递归backtrack(n, k, 1, path, result);return result;
}void backtrack(int n, int k, int startNum, ListInteger path, ListListInteger result) {if (path.size() k) {// --if-- 组合的元素个数k说明找到了新的解存储到result中result.add(new ArrayList(path));return;}for (int num startNum; num n - (k - path.size()) 1; num) {// --for--遍历加下来的元素// 将遍历到的元素添加到搜索路径中path.add(num);// 递归开始数量1backtrack(n, k, num 1, path, result);// 移除刚刚添加的数量path.remove(path.size() - 1);}
}在创建ListInteger path new ArrayList();因为path的长度已知因此可以在初始化集合的时候传入集合长度避免后面发生集合扩容ListInteger path new ArrayList(k);
组合总和 III
https://leetcode.cn/problems/combination-sum-iii/description/ public ListListInteger combinationSum3(int k, int n) {ListListInteger result new ArrayList();ListInteger path new ArrayList();backtrack(k, n, 1, result, path, 0);return result;
}private void backtrack(int k, int n, int startNum, ListListInteger result, ListInteger path, int sum) {if (path.size() k) {// --if-- 搜索到的组合元素个数为kif (sum n) {// --if-- sum等于n存储组合result.add(new ArrayList(path));} else {// --if-- 元素个数已经为3无需再往下递归否则元素个数超出k了再搜索也是白费return;}}for (int i startNum; i 9; i) {path.add(i);backtrack(k, n, i 1, result, path, sum i);path.remove(path.size() - 1);}
}【剪枝优化】
剪枝1path.size()k剪枝2sumn剪枝3无效组合起点类似上一题i 10- (k - path.size())
public ListListInteger combinationSum3(int k, int n) {ListListInteger result new ArrayList();ListInteger path new ArrayList();backtrack(k, n, 1, result, path, 0);return result;
}private void backtrack(int k, int n, int startNum, ListListInteger result, ListInteger path, int sum) {if (path.size() k) {// --if-- 搜索到的组合元素个数为kif (sum n) {// --if-- sum等于n存储组合result.add(new ArrayList(path));} else {// --if-- 元素个数已经为3无需再往下递归否则元素个数超出k了再搜索也是白费return;}} else if (sum n) {// --if-- 搜索到的组sum已经大于n无需再往下搜索return;}for (int i startNum; i 10- (k - path.size()) ; i) {path.add(i);backtrack(k, n, i 1, result, path, sum i);path.remove(path.size() - 1);}
}电话号码的字母组合
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/ public ListString letterCombinations(String digits) {if (digits.length() 0) {return new ArrayList();}// 先将字符串转化为char数组方便遍历操作char[] charArray digits.toCharArray();// 存储结果ListString result new ArrayList();// 存储搜索组合为什么使用数组呢因为组合的元素数量是没有变化的而且后面需要将元素组合转化为字符串使用char数组更加方便char[] path new char[digits.length()];// 从1开始递归backtrack(charArray, 0, path, result);return result;
}void backtrack(char[] charArray, int charIndex, char[] path, ListString result) {if (charIndex charArray.length) {// --if-- 数字已经遍历完成存储结果result.add(new String(path));return;}char numChar charArray[charIndex];// 根据输入的数字转化为对应的字符数组char[] chooseCharArr null;switch (numChar) {case 2:chooseCharArr new char[]{a, b, c};break;case 3:chooseCharArr new char[]{d, e, f};break;case 4:chooseCharArr new char[]{g, h, i};break;case 5:chooseCharArr new char[]{j, k, l};break;case 6:chooseCharArr new char[]{m, n, o};break;case 7:chooseCharArr new char[]{p, q, r, s};break;case 8:chooseCharArr new char[]{t, u, v};break;case 9:chooseCharArr new char[]{w, x, y, z};break;}// 循环字符数组挑选一个并进入下一个数字对应的字符挑选for (int i 0; i chooseCharArr.length; i) {path[charIndex] chooseCharArr[i];backtrack(charArray, charIndex 1, path, result);// 这里不需要回溯操作因为下一次循环会主动将 path[charIndex] 替换成另一个元素}
}【代码随想录实现】
//设置全局列表存储最后的结果
ListString list new ArrayList();public ListString letterCombinations(String digits) {if (digits null || digits.length() 0) {return list;}//初始对应所有的数字为了直接对应2-9新增了两个无效的字符串String[] numString {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};//迭代处理backTracking(digits, numString, 0);return list;}//每次迭代获取一个字符串所以会涉及大量的字符串拼接所以这里选择更为高效的 StringBuilder
StringBuilder temp new StringBuilder();//比如digits如果为23,num 为0则str表示2对应的 abc
public void backTracking(String digits, String[] numString, int num) {//遍历全部一次记录一次得到的字符串if (num digits.length()) {list.add(temp.toString());return;}//str 表示当前num对应的字符串String str numString[digits.charAt(num) - 0];for (int i 0; i str.length(); i) {temp.append(str.charAt(i));//递归处理下一层backTracking(digits, numString, num 1);//剔除末尾的继续尝试temp.deleteCharAt(temp.length() - 1);}
}组合总和
https://leetcode.cn/problems/combination-sum/description/ public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger result new ArrayList();ListInteger path new ArrayList();backtrack(candidates, target, 0, result, path);return result;
}private void backtrack(int[] candidates, int target, int startIndex,ListListInteger result, ListInteger path) {if (target 0) {result.add(new ArrayList(path));return;}for (int i startIndex; i candidates.length; i) {// 计算剩下的target最多还可以容纳多少个 candidates[i] int num target / candidates[i];// 循环取不同个数 candidates[i] 的情况// 注意j从1开始j0的情况其实在i的循环中已经考虑到了例如当i等于startIndex1时实际上就是startIndex对应的元素j0for (int j 1; j num; j) {// 将j个元素添加到搜索路径中for (int k 0; k j; k) {path.add(candidates[i]);}backtrack(candidates, target - candidates[i] * j, i 1, result, path);// 将j个元素从搜索路径中移除for (int k 0; k j; k) {path.remove(path.size() - 1);}}}
}从结果可以分析出来上面的代码还有效率问题
其中的一个原因就是如下代码每次需要添加j个元素然后移除j个元素
// 将j个元素添加到搜索路径中
for (int k 0; k j; k) {path.add(candidates[i]);
}// 将j个元素从搜索路径中移除
for (int k 0; k j; k) {path.remove(path.size() - 1);
}改成下面的代码效率会更好一点
public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger result new ArrayList();ListInteger path new ArrayList();backtrack(candidates, target, 0, result, path);return result;
}private void backtrack(int[] candidates, int target, int startIndex,ListListInteger result, ListInteger path) {if (target 0) {result.add(new ArrayList(path));return;}for (int i startIndex; i candidates.length; i) {if (target candidates[i]) {path.add(candidates[i]);backtrack(candidates, target - candidates[i], i, result, path);path.remove(path.size() - 1);}}
}最后还存在一个剪枝策略就是先将candidates升序排序当遇到一个candidates[i]target时直接break出循环即可 public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger result new ArrayList();ListInteger path new ArrayList();Arrays.sort(candidates);backtrack(candidates, target, 0, result, path);return result;
}private void backtrack(int[] candidates, int target, int startIndex,ListListInteger result, ListInteger path) {if (target 0) {result.add(new ArrayList(path));return;}for (int i startIndex; i candidates.length; i) {if (target candidates[i]) {path.add(candidates[i]);backtrack(candidates, target - candidates[i], i, result, path);path.remove(path.size() - 1);} else {break;}}
}不过跑了很多次还没有前面的效率高可能是排序也比较耗时 组合总和II
https://leetcode.cn/problems/combination-sum-ii/description/ 思路
如下图所示常规的回溯方法会导致搜索到重复的组合题目中要求不能出现重复组合。可以做一些去重操作来解决这个问题但是性能肯定不好。我们应该在搜索的时候进行剪枝。 如下图所示分支2 其实已经被 分支1 包含因此算法在搜索过程无需搜索分支2 如何识别出分支2呢一个明显的特征是candidates[1] candidates[0] 2那当candidates[i] candidates[i-1]时就把i对应分支剪掉
答案是不允许因为这样的话会导致分支1也没有搜索完全。如下图所示分支a 和 分支b 都会被剪掉。如果target7 的话组合[2,2,3]就搜索不到了。因此需要区分 分支a 和 分支b 分支b才是要被剪枝的。 那么如何区分 分支a 和 分支b 呢我使用一个数组useArr来帮助区分useArr[i]表示candidates[i]在当前搜索组合中是否被使用。如下图所示搜索过程中useArr的变化如下图所示。从图中可以很容易发现分支a和分支b的useArr不一样准确来说是useArr[i-1]不一样分支a对应的useArr[i-1]1而分支b对应的useArr[i-1]0。因此当i 0 useArr[i - 1] 0 candidates[i - 1] candidates[i]时进行剪枝。注意在搜索之前需要先对candidates进行升序排序才通过判断i和i-1对应的元素是否相同。 代码实现
public ListListInteger combinationSum2(int[] candidates, int target) {ListListInteger result new ArrayList();ListInteger path new ArrayList();// 存储组合使用的元素1说明元素被使用0说明元素没有被使用int[] useArr new int[candidates.length];// 先将数组的值升序排序Arrays.sort(candidates);backtrack(candidates, useArr, target, 0, result, path);return result;
}private void backtrack(int[] candidates, int[] useArr, int target, int startIndex,ListListInteger result, ListInteger path) {if (target 0) {result.add(new ArrayList(path));return;}for (int i startIndex; i candidates.length; i) {if (target candidates[i]) {// target很小了candidates后的数只会更大所以可以breakbreak;}// 如果 candidates[i - 1] candidates[i] 说明同一层遍历到和之前的元素一样。如果useArr[i - 1] 0进行剪枝if (i 0 useArr[i - 1] 0 candidates[i - 1] candidates[i]) {continue;}// 使用了candidates[i]useArr[i] 1;path.add(candidates[i]);backtrack(candidates, useArr, target - candidates[i], i 1, result, path);path.remove(path.size() - 1);// 去除candidates[i]的使用useArr[i] 0;}
}分割回文串※
https://leetcode.cn/problems/palindrome-partitioning/description/ 思路
字符串分割 public ListListString partition(String s) {ListListString result new ArrayList();ListString path new ArrayList();char[] charArray s.toCharArray();backtrack(result, path, charArray, 0);return result;
}private void backtrack(ListListString result, ListString path, char[] charArray, int startIndex) {if (startIndex charArray.length) {// --if-- 字符串切割完成了result.add(new ArrayList(path));return;}for (int i startIndex; i charArray.length; i) {String s ;// 截取[startIndex,i]对应子串for (int j startIndex; j i; j) {s charArray[j];}// 将子串添加到path中path.add(s);// 递归处理剩下的子串backtrack(result, path, charArray, i 1);// 回溯path.remove(path.size() - 1);}
}当然上面的代码是生成所有的切割方案并没有判断切割出来的子串是否符合回文串要求 回文串判断
判断一个字符串非常简单使用双指针法。一个指针从头开始一个指针从尾开始判断两个指针对应的字符是否相同即可如果出现不相同说明字符串不是回文串。
private boolean isPalindromeSubStr(String s) {int start 0;int end s.length() - 1;while (start end) {if (s.charAt(start) ! s.charAt(end--)) {return false;}}return true;
}【总代码】
public ListListString partition(String s) {ListListString result new ArrayList();ListString path new ArrayList();char[] charArray s.toCharArray();backtrack(result, path, charArray, 0);return result;
}private void backtrack(ListListString result, ListString path, char[] charArray, int startIndex) {if (startIndex charArray.length) {// --if-- 字符串切割完成了result.add(new ArrayList(path));return;}for (int i startIndex; i charArray.length; i) {String s ;for (int j startIndex; j i; j) {s charArray[j];}// 判断子串是否为回文串如果不是的遍历下一个回文串if (isPalindromeSubStr(s) false) {continue;}path.add(s);backtrack(result, path, charArray, i 1);path.remove(path.size() - 1);}
}private boolean isPalindromeSubStr(String s) {int start 0;int end s.length() - 1;while (start end) {if (s.charAt(start) ! s.charAt(end--)) {return false;}}return true;
}通过结果可以发现计算效率非常低因为在搜索过程中不断使用字符串拼接
效率优化※
直接使用substring
public ListListString partition(String s) {ListListString result new ArrayList();ListString path new ArrayList();backtrack(result, path, s, 0);return result;
}private void backtrack(ListListString result, ListString path, String s, int startIndex) {if (startIndex s.length()) {// --if-- 字符串切割完成了result.add(new ArrayList(path));return;}for (int i startIndex; i s.length(); i) {// 判断子串是否为回文串如果不是的遍历下一个回文串String str s.substring(startIndex, i 1);if (isPalindromeSubStr(str) false) {continue;}path.add(str);backtrack(result, path, s, i 1);path.remove(path.size() - 1);}
}private boolean isPalindromeSubStr(String s) {int start 0;int end s.length() - 1;while (start end) {if (s.charAt(start) ! s.charAt(end--)) {return false;}}return true;
}效率提高了一点点 多跑一次结果完全不同所以大家不能太相信leetcode的数据统计。同一段代码在计算机中跑运行时间有波动非常正常 性能还有优化的空间还可以使用动态规划来进行优化等学完动态规划再回来改进
复原 IP 地址
https://leetcode.cn/problems/restore-ip-addresses/description/ public ListString restoreIpAddresses(String s) {ListString result new ArrayList();ListString path new ArrayList();char[] charArray s.toCharArray();backtrack(result, path, charArray, 0);return result;
}private void backtrack(ListString result, ListString path, char[] charArray, int startIndex) {if (startIndex charArray.length path.size() 4) {// --if-- 字符串切割完成了且符合ip形式就存储ipStringBuilder ipSb new StringBuilder();for (int i 0; i path.size() - 1; i) {ipSb.append(path.get(i) .);}ipSb.append(path.get(path.size() - 1));result.add(ipSb.toString());return;} else if (path.size() 4) {// --if-- 超过4个整数了ip不合法return;}StringBuilder sb new StringBuilder();for (int i startIndex; i charArray.length; i) {sb.append(charArray[i]);// 判断子串是否为回文串如果不是的遍历下一个回文串if (isReasonable(sb.toString()) false) {break;}path.add(sb.toString());backtrack(result, path, charArray, i 1);path.remove(path.size() - 1);}
}private boolean isReasonable(String string) {// 不能含有前导 0if (string.length() 1 string.charAt(0) 0) {return false;}// 每个整数位于 0 到 255 之间组成int num Integer.parseInt(string);if (num 255) {return false;}return true;
}优化版本
统一使用一个StringBuilder
String temp;public ListString restoreIpAddresses(String s) {ListString result new ArrayList();StringBuilder sb new StringBuilder();backtrack(result, sb, s, 0, 0);return result;
}/*** 回溯方法** param result 记录结果集* param sb 记录当前ip* param s 原字符串* param startIndex 开始索引* param splitNum 逗号分割数量*/
private void backtrack(ListString result, StringBuilder sb, String s, int startIndex, int splitNum) {if (startIndex s.length() splitNum 4) {// --if-- 字符串切割完成了且符合ip形式就存储ipresult.add(sb.toString());return;} else if (splitNum 4) {// --if-- 超过4个整数了ip不合法return;}for (int i startIndex; i s.length(); i) {if (i - startIndex 1 s.charAt(startIndex) 0) {// --if-- 当前网段长度1且含有前导 0不合法ipbreakbreak;}if (i - startIndex 3) {// --if-- 当前网段长度3不合法ipbreakbreak;}// 截取字符串作为网段注意是左闭右开所以i1temp s.substring(startIndex, i 1);if (Integer.parseInt(temp) 255) {// --if-- 当前网段值255不合法ipbreakbreak;}// 将当前网段添加到ip中sb.append(temp);// 如果逗号数量 3一个ip网段最多4个逗号最多3个拼接一个逗号if (splitNum 3) {sb.append(.);}// 递归backtrack(result, sb, s, i 1, splitNum 1);// 回溯删除最后一个网段例如现在是255.255.11.13回溯之后为 255.255.11.sb.delete(startIndex splitNum, sb.length());}
}子集
https://leetcode.cn/problems/subsets/description/ 注意题目说了nums中的所有元素各不相同所以下面的代码没有必要去重
public ListListInteger subsets(int[] nums) {ListListInteger result new ArrayList();ListInteger path new ArrayList();backtrack(result, path, nums, 0);return result;
}private void backtrack(ListListInteger result, ListInteger path, int[] nums, int startIndex) {// 任何集合都要存储没有说需要满足什么条件才可以存储result.add(new ArrayList(path));// 当 startIndex nums长度 的时候本来需要return但是下面的循环不会进行所以无需把这部分代码写出来了for (int i startIndex; i nums.length; i) {path.add(nums[i]);backtrack(result, path, nums, i 1);path.remove(path.size() - 1);}
}子集 II
https://leetcode.cn/problems/subsets-ii/description/ 使用usedArr辅助去重
注意这道题目和上面的不同数组里面含有重复元素需要去重操作其实就和 组合总和II 的思路一样
public ListListInteger subsetsWithDup(int[] nums) {ListListInteger result new ArrayList();ListInteger path new ArrayList();Arrays.sort(nums);int[] useArr new int[nums.length];backtrack(result, path, nums, 0, useArr);return result;
}private void backtrack(ListListInteger result, ListInteger path, int[] nums, int startIndex, int[] useArr) {// 任何集合都要存储没有说需要满足什么条件才可以存储result.add(new ArrayList(path));// 当 startIndex nums长度 的时候本来需要return但是下面的循环不会进行所以无需把这部分代码写出来了for (int i startIndex; i nums.length; i) {// 去重if (i 0 useArr[i - 1] 0 nums[i - 1] nums[i]) {continue;}path.add(nums[i]);useArr[i] 1;backtrack(result, path, nums, i 1, useArr);path.remove(path.size() - 1);useArr[i] 0;}
}不使用usedArr辅助去重
其实这道题还可以不用use数组
public ListListInteger subsetsWithDup(int[] nums) {ListListInteger result new ArrayList();ListInteger path new ArrayList();Arrays.sort(nums);backtrack(result, path, nums, 0);return result;
}private void backtrack(ListListInteger result, ListInteger path, int[] nums, int startIndex) {// 任何集合都要存储没有说需要满足什么条件才可以存储result.add(new ArrayList(path));// 当 startIndex nums长度 的时候本来需要return但是下面的循环不会进行所以无需把这部分代码写出来了for (int i startIndex; i nums.length; i) {// 去重if (i startIndex nums[i - 1] nums[i]) {continue;}path.add(nums[i]);backtrack(result, path, nums, i 1);path.remove(path.size() - 1);}
}注意去重判断变成了如下代码。和上面代码的区别是一个为i 0一个为i startIndex。以[1,2,2]为例子当startIndex2时。
如果代码为i 0就会进入去重导致子集[1,2,2]无法找到只能找到[]、[1]、[1,2]。但是如果代码为i startIndex不会触发去重因为i startIndex
// 去重
if (i startIndex nums[i - 1] nums[i]) {continue;
}递增子序列※ public ListListInteger findSubsequences(int[] nums) {ListListInteger result new ArrayList();ListInteger path new ArrayList();backtrack(result, path, nums, 0);return result;
}private void backtrack(ListListInteger result, ListInteger path, int[] nums, int startIndex) {// 任何集合都要存储没有说需要满足什么条件才可以存储if (path.size() 2) {result.add(new ArrayList(path));}// 用来去重HashMapInteger, Boolean useMap new HashMap();for (int i startIndex; i nums.length; i) {// 如果不是递增continueif (path.size() 0 nums[i] path.get(path.size() - 1)) {continue;}// 去重如果前面有用过相同的元素直接continueif (useMap.getOrDefault(nums[i], false) true) {continue;}useMap.put(nums[i], true);path.add(nums[i]);backtrack(result, path, nums, i 1);path.remove(path.size() - 1);}
}如果说数据为 [1, 2, 3, 4, 1, 1] 不去重答案就会出问题
全排列
https://leetcode.cn/problems/permutations/ 这道题只能暴力求解
public ListListInteger permute(int[] nums) {ListListInteger result new ArrayList();ListInteger path new ArrayList();boolean[] useArr new boolean[nums.length];backtrack(result, path, nums, useArr);return result;
}private void backtrack(ListListInteger result, ListInteger path, int[] nums, boolean[] useArr) {if (path.size() nums.length) {result.add(new ArrayList(path));}for (int i 0; i nums.length; i) {if (useArr[i] true) {continue;}useArr[i] true;path.add(nums[i]);backtrack(result, path, nums, useArr);useArr[i] false;path.remove(path.size() - 1);}
}不用数组useArr来辅助也可以直接使用path的contain方法来判断元素是否已经存在即可
这道题和前面比较大的一个区别是不再需要startIndex这个变量而是遍历整个数组因为需要的所有排序
全排列 II
https://leetcode.cn/problems/permutations-ii/description/ public ListListInteger permuteUnique(int[] nums) {ListListInteger result new ArrayList();ListInteger path new ArrayList();boolean[] useArr new boolean[nums.length];// 升序排序Arrays.sort(nums);backtrack(result, path, nums, useArr);return result;
}private void backtrack(ListListInteger result, ListInteger path, int[] nums, boolean[] useArr) {if (path.size() nums.length) {result.add(new ArrayList(path));}for (int i 0; i nums.length; i) {if (useArr[i] true) {continue;}// 去重如果当前元素和前一个元素相同而且useArr[i - 1] false前面一个元素肯定已经被同样的方式使用过当前组合不需要再往下遍历了if (i 0 nums[i - 1] nums[i] useArr[i - 1] false) {continue;}useArr[i] true;path.add(nums[i]);backtrack(result, path, nums, useArr);useArr[i] false;path.remove(path.size() - 1);}
}重新安排行程
https://leetcode.cn/problems/reconstruct-itinerary/description/ 题意
ListListString tickets 中存储了多张票的起点和终点我们要做的是从起点JFK开始旅行然后把每张票使用一遍注意每张票只能使用一次
字典排序的意思如下例如有两个字符串 ACD 和 ABE
首先对比两个字符串的第一个字母两者都是A打平手然后对比两个字符串的第二个字母第一个字符串的字母为C第二个字符串的字母为B因为B在字母表中的顺序更加靠前因此排序时ABE要排在ACD前面
代码
public ListString findItinerary(ListListString tickets) {ListString result new ArrayList();ListString path new ArrayList();// 存储开始站点 及 开始站点所对应的票 索引MapString, ListInteger startStationAndIndexListMap new HashMap();// 填充 startStationAndIndexListMap 的数据for (int i 0; i tickets.size(); i) {ListString ticket tickets.get(i);if (!startStationAndIndexListMap.containsKey(ticket.get(0))) {ArrayListInteger indexList new ArrayList();indexList.add(i);startStationAndIndexListMap.put(ticket.get(0), indexList);} else {startStationAndIndexListMap.get(ticket.get(0)).add(i);}}// 将indexList按照字典序升序排序for (Map.EntryString, ListInteger entry : startStationAndIndexListMap.entrySet()) {ListInteger indexList entry.getValue();Collections.sort(indexList, ((o1, o2) - {return compare(tickets.get(o1).get(1), tickets.get(o2).get(1));}));}// 用来标识哪张机票已经被使用过boolean[] useArr new boolean[tickets.size()];// 起点是固定的添加起点path.add(JFK);backtrack(tickets, result, path, startStationAndIndexListMap, useArr, 0, JFK);return result;
}private void backtrack(ListListString tickets, ListString result, ListString path, MapString, ListInteger startStationAndIndexListMap, boolean[] useArr, int useTicketNum, String startStation) {if (useTicketNum tickets.size() result.size() 0) {// --if-- 所有机票已经用完了存储当前路径result.addAll(path);return;}ListInteger indexList startStationAndIndexListMap.get(startStation);if (indexList null) {// 当前起点站没有机票了直接退出return;}// 遍历从当前起始站出发的机票for (int i 0; i indexList.size(); i) {if (result.size() 0) {// --if-- 因为题目要求只要字典序最小的一条路径因此找到一个结果就可以结束整个搜索了这里直接returnreturn;}// 机票索引Integer ticketIndex indexList.get(i);if (useArr[ticketIndex] true) {// --if-- 该机票已经被使用过continue;}// 去重当前机票首站-尾站和上一张机票的相同直接跳过即可if (i 0 tickets.get(indexList.get(i - 1)).get(1).equals(tickets.get(indexList.get(i)).get(1)) useArr[indexList.get(i - 1)] false) {continue;}// 标识当前机票已经被使用useArr[ticketIndex] true;path.add(tickets.get(ticketIndex).get(1));backtrack(tickets, result, path, startStationAndIndexListMap, useArr, useTicketNum 1, tickets.get(ticketIndex).get(1));path.remove(path.size() - 1);useArr[ticketIndex] false;}
}/*** 字典排序** param str1* param str2* return*/
private int compare(String str1, String str2) {for (int i 0; i str1.length(); i) {int compare Integer.compare(str1.charAt(i), str2.charAt(i));if (compare ! 0) {// --if-- 当前字母没有分出胜负继续比较下一个字母return compare;}}return 0;
}当然**return **compare(tickets.get(o1).get(1), tickets.get(o2).get(1));可以使用
return tickets.get(o1).get(1).compareTo(tickets.get(o2).get(1));来代替
小小优化了一下去掉path只使用result
public ListString findItinerary(ListListString tickets) {ListString result new ArrayList();// 存储开始站点 及 开始站点所对应的票 索引MapString, ListInteger startStationAndIndexListMap new HashMap();// 填充 startStationAndIndexListMap 的数据for (int i 0; i tickets.size(); i) {ListString ticket tickets.get(i);if (!startStationAndIndexListMap.containsKey(ticket.get(0))) {ArrayListInteger indexList new ArrayList();indexList.add(i);startStationAndIndexListMap.put(ticket.get(0), indexList);} else {startStationAndIndexListMap.get(ticket.get(0)).add(i);}}// 将indexList按照字典序升序排序for (Map.EntryString, ListInteger entry : startStationAndIndexListMap.entrySet()) {ListInteger indexList entry.getValue();Collections.sort(indexList, ((o1, o2) - {return tickets.get(o1).get(1).compareTo(tickets.get(o2).get(1));}));}// 用来标识哪张机票已经被使用过boolean[] useArr new boolean[tickets.size()];// 起点是固定的添加起点result.add(JFK);backtrack(tickets, result, startStationAndIndexListMap, useArr, JFK);return result;
}private void backtrack(ListListString tickets, ListString result, MapString, ListInteger startStationAndIndexListMap, boolean[] useArr, String startStation) {if (result.size() tickets.size() 1) {// --if-- 所有机票已经用完了存储当前路径return;}ListInteger indexList startStationAndIndexListMap.get(startStation);if (indexList null) {// 当前起点站没有机票了直接退出return;}// 遍历从当前起始站出发的机票for (int i 0; i indexList.size(); i) {// 机票索引Integer ticketIndex indexList.get(i);if (useArr[ticketIndex] true) {// --if-- 该机票已经被使用过continue;}// 去重当前机票首站-尾站和上一张机票的相同直接跳过即可if (i 0 tickets.get(indexList.get(i - 1)).get(1).equals(tickets.get(ticketIndex).get(1)) useArr[indexList.get(i - 1)] false) {continue;}// 标识当前机票已经被使用useArr[ticketIndex] true;result.add(tickets.get(ticketIndex).get(1));backtrack(tickets, result, startStationAndIndexListMap, useArr, tickets.get(ticketIndex).get(1));if (result.size() tickets.size() 1) {// --if-- 因为题目要求只要字典序最小的一条路径因此找到一个结果就可以结束整个搜索了这里直接returnreturn;}result.remove(result.size() - 1);useArr[ticketIndex] false;}
}字典直接存储一个站可以去往哪些站点如果选择了该站点将其从集合中删除回溯的时候再将该站点加回来
int totalStationNum;public ListString findItinerary(ListListString tickets) {totalStationNum tickets.size() 1;ListString result new ArrayList();// 存储开始站点 及 开始站点所对应的票 索引MapString, ListString startStationAndEndStationListMap new HashMap();// 填充 startStationAndIndexListMap 的数据for (int i 0; i tickets.size(); i) {ListString ticket tickets.get(i);if (!startStationAndEndStationListMap.containsKey(ticket.get(0))) {ListString endStationList new ArrayList();endStationList.add(ticket.get(1));startStationAndEndStationListMap.put(ticket.get(0), endStationList);} else {startStationAndEndStationListMap.get(ticket.get(0)).add(ticket.get(1));}}// 将indexList按照字典序升序排序for (Map.EntryString, ListString entry : startStationAndEndStationListMap.entrySet()) {Collections.sort(entry.getValue(), ((o1, o2) - {return o1.compareTo(o2);}));}// 起点是固定的添加起点result.add(JFK);backtrack(result, startStationAndEndStationListMap, JFK);return result;
}private boolean backtrack(ListString result, MapString, ListString startStationAndEndStationListMap, String startStation) {if (result.size() totalStationNum) {// --if-- 所有机票已经用完了存储当前路径return true;}ListString endStationList startStationAndEndStationListMap.get(startStation);if (endStationList null) {// 当前起点站没有机票了直接退出return false;}// 遍历从当前起始站出发的机票int i 0;while (i endStationList.size()) {// 目标站点String endStation endStationList.get(i);// 去重当前机票首站-尾站和上一张机票的相同直接跳过即可if (i 0 endStation.equals(endStationList.get(i - 1))) {i;continue;}// 去往该站点将其从集合中删除endStationList.remove(i);result.add(endStation);if (backtrack(result, startStationAndEndStationListMap, endStation) true) {// --if-- 因为题目要求只要字典序最小的一条路径因此找到一个结果就可以结束整个搜索了这里直接returnreturn true;}result.remove(result.size() - 1);endStationList.add(i, endStation);i;}return false;
}代码随想录的代码效率更高
N 皇后
https://leetcode.cn/problems/n-queens/description/ 思路遍历每一行然后看当行的每列再判断当前位置是否可行
public ListListString solveNQueens(int n) {ListListString result new ArrayList();// 初始化棋盘char[][] chessboard new char[n][n];for (int i 0; i n; i) {Arrays.fill(chessboard[i], .);}backtrack(result, chessboard, 0, n);return result;
}private void backtrack(ListListString result, char[][] chessboard, int layer, int n) {if (layer n) {// --for-- 遍历到最后一行了保存结果就结束ListString path new ArrayList();for (int i 0; i chessboard.length; i) {path.add(new String(chessboard[i]));}result.add(path);}for (int j 0; j n; j) {// --for-- 遍历棋盘中当前行的每一列boolean isCanPlace true;if (layer 0) {// --if-- 如果是第二行以上需要判断上面行有没有皇后排斥。第一行不需要看for (int i 0; i layer; i) {// 判断同列是否有皇后if (chessboard[i][j] Q) {isCanPlace false;break;}// 判断斜对角是否有皇后if (((j - (layer - i)) 0 chessboard[i][j - (layer - i)] Q) ||(j (layer - i) n chessboard[i][j (layer - i)] Q)) {isCanPlace false;break;}}}if (isCanPlace true) {// --if-- 当前位置可以放皇后chessboard[layer][j] Q;backtrack(result, chessboard, layer 1, n);chessboard[layer][j] .;}}
}代码随想录中有更快的方法
解数独
https://leetcode.cn/problems/sudoku-solver/description/ 直接遍历
一个单元格一个单元格的遍历然后遍历[1,9]的每个数字判断该数字是否可设置。如果所有数字都不可以设置回溯
char[] selectNumCharArr new char[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
int cellRowIndex;
int cellColumnIndex;
int cellRowIndexStart;
int cellColumnIndexStart;
int cellRowIndexEnd;
int cellColumnIndexEnd;
boolean reachEnd;
boolean isFindResult;
boolean isExit;public void solveSudoku(char[][] board) {backtrack(0, 0, board);
}/*** 思路依次遍历每一个格子来填充数字** param rowIndex* param columnIndex* param board* return*/
private boolean backtrack(int rowIndex, int columnIndex, char[][] board) {if (rowIndex board.length) {// --if-- 所有行都已经遍历完成说明全部数字填充完成return true;}if (board[rowIndex][columnIndex] ! .) {// --if-- 当前格子已经有数字// 判断当前行的每个格子是否遍历完成reachEnd (columnIndex 1 board.length);// 如果当前行遍历完成就要换行columnIndex从0开始isFindResult backtrack(reachEnd ? rowIndex 1 : rowIndex, reachEnd ? 0 : columnIndex 1, board);if (isFindResult) {// --if-- 找到结果直接返回return true;}} else {for (int k 0; k selectNumCharArr.length; k) {char numChar selectNumCharArr[k];// 检测同一行是否有重复值isExit false;for (int j 0; j board.length; j) {if (board[rowIndex][j] numChar) {isExit true;break;}}if (isExit) {continue;}// 检测同一列是否有重复值for (int i 0; i board.length; i) {if (board[i][columnIndex] numChar) {isExit true;break;}}if (isExit) {continue;}// 检测框里面是否有重复值cellRowIndex rowIndex / 3;cellColumnIndex columnIndex / 3;cellRowIndexStart cellRowIndex * 3;cellColumnIndexStart cellColumnIndex * 3;cellRowIndexEnd (cellRowIndex 1) * 3;cellColumnIndexEnd (cellColumnIndex 1) * 3;for (int i cellRowIndexStart; i cellRowIndexEnd; i) {for (int j cellColumnIndexStart; j cellColumnIndexEnd; j) {if (board[i][j] numChar) {isExit true;break;}}if (isExit) {break;}}if (isExit) {continue;}// 通过上述校验可以放下当前数字board[rowIndex][columnIndex] numChar;// 递归到下一个格子reachEnd (columnIndex 1 board.length);isFindResult backtrack(reachEnd ? rowIndex 1 : rowIndex, reachEnd ? 0 : columnIndex 1, board);if (isFindResult) {return true;}// 回溯board[rowIndex][columnIndex] .;}}return false;
}优化
使用boolean数组去重减少行、列、单元格的循环判断
char[] selectNumCharArr new char[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
boolean reachEnd;
boolean isFindResult;
// 行去重
boolean[][] rowUsedArr new boolean[9][9];
// 列去重
boolean[][] columnUsedArr new boolean[9][9];
// 单元去重
boolean[][] cellUsedArr new boolean[9][9];public void solveSudoku(char[][] board) {int num;for (int i 0; i board.length; i) {for (int j 0; j board.length; j) {if (board[i][j] ! .) {num board[i][j] - 1;rowUsedArr[i][num] true;columnUsedArr[j][num] true;cellUsedArr[(i / 3) * 3 (j / 3)][num] true;}}}backtrack(0, 0, board);
}/*** 思路依次遍历每一个格子来填充数字** param rowIndex* param columnIndex* param board* return*/
private boolean backtrack(int rowIndex, int columnIndex, char[][] board) {if (rowIndex board.length) {// --if-- 所有行都已经遍历完成说明全部数字填充完成return true;}if (board[rowIndex][columnIndex] ! .) {// --if-- 当前格子已经有数字// 判断当前行的每个格子是否遍历完成reachEnd (columnIndex 1 board.length);// 如果当前行遍历完成就要换行columnIndex从0开始isFindResult backtrack(reachEnd ? rowIndex 1 : rowIndex, reachEnd ? 0 : columnIndex 1, board);if (isFindResult) {// --if-- 找到结果直接返回return true;}} else {for (int k 0; k selectNumCharArr.length; k) {int num selectNumCharArr[k] - 1;// 检测同一行是否有重复值if (rowUsedArr[rowIndex][num]) {continue;}// 检测同一列是否有重复值if (columnUsedArr[columnIndex][num] true) {continue;}// 检测框里面是否有重复值int cellIndex (rowIndex / 3) * 3 (columnIndex / 3);if (cellUsedArr[cellIndex][num]) {continue;}// 通过上述校验可以放下当前数字board[rowIndex][columnIndex] selectNumCharArr[k];rowUsedArr[rowIndex][num] true;columnUsedArr[columnIndex][num] true;cellUsedArr[cellIndex][num] true;// 递归到下一个格子reachEnd (columnIndex 1 board.length);isFindResult backtrack(reachEnd ? rowIndex 1 : rowIndex, reachEnd ? 0 : columnIndex 1, board);if (isFindResult) {return true;}// 回溯board[rowIndex][columnIndex] .;rowUsedArr[rowIndex][num] false;columnUsedArr[columnIndex][num] false;cellUsedArr[cellIndex][num] false;}}return false;
}
