网站图片上的水印怎么做,出国看病网站开发,asp.net网站开发实训,义乌做网站哪家好随想录日记part21 t i m e #xff1a; time#xff1a; time#xff1a; 2024.03.16 主要内容#xff1a;今天主要是结合类型的题目加深对回溯算法的理解#xff1a;1#xff1a;组合总和#xff1b;2#xff1a;电话号码的字母组合
216.组合总和III17.电话号码的字母…随想录日记part21 t i m e time time 2024.03.16 主要内容今天主要是结合类型的题目加深对回溯算法的理解1组合总和2电话号码的字母组合
216.组合总和III17.电话号码的字母组合 Topic1组合总和
题目 找出所有相加之和为 n n n 的 k k k 个数的组合且满足下列条件 只使用数字 1 1 1 到 9 9 9每个数字最多使用一次 返回所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。 输入 k 3 , n 9 k 3, n 9 k3,n9 输出 [ [ 1 , 2 , 6 ] , [ 1 , 3 , 5 ] , [ 2 , 3 , 4 ] ] [[1,2,6], [1,3,5], [2,3,4]] [[1,2,6],[1,3,5],[2,3,4]] 解释 1 2 6 9 1 2 6 9 1269 1 3 5 9 1 3 5 9 1359 2 3 4 9 2 3 4 9 2349 没有其他符合的组合了。
思路 按照回溯模板我们进行回溯三部曲 递归三部曲 1.回溯函数模板返回值以及参数 在这里要定义两个全局变量 p a t h path path用来存放符合条件单一结果 r e s u l t result result用来存放符合条件结果的集合。回溯函数里一定有两个参数既然是集合 [ 1 , 9 ] [1,9] [1,9] 里面取 k k k 个数和为 n n n所以需要 n n n 和 k k k 是两个 i n t int int 的参数。还需要一个参数为 i n t int int 型变量 s t a r t I n d e x startIndex startIndex这个参数用来记录本层递归的中集合从哪里开始遍历集合就是 [ 1 , . . . , n ] [1,...,n] [1,...,n] 。 所以整体代码如下 ListListInteger resultnew ArrayList();
LinkedListInteger pathnew LinkedList();
private void backtracking(int n,int k, int statindex){}2.回溯函数终止条件 回溯出口如果 p a t h path path 里面的数量等于 K K K说明其到达叶子节点若 p a t h path path 中所有元素之和为 n n n则将其加入到 r e s u l t result result否则直接返回 r e t u r n return return 代码如下 if (k path.size()) {// 回溯出口如果Path里面的数量等于K说明其到达叶子节点int sum 0;for (int i 0; i k; i) {sum path.get(i);}if (sum targetSum)result.add(new ArrayList(path));return;// 如果path.size() k 但sum ! targetSum 直接返回}3.回溯搜索的遍历过程 f o r for for 循环每次从 s t a r t I n d e x startIndex startIndex 开始遍历然后用 p a t h path path 保存取到的节点i搜索的过程如下图 实现代码如下 for (int i startindex; i 9; i) {path.add(i);backtracking(targetSum, k, i 1);path.removeLast();}完整的代码如下 class Solution {ListListInteger result new ArrayList();// 存放结果集合LinkedListInteger path new LinkedList();// 存放一个满足条件的路径public ListListInteger combinationSum3(int k, int n) {result.clear();path.clear();backtracking(n, k, 1);return result;}// targetSum目标和也就是题目中的n。// k题目中要求k个数的集合。// startIndex下一层for循环搜索的起始位置。private void backtracking(int targetSum, int k, int startindex) {if (k path.size()) {// 回溯出口如果Path里面的数量等于K说明其到达叶子节点int sum 0;for (int i 0; i k; i) {sum path.get(i);}if (sum targetSum)result.add(new ArrayList(path));return;}for (int i startindex; i 9; i) {path.add(i);// sum i;backtracking(targetSum, k, i 1);// sum - i;path.removeLast();}}}Topic2电话号码的字母组合
题目 给定一个仅包含数字 2 2 2- 9 9 9 的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意 1 1 1 不对应任何字母。 输入 d i g i t s 23 digits 23 digits23 输出 [ a d , a e , a f , b d , b e , b f , c d , c e , c f ] [ad,ae,af,bd,be,bf,cd,ce,cf] [ad,ae,af,bd,be,bf,cd,ce,cf]
思路 按照回溯模板我们进行回溯三部曲 递归三部曲 1.回溯函数模板返回值以及参数 在这里要定义两个全局变量 t e m p temp temp用来存放符合条件单一结果 l i s t list list用来存放符合条件结果的集合与此同时我们需要建立一个数字到字符的映射我们使用字符串数组 n u m S t r i n g numString numString 表示还需要一个记录查到第几个第几个字符的索引 s t a r t i n d e x startindex startindex 所以整体代码如下 // 设置全局列表存储最后的结果
ListString list new ArrayList();
// 每次迭代获取一个字符串所以会设计大量的字符串拼接所以这里选择更为高效的
StringBuild StringBuilder temp new StringBuilder();
void backtracking(String digits, String[] numString, int startindex)2.回溯函数终止条件 回溯出口如果索引值 s t a r t i n d e x startindex startindex 里面的数量等于 d i g i t s . l e n g t h ( ) digits.length() digits.length()说明其到达叶子节点则将 t e m p temp temp其加入到 l i s t list list否则直接返回 r e t u r n return return 代码如下 if (startindex digits.length()) {// 查完最后一个字符到达回溯出口list.add(temp.toString());return;
}3.回溯搜索的遍历过程 f o r for for 循环每次从 s t a r t I n d e x startIndex startIndex 开始遍历然后用 t e m p temp temp 保存取到的节点i搜索的过程如下图 实现代码如下 String str numString[digits.charAt(startindex) - 0];for (int i 0; i str.length(); i) {temp.append(str.charAt(i));backtracking(digits, numString, startindex 1);temp.deleteCharAt(temp.length() - 1); }完整的代码如下 class Solution {ListString list new ArrayList();// 设置全局列表存储最后的结果// 每次迭代获取一个字符串所以会设计大量的字符串拼接所以这里选择更为高效的 StringBuildStringBuilder temp new StringBuilder();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;}private void backtracking(String digits, String[] numString, int startindex) {if (startindex digits.length()) {// 查完最后一个字符到达回溯出口list.add(temp.toString());return;}// 得到digits[startindex]映射的字符串String str numString[digits.charAt(startindex) - 0];for (int i 0; i str.length(); i) {temp.append(str.charAt(i));backtracking(digits, numString, startindex 1);temp.deleteCharAt(temp.length() - 1); }}
}时间复杂度: O ( 3 m ∗ 4 n ) O(3^m * 4^n) O(3m∗4n)其中 m 是对应四个字母的数字个数n 是对应三个字母的数字个数 空间复杂度: O ( 3 m ∗ 4 n ) O(3^m * 4^n) O(3m∗4n)
