代码随想录|Day22|回溯02|216.组合总和III、17.电话号码的字母组合

216.组合总和III

本题思路和 77. 组合 类似,在此基础上多了一个和为 n 的判断。

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:

        def backtrack(start, path, currentSum):
            # 递归终止条件:到达叶子节点
            # 如果和满足条件,则收集后终止,否则直接终止
            if len(path) == k:
                if currentSum == n:
                    result.append(path[:])
                return
            
            for num in range(start, 9 + 1):
                currentSum += num
                path.append(num)
                backtrack(num + 1, path, currentSum)
                path.pop()
                currentSum -= num

        result = []
        backtrack(start = 1, path = [], currentSum = 0)
        return result

 本题有两个地方可以剪枝:

  • 当前组合元素的 和 超过要求
  • 当前组合元素的 数量 超过要求

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:

        def backtrack(start, path, currentSum):
            # 剪枝1: 和超过要求
            if currentSum > n:
                return

            if len(path) == k:
                if currentSum == n:
                    result.append(path[:])
                return
            # 剪枝2: 组合元素数量超过要求
            for num in range(start, 9 - (k - len(path)) + 1 + 1):
                currentSum += num
                path.append(num)
                backtrack(num + 1, path, currentSum)
                path.pop()
                currentSum -= num

        result = []
        backtrack(start = 1, path = [], currentSum = 0)
        return result

17.电话号码的字母组合

本题相当于从每个数字对应的字母中构建结果,我们需要借助一个 index 来跟踪数字。由于每个数字对应的字母都没有重复,因此每个结果都符合题意,不需要剪枝。

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        phoneMap = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        
        def backtrack(index, path):
            # 递归结束条件
            # 当组合的长度等于输入数字的长度,收集结果
            if len(path) == len(digits):
                result.append(''.join(path))
                return
            # 获取当前数字所对应的所有可能字母
            possible_letters = phoneMap[digits[index]]
            # 遍历这些字母,递归构造剩余的组合
            for letter in possible_letters:
                path.append(letter)
                backtrack(index + 1, path)
                path.pop()
        
        result = []
        backtrack(index = 0, path = [])
        return result

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/462341.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

替代 VMware ,为什么需要重新考虑您的存储?

