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

代码随想录算法训练营第24天25天|● 77. 组合● 216.组合总和III ● 17.电话号码的字母组合

77组合

看完题后的思路

在这里插入图片描述

  1. void f(数组,startIndex)
  2. 递归终止
    if(startIndex数组长度||path.sizek){
    if(path.size==k){
    加入}
    }
  3. 递归

for(;startIndex<num.size;startIndex++){
加入;
4.剪枝
if(path.size>k){
吐出来;
return;
}
f(num,startIndex+1);
// 回溯
吐出来

}

代码

 List<List<Integer>> ires = new ArrayList<>();ArrayList<Integer> ipath = new ArrayList<>();public List<List<Integer>> combine(int n, int k) {combineTB(n,0,k);return ires;}public void combineTB(int n,int startIndex,int k){//终止if (startIndex==n||ipath.size()==k){if (ipath.size()==k){ires.add(new ArrayList<>(ipath));}return;}for (; startIndex<n; startIndex++) {// 尝试加入ipath.add(startIndex);// 剪枝if (ipath.size()>k){  // 这一步永远不会生效,因为终止条件已经剪枝了return;}// 进入下一层combineTB(n,startIndex+1,k);// 回溯ipath.remove(ipath.size()-1);// 进入本层下一个 ----->}}

复杂度

优化:添加剪枝条件

      // 剪枝if (ipath.size()==k||n-startIndex+1<(k-ipath.size())){return;}

后一个剪枝条件表示当前可加入的元素<所缺的元素

在这里插入图片描述

List<List<Integer>> ires = new ArrayList<>();ArrayList<Integer> ipath = new ArrayList<>();public List<List<Integer>> combine(int n, int k) {combineTB(n,1,k);return ires;}public void combineTB(int n,int startIndex,int k){//终止if (startIndex>n||ipath.size()==k){if (ipath.size()==k){ires.add(new ArrayList<>(ipath));}return;}for (; startIndex<=n; startIndex++) {// 剪枝if (ipath.size()==k||n-startIndex+1<(k-ipath.size())){return;}// 尝试加入ipath.add(startIndex);// 剪枝// if (ipath.size()>k){//     return;// }// 进入下一层combineTB(n,startIndex+1,k);// 回溯ipath.remove(ipath.size()-1);// 进入本层下一个 ----->}}

递归深度: k
递归宽度:n-startIndex+1<(k-ipath.size())
在这里插入图片描述

收获

  1. 三刷看一遍
  2. 组合问题模板
    在这里插入图片描述
  3. 做回溯题步骤
    (0)判断问题类型
    (1)树状图
    (2)递归三部曲
    (3)剪枝条件

216.组合总和III

看完题后的思路

a+b=b+a,这是一个组合问题
在这里插入图片描述

  1. void f(n,k,startIndex,sum) // 纵向剪枝
  2. 终止条件
    if(path.size==k){
    if(和为n){
    加入
    }
    return;
    }
  3. 回溯模型
  4. 剪枝条件
    if(path内的数+当前树大于k) return

代码

  List<List<Integer>> ires = new ArrayList<>();ArrayList<Integer> ipath = new ArrayList<>();//216. 组合总和 IIIpublic List<List<Integer>> combinationSum3(int k, int n) {combinationSum3BT(k,n,0,1);return ires;}public void combinationSum3BT(int k, int n,int sum,int startIndex ) {if(ipath.size()==k){// 终止+纵向剪枝if (sum==n){ires.add(new ArrayList<>(ipath));}return;}for (; startIndex <=9 ; startIndex++) {// 纵向剪枝if (startIndex+sum>n){return;  // (纵)横向剪枝  因为兄弟节点 (startIndex++)+sum也一定>k}sum+=startIndex;ipath.add(startIndex);combinationSum3BT(k,n,sum,startIndex+1);// 回溯sum-=startIndex;ipath.remove(ipath.size()-1);// 本层下一个}}

复杂度

最坏时间复杂度 0(9*k)
在这里插入图片描述

收获

1.本题让组合剪枝变得明朗,三刷大脑过一遍
2, 组合问题中的纵横剪枝
==有图==

17.电话号码的字母组合

看完题后的思路

在这里插入图片描述

  1. 本体可以抽象为若干个筐,筐中有若干个球,每次从筐中取一个球,所有可能的球的组合。
    本质上是只取组合传统递归树最左边分支
  2. void f(map<数字,字母>,startIndex,[数字])
  3. if(ipath.size==数字个数){
    加入结果;
    return;
    }
  4. 回溯算法
    num【startIndex】;
    取出对应的字母;
    for(字母){
    加入ipath;
    f(map<数字,字母>,startIndex+1,[数字])
    回溯;
    }

代码

 StringBuilder sbPath = new StringBuilder();ArrayList<String> slistRes = new ArrayList<>();public List<String> letterCombinations(String digits) {if (digits==null||digits.length()==0){return slistRes;}String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};letterCombinationsBT(digits,numString,0);return slistRes;}public void letterCombinationsBT(String digits,String[] map,int startIndex) {// 出口if (sbPath.length()==digits.length()){slistRes.add(new String(sbPath));return;}// 回溯算法char c = digits.charAt(startIndex);String s = map[c - '0'];// 对应的字符组合// 内部回溯for (char c1 : s.toCharArray()) {sbPath.append(c1);// 下一层递归letterCombinationsBT(digits,map,startIndex+1); // 关键是startIndex+1// 回溯sbPath.delete(sbPath.length()-1,sbPath.length());// 进入本层下一层}}

复杂度

时间复杂度 0(数字个数*(3或4))
在这里插入图片描述

收获🐱‍🚀🐱‍🚀

1. 三刷在大脑过一遍
2. 本题通过画树竟然完美解决了
3. 若干袋子,求小球组合递归树
在这里插入图片描述

相关文章:

代码随想录算法训练营第24天25天|● 77. 组合● 216.组合总和III ● 17.电话号码的字母组合

77组合 看完题后的思路 void f&#xff08;数组&#xff0c;startIndex&#xff09;递归终止 if&#xff08;startIndex数组长度||path.sizek&#xff09;{ if(path.sizek){ 加入} }递归 for&#xff08;&#xff1b;startIndex<num.size&#xff1b;startIndex&#xff0…...

Python_pytorch

python_pytorch 小土堆pytotch学习视频链接 from的是一个个的包&#xff08;package) import 的是一个个的py文件(file.py) 所使用的一般是文件中的类(.class) 第一步实例化所使用的类,然后调用类中的方法&#xff08;def) Dataset 数据集处理 import os from PIL impo…...

【Java|golang】2335. 装满杯子需要的最短总时长

现有一台饮水机&#xff0c;可以制备冷水、温水和热水。每秒钟&#xff0c;可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。 给你一个下标从 0 开始、长度为 3 的整数数组 amount &#xff0c;其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的…...

shell编程之sed

文章目录八、shell编程之sed8.1 工作原理8.2 sed基本语法8.3 模式空间中的编辑操作8.3.1 地址定界8.3.2 常用编辑命令8.4 sed扩展八、shell编程之sed 8.1 工作原理 sed是一种流编辑器&#xff0c;它是文本处理中非常有用的工具&#xff0c;能够完美的配合正则表达式使用&…...

安全寒假作业nginx反向代理+负载均衡上传webshell重难点+apache漏洞

1.应用场景 负载均衡作为现今解决web应用承载大流量访问问题的一种方案&#xff0c;在真实环境中得到广泛的部署。实现负载均衡的方式有很多种&#xff0c;比如 DNS 方式、HTTP 重定向方式、IP 负载均衡方式、反向代理方式等等。 比如基于dns的负载均衡&#xff1a; 当然还有…...

day35|01背包问题、416. 分割等和子集

01背包问题 有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品只能用一次&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 例&#xff1a;背包最大重量为4。 物品为&#xff1a; 重量价值物品0115物品…...

Linux内核启动(3,0.11版本)内核启动完成与进入内核main函数

这一部分是在讲解head.s代码&#xff0c;这个代码与bootsect.s和setup.s在同一目录下&#xff0c;但是head.s程序在被编译生成目标文件后会与内核其他程序一起被链接成system模块&#xff0c;位于system模块的最前面开始部分。system模块将被放置在磁盘上setup模块之后开始的扇…...

【2023】Prometheus-Alertmanager高可用集群

本次实验准备了三个节点&#xff0c;分别为laert-01~03 目录1.安装Alertmanager2.配置启动文件3.验证集群4.关于集群的配置项1.安装Alertmanager 这部分内容在三个节点上都要执行 下载安装包&#xff0c;将安装包解压至/data目录下 wget https://github.com/prometheus/aler…...

2023-2-11 刷题情况

最短路计数 题目描述 给出一个 NNN 个顶点 MMM 条边的无向无权图&#xff0c;顶点编号为 1∼N1\sim N1∼N。问从顶点 111 开始&#xff0c;到其他每个点的最短路有几条。 输入格式 第一行包含 222 个正整数 N,MN,MN,M&#xff0c;为图的顶点数与边数。 接下来 MMM 行&…...

2019_41 考研408

2019年(单链表)41.(13分)设线性表采用带头结点的单链表保存&#xff0c;链表中的结点定义如下:typedef struct node {int data;struct node* next;}NODE;请设计一个空间复杂度为O(1)且时间上尽可能高效的算法&#xff0c;重新排列L中的各结点&#xff0c;得到线性表L(q,a,,a,an…...

Linux账号与用户组

目录 用户标识符&#xff1a;UID与GID 用户账号 /etc/passwd文件结构 1、账号名称 2、密码 3、UID 4、GID 5、用户信息说明栏 6、家目录 7、shell /etc/shadow文件结构 1、账号名称 2、密码 3、最近修改密码的日期 4、密码不可被修改的天数&#xff08;与第三字…...

有趣的Hack-A-Sat黑掉卫星挑战赛——定位卫星Jackson

国家太空安全是国家安全在空间领域的表现。随着太空技术在政治、经济、军事、文化等各个领域的应用不断增加&#xff0c;太空已经成为国家赖以生存与发展的命脉之一&#xff0c;凝聚着巨大的国家利益&#xff0c;太空安全的重要性日益凸显[1]。而在信息化时代&#xff0c;太空安…...

JAVA集合专题3 —— vector + LinkedList + Set

目录vector的特点LinkedList底层结构模拟双向链表比较ArrayList和LinkedListSet接口基本介绍Set接口的遍历方式Set接口实现类对象的特点Set接口实现类HashSet模拟HashSet/HashMap的底层结构vector的特点 Vector底层是一个对象数组Vector是线程同步的&#xff0c;即线程安全的&…...

Scout:一款功能强大的轻量级URL模糊测试与爬取工具

关于Scout Scout是一款功能强大的轻量级URL模糊测试与爬取工具&#xff0c;可以帮助广大研究人员进行URL模糊测试&#xff0c;并爬取目标Web服务器中难以扫描发现的VHSOT、文件和目录等资源。 项目中包含了一个完整的字典文件&#xff0c;并尽可能地提供了更多的便携性&#…...

leaflet 解决marker呈现灰色边框的问题

第052个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+leaflet示例中处理marker外面有灰色边框的问题,请看未处理会后的图片。 处理后的结果非常满意,不再显示灰色边框。处理方法参考源代码。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果; 注意…...

MySQL JSON类型字段的查找与更新

MySQL 提供了丰富的函数用于 JSON 类型字段的查找与更新&#xff0c;详见官方文档。 创建一个表 t1&#xff0c;basic_info 字段为JSON类型: CREATE TABLE t1 (id int(11) NOT NULL AUTO_INCREMENT,basic_info json DEFAULT NULL,PRIMARY KEY (id) ) ENGINEInnoDB DEFAULT CH…...

element Ui树状图控件 spring boot Vue 实现角色授权功能

目录 前言&#xff1a; 二. element ui 2.1官网提供的核心代码 三.表结构 ​编辑 四.后端 4.1功能分析 4.2实体类 4.3 查询全部权限显示的结果 4.2修改角色权限的后台方法 五.vue 5.0代码总览 5.1树形图 5.2所需要的绑定数据 5.3所需方法 前言&#xff1a; 先上图…...

已解决sc delete MongoDB卸载MongoDB拒绝访问。

已解决sc delete MongoDB卸载MongoDB拒绝访问。 文章目录报错问题报错翻译报错原因解决方法联系博主免费帮忙解决报错报错问题 粉丝群里面的一个小伙伴遇到问题跑来私信我&#xff0c;想卸载MongoDB数据库&#xff0c;但是发生了报错&#xff08;当时他心里瞬间凉了一大截&…...

python的opencv操作记录11——阈值分割

文章目录传统图像处理分割阈值分割一个应用场景opencv库中的阈值分割固定阈值THRESH_OTSU 大津法阈值自适应阈值传统图像处理分割 现在提到图像分割&#xff0c;很多人会直接想到当前火爆的深度学习的各种分割网络&#xff0c;比如实例分割&#xff0c;语义分割等。其实在传统…...

Python-项目实战--飞机大战-英雄登场(7)

目标设计英雄和子弹类使用pygame.key.get_pressed()移动英雄发射子弹1.设计英雄和子弹类1.1英雄需求游戏启动后&#xff0c;英雄出现在屏幕的水平中间位置&#xff0c;距离屏幕底部120像素英雄每隔0.5秒发射一次子弹&#xff0c;每次连发三枚子弹英雄默认不会移动&#xff0c;需…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...

VSCode 没有添加Windows右键菜单

关键字&#xff1a;VSCode&#xff1b;Windows右键菜单&#xff1b;注册表。 文章目录 前言一、工程环境二、配置流程1.右键文件打开2.右键文件夹打开3.右键空白处打开文件夹 三、测试总结 前言 安装 VSCode 时没有注意&#xff0c;实际使用的时候发现 VSCode 在 Windows 菜单栏…...