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

数据结构刷题(十九):77组合、216组合总和III

1.组合

题目链接

  1. 过程图:先从集合中取一个数,再依次从剩余数中取k-1个数。

  1. 思路:回溯算法。使用回溯三部曲进行解题:

  • 递归函数的返回值以及参数:n,k,startIndex(记录每次循环集合从哪里开始遍历的位置),其中startIndex 就是防止出现重复的组合。比如从1开始了循环,则使用startindex=2,让startindex作为下次循环的开始。

还有全局变量:一个是用来存放一个符合条件的结果path,一个用来存放所有符合条件的结果集合result。

  • 回溯函数终止条件:path这个数组的大小如果达到k,说明我们找到了一个子集大小为k的组合,在图中path存的就是根节点到叶子节点的路径

  • 单层搜索的过程:for循环用来横向遍历,递归的过程是纵向遍历。

(1)for循环每次从startIndex开始遍历,然后用path保存取到的节点i。

(2)递归函数不断调用自己往深处遍历,总会遇到叶子节点,遇到了叶子节点就要返回。

(3)递归函数下面部分就是回溯的操作了,撤销本次处理的结果。

最终结果代码:

class Solution {// 存放单个结果path, 存放所有结果resList<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {combineHelper(n, k, 1);return res;}// startindex就是循环开始位置private void combineHelper(int n, int k, int startindex) {// 终止条件 if (path.size() == k){res.add(new ArrayList<>(path));return;}// 单层逻辑for (int i = startindex; i <= n ; i++ ){path.add(i);combineHelper(n, k, i + 1);path.removeLast();}}
}
  1. 剪枝优化:

(1)假设n = 4,k = 4,就四个数,还求四个数的组合,那必然只有一个组合,从2开始for循环再找其他数没有意义。所以,可以剪枝的地方就在递归中每一层的for循环所选择的起始位置,在循环中i就是循环的起始位置。也就是说for循环的开始位置到结束位置一共的元素个数<k时,就不需要判断了。

(2)过程:

  • 已经选择的元素个数:path.size();

  • 还需要的元素个数为: k - path.size();

  • 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1,开始遍历。也就是说 n - (k - path.size()) + 1是最晚的起始位置,如果超过了这个位置找元素,path的元素个数不可能到达k个。这里面+1是闭区间的意思。

最终优化后的代码:

List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {combineHelper(n, k, 1);return res;
}private void combineHelper(int n, int k, int startindex) {if (path.size() == k){res.add(new ArrayList<>(path));return;}for (int i = startindex; i <= n - (k - path.size()) + 1; i++ ){path.add(i);combineHelper(n, k, i + 1);path.removeLast();}
}

2.组合总和III

题目链接

  1. 过程图:和上一题组合类似,仍然是先取某个值,然后再从其他数中k-1个进行组合。

  1. 思路:回溯三部曲。

  • 确定递归函数参数:题目中的n和k,sum(已经收集的元素的总和也就是path里元素的总和),startIndex为下一层for循环搜索的起始位置。

  • 确定终止条件:path.size() 和 k相等且sum=n

  • 单层搜索过程: path收集每次选取的元素,sum来统计path里元素的总和。别忘了回溯。

3.代码:

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum3(int k, int n) {backTracking(n, k, 1, 0);return result;}// targetSum就是n, sum是和private void backTracking(int targetSum, int k, int startIndex, int sum) {// 减枝if (sum > targetSum) {return;}if (path.size() == k) {if (sum == targetSum) result.add(new ArrayList<>(path));return;}// 减枝 9 - (k - path.size()) + 1for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {path.add(i);sum += i;backTracking(targetSum, k, i + 1, sum);//回溯path.removeLast();//回溯sum -= i;}}
}

相关文章:

数据结构刷题(十九):77组合、216组合总和III

1.组合题目链接过程图&#xff1a;先从集合中取一个数&#xff0c;再依次从剩余数中取k-1个数。思路&#xff1a;回溯算法。使用回溯三部曲进行解题&#xff1a;递归函数的返回值以及参数&#xff1a;n&#xff0c;k&#xff0c;startIndex(记录每次循环集合从哪里开始遍历的位…...

PyQt 做美*女GIF设置桌面,每天都很爱~

人生苦短&#xff0c;我用python 要说程序员工作的最大压力不是来自于工作本身&#xff0c; 而是来自于需要不断学习才能更好地完成工作&#xff0c; 因为程序员工作中面对的编程语言是在不断更新的&#xff0c; 同时还要学习熟悉其他语言来提升竞争力… 好了&#xff0c;学习…...

[渗透测试笔记] 54.日薪2k的蓝队hw中级定级必备笔记系列篇3之域渗透黄金票据和白银票据

前文链接 [渗透测试笔记] 52.告别初级,日薪2k的蓝队hw中级定级必备笔记 [渗透测试笔记] 53.日薪2k的蓝队hw中级定级必备笔记2 文章目录 Kerberos认证协议NTLM认证协议Kerberos和NTLM比较黄金票据原理黄金票据条件复现过程白银票据原理白银票据条件复现过程黄金票据和白银票据…...

【异常】Spring Cloud Gateway网关自定义过滤器无法获取到请求体body的内容?不存在的!

一、需求说明 项目要使用到网关SpringCloud Gateway进行验签,现在定义了一个过滤器ValidateSignFilter, 我希望,所以过网关SpringCloud Gateway的请求,都能够校验一下请求头,看看是否有Sign这个字段放在请求头中。 二、异常说明 但是,我遇到了SpringCloud Gateway网关…...

CNN 卷积神经网络对染色血液细胞分类(blood-cells)

目录 1. 介绍 2. 加载数据 3. 可视化 3.1 显示单幅图像 3.2 显示多幅图像...

Kubernetes学习(三)Service

Service对象 为什么需要Service 每个Pod都有自己的IP地址&#xff0c;但是在Deployment中&#xff0c;在同一时刻运行的Pod集合可能与稍后运行该应用程序的Pod集合不同。 这就导致了一个问题&#xff1a;如果一组Pod&#xff08;称为后端&#xff09;为集群内其他Pod&#x…...

数学小课堂:古德-图灵折扣估计法和插值法(防范黑天鹅事件的方法)

文章目录 引言I 黑天鹅事件产生的原因1.1 置信度1.2 数据的稀疏性1.3 零概率问题II 防范黑天鹅事件的方法2.1 古德-图灵折扣估计法2.2 插值法引言 防范黑天鹅事件的方法 古德-图灵折扣估计法:它主要是解决零概率的事件古德的方法虽然解决了零概率的问题,但是依然没有解决数据…...

redis getshell方法

前言 参考文章 https://paper.seebug.org/1169 https://blog.csdn.net/weixin_55843787/article/details/123829606 https://blog.csdn.net/chenglanqi6606/article/details/100909518 Redis是什么 Redis是一款基于键值对的NoSQL数据库&#xff0c;它的值支持多种数据结构 …...

【ONE·C || 程序编译简述】

总言 C语言&#xff1a;程序编译相关。    文章目录总言1、程序的翻译环境和运行环境1.1、简述1.2、翻译环境&#xff1a;程序编译与链接1.2.1、简介&#xff1a;程序如何从.c文件形成.exe可执行程序1.2.2、过程说明1.3、运行环境2、预处理详解2.1、预定义符号2.2、#define2.…...

MGAT: Multimodal Graph Attention Network for Recommendation

模型总览如下&#xff1a; 图1&#xff1a;多模态图注意力网络背景&#xff1a;本论文是对MMGCN&#xff08;Wei et al., 2019&#xff09;的改进。MMGCN简单地在并行交互图上使用GNN&#xff0c;平等地对待从所有邻居传播的信息&#xff0c;无法自适应地捕获用户偏好。 MMGCN…...

在SNAP中用sentinel-1数据做InSAR测量,以门源地震为例