国内大部分 VMware 用户使用的是 vSphere,很少使用 vSAN,这使得在国内,企业实施 VMware 替代时,考虑最多的因素很可能是存储。企业级块存储产品 XEBS,作为业界最开放的中立的专业软件定义存储(SDS&#xff…

数字电子技术实验(四)

单选题 1.组合逻辑电路中产生竞争冒险的原因是? A. 电路没有最简化 。 B. 时延 。 C. 电路有多个输出。 D. 逻辑门的类型不同。 答案:B 评语:10分 单选题 2.下列表达式不存在竞争冒险的有? 答案:A 评语&#x…

进入jupyter notebook发现没有虚拟环境,最简单实用的解决办法!

jupyter notebook 1. 进入jupyter notebook发现没有虚拟环境2.解决办法2.1 检查是否有库ipykernel,我发现我没有2.2 开始安装ipykernel2.3 将虚拟环境写入 总结 1. 进入jupyter notebook发现没有虚拟环境 2.解决办法 2.1 检查是否有库ipykernel,我发现我…

使用R语言计算并绘制流体力学中的二维泊肃叶流

平行平板间的二维流动 在流体力学中,当考虑两平行平板间的二维、定常、不可压缩流动,并且只存在沿x方向的流动速度,我们可以从N-S方程推导出方向的动量方程。对于给定的方程: (式1) 其中,是压力,是动力粘度…

一瓶5.86万,听花酒什么来头?

听花酒,到底什么来头? 宣称有提升免疫力、改善睡眠、保障男性功能、调节生理紊乱、抗衰老等功效的听花酒,被315晚会曝光了。 相关话题词随即冲上了热搜。之后,售价最高达58600元的听花酒被京东、拼多多、淘宝等电商平台火速下架…

react中JSX的详解

目录 JSX的本质及其与JavaScript的关系探究 一、JSX的本质 二、JSX与JavaScript的关系 三、为什么要使用JSX 四、不使用JSX的后果 五、JSX背后的功能模块 JSX的本质及其与JavaScript的关系探究 在React开发中,JSX是一个不可或缺的部分。那么,JSX的…

信息系统项目管理(第四版)(高级项目管理)考试重点整理 第14章 项目沟通管理(四)

博主2023年11月通过了信息系统项目管理的考试,考试过程中发现考试的内容全部是教材中的内容,非常符合我学习的思路,因此博主想通过该平台把自己学习过程中的经验和教材博主认为重要的知识点分享给大家,希望更多的人能够通过考试&a…

【编程项目开源】拼图游戏(鸿蒙版)

目标 做个拼图游戏 效果 开发工具 下载DevEco Studio 工程截图 开源地址 https://gitee.com/lblbc/puzzle/tree/master/puzzle_hongmeng_arkUI 关于 厦门大学计算机专业|华为八年高级工程师 专注《零基础学编程系列》 http://lblbc.cn/blog 包含:Java | 安卓…

蓝桥杯刷题(九)

1.三国游戏 代码 #输入数据 nint(input()) Xlilist(map(int,input().split())) Ylilist(map(int,input().split())) Zlilist(map(int,input().split())) #分别计算X-Y-Z/Y-Z-X/Z-X-Y并排序 newXli sorted([Xli[i] - Yli[i] - Zli[i] for i in range(n)],reverseTrue) newYli …

图像去噪--(1)

系列文章目录 文章目录 系列文章目录前言一、图像噪声1.1 噪声定义1.2 基本特征 二、按照噪声概率分布分类1.高斯噪声2.泊松噪声 三、去噪算法3.1 线性滤波3.1.1 高斯滤波3.1.2 均值滤波 3.2 非线性滤波3.2.1 中值滤波3.2.2 双边滤波 四、深度学习总结 前言 一、图像噪声 1.1 …

如何使用Python进行数据可视化:Matplotlib和Seaborn指南【第123篇—Matplotlib和Seaborn指南】

如何使用Python进行数据可视化:Matplotlib和Seaborn指南 数据可视化是数据科学和分析中不可或缺的一部分,而Python中的Matplotlib和Seaborn库为用户提供了强大的工具来创建各种可视化图表。本文将介绍如何使用这两个库进行数据可视化,并提供…

(每日持续更新)jdk api之StringBufferInputStream基础、应用、实战

博主18年的互联网软件开发经验,从一名程序员小白逐步成为了一名架构师,我想通过平台将经验分享给大家,因此博主每天会在各个大牛网站点赞量超高的博客等寻找该技术栈的资料结合自己的经验,晚上进行用心精简、整理、总结、定稿&…

前端学习笔记 | WebAPIs(DOM+BOM)

一、作用和分类 1、基本概念 作用:使用JS去操作HTML和浏览器 分类:DOM(文档对象模型)和BOM(浏览器对象模型) html的标签JS的DOM对象 2、获取DOM对象-参数必须加引号 (1)选择匹配的第…

使用 OpenAI 的 Embedding模型 构建知识向量库并进行相似搜索

OpenAI的embedding模型的使用 首先第一篇文章中探讨和使用了ChatGPT4的API-Key实现基础的多轮对话和流式输出,完成了对GPT-API的一个初探索,那第二步打算使用OpenAI的embedding模型来构建一个知识向量库,其实知识向量库本质上就是一个包含着一…

电脑自带dll修复在哪里打开呢?马上教会你

由于各种原因,电脑可能会出现一些问题,其中之一就是dll文件丢失。Dll文件是动态链接库文件,它们包含了许多程序运行所需的函数和资源。当这些文件丢失或损坏时,可能会导致程序无法正常运行或出现错误提示。本文将介绍电脑dll文件丢…

springboot蛋糕订购小程序的设计与实现

摘 要 相比于以前的传统手工管理方式,智能化的管理方式可以大幅降低商家的运营人员成本,实现了蛋糕订购的标准化、制度化、程序化的管理,有效地防止了蛋糕订购的随意管理,提高了信息的处理速度和精确度,能够及时、准确…

工作总结!日志打印的11条建议

前言 大家好,我是 JavaPub。日志是我们定位问题的得力助手,也是我们团队间协作沟通(甩锅)、明确责任归属(撕B)的利器。没有日志的程序运行起来就如同脱缰的野🐎。打印日志非常重要。今天我们来…

Linux内存管理--系列文章貮

接上文,用户态写完,本章写内核态内存空间。 3.2内核态内存 大家会发现用户态空间不管32还是64位,这种内存分布是相差不大的。是因为使用虚拟内存的系统,会让应用程序感到和别的程序是相互独立的,互不干扰&#xff0c…

mysql索引 (索引的忧缺点 ,联合索引)

索引的忧缺点 优点 (增加读操作效率,排序成本) 1 查询效率高 2 降低排序成本,索引对应的字段 就已经 自动排序,因为索引本身就是一种排好序的数据结构 缺点(降低写操作效率,占用空间&#xf…

【Unity】读取Json的三种方法(JsonUtility,LitJson,Newtonsoft)

介绍 在Unity开发过程中,Json是比较常用的一种数据存储文本,尤其是在和第三方交互中,基本都是json格式。 先给出一个Json示例,我们来看看是如何解析的。 {"Player": [{"id": 1001,"name": "…