六盘水网站设计,做摄影的网站知乎,备案网站可以做卡盟么,免费域名qq空间申请目录
回溯算法理论基础
1.题目分类
2.理论基础
3.回溯法模板
补充一个JAVA基础知识
什么时候用ArrayList什么时候用LinkedList
77. 组合
未剪枝优化
剪枝优化
216. 组合总和III
17. 电话号码的字母组合 回溯法的一个重点理解#xff1a;细细理解这句话#xff01;…目录
回溯算法理论基础
1.题目分类
2.理论基础
3.回溯法模板
补充一个JAVA基础知识
什么时候用ArrayList什么时候用LinkedList
77. 组合
未剪枝优化
剪枝优化
216. 组合总和III
17. 电话号码的字母组合 回溯法的一个重点理解细细理解这句话
回溯法抽象为树形结构后其遍历过程就是for循环横向遍历递归纵向遍历回溯不断调整结果集。
回溯算法理论基础
1.题目分类 2.理论基础
什么是回溯算法
回溯和递归是相辅相成的。
回溯法也可以叫做回溯搜索法它是一种搜索的方式。
回溯法的效率
回溯法其实就是暴力查找并不是什么高效的算法。
因为回溯的本质是穷举穷举所有可能然后选出我们想要的答案如果想让回溯法高效一些可以加一些剪枝的操作但也改不了回溯法就是穷举的本质。
回溯法可以解决几类问题
回溯法一般可以解决如下几种问题
组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等
3.回溯法模板
回溯法解决的问题都可以抽象为树形结构N叉树。
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}
回溯三部曲
回溯函数模板返回值以及参数
回溯算法中函数返回值一般为void。先写逻辑然后需要什么参数就填什么参数。
回溯函数终止条件
一般来说搜到叶子节点了也就找到了满足条件的一条答案把这个答案存放起来并结束本层递归。
回溯搜索的遍历过程
for循环可以理解是横向遍历backtracking递归就是纵向遍历这样就把这棵树全遍历完了一般来说搜索叶子节点就是找的其中一个结果了。
补充一个JAVA基础知识
什么时候用ArrayList什么时候用LinkedList
1. 存储结构与基本概念 ArrayList: 底层是基于数组的数据结构。元素是连续存储的这意味着可以通过索引快速访问元素。如果数组容量不足时ArrayList会创建一个更大的数组并将原数组的元素复制到新数组中。 LinkedList: 底层是基于双向链表的数据结构。每个节点存储元素值及前一个和后一个节点的引用。元素在内存中不必是连续的增删节点时不需要像ArrayList那样复制数组。
2. 选择依据 使用ArrayList的场景 需要频繁访问元素由于ArrayList基于数组结构可以通过索引在O(1)时间内访问任意元素因此如果你的主要操作是访问而不是插入和删除ArrayList会更适合。元素数量较多但插入和删除操作较少ArrayList在添加元素时只要不超出容量添加时间是O(1)但当数组需要扩容时时间复杂度会变为O(n)。遍历操作较多ArrayList因为底层是连续内存存储遍历时缓存命中率较高因此在遍历时性能会比LinkedList好。 使用LinkedList的场景 需要频繁的插入和删除操作LinkedList在头部或中间插入/删除元素时不需要移动其他元素只需要调整指针即可效率更高。如果你的操作集中在头部或尾部LinkedList会表现更好。需要在列表的任意位置频繁插入/删除在这种情况下LinkedList可以通过调整节点的指向来高效完成操作而ArrayList则需要移动元素来维护数组的连续性。存储的元素数量不大且不需要频繁访问LinkedList的随机访问时间是O(n)因此如果需要频繁通过索引访问元素LinkedList性能较差。
3. 总结选择
如果主要是读操作访问元素选择ArrayList。如果主要是写操作插入、删除并且特别是在头部或中间选择LinkedList。如果数据规模大并且需要高效的遍历ArrayList更好。如果数据规模小并且操作模式比较多变LinkedList的灵活性更好。
4. 示例应用场景 使用ArrayList: ListString arrayList new ArrayList();
arrayList.add(a); // O(1) - 添加元素
arrayList.get(0); // O(1) - 通过索引访问 使用LinkedList: LinkedListString linkedList new LinkedList();
linkedList.addFirst(a); // O(1) - 在头部插入
linkedList.removeFirst(); // O(1) - 从头部删除
77. 组合
本题是回溯法的经典题目。
把组合问题抽象为如下树形结构
图中每次搜索到了叶子节点我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来就可以求得 n个数中k个数的组合集合。 未剪枝优化
回溯法三部曲
递归函数的返回值以及参数
vectorvectorint result; // 存放符合条件结果的集合
vectorint path; // 用来存放符合条件单一结果
void backtracking(int n, int k, int startIndex)
函数里一定有两个参数既然是集合n里面取k个数那么n和k是两个int型的参数。
然后还需要一个参数为int型变量startIndex这个参数用来记录本层递归的中集合从哪里开始遍历集合就是[1,...,n] 。startIndex 就是防止出现重复的组合。需要startIndex来记录下一层递归搜索的起始位置。
回溯函数终止条件
path这个数组的大小如果达到k说明我们找到了一个子集大小为k的组合了在图中path存的就是根节点到叶子节点的路径。
此时用result二维数组把path保存起来并终止本层递归。
if (path.size() k) {result.push_back(path);return;
}
单层搜索的过程
回溯法的搜索过程就是一个树型结构的遍历过程在如下图中可以看出for循环用来横向遍历递归的过程是纵向遍历。
for循环每次从startIndex开始遍历然后用path保存取到的节点i。
可以看出backtracking递归函数通过不断调用自己一直往深处遍历总会遇到叶子节点遇到了叶子节点就要返回。
backtracking的下面部分就是回溯的操作了撤销本次处理的结果。 时间复杂度: O(n * 2^n)空间复杂度: O(n)
整体代码如下 class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger combine(int n, int k) {// 未剪枝优化backtracking(n, k, 1);return result;}// 递归的每一层在执行完所有可能的路径所有从startIndex到n的i之后会自然退出当前循环并结束当前的backtracking调用。public void backtracking(int n, int k, int startIndex) {if (path.size() k) {result.add(new ArrayList(path));return;}for (int i startIndex; i n; i) {path.add(i);backtracking(n, k, i 1);// 在递归调用返回之后path.removeLast()会将最后添加的元素移除以准备下一轮循环中添加不同的元素。path.removeLast();}}}
剪枝优化
剪枝的目标是减少不必要的递归调用避免继续探索那些不可能满足条件的路径从而提高效率。
来举一个例子n 4k 4的话那么第一层for循环的时候从元素2开始的遍历都没有意义了。 在第二层for循环从元素3开始的遍历都没有意义了。
这么说有点抽象如图所示 可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了那么就没有必要搜索了。
优化过程如下 已经选择的元素个数path.size(); 还需要的元素个数为: k - path.size(); 在集合n中至多要从该起始位置 : n - (k - path.size()) 1开始遍历
所以优化之后的for循环是
for (int i startIndex; i n - (k - path.size()) 1; i) // i为本次搜索的起始位置
为什么是 n - (k - path.size()) 1重点理解一下 n - (k - path.size()) 1的含义是 k - path.size()当前还需要选择的元素数量。n - (k - path.size())表示当前可选择元素的最大起始位置即从这个位置开始剩余的元素刚好足够填充到k个。1是为了让i的范围包含这个起始位置。 例如如果n 5k 3并且当前path.size() 1也就是已经选择了一个元素还需要选择2个元素。 此时k - path.size() 3 - 1 2。n - (k - path.size()) 5 - 2 3。所以i的最大值是3 1 4。换句话说从i 4开始时只有4和5两个元素可选这正好可以凑齐3个元素的组合。
剪枝示例进一步理解
假设n 5k 3我们在不同的递归层次下看i的取值范围 当path.size() 0还没选任何元素时 需要选k 3个元素。可选择范围是i 5 - (3 - 0) 1 3所以i可以从1到3。选择1时递归进入下一层。 当path.size() 1已选择1时 需要再选2个元素。可选择范围是i 5 - (3 - 1) 1 4所以i可以从2到4。 当path.size() 2已选择1, 2时 需要再选1个元素。可选择范围是i 5 - (3 - 2) 1 5所以i可以从3到5。 以此类推当path.size() k时就停止递归将结果存入result。
优化后整体代码如下
class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger combine(int n, int k) {combineHelper(n, k, 1);return result;}/*** 每次从集合中选取元素可选择的范围随着选择的进行而收缩调整可选择的范围就是要靠startIndex* param startIndex 用来记录本层递归的中集合从哪里开始遍历集合就是[1,...,n] 。*/private void combineHelper(int n, int k, int startIndex){//终止条件if (path.size() k){result.add(new ArrayList(path));return;}for (int i startIndex; i n - (k - path.size()) 1; i){path.add(i);combineHelper(n, k, i 1);path.removeLast();}}
}
216. 组合总和III
本题就是在77基础上多了一个求和的限制罢了简单。
注意处理过程 和 回溯过程是一一对应的处理有加回溯就要有减
这里我自己写的时候漏了一个sum - i的回溯 class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();int sum 0;public ListListInteger combinationSum3(int k, int n) {backTrackingSum(k, n, 1);return result;}private void backTrackingSum(int k, int n, int startIndex) {if (sum n) return; // 剪枝if (path.size() k) {if (sum n) {result.add(new ArrayList(path));}return;}// 剪枝 9 - (k - path.size()) 1for (int i startIndex; i 10 - (k - path.size()); i) {path.add(i);sum i;backTrackingSum(k, n, i 1);sum - i; // 回溯path.removeLast(); //回溯}}}
// 上面剪枝 i 9 - (k - path.size()) 1; 如果还是不清楚
// 也可以改为 if (path.size() k) return; 执行效率上是一样的
class Solution {LinkedListInteger path new LinkedList();ListListInteger ans new ArrayList();public ListListInteger combinationSum3(int k, int n) {build(k, n, 1, 0);return ans;}private void build(int k, int n, int startIndex, int sum) {if (sum n) return;if (path.size() k) return;if (sum n path.size() k) {ans.add(new ArrayList(path));return;}for(int i startIndex; i 9; i) {path.add(i);sum i;build(k, n, i 1, sum);sum - i;path.removeLast();}}
}
17. 电话号码的字母组合
本题需要多理解一下递归逻辑看着代码
本题就是要解决如下三个问题
数字和字母如何映射两个字母就两个for循环三个字符我就三个for循环以此类推然后发现代码根本写不出来输入1 * #按键等等异常情况
数字和字母如何映射
可以使用map或者定义一个二维数组例如string letterMap[10]来做映射。
回溯法来解决n个for循环的问题 回溯三部曲
确定回溯函数参数
首先需要一个字符串s来收集叶子节点的结果然后用一个字符串数组result保存起来。
参数指定是有题目中给的string digits然后还要有一个参数就是int型的index。
这个index是记录遍历第几个数字了就是用来遍历digits的题目中给出数字字符串同时index也表示树的深度。
确定终止条件
终止条件就是如果index 等于 输入的数字个数digits.size了就收集结果结束本层递归。
确定单层遍历逻辑
int digit digits[index] - 0; // 将index指向的数字转为int
string letters letterMap[digit]; // 取数字对应的字符集
for (int i 0; i letters.size(); i) {s.push_back(letters[i]); // 处理backtracking(digits, index 1); // 递归注意index1一下层要处理下一个数字了s.pop_back(); // 回溯
}
整体代码如下。需要多理解一下 class Solution {//设置全局列表存储最后的结果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};//迭代处理backTraciking(digits, numString, 0);return list;}//每次迭代获取一个字符串所以会涉及大量的字符串拼接所以这里选择更为高效的 StringBuilderStringBuilder temp new StringBuilder();//比如digits如果为23,num 为0则str表示2对应的 abcpublic void backTraciking(String digits, String[] numString, int num) {//遍历全部一次记录一次得到的字符串if (num digits.length()) {list.add(temp.toString());return;}//str 表示当前num对应的字符串//获取当前数字对应的字母字符串String str numString[digits.charAt(num) - 0]//digits.charAt(num) 获取当前 num 指向的数字字符通过减去字符 0 转换为对应的数组索引得到当前数字对应的字符串。String str numString[digits.charAt(num) - 0];for (int i 0; i str.length(); i) {temp.append(str.charAt(i));//递归处理下一层backTraciking(digits, numString, num 1);//剔除末尾的继续尝试temp.deleteCharAt(temp.length() - 1);}}}
第二十二天的总算是结束了直冲Day23
