当前位置: 首页 > news >正文

【代码随想录训练营】【Day25】第七章|回溯算法 |216.组合总和III|17.电话号码的字母组合

组合总和III

题目详细:LeetCode.216

做过上一题组合后,再来写这道题就显得得心应手了,通过理解回溯算法的模版,也总结出了算法中的一些特点:

  • 回溯算法与递归算法类似,同样需要参数、结束条件和主体逻辑
  • 回溯算法我们可以将它看作是一棵二叉树,树丛根节点到叶子节点的一条路径,就是一个结果:
    • 结束条件就相当于遇到了叶子节点,保存当前路径,返回上一层
    • for循环相当于是一个选择结构,因为每个数字最多使用一次
    • 同时for循环的次数也决定了树的宽度
    • 递归的次数就相当于是for循环的嵌套次数,决定了树的深度
    • 每一次递归结束后,都要对结果进行回溯,相当于从叶子节点退回上一个节点,然后继续循环,进入下一条路径,寻找另一个结果
  • 从上述回溯过程,我们也可以发现,回溯法类似对树进行深度优先遍历,找出所有的路径,保存符合预期结果的路径,所以本质上也是一种暴力法。

Java解法(回溯,递归):

class Solution {List<List<Integer>> ans = new ArrayList<>();Deque<Integer> path = new ArrayDeque<>();public void backtracking(int k, int n, int sum, int startNum){// 结束条件,叶子节点if(path.size() == k && sum == n){this.ans.add(new ArrayList<>(path));return;}// for循环,选择节点for(int i = startNum; i <= 9; i++){this.path.offer(i);sum += i;// 递归,深度优先遍历backtracking(k, n, sum, i + 1);// 回溯,返回叶子节点的上一节点this.path.removeLast();sum -= i;// 继续循环,进入其他节点,寻找符合结果的路径}}public List<List<Integer>> combinationSum3(int k, int n) {this.backtracking(k, n, 0, 1);return this.ans;}
}

电话号码的字母组合

题目详细:LeetCode.17

这道题我一开始的思路和前两道练习搞混了,琢磨了一个钟之后,看了题解才恍然大悟,原来这道题的不同点是在于在不同集合中找组合。

详细的解释可以看题解:《代码随想录—电话号码的字母组合》

Java解法(递归, 回溯):

class Solution {public List<String> ans = new ArrayList<>();public StringBuffer path = new StringBuffer();public char[][] mapper_all = {{'a','b','c'},{'d','e','f'}, {'g','h','i'}, {'j','k','l'}, {'m','n','o'}, {'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};public List<String> letterCombinations(String digits) {this.backtracking(digits, 0);return this.ans;}public void backtracking(String digits, int startNum){if(path.length() == digits.length()){if(path.length() != 0){ans.add(path.toString());}return;}char[] mapper = mapper_all[digits.charAt(startNum) - '0' - 2];for(int i = 0; i < mapper.length; i++){this.path.append(mapper[i]);// 递归,注意startNum + 1,表示要处理下一个数字了backtracking(digits, startNum + 1);this.path.deleteCharAt(path.length() - 1);}}
}

注意这里for循环,可不像前两天的练习(LeetCode.77和.216)中从startIndex开始遍历的。
因为本题每一个数字代表的是不同集合,也就是求不同集合之间的组合,而之前的练习(LeetCode.77和.216)是求同一个集合中的组合!


相关文章:

【代码随想录训练营】【Day25】第七章|回溯算法 |216.组合总和III|17.电话号码的字母组合

组合总和III 题目详细&#xff1a;LeetCode.216 做过上一题组合后&#xff0c;再来写这道题就显得得心应手了&#xff0c;通过理解回溯算法的模版&#xff0c;也总结出了算法中的一些特点&#xff1a; 回溯算法与递归算法类似&#xff0c;同样需要参数、结束条件和主体逻辑回…...

docker使用

https://blog.csdn.net/u012563853/article/details/125295985http://www.ppmy.cn/news/11249.html启动 docker服务并设置开机自动启动dockersudo systemctl start docker sudo systemctl enable dockerdocker 常见启动失败问题:https://blog.csdn.net/zhulianseu/article/deta…...

手把手docker registry配置登录名/密码

我们的Docker私有仓库Registry服务只有加了认证机制之后我们的Registry服务才会更加的安全可靠。赶快跟随以下步骤来增加认证机制吧。 创建docker registry工作目录 mkdir -p /data/docker.registry 创建将保存凭据的文件夹 mkdir -p /data/docker.registry/etc/registry/auth…...

一步打通多渠道服务场景 中电金信源启移动开发平台MADP功能“上新”

日前&#xff0c;中电金信源启移动开发平台MADP功能迭代升级&#xff0c;“上新”源启小程序开发平台。定位“为金融业定制”的移动PaaS平台&#xff0c;源启小程序开发平台为银行、互联网金融、保险、证券客户提供一站式小程序的开发、运营、营销全生命周期管理技术支撑&#…...

Kubernetes06:Controller (Deployment无状态应用)

Kubernetes06:Controller 1、什么是controller 管理和运行容器的对象&#xff0c;是一个物理概念 在集群上管理和运行容器的对象 2、Pod和Controller之间的关系 Pod是通过controller来实现应用的运维 比如伸缩、滚动升级等等操作Pod和Controller之间通过 label 标签建立关系…...

低代码开发平台选型必看指南

低代码开发是近年来逐渐兴起的一种新型软件开发方式。它通过封装常见的软件开发流程和代码&#xff0c;使得非专业的开发者也能够轻松创建复杂的应用程序。这种开发方式已经受到了许多企业的青睐&#xff0c;成为提高生产效率、降低开发成本的一种有效途径。 低代码开发的核心…...

OVN:ovn20.03.1/ovs2.13.0编译rpm过程

操作系统openeuler22.0&#xff0c;x86架构分别下载ovn和ovs的源码https://github.com/openvswitch/ovs/tree/v2.13.0https://github.com/ovn-org/ovn/tree/v20.03.1安装必要工具&#xff1a;yum install -y unzip tar make autoconf automake libtool rpm-build gcc libuuid-d…...

Shell管道

一、管道是什么 英文是pipe。 把一个命令的标准输出作为下一个命令的标准输入&#xff0c;以这种方式连接的两个或者多个命令就形成了管道 使用竖线|连接多个命令&#xff0c;称为管道符。 语法格式如下&#xff1a; command1 | command2 [ | commandN... ] command1的标准…...

Zynq UltraScale系列使用MIPI CSI-2 RX Subsystem 解码MIPI视频PD输出 提供2套工程源码和技术支持

目录1、前言2、设计思路和架构3、vivado工程详解4、上板调试验证5、福利&#xff1a;工程代码的获取1、前言 本设计采用OV5640摄像头MIPI模式作为输入&#xff0c;分辨率为1280x72060Hz&#xff0c;MIPI解码方案采用Xilinx官方提供的MIPI CSI-2 RX Subsystem IP解码MIPI视频&a…...

C++:详解C++11 线程休眠函数

休眠函数简介1: 让线程休眠一段时间1.1&#xff1a;std::chrono 的时钟 clock简介 C11 之前并未提供专门的休眠函数&#xff0c;C语言的 sleep、usleep函数其实是系统提供的函数&#xff0c;不同的系统函数的功能还要些差异。 在Windows系统中&#xff0c;sleep的参数是毫秒 …...

TryHackMe-The Great Escape(Docker)

The Great Escape 我们的开发人员创建了一个很棒的新网站。你能冲出沙盒吗&#xff1f; 端口扫描 循例 nmap Web信息收集 robots.txt: /exif-util是文件上传点&#xff0c;但是绕过之后貌似没啥用 在robots.txt当中披露了可能存在.bak.txt&#xff0c;现在我们已知的文件就是…...

这么强才给我28k,我头都不回,转身拿下40k~

时间真的过得很快&#xff0c;眨眼就从校园刚出来的帅气小伙变成了油腻大叔&#xff0c;给各位刚入道的测试朋友一点小建议&#xff0c;希望你们直通罗马吧&#xff01; 如何选择自己合适的方向 关于选择测试管理&#xff1a; 第一&#xff0c;你一定不会是一个喜欢技术&…...

【Python学习笔记】第二十一节 Python Lambda 函数

Python 提供了非常多的库和内置函数。有不同的方法可以执行相同的任务&#xff0c;而在 Python 中&#xff0c;有个万能之王函数&#xff1a;lambda 函数&#xff0c;它以不同的方式在任何地方使用。一、Lambda 函数简介在 Python 中&#xff0c;函数可以接受一个或多个位置参数…...

Nginx学习整理

Nginx学习第一章 Nginx概述1.1、Nginx概述1.2、Nginx官网1.3、Nginx用处第二章 Nginx单实例安装2.1、环境说明2.2、安装依赖2.3、Nginx下载2.4、Nginx解压2.5、Nginx安装2.6、Nginx命令2.7、开放防火墙2.8、启动后效果第三章 Nginx正向代理、反向代理3.1、概述3.2、反向代理配置…...

阿里面试之Hr面,这个套路把我坑惨了......

作为技术类的测试工程师面试&#xff0c;往往要经过多次面试才能拿到心仪的offer&#xff0c;这里面有技术一面、二面…&#xff0c;甚至总监面等&#xff0c;还有一个必不可少的就是HR面&#xff0c;一般HR会出现在你面试的最前面和最后面&#xff0c;前面是了解你的基本情况&…...

域基础和基本环境搭建

1.1 名词解释 域和工作组的区别&#xff1a; 工作组中所有的计算机都是对等的&#xff0c;也就是没有服务器和客户机的之分&#xff0c;所以工作组并不存在真正的集中管理作用&#xff1b;域是一个有安全边界的计算机集合&#xff0c;安全边界指的是一个域中的用户无法访问到另…...

Java Map集合体系(HashMap、LinkedHashMap、TreeMap、集合嵌套)

目录Map集合体系一、Map集合的概述二、Map集合体系特点三、Map集合常用API四、Map集合的遍历4.1 Map集合的遍历方式一&#xff1a;键找值4.2 Map集合的遍历方式二&#xff1a;键值对4.3 Map集合的遍历方式三&#xff1a;lambda表达式五、Map集合案例-统计投票人数六、Map集合的…...

使用邮箱验证实现登录功能(发送邮件,redis)

目录 概述 前端搭建 后端搭建 生成验证码-存入redis&#xff08;主要过程代码&#xff09; 发送邮件&#xff08;主要过程代码&#xff09; 登录验证-取出redis中数据进行验证&#xff08;主要代码&#xff09; 完整代码一-LoginController 完整代码二-LoginService 完…...

【Linux】网卡的7种bond模式

网卡的7种bond模式 一、bond模式 Mode0(balance-rr) 表示负载分担round-robin&#xff0c;和交换机的聚合强制不协商的方式配合 Mode1(active-backup) 表示主备模式&#xff0c;只有一块网卡是active,另外一块是备的standby&#xff0c;这时如果交换机配的是捆绑&#xff0c…...

AQS抽象队列同步器

aqs 抽象队列同步器&#xff0c;内部存储了一个valitail修饰的status 和内部类node &#xff0c;来实现对共享变量并发同步队列机制,以reentrantLock为例&#xff0c;lock底层实际上调用的是sync的lock&#xff0c;会调用cas对status的状态进行修改&#xff0c;来确定是否获得锁…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...