代码随想录算法训练营第十九天| 回溯理论、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将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当