当前位置: 首页> 文旅> 艺术 > 二级域名子域名大全_深圳建筑工地招工平台_简阳seo排名优化培训_合肥关键词快速排名

二级域名子域名大全_深圳建筑工地招工平台_简阳seo排名优化培训_合肥关键词快速排名

时间:2025/7/11 0:20:15来源:https://blog.csdn.net/xiangjiaonigebun/article/details/146769881 浏览次数:1次
二级域名子域名大全_深圳建筑工地招工平台_简阳seo排名优化培训_合肥关键词快速排名

回溯法也可以叫做回溯搜索法,它是一种搜索的方式。

回溯是递归的副产品,只要有递归就会有回溯。

所以以下讲解中,回溯函数也就是递归函数,指的都是一个函数

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 棋盘问题:N皇后,解数独等等

可以抽象为图形结构,树形结构

回溯函数伪代码如下:

void backtracking(参数)
  • 回溯函数终止条件(在叶子节点收集结果)
  • 所以回溯函数终止条件伪代码如下:

    if (终止条件) {存放结果;return;
    }

回溯函数遍历过程伪代码如下:

for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果
}
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}

77. 组合

本题关于剪枝操作是大家要理解的重点,因为后面很多回溯算法解决的题目,都是这个剪枝套路。

题目链接/文章讲解:代码随想录

视频讲解:带你学透回溯算法-组合问题(对应力扣题目:77.组合)| 回溯法精讲!_哔哩哔哩_bilibili

复习语法知识:

LinkedList 是 Java 集合框架中的一个类,继承自 AbstractSequentialList,实现了 ListDeque 接口。与 ArrayList 不同,LinkedList 基于链表结构(节点连接)。它不仅可以用作普通的列表(List),还可以充当 队列双端队列(Deque)

LinkedList 作为栈:

栈的特点是 后进先出(LIFO),而 LinkedList 提供了非常适合这种操作的方法,特别是:

  • addFirst() / removeFirst():从链表头部添加或删除元素

  • addLast() / removeLast():从链表尾部添加或删除元素

  • peekFirst() / peekLast():查看链表头或尾部的元素

class Solution {LinkedList<Integer>path=new LinkedList<>();List<List<Integer>> res=new ArrayList<>();//返回的集合public List<List<Integer>> combine(int n, int k) {//List是一个接口,  Integer为泛型back(n,k,1);return res;}//以下为回溯函数public void back(int n,int k,int startindex){if(path.size()==k)//抵达最终的叶子节点,回溯结束{res.add(new ArrayList<>(path));return;}
for(int i=startindex;i<=n;i++)//starindex控制不能重复,因为是组合
{path.add(i);
back(n,k,i+1);//调用回溯函数
path.removeLast();//要将末尾元素弹出,再进入新的元素,使用双向链表,便于弹出首尾元素
}}
}
res.add(new ArrayList<>(path));

new ArrayList<>(path)

这是创建一个新的 ArrayList,并将 path 的内容复制到新的 ArrayList 中。

  • path 是一个 LinkedList<Integer>,用来记录当前的组合路径。

  • new ArrayList<>(path):通过传入 path,将 path 中的所有元素复制到一个新的 ArrayList 中。这个操作非常关键,目的是创建一个全新的列表对象,否则 path 的引用会继续变化,导致 res 中的多个元素都指向同一个 path 对象,导致结果错误。

    • 为什么需要复制而不是直接添加 path 呢?

      • path 是在回溯过程中动态改变的。如果直接 add(path),每次修改 path 的时候,res 中的所有元素都会受到影响。为了防止这种情况,我们需要创建一个新的 ArrayList,让它存储 path快照,从而避免引用问题。

剪枝操作:

class Solution {LinkedList<Integer>path=new LinkedList<>();List<List<Integer>> res=new ArrayList<>();//返回的集合public List<List<Integer>> combine(int n, int k) {//List是一个接口,  Integer为泛型back(n,k,1);return res;}//以下为回溯函数public void back(int n,int k,int startindex){if(path.size()==k)//抵达最终的叶子节点,回溯结束{res.add(new ArrayList<>(path));return;}
for(int i=startindex;i<=n-(k-path.size())+1;i++)//starindex控制不能重复,因为是组合
{path.add(i);
back(n,k,i+1);//调用回溯函数
path.removeLast();//要将末尾元素弹出,再进入新的元素,使用双向链表,便于弹出首尾元素
}//控制递归深度的是path.size()}
}

剪枝操作的区别:如果剩余可选的元素小于还需要选择的元素,不进行遍历回溯

