代码随想录算法训练营第十九天| 回溯理论、77. 组合、216. 组合总和Ⅲ、17. 电话号码的字母组合

本文主要是介绍代码随想录算法训练营第十九天| 回溯理论、77. 组合、216. 组合总和Ⅲ、17. 电话号码的字母组合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

今日内容

  • 回溯的理论基础
  • leetcode. 77 组合
  • leetcode. 216 组合总和Ⅲ
  • leetcode. 17 电话号码的字母组合

回溯理论基础

回溯法也叫回溯搜索法,它是一种搜索的方式,而且只要有递归就会有回溯,回溯就是递归的副产品。

回溯说到底并不是什么非常高深的搜索方式,本质上仍然是穷举,穷举所有可能然后选择出我们要的答案。剪枝会使回溯法更加高效一点,但改变不了回溯本质就是穷举这一事实

虽然回溯是偏暴力地穷举出所有可能结果,但是这对于某些问题来说已经是很好的解法了,有些问题不求能用多简便的方法求出了,能用暴力法搜索出一个结果就已经是非常不错了。而这些只能用穷举求解的方法可以被概括为下面几类:

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

此处比较搞混的是组合问题和排列问题的区别,需要明确:组合不强调元素顺序,而排列强调元素顺序。比如 {1, 2}、{2, 1} 在组合问题中属于同一结果,而在排列问题中就是两个结果。

能用回溯法解决的问题都可以抽象为树形结构,这也是为什么要把回溯法放在二叉树专题后介绍。因为回溯法解决的是在集合中递归查找子集,集合的大小构成了树的宽度,递归深度构成了树的深度

回溯法一般需要用到回溯函数去解决,而正如之前所说,回溯是递归的副产品,所以回溯函数和递归函数是非常类似的。回溯函数也和递归函数一样拥有三要素:

  1. 回溯函数返回值和参数。回溯函数的返回值一般为 void,然后回溯函数的参数并不能像做二叉树递归一样一次性确定下来,所以一般写回溯函数是先写逻辑,再写参数
  2. 终止条件。一般来说,到叶子节点的时候就可以结束了。
  3. 单层逻辑。把回溯问题抽象为树形结构后,图片如下。实际上,我们每一层都用一个 for 循环遍历,通过递归下到下一层。这样讲可能会比较抽象,等做了实际题目后,就会比较清晰了。

总体而言,回溯法的解题模板如下所示:

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

Leetcode. 77 组合

文章链接:代码随想录 (programmercarl.com)

题目链接:77. 组合 - 力扣(LeetCode)

本题从题名看,就知道是组合问题。

借本题也讲讲为什么一定要用递归来进行暴力穷举。一般我们想到的暴力穷举就是使用 for 循环来实现的,像本题中从 n 个数中取 k 个数,如果 k 取值为2、3、4等小数,那么嵌套2、3、4个 for 循环就好。倘若 k 为大数,比如500、1000,嵌套500、1000个 for 循环那就是灾难级别了。

递归就可以避免嵌套多层循环的问题。

前面所说,回溯法能解决的问题都可以抽象为树形结构,该题抽象的树形结构如下图所示:

根据回溯法模板 + 树形结构图,我们写出如下代码:

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> elem = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {backtracking(1, n, k);return result;}public void backtracking(int startIndex, int n, int k){if (elem.size() == k){ // 停止条件,当元素长度符合题意时result.add(new ArrayList<>(elem));return;}for (int i = startIndex; i <= n; i++){ // 每一次 for 循环表示当前层的遍历elem.add(i);backtracking(i + 1, n, k); // 递归到下一层elem.remove(elem.size() - 1);}}
}
  • 时间复杂度:O(n * 2 ^ n)
  • 空间复杂度:O(n)

其中容易搞不明白的就是:

  • startIndex
  • for 循环与递归的区别

再题目中,我们不希望获取到重复的组合结果,我们希望第一层获取到第一个元素后,递归进入下一层后可以从第二个元素开始遍历。而startIndex的作用就是如此。

再就是 for 循环和递归的区别。for 循环表示当前层的遍历,递归用于进入到下一层。以本题为例,先创建两个列表,一个用于存储临时集合 elem,一个返回最终结果 result:

  1. 第一层集合为{1, 2, 3, 4},for 循环就是遍历这一层的元素。
  2. 在遍历到第一个元素时,也就是 1,写入列表 elem。再通过递归进入到第二层。结合 startIndex,第二层的集合就是{2, 3, 4}。
  3. for 循环遍历第二层的第一个元素,也就是 2,写入列表 elem。此时elem列表长度为 2,符合题意,将结果写入result。进行回溯,将elem的元素 2 剔除。
  4. for 循环遍历第二层的第二个元素,也就是3,写入列表 elem。此时elem列表长度为 2,符合题意,将结果写入result。进行回溯,将elem的元素 3 剔除。
  5. for 循环遍历第二层的第三个元素,也就是4,写入列表 elem。此时elem列表长度为 2,符合题意,将结果写入result。进行回溯,将elem的元素 4 剔除。
  6. 第一层的第一个元素遍历完成,进行第一层第二个元素的遍历。重复步骤3-5,直到第一层集合中的元素被遍历完全。

剪枝操作

虽然回溯本质是穷举,但在某些情况下,穷举已经失去意义,比如我们想要长度为3的集合,但此时剩余元素只有2时,接下来无论如何穷举,剩余元素都无法满足要求。因此剩余无意义的操作就可以通过剪枝剔除,从而提高效率。

剪枝后的代码如下:

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> elem = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {backtracking(1, n, k);return result;}public void backtracking(int startIndex, int n, int k){if (elem.size() == k){result.add(new ArrayList<>(elem));return;}// 进行剪枝操作后for (int i = startIndex; i <= n - (k - elem.size()) + 1; i++){elem.add(i);backtracking(i + 1, n, k);elem.remove(elem.size() - 1);}}
}

此处剪枝操作体现在 for 循环的条件表达式上,其中:

  1. 已经选择的元素个数:elem.size()
  2. 还需要的元素个数:k - elem.size()
  3. 在集合中至多要从该起始位置开始遍历:n - ( k - elem.size()) + 1

Leetcode. 216 组合总和Ⅲ

文章链接:代码随想录 (programmercarl.com)

题目链接:216. 组合总和 III - 力扣(LeetCode)

通过上一题的洗礼,对于回溯法的使用有了一些眉目。

题目中有这样一段:该列表不能包含相同的组合两次,为了避免出现同一组合,所以用过的元素都不能再次出现。

将该问题抽象为树形结构,我们可以得到:

根据回溯模板和上述图片,写出如下代码:

class Solution {List<Integer> elem = new LinkedList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {backtracking(1, k, n);return result;}public void backtracking(int startIndex, int k, int n){if (elem.size() == k){int sum = 0;for (int i = 0; i < elem.size(); i++){sum += elem.get(i);}if (sum == n){result.add(new ArrayList<>(elem));return;}}/*此处也可通过剪枝操作提高效率,剪枝后:for (int i = startInex; i <= 9 - (k - elem.size()) + 1; i++)*/for (int i = startIndex; i <= 9; i++){elem.add(i);backtracking(i + 1, k, n);elem.remove(elem.size() - 1);}}
}
  • 空间复杂度:O(n * 2 ^ n)
  • 时间复杂度:O(n)

Leetcode. 17 电话号码的字母组合

文章链接:代码随想录 (programmercarl.com)

题目链接:17. 电话号码的字母组合 - 力扣(LeetCode)

本题思路:

  1. 先创建一个映射,可以将数字与对应字母列表映射起来。
  2. 遍历字符串,读取对应数字的字母列表。
  3. 分别将这些字母列表的元素进行拼接,做出最后的组合。

代码如下:

class Solution {List<String> result = new ArrayList<>();StringBuilder sb = new StringBuilder();public List<String> letterCombinations(String digits) {if (digits.isEmpty()){return result;}// 创建映射String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};backtracking(digits, map, 0);return result;}public void backtracking(String digits, String[] map, int startIndex){if (digits.length() == startIndex){result.add(sb.toString());return;}// 获取字符串中对应数字的字母列表String list = map[digits.charAt(startIndex) - '0'];// 遍历字母列表for (int i = 0; i < list.length(); i++){sb.append(list.charAt(i));// 递归到字符串中下一个数字的字母列表中backtracking(digits, map, startIndex + 1);sb.deleteCharAt(sb.length() - 1);}}
}
  • 时间复杂度:O(3 ^ n * 4 ^ m)
  • 空间复杂度:O(3 ^ n * 4 ^ m)

这篇关于代码随想录算法训练营第十九天| 回溯理论、77. 组合、216. 组合总和Ⅲ、17. 电话号码的字母组合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1143432

相关文章

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论

Vue 调用摄像头扫描条码功能实现代码

《Vue调用摄像头扫描条码功能实现代码》本文介绍了如何使用Vue.js和jsQR库来实现调用摄像头并扫描条码的功能,通过安装依赖、获取摄像头视频流、解析条码等步骤,实现了从开始扫描到停止扫描的完整流... 目录实现步骤:代码实现1. 安装依赖2. vue 页面代码功能说明注意事项以下是一个基于 Vue.js

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

使用Dify访问mysql数据库详细代码示例

《使用Dify访问mysql数据库详细代码示例》:本文主要介绍使用Dify访问mysql数据库的相关资料,并详细讲解了如何在本地搭建数据库访问服务,使用ngrok暴露到公网,并创建知识库、数据库访... 1、在本地搭建数据库访问的服务,并使用ngrok暴露到公网。#sql_tools.pyfrom