当前位置: 首页 > 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;需…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...