在SNAP中用sentinel-1数据做InSAR0 写在前面1 数据下载2 处理步骤2.1 split2.2 apply orbit 导入精密轨道2.3 查看数据的时空基线base line2.4 back-geocoding 配准2.5 Enhanced Spectral Diversity2.6 Deburst2.7 Interogram Formation 生成干涉图2.8 Multilook 多视2.9 Golds…...

MySQL常用函数

什么是函数&#xff1f; 函数是指一段可以直接被另一段程序调用的程序或代码。 字符串函数 函数功能CONCAT(S1,S2,…Sn)字符串拼接&#xff0c;将S1&#xff0c;S2&#xff0c;… Sn拼接成一个字符串LOWER(str)将字符串str全部转为小写LOWER(str)将字符串str全部转为小写LPAD(…...

51单片机数字电子钟开题报告

目录 选题背景 初步设计方案 芯片的选型 编译环境 关键问题 策略 方案 参考文献 选题背景 数字电子钟是一种受到越来越多人喜爱的钟表&#xff0c;其准确性和稳定性成为设计和研发的重要考虑因素。在现代社会&#xff0c;时间的准确性对于各行各业都非常重要&#xff0…...

day7 HTTP协议

HTTP协议 什么是协议&#xff1f; 协议实际上是某些人&#xff0c;或者某些组织提前制定好的一套规范&#xff0c;大家都按照这个规范来&#xff0c;这样可以做到沟通无障碍。协议就是一套规范&#xff0c;就是一套标准。由其他人或其他组织来负责制定的。我说的话你能听懂&…...

3DCAT+一汽奥迪:共建线上个性化订车实时云渲染方案

近年来&#xff0c;随着5G网络和云计算技术的不断发展&#xff0c;交互式3D实时云看车正在成为一种新的看车方式。与传统的到4S店实地考察不同&#xff0c;消费者可以足不出户&#xff0c;通过网络与终端设备即可实现全方位展示、自选汽车配色、模拟效果、快捷选车并进行个性化…...

yii2项目使用frp https2http插件问题

yii2内网项目&#xff0c;使用frp进行内网穿透&#xff0c;使用 https2http插件把内网服务器http流量转成https&#xff0c;会存在一个问题&#xff1a;当使用 $this->redirect(...) 或 $this->goHome() &#xff08;其实用的也是前者&#xff09;等重定向时&#xff0c;…...

关于 interface{} 会有啥注意事项?下

我们一起来回顾一下上一次说到的 interface{} 可以用来做多态 接口类型分为空接口类型和非空接口类型&#xff0c;他们的底层数据结构不太一样 这里顺便说一下&#xff0c;用来作态需要满足这样的条件&#xff1a; 首先得有父类指针指向子类的对象这个接口还必须是非空接口…...

ansible组件介绍和简单playbook测试

一、ansible inventory 在大规模的配置管理工作中&#xff0c;管理不同业务的机器&#xff0c;机器的信息都存放在ansible的inventory组件里面。在工作中&#xff0c;配置部署针对的主机必须先存放在Inventory里面&#xff0c;然后ansible才能对它进行操作。默认的Ansible的in…...

[数据结构]:13-插入排序(顺序表指针实现形式)(C语言实现)

目录 前言 已完成内容 插入排序实现 01-开发环境 02-文件布局 03-代码 01-主函数 02-头文件 03-PSeqListFunction.cpp 04-SortCommon.cpp 05-SortFunction.cpp 结语 前言 此专栏包含408考研数据结构全部内容&#xff0c;除其中使用到C引用外&#xff0c;全为C语言代…...

es6 new Promise

Promise 是一个构造函数&#xff0c;本身身上有 all、reject、resolve 这几个方法&#xff0c;原型上有 then、catch 等方法。所以 Promise new 出来的对象确定就有 then、catch 方法。Promise 的构造函数接收一个参数&#xff0c;是函数&#xff0c;而且传入两个参数&#xff…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...