代码随想录算法训练营第22、23天|回溯理论基础、组合问题、216.组合总和III 17.电话号码的字母组合

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

文章目录

  • 前言
  • 回溯理论基础
  • 77、组合问题
    • 思路
    • 方法一 没有剪枝
    • 方法二 剪枝
  • 216.组合总和III
    • 思路
    • 方法一 没有剪枝
    • 方法二 有剪枝
  • 17.电话号码的字母组合
    • 思路
    • 方法一
    • 方法一2 隐藏回溯
    • 方法一3 不用字符串而是列表来处理
  • 总结


前言

回溯理论基础

回溯可以用于解决一些经典的问题,可以看到理论框架,
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
回溯的框架
在这里插入图片描述

77、组合问题

在这里插入图片描述

思路

回溯算法引入:C5-2这样的组合问题可以用两层for循环来实现,C5-3就是再套一层for循环,如果是C100-50呢?50层for循环。所以需要使用回溯算法;

  • 核心在于:递归几次就是for循环几次
  • 回溯算法就是使得这样的递归可以得到想要的结果:💖💜即,for给每一个元素遍历的时候,每一个元素都是需要递归的,所以进入了第一个元素之后出来需要回溯,pop掉第一个元素,然后再进入第二个元素; 所以回溯是紧跟在递归的后面,也是只在单层逻辑里面

按照老师的解题思路
首先看一下构建的树形结构
在这里插入图片描述
每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围。
图中可以发现n相当于树的宽度,k相当于树的深度。

那么如何在这个树上遍历,然后收集到我们要的结果集呢?

图中每次搜索到了叶子节点,我们就找到了一个结果

相当于只需要把达到叶子节点的结果收集起来,就可以求得 n个数中k个数的组合集合。
???有毒吧突然卡了写不了
回溯三部曲【看教程】
传入传出:定义两个全局变量,一个用来存放符合条件单一结果,一个用来存放符合条件结果的集合。传入startIndex来记录下一层递归,搜索的起始位置。

终止条件:path记录的长度等于k了

其中单层逻辑:
for循环每次从startIndex开始遍历,然后用path保存取到的节点i。
在这里插入图片描述

方法一 没有剪枝

下面是我自己写的代码
💦💘同样的错误:结果传入的时候必须是浅复制之后的self.result.append(self.path[:]),而不是self.result.append(self.path),因为python是指向变量空间,self.path最后为空,这会导致结果为空

class Solution(object):def __init__(self):self.path = []self.result = []def backtrack(self,n,k,startindex):#终止条件if len(self.path) == k:self.result.append(self.path[:])#必须要是复制切片return#单层递归逻辑,也就是处理一个节点for i  in range(startindex,n+1):print(i)self.path.append(i)print(self.path)self.backtrack(n,k,i+1)self.path.pop()return def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""self.backtrack(n,k,1)return self.result

方法二 剪枝

老师讲解了一个非常常见的剪枝思路:单层逻辑中修改for遍历的范围在这里插入图片描述
具体思路:如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了,那么就没有必要搜索了
具体实现:
在这里插入图片描述
注意:range是不包括右边界的,所以需要再+1

class Solution(object):def __init__(self):self.path = []self.result = []def backtrack(self,n,k,startindex):#终止条件if len(self.path) == k:self.result.append(self.path[:])#必须要是复制切片return#单层递归逻辑,也就是处理一个节点for i  in range(startindex,n-(k-len(self.path))+2):print(i)self.path.append(i)print(self.path)self.backtrack(n,k,i+1)self.path.pop()return def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""self.backtrack(n,k,1)return self.result

216.组合总和III

在这里插入图片描述

思路

方法一 没有剪枝

这是没听讲解直接写的,确实有了前面的基础就很简答了。

class Solution(object):def __init__(self):self.result = []self.path = []self.count = 0def backtrace(self,target,k,startindex):if len(self.path) == k:if self.count == target:self.result.append(self.path[:])returnfor i in range(startindex,10):self.path.append(i)self.count += iself.backtrace(target,k,i+1)self.count -= iself.path.pop()def combinationSum3(self, k, n):""":type k: int:type n: int:rtype: List[List[int]]"""self.backtrace(n,k,1)return self.result

