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

news/2024/3/29 4:43:02/文章来源:https://blog.csdn.net/qq_19841021/article/details/129253369

组合总和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)是求同一个集合中的组合!


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

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

相关文章

小米mix2s刷win11和android双系统

在给电脑安装系统的过程中&#xff0c;可能会因为各种原因出现windows无法安装的情况&#xff0c;我在给小米mix2s安装win11时发现出现了“计算机意外地重新启动或遇到错误&#xff0c;windows无法安装”的情况&#xff0c;下面就来教一下大家两种解决方法&#xff0c;希望可以…

【解决办法】windows防火墙出入站规则放通telnet方法

【操作方法】windows防火墙出站规则放通telnet方法一、出站规则1.新建出站规则中选择“程序”2.选择路径&#xff0c;点击“下一页”3.选择“允许连接”4.选择所有区域二、入站规则注&#xff1a;打开防火墙添加出入站规则参考【操作方法】windows防火墙添加出入站规则方法 一、…

JUC(二)

1.可重入锁–ReentrantLock原理 1.1.非公平锁的实现原理 1.1.1.加锁解锁流程 1>.先从构造器开始看,默认为非公平锁,可以在构造函数中设置参数指定公平锁 public ReentrantLock() {sync = new NonfairSync(); }public ReentrantLock

【C++】STL 模拟实现之 list

文章目录一、list 的常用接口及其使用1、list 一般接口2、list 特殊接口3、list 排序的性能分析二、list 迭代器的实现1、迭代器的分类2、list 迭代器失效问题3、list 迭代器源码分析4、list 迭代器模拟实现4.1 普通迭代器4.2 const 迭代器4.3 完整版迭代器三、list 的模拟实现…

十分钟学习nfs服务器

NFS服务器简介 NFS的使用 权限参数 简易实验配置一&#xff1a; 要求&#xff1a;客户端借用nfs服务器可以同步服务端的文件 步骤&#xff1a;服务端配置&#xff08;/var/lib/nfs日志存放目录&#xff09; 创建文件&#xff1a;&#xff08;主配置文件有可能存在&#x…

机器学习的特征归一化Normalization

为什么需要做归一化&#xff1f; 为了消除数据特征之间的量纲影响&#xff0c;就需要对特征进行归一化处理&#xff0c;使得不同指标之间具有可比性。对特征归一化可以将所有特征都统一到一个大致相同的数值区间内。 为了后⾯数据处理的⽅便&#xff0c;归⼀化可以避免⼀些不…

spring boot 配合element ui vue实现表格的批量删除(前后端详细教学,简单易懂,有手就行)

目录 一.前言&#xff1a; 二. 前端代码&#xff1a; 2.1.element ui组件代码 2.2删除按钮 2.3.data 2.4.methods 三.后端代码&#xff1a; 一.前言&#xff1a; 研究了其他人的博客&#xff0c;找到了一篇有含金量的&#xff0c;进行了部分改写实现前后端分离&#xff0…

频率信号转电压或电流信号隔离变送器0-1KHz /0-5KHz /0-10KHz转0-2.5V/0-5V/0-20mA

主要特性:>> 精度等级&#xff1a;0.2级>> 全量程内极高的线性度&#xff08;非线性度<0.1%&#xff09; >> 辅助电源/信号输入/信号输出&#xff1a; 2500VDC 三隔离>> 辅助电源&#xff1a;5VDC&#xff0c;12VDC&#xff0c;24VDC等单电源供电&g…

SpringBoot项目启动成功后打印Banner

SpringBoot项目启动成功后打印Banner 背景 可能有些同学看到就觉得&#xff0c;这个都要发文章&#xff1f;这不是整个banner.txt再配置一下spring.banner.locationclasspath:banner.txt就行了吗&#xff1f;还真不是&#xff0c;这个是在项目启动时&#xff0c;先打印的bann…

Big_Data

Linux 计算机硬件软件体系 冯 诺依曼体系结构 计算机处理的数据和指令一律用二进制数表示 顺序执行程序 计算机硬件由运算器、控制器、存储器、输入设备和输出设备五大部分组成计算机硬件组成 输入设备输入设备用来将人们熟悉的信息形式转换为机器能够识别的信息形式常见的…

人工智能写的十段代码,九个通过测试了

“抢走你工作的不会是 AI &#xff0c;而是先掌握 AI 能力的人” 编程测试 1. 我想用golang实现二叉树前序&#xff0c;请你帮我写一下代码。 // 定义二叉树节点 type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode }// 前序遍历 func PreOrderTraversal(root *Tre…

Nvidia jetson nano硬件架构

资料来源 官方文档中心 https://developer.nvidia.com/embedded/downloads -> 选jetson -> Jetson Nano Product Design Guide //产品设计指导(入口) //-> 1.1 References 列出了相关的文档 -> Jetson Nano Developer Kit Carrier Board Specification //板子标注…

torchserve安装、模型的部署与测试(基于docker)

问题描述 pytorch 一直很受大家的欢迎&#xff0c;但是作为一个深度模型&#xff0c;与外界复杂的业务需求交互其实是一件比较麻烦的事情&#xff0c;这里 torchserve 提供一个基于 TCP 的交互方法&#xff0c;算法模型部署后&#xff0c;用户可以通过提交 post 请求&#xff…

Linux服务器磁盘分区、挂载、卸载及报错处理

整体操作是&#xff1a;先对磁盘进行格式化&#xff0c;格式化后挂载到需要的挂载点&#xff0c;最后添加分区启动表&#xff0c;以便下次系统启动时自动挂载。一、linux分区1、Linux来说wulun有几个分区&#xff0c;分给哪一目录使用&#xff0c;他归根结底只有一个根目录&…

549、RocketMQ详细入门教程系列 -【消息队列之 RocketMQ(三)】 2023.02.28

目录一、Spring 整合 RocketMQ1.1 消息生产者1.2 消息消费者1.3 Spring 配置文件1.4 运行实例程序二、参考链接一、Spring 整合 RocketMQ 不同于 RabbitMQ、ActiveMQ、Kafka 等消息中间件&#xff0c;Spring 社区已经通过多种方式提供了对这些中间件产品集成&#xff0c;例如通…

Linux | 2. 用户管理

如有错误&#xff0c;恳请指出。 1. 设置文件权限 权限设置如下&#xff1a; root表示文件所有者&#xff0c;stud1表示文件所属组。其他用户无法访问。更改指令是chown。 更改目录文件所属组&#xff1a;chown .lab lossfound/更改目录文件所有者&#xff1a;chown lab loss…

html实现浪漫的爱情日记(附源码)

文章目录1.设计来源1.1 主界面1.2 遇见1.3 相熟1.4 相知1.5 相念2.效果和源码2.1 动态效果2.2 源代码2.3 代码结构源码下载更多爱情表白源码作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/article/details/129264757 html实现浪漫的爱情…

Javaweb复习之HTTPTomcatServelet

1.Web概述 1.1 Web和JavaWeb的概念 Web是全球广域网&#xff0c;也称为万维网(www)&#xff0c;能够通过浏览器访问的网站。 JavaWeb就是用Java技术来解决相关web互联网领域的技术栈 1.2 JavaWeb技术栈 B/S 架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器 架构模…

Linux: malloc()的指向指针发生指向偏移后,释放前需要将指针指向复原。

Linux: malloc()的指向指针发生指向偏移后&#xff0c;释放前需要将指针指向复原。 #include <stdlib.h> #include <stdio.h> #include <unistd.h> #include <sys/types.h> #include <sys/stat.h> #include <string.h> #include <time…

MIT:只需一层RF传感器,就能为AR头显赋予“X光”穿透视力

近年来&#xff0c;AR在仓库、工厂等场景得到应用&#xff0c;比如GlobalFoundries、亚马逊、菜鸟裹裹就使用摄像头扫描定位货品&#xff0c;并使用AR来导航和标记。目前&#xff0c;这种方案主要基于视觉算法&#xff0c;因此仅能定位视线范围内的目标。然而&#xff0c;在一些…