写作网站投稿赚钱,成都公司注册流程完整版,好的室内设计网站,国家工商商标注册官网查询学回溯的第二天#xff0c;发现之前做过的一道洛谷的枚举题也可以用回溯法去解决#xff0c;还是相当滴nice的。
先来看看leetcode上的这两道题
216.组合总和III
题目链接#xff1a;216. 组合总和 III
思路就是比组合问题多了一个和为n的限制#xff0c;大体还是可以…学回溯的第二天发现之前做过的一道洛谷的枚举题也可以用回溯法去解决还是相当滴nice的。
先来看看leetcode上的这两道题
216.组合总和III
题目链接216. 组合总和 III
思路就是比组合问题多了一个和为n的限制大体还是可以按模板来的代码如下
代码
class Solution {ListInteger temp new ArrayList();ListListInteger result new ArrayList();public ListListInteger combinationSum3(int k, int n) {backtracking(k, n, 1, 0);return result;}// 1. 参数分别是k个数、和为n、起始下标值保证组合元素不重复、求和计数器public void backtracking(int k, int n, int startIndex, int sum) {// 2. 循环终止条件当temp中元素达到K个时说明要停止往下递归了if(temp.size() k) {if(sum n) { // 如果和等于n则收集结果result.add(new ArrayList(temp));return;}else { // 如果不满足那么什么都不干return;}}// 3. 单层循环逻辑for(int i startIndex; i 9; i) { // 每次从传入的起始下标开始 sum i; // 记录这一次的和if(sum n){ // 剪枝操作如果和都大于n了下面也就没有递归和加入集合temp集合的必要了return;}temp.add(i); // 满足条件的直接加入temp中backtracking(k, n, i 1, sum); // 递归sum - i; // 回溯计数器也要回溯temp.remove(temp.size() - 1);}}
}
P2089 烤鸡
题目链接P2089 烤鸡
做完这道题我就想起了洛谷的这道P2089 烤鸡问题这道题比216.组合总和III 还更简单它就是当n等于输入的nk10的限制要求所以很容易写出类似的回溯代码
回溯法代码
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;public class Main {static StreamTokenizer in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));static PrintWriter out new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static ListInteger temp new ArrayList(); static ListListInteger result new ArrayList();static int count 0; // 结果次数计数器public static void main(String[] args) throws IOException {in.nextToken();int n (int) in.nval;backtracking(n,0); // 调用递归回溯方法// 由于题目中说了要先打印个数再打印组合情况所以要单独写个逻辑if(count 0) {out.println(count);for(ListInteger list : result) {for(int s : list) {out.print(s );}out.println();}}else {out.println(count);}out.close();}private static void backtracking(int n, int sum) {if(temp.size() 10) {if(sum n) {count;result.add(new ArrayList(temp));return;}else {return;}}for(int i 1; i 3; i) {sum i;if(sum n) {// 剪枝return;}temp.add(i);backtracking(n,sum);// 回溯sum - i;temp.remove(temp.size() - 1);}}
}
可以看出来和上面的216.组合总和III 问题没什么区别就是多了一个题目要求的需要先打印次数再打印结果但是这是洛谷上的题还需要写Main函数不能单单只写一个方法体当然下面还有一种这道题的解法因为这道题只需要10个数字组合并且数字只有1-3所以可以直接10个for循环类似于“百钱白鸡”问题的升级版时间复杂度也只有O(3^10)而已是个常数可以AC的下面是代码
暴力枚举代码
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;public class Main {public static void main(String[] args) throws IOException {StreamTokenizer in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));PrintWriter out new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));in.nextToken();int count 0;int n (int) in.nval;if(n - 1 9 || n 30) {out.print(0);}else {for(int a 1; a 3; a) {for(int b 1; b 3; b) {for(int c 1; c 3; c) {for(int d 1; d 3; d) {for(int e 1; e 3; e) {for(int f 1; f 3; f) {for(int g 1; g 3; g) {for(int h 1; h 3; h) {for(int i 1; i 3; i) {for(int j 1; j 3; j) {if(a b c d e f g h i j n) {count;}}}}}}}}}}}out.println(count);for(int a 1; a 3; a) {for(int b 1; b 3; b) {for(int c 1; c 3; c) {for(int d 1; d 3; d) {for(int e 1; e 3; e) {for(int f 1; f 3; f) {for(int g 1; g 3; g) {for(int h 1; h 3; h) {for(int i 1; i 3; i) {for(int j 1; j 3; j) {if(a b c d e f g h i j n) {out.print(a );out.print(b );out.print(c );out.print(d );out.print(e );out.print(f );out.print(g );out.print(h );out.print(i );out.println(j);}}}}}}}}}}}}out.close();}
}
看这代码也是相当的炸裂了哈哈哈哈但是可以AC还比回溯法AC更快
两种方法测试通过情况对比 17.电话号码的字母组合 题目链接17. 电话号码的字母组合 一开始也是没想到用哈希表的思想来映射每一个数字对应的字符串所以导致最后没做出来这题关键就在于用一个String数组通过数组下标作为值映射一个字符串作为键即 String[] table {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; 然后回溯就是以传入的字符串大小为抽象树的深度下面是代码
代码
class Solution {ListString result new ArrayList();String[] table {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};public ListString letterCombinations(String digits) {if(digits.isEmpty()) {return result;}StringBuilder str new StringBuilder();backtracking(digits, 0, str);return result;}// 1. k表示深度用StringBuilder类型来做拼接操作更方便private void backtracking(String digits, int k, StringBuilder str) {if(str.length() digits.length()) {result.add(str.toString());return;}int number digits.charAt(k) - 0; // 获取digits对应的第k个数字的数值String numberStr table[number]; // 根据数字在表中找到相应数字如2对应的“abc”for(char ch : numberStr.toCharArray()) {str.append(ch);backtracking(digits, k 1, str); // 注意这里层数参数时不能传k因为k会改变所有递归的k// k只记录这一个分支的层数所以直接加1// 回溯str.deleteCharAt(str.length() - 1);}}
}
这题还有一个关键就是在调用递归时深度的参数不能传k即使是回溯了也不行k是随着层数越往下越深而不是所有的k。