方法二 有剪枝

当然,剪枝的思路有两个

  1. size角度:和之前一样,就是改变for循环语句
    for i in range(startindex,10-(k-len(self.path))+1):
  2. count的角度,如果当前的sum已经大于目标sum了,就返回。
class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:result = []  # 存放结果集self.backtracking(n, k, 0, 1, [], result)return resultdef backtracking(self, targetSum, k, currentSum, startIndex, path, result):if currentSum > targetSum:  # 剪枝操作return  # 如果path的长度等于k但currentSum不等于targetSum,则直接返回if len(path) == k:if currentSum == targetSum:result.append(path[:])returnfor i in range(startIndex, 9 - (k - len(path)) + 2):  # 剪枝currentSum += i  # 处理path.append(i)  # 处理self.backtracking(targetSum, k, currentSum, i + 1, path, result)  # 注意i+1调整startIndexcurrentSum -= i  # 回溯path.pop()  # 回溯

17.电话号码的字母组合

在这里插入图片描述

思路

本题思路依然和之前的差不多;不多要注意细节的传入参数,我自己就没有想出来
回溯三部曲

  1. 传入传出参数:传入的应该是digits和指向digits的index(表示是digits中第几个数)
  2. 终止条件:如果index大于digit-size,说明到头了
  3. 单层递归逻辑:首先要取index指向的数字,并找到对应的字符集(手机键盘的字符集)。

💛本题注意点和小细节

  • 💘使用map来表征数字和对应的字母;但是进一步可以用list来创建哈希表,其下标就是数字,元素值就是数字对应的字母(所以0和1是空的)
  • digits[index]得到的结果是“2”这样的,要记得转换为数字类型;在c++中处理的方法是int digit = digits[index] - ‘0’
  • 对于string类型的处理:python是string类型直接+就行,string类型删除的话使用[:-1]的方式;下面方法一3使用的是列表最后转为字符串,result.append(‘’.join(path))
  • 在这里插入图片描述在这里插入图片描述

方法一

下面是我自己写 的

class Solution(object):def __init__(self):self.map_ = [" ",#0" ",#1"abc",#2"def",#3"ghi",#4"jkl",#5"mno",#6"pqrs",#7"tuv",#8"wxyz",#9]self.result = []self.s = ""def backtrace(self,digits,index_):if index_ == len(digits):self.result.append(self.s)returnfor i in self.map_[int(digits[index_])]:self.s += iself.backtrace(digits,index_+1)self.s = self.s[:-1]def letterCombinations(self, digits):""":type digits: str:rtype: List[str]"""if len(digits) == 0:return self.resultself.backtrace(digits,0)return self.result

方法一2 隐藏回溯

具体方法:self.s不再设为全局变量,而是变成参数每次传进去;
回溯的是时候变成self.backtrace(digits,index_+1,s+letter);这样s就是没有变过的;

class Solution:def __init__(self):self.letterMap = ["",     # 0"",     # 1"abc",  # 2"def",  # 3"ghi",  # 4"jkl",  # 5"mno",  # 6"pqrs", # 7"tuv",  # 8"wxyz"  # 9]self.result = []def getCombinations(self, digits, index, s):if index == len(digits):self.result.append(s)returndigit = int(digits[index])letters = self.letterMap[digit]for letter in letters:self.getCombinations(digits, index + 1, s + letter)def letterCombinations(self, digits):if len(digits) == 0:return self.resultself.getCombinations(digits, 0, "")return self.result

方法一3 不用字符串而是列表来处理

    def getCombinations(self, digits, index, path, result):if index == len(digits):result.append(''.join(path))returndigit = int(digits[index])letters = self.letterMap[digit]for letter in letters:path.append(letter)self.getCombinations(digits, index + 1, path, result)path.pop()def letterCombinations(self, digits):result = []if len(digits) == 0:return resultself.getCombinations(digits, 0, [], result)return result

总结

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



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

相关文章

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》:本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用?循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1