剩余可选的元素(i-n):n-i+1

还需要选择的元素:k-path.size()

可得i<=n-(k-path.size())+1

for进行横向遍历,back()进行纵向深度遍历,每个back()中包含一个for循环

回溯三部曲(我往路上放了一块石头(add),然后继续往前走(递归)。
如果走到尽头(满足条件),我记录下这条路,然后回退,把石头拿起来(removeLast()),去试别的方向。”

for (int i = startindex; i <= ...; i++) {path.add(i);             // 第一步:做选择back(n, k, i + 1);       // 第二步:递归进入下一层path.removeLast();       // 第三步:撤销选择(回溯)
}

推导剪枝条件:

步骤 1️⃣:当前还需要选多少个数?

rest = k - path.size()

步骤 2️⃣:从 i 开始到 n 一共有多少个数可选?

available = n - i + 1

条件是:可选数量 >= 需要数量

n - i + 1 >= k - path.size()

两边同时移项:

i <= n - (k - path.size()) + 1 ✅

时间复杂度:

空间复杂度:

216.组合总和III

如果把 组合问题理解了,本题就容易一些了。

题目链接/文章讲解:代码随想录

视频讲解:和组合问题有啥区别?回溯算法如何剪枝?| LeetCode:216.组合总和III_哔哩哔哩_bilibili

class Solution {LinkedList<Integer>path=new LinkedList<>();List<List<Integer>>res=new ArrayList<>();//注意接口和实现类public List<List<Integer>> combinationSum3(int k, int n) {back(n,k,1,0);return res;}public void back(int n,int k,int startindex,int sum){if(path.size()==k&&sum==n){res.add(new LinkedList<>(path));return;}//递归截止条件for(int i=startindex;i<=9;i++){path.add(i);back(n,k,i+1,sum+i);path.removeLast();//先把所有组合数都找出来}}}

修改回溯函数的参数:追踪他的总和

  • sum 是在函数调用时每次计算 sum + i 传进去的

  • 每一层递归都有独立的 sum 副本,互不干扰

  • 所以不需要显式回溯 sum

项目建议
如果你使用 sum + i 传参可以不回溯 sum
如果你写成 sum += i一定要 sum -= i 回溯
一致性风格建议尽量保持所有回溯变量都有明确的前进和撤销逻辑,代码更安全易读 ✅

剪枝操作

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum3(int k, int n) {backTracking(n, k, 1, 0);return result;}private void backTracking(int targetSum, int k, int startIndex, int sum) {// 减枝if (sum > targetSum) {return;}if (path.size() == k) {if (sum == targetSum) result.add(new ArrayList<>(path));return;}// 减枝 9 - (k - path.size()) + 1for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {path.add(i);sum += i;backTracking(targetSum, k, i + 1, sum);//回溯path.removeLast();//回溯sum -= i;}}
}

17.电话号码的字母组合

题目链接/文章讲解:代码随想录

视频讲解:还得用回溯算法!| LeetCode:17.电话号码的字母组合_哔哩哔哩_bilibili

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

class Solution {List<String>res=new ArrayList<>();StringBuilder path=new StringBuilder();Map<Character,String>map=new HashMap<>();//注意接口和实现类,存储映射关系public List<String> letterCombinations(String digits) {map.put('2',"abc");map.put('3',"def");map.put('4',"ghi");map.put('5',"jkl");map.put('6',"mno");map.put('7',"pqrs");map.put('8',"tuv");map.put('9',"wxyz");back( digits,0);return res;}//不能有嵌套类public void back(String digits,int index){if(digits==null||digits.length()==0)return;if(path.length()==digits.length()){res.add(path.toString());//加入的是字符串的副本return;}String letters=map.get(digits.charAt(index));for(char a:letters.toCharArray()){path.append(a);back(digits,index+1);path.deleteCharAt(path.length()-1);}}
}

注意点:java中为空是null

用于哪种对象方法说明示例
数组(如 int[], char[].length属性,不是方法,没有括号arr.length
String.length()是方法,有括号"abc".length()
ArrayList / LinkedList.size()是方法,有括号list.size()
StringBuilder / StringBuffer.length()是方法,有括号sb.length()

只记一点:数组用 .length,集合用 .size(),字符串相关用 .length()

  • StringBuilder.toString() 非常常用,用于拼接完字符串后转换成真正的字符串。

 String letters 在for循环的前面,是因为在第一个字符串中选一个,然后在第二个字符串中选一个,再拼接

关键字:二级域名子域名大全_深圳建筑工地招工平台_简阳seo排名优化培训_合肥关键词快速排名

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: