郑州网站制作/小璇seo优化网站
回溯章节理论基础:
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
216.组合总和III
题目链接:https://leetcode.cn/problems/combination-sum-iii/
思路:
本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。
对于昨天做的77.组合而言,多了一个限制,本题是要找到和为n的k个数的组合,而整个集合已经是固定的了[1…9],本题k相当于树的深度,9(因为整个集合就是9个数)就是树的宽度。
例如 k = 2,n = 4的话,就是在集合[1,2,3,4,5,6,7,8,9]中求 k(个数) = 2, n(和) = 4的组合。
选取过程如图:
因为这道题的话,多了一个要求和,所以传入的参数里面多了一个sum。
终止条件就是,如果path.size() 和 k相等了,就终止。
如果此时path里收集到的元素和(sum) 和targetSum(就是题目描述的n)相同了,就用result收集当前的结果。
同时,别忘了处理过程 和 回溯过程是一一对应的,处理有加,回溯就要有减!
剪枝:
(1)如果已选元素总和如果已经大于n(图中数值为4)了,那么往后遍历就没有意义了,直接剪掉。
(2)for循环的范围也可以剪枝,i <= 9 - (k - path.size()) + 1就可以了。k - path.size() 就代表剩余还要选多少个数,比如我们这里k=5,那么取7,取8都没有意义了,因为这个时候往后再取,也取不到5个数。
class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> paths = new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {backtracking(n,k,1,0);return result;}public void backtracking(int n, int k, int startIndex, int sum){if(sum > n) return ;if(paths.size() == k){if(sum == n)result.add(new ArrayList<>(paths));return ;}// 对取k个数,这里也进行剪枝for(int i=startIndex; i <= 9-(k-paths.size()) + 1; i++){paths.add(i);sum = sum + i;backtracking(n, k, i+1, sum);sum = sum - i;paths.removeLast();}}
}
时间复杂度: O(n * 2^n)
空间复杂度: O(n)
17.电话号码的字母组合
首先是数字和字母如何映射的问题,这里可以使用map或者定义一个二维数组,例如:string letterMap[10],来做映射。
遍历的深度,就是输入"23"的长度,而叶子节点就是我们要收集的结果,输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。
首先需要一个字符串s来收集叶子节点的结果,然后用一个字符串数组result保存起来,这两个变量定义为全局。
再来看参数,参数指定是有题目中给的string digits,然后还要有一个参数就是int型的index。这个参数可不是startIndex了,而是记录遍历第几个数字了,就是用来遍历digits的(题目中给出数字字符串),同时index也表示树的深度。
例如输入用例"23",两个数字,那么根节点往下递归两层就可以了,叶子节点就是要收集的结果集。
那么终止条件就是如果index 等于 输入的数字个数(digits.size)了。然后收集结果,结束本层递归。
class Solution {String[] letterMap = {"", // 0"", // 1"abc", // 2"def","ghi","jkl","mno","pqrs","tuv","wxyz"};List<String> result = new ArrayList<>(); StringBuilder s = new StringBuilder(); // 每次迭代的字符串拼接public List<String> letterCombinations(String digits) {// 特殊情况:用例2 输入:digits = "" 输出:[]if(digits == null || digits.length() == 0)return result;backtracking(digits,0);return result;}public void backtracking(String digits, int index){if(index ==digits.length()){result.add(s.toString());return ;}int digit = digits.charAt(index) - '0'; // 类型转换成intString letters = letterMap[digit]; // 数字对应的字母组合for(int i=0;i<letters.length();i++){s.append(letters.charAt(i));backtracking(digits,index+1);s.deleteCharAt(s.length() - 1);}}
}
相关文章:

代码随想录算法训练营第25天 | 216.组合总和III ,17.电话号码的字母组合
回溯章节理论基础: https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 216.组合总和III 题目链接:https://leetcode.cn/problems/combination-sum-iii/ 思路: 本题就是在[1,2,3,4,5,6,7,…...

Rust 第一个rust程序Hello Rust️
文章目录 前言一、vscode 安装rust相关插件二、Cargo New三、vscode调试rustLLDB 前言 Rust学习系列。今天就让我们掌握第一个rust程序。Hello Rust 🦀️。 在上一篇文章我们在macOS成功安装了rust。 一、vscode 安装rust相关插件 以下是一些常用的 Rust 开发插件…...

高斯消去法 | LU分解 | PA=LU分解(MatLab)
一、问题描述 利用高斯消去法,LU 分解及PALU 分解求解非线性方程组。 二、实验目的 掌握高斯消去法、LU 分解、PALU 分解的算法原理;编写代码实现利用高斯消去法、LU 分解、PALU 分解来求解线性方程组。 三、实验内容及要求 1. 利用顺序高斯消去法求…...

Linux笔记之expect和bash脚本监听输出并在匹配到指定字符串时发送中断信号
Linux笔记之expect和bash脚本监听输出并在匹配到指定字符串时发送中断信号 code review! 文章目录 Linux笔记之expect和bash脚本监听输出并在匹配到指定字符串时发送中断信号1.expect2.bash 1.expect 在Expect脚本中,你可以使用expect来监听程序输出,…...

项目02《游戏-12-开发》Unity3D
基于 项目02《游戏-11-开发》Unity3D , 任务:实现场景怪物自动巡航 , 首先在场景中创建小球命名为路径点WayPoint0, 取消小球的碰撞器Collider, 再复制两个改名为WayPoint1 和 WayPoint2 , 在…...

记一次面试题
1.Php 私有化包(composer)的部署 1. 创建你的PHP包 确定你的包的功能和命名空间。 创建一个新的目录并初始化一个Git仓库。 使用composer init命令创建一个composer.json文件,并定义你的包名、版本、依赖等信息。 2. 开发并测试你的包 在本地…...

Rust入门2——随机数
文章目录 一、生成随机数二、比较两个数相等 简单列出两个Rust的小例子 一、生成随机数 在Cargo.toml的dependencies中引入rand,指定rand的版本 [dependencies] rand "^0.3.14"之后在主函数中调用rand函数,生成随机数 use rand::Rng; f…...

c#: 表达式树的简化
环境: .net 6 一、问题? 有下面的表达式: var nums new List<int> { 1, 2, 3 }; Expression<Func<int, bool>> exp i > i > nums.Max();我们知道,它其实就是:exp i > i > 3; 那么…...

13. UE5 RPG限制Attribute的值的范围以及生成结构体
前面几章,我们实现了通过GameplayEffect对Attribute值的修改,比如血量和蓝量,我们都是有一个最大血量和最大蓝量去限制它的最大值,而且血量和蓝量最小值不会小于零。之前我们是没有实现相关限制的,接下来,我…...

UE4运用C++和框架开发坦克大战教程笔记(十九)(第58~60集)完结
UE4运用C和框架开发坦克大战教程笔记(十九)(第58~60集)完结 58. 弹窗显示与隐藏59. UI 面板销毁60. 框架完成与总结 58. 弹窗显示与隐藏 这节课我们先来补全 TransferMask() 里对于 Overlay 布局类型面板的遮罩转移逻辑ÿ…...

ModuleNotFoundError: No module named ‘_ctypes‘报错解决方案
1、须命令安装libbffi-devel软件包: yum install libffi-devel -y2、安装完后再重装python3,无须卸载 找到之前的python3安装包,如果安装包删除了通过 history | grep python命令找到最初安装时的包下载的命令下载,保证版本一样&…...

【服务器数据恢复】服务器RAID模块硬件损坏的数据恢复案例
服务器数据恢复环境&故障: 某品牌服务器中有一组由数块SAS硬盘组建的RAID5磁盘阵列,服务器操作系统是WINDOWS SERVER,服务器中存放企业数据,无数据库文件。 服务器出故障之前出现过几次意外断电的情况,服务器断电…...

spring boot3x登录开发-上(整合jwt)
⛰️个人主页: 蒾酒 🔥系列专栏:《spring boot实战》 🌊山高路远,行路漫漫,终有归途。 目录 前置条件 jwt简介 导依赖 编写jwt工具类 1.配置项直接嵌入代码,通过类名.静态方法使用 2.配置项写到…...

git 克隆拉取代码出现私钥权限问题。
问题反馈: rootdd:~/android/boost-1.74-for-android-r20b# git clone https://github.com/liulilittle/boost-1.74-for-android-r20b.git Cloning into boost-1.74-for-android-r20b... WARNING: UNPROTECTED PRIVATE KEY FILE! Permissions 0777 for /root/…...

【5G NR】【一文读懂系列】移动通讯中使用的信道编解码技术-卷积码原理
目录 一、引言 二、卷积编码的发展历史 2.1 卷积码的起源 2.2 主要发展阶段 2.3 重要里程碑 三、卷积编码的基本概念 3.1 基本定义 3.2 编码器框图 3.3 编码多项式 3.4 网格图(Trellis)描述 四、MATLAB示例 一、引言 卷积编码,作为数字通信领域中的一项…...

揭开Markdown的秘籍:标题|文字样式|列表
🌈个人主页:聆风吟 🔥系列专栏:Markdown指南、网络奇遇记 🔖少年有梦不应止于心动,更要付诸行动。 文章目录 📋前言一. ⛳️Markdown 标题二. ⛳️Markdown 文字样式2.1 🔔斜体2.2 &…...

移动最小二乘法
移动最小二乘法(Moving Least Square,MLS)主要应用于曲线与曲面拟合,该方法基于紧支撑加权函数(即函数值只在有限大小的封闭域中定义大于零,而在域外则定义为零)和多项式基函数,通过…...

【LeetCode】37. 解数独(困难)——代码随想录算法训练营Day30
题目链接:37. 解数独 题目描述 编写一个程序,通过填充空格来解决数独问题。 数独的解法需 遵循如下规则: 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&…...

VUE学习——属性绑定
属性绑定,就是给html添加id、class这样类似的操作。 <template><div v-bind:id"dynamicId"><div v-bind:class"dynamicClass">Test</div></div> </template><script>export default{data(){return{…...

vue3 之 通用组件统一注册全局
components/index.js // 把components中的所组件都进行全局化注册 // 通过插件的方式 import ImageView from ./ImageView/index.vue import Sku from ./XtxSku/index.vue export const componentPlugin {install (app) {// app.component(组件名字,组件配置对象)…...

[Java][算法 双指针]Day 02---LeetCode 热题 100---04~07
LeetCode 热题 100---04~07 第一题:移动零 思路 找到每一个为0的元素 然后移到数组的最后 但是需要注意的是 要在给定的数组原地进行修改 并且其他非零元素的相对顺序不能改变 我们采用双指针法 定义两个指针i和j i和j一开始分别都在0索引位置 然后判断j所…...

【问题解决】如何将一个服务器的docker迁移到另一个服务器
要将Docker容器从一台机器迁移到另一台机器,可以按照以下步骤操作: 在机器A上提交容器为镜像: 使用docker commit命令将运行中的容器保存为新的镜像。这里需要容器的ID或名称,以及你想要命名的目标镜像名。 docker commit [容器…...

C++单例模式详解
目录 0. 前言 1. 懒汉式单例模式 1.1 最简单的单例模式 1.2 防止内存泄漏 1.2.1 智能指针的方法 1.2.2 静态嵌套的方法 1.3 保证线程安全 1.4 C11版本的优雅解决方案 2. 饿汉式单例模式 0. 前言 起因是在程序中重复声明了一个单例模式的变量,后来程序怎么调…...

LLM应用开发与落地:流式响应
一、背景 最近智能客服产品给到一个游戏客户那边,客户那边的客服负责人体验后认为我们产品回答的准确率是还是比较高的。同时,他反馈了几个需要改进的地方,其中一个就是机器人回复慢。机器人回复慢有很多原因,也有优化方式&#…...

神经网络 | 基于 CNN 模型实现土壤湿度预测
Hi,大家好,我是半亩花海。在现代农业和环境监测中,了解土壤湿度的变化对于作物生长和水资源管理至关重要。通过深度学习技术,特别是卷积神经网络,我们可以利用过去的土壤湿度数据来预测未来的湿度趋势。本文将使用 Pad…...

江科大STM32 终
目录 SPI协议10.1 SPI简介W25Q64简介10.3 SPI软件读写W25Q6410.4 SPI硬件外设读写W25Q64 BKP备份寄存器、PER电源控制器、RTC实时时钟11.0 Unix时间戳代码示例:读写备份寄存器BKP11.2 RTC实时时钟 十二、PWR电源控制12.1 PWR简介代码示例:修改主频12.3 串…...

《MySQL 简易速速上手小册》第10章:未来趋势和进阶资源(2024 最新版)
文章目录 10.1 MySQL 在云计算和容器化中的应用10.1.1 基础知识10.1.2 重点案例:使用 Python 部署 MySQL 到 Kubernetes10.1.3 拓展案例 1:在 AWS RDS 上部署 MySQL 实例10.1.4 拓展案例 2:使用 Docker 部署 MySQL 10.2 MySQL 和 NoSQL 的整合…...

Stable Diffusion 模型下载:GhostMix(幽灵混合)
文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十 下载地址 模型介绍 GhostMix 是绝对让你惊艳的模型,也是自己认为现在最强的2.5D模型。我认为模型的更新应该是基于现有的画面整体不大变的前提下,提高模型的成…...

django解决Table ‘xx‘ already exists的方法
1,首先看已存在的这个库表结构是什么样的,先让对应的model.py恢复到和他一样的字段 2,删除对应app下的migrations目录里面除__init__.py文件的其他所有文件 3,回到manage.py所在目录执行python manage.py makemigrations 4&#x…...

qt学习:arm摄像头+c调用v412框架驱动+qt调用v412框架驱动 显示摄像头画面
目录 跟内核进行数据通信的函数 编程步骤 c代码 头文件 打开摄像头文件 /dev/videox 获取当前主机上(开发板)摄像头列表信息 设置当前摄像头的画面格式 比如说 设置 采集图像的宽度为640 高度 480 在内核空间中,申请一个缓冲区队列…...