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

leetcode-19-回溯-组合问题(剪枝、去重)

引自代码随想录

一、[77]组合

给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

1、大致逻辑

 k为树的深度,到叶子节点的路径即为一个结果

开始索引保证不重复取数(从当前位置往后取值)

每一个节点为一个for循环

2、剪枝(优化)

(1)和大于n,结束递归。

(2)剩余元素不足以满足k(k个元素)

剩下所需元素:k-path.size()

 至多从该起始位置开始遍历(否则元素个数不够):n - (k - path.size()) + 1

为什么有个+1呢,因为包括起始位置(从起始位置开始遍历)

我们要是一个左闭的集合(重要!!!!)

path.size() : 已经找的个数
k-path.size() :还需找的个数

[x, n]的数组长度起码应该是k-path.size()才有继续搜索的可能

那么 n-x+1 = k-path.size()

解方程得 x = n+1 - (k-path.size()),

而且这个x是可以作为起点往下搜的

也就是for(i = s; i<=x; i++) 这里的x是可以取到的

类似题目[216]、[17](有点难度)、[39]、[40](需要对开始索引做处理)

相关文章:

leetcode-19-回溯-组合问题(剪枝、去重)

引自代码随想录 一、[77]组合 给定两个整数 n 和 k&#xff0c;返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4]] 1、大致逻辑 k为树的深度&#xff0c;到叶子节点的路径即为一个结果 开始索引保证不…...

Java案例实现双色球

一问题&#xff1a; 二具体代码&#xff1a; package 重修;import java.util.Random; import java.util.Scanner;public class first {public static void main(String[] args) {int []usersnumbersusernumslect();System.out.println("用户");for (int i 0; i <…...

JS(JavaScript)的BOM操作

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…...

【CT】LeetCode手撕—82. 删除排序链表中的重复元素 II

题目 原题连接&#xff1a;82. 删除排序链表中的重复元素 II 1- 思路 模式识别1&#xff1a;已排序链表 ——> 判重逻辑 &#xff0c;涉及到 while 2- 实现 ⭐82. 删除排序链表中的重复元素 II——题解思路 class Solution {public ListNode deleteDuplicates(ListNode h…...

C++ STL unique_ptr智能指针源码剖析

由于上一篇博客将shared_ptr,weak_ptr,enable_shared_form_this的源码实现整理了一遍,想着cpp智能指针还差个unique_ptr故写下此篇博客,以供学习 源码剖析 一,模板参数 首先,我们先看unique_ptr的模板参数,第一个参数_TP自是不用说表示对象类型,第二个模板参数定义了unique_p…...

Unity中的的文件夹(特殊文件夹)

Unity中的的文件夹(特殊文件夹) Unity工程中的关键文件夹和路径知识点, 以下是对Unity工程中几个关键文件夹和路径的总结&#xff1a; 1. 工程路径获取 ​ print(Application.dataPath) 用途&#xff1a;通常只在编辑模式下使用。注意事项&#xff1a;游戏发布后&#xff0…...

Go语言定时器Timer和Ticker到底怎么用

原文链接&#xff0c;可获取更多Go语言学习资料 概述 在日常开发中&#xff0c;我们不可避免的需要使用到定时任务用来处理业务逻辑。在Go语言中内置的有两个定时器&#xff0c;Timer和Ticker&#xff0c;合理的使用这两个定时器可以很好的解决定时任务的需求&#xff0c;同时…...

41、web基础和http协议

web基础与http协议 一、web web&#xff1a;就是我们所说得页面&#xff0c;打开网页展示得页面。&#xff08;全球广域网&#xff0c;万维网&#xff09; world wide webwww 分布式图形信息系统 http&#xff1a;超文本传输协议 https&#xff1a;加密的超文本传输协议…...

6-173 二分查找的关键字比较次数

6-173 二分查找的关键字比较次数 - &#xff08;32&#xff09;专科段数据结构专项练习&#xff08;2024版&#xff09; (pintia.cn) int CountSearchTimes(int a[], int low, int high, int x) {int time0;while(low < high){int mid(lowhigh)/2;time;if(a[mid]x)return t…...

【基础篇】第5章 Elasticsearch 数据聚合与分析

在Elasticsearch的庞大功能体系中&#xff0c;数据聚合与分析扮演着至关重要的角色&#xff0c;它使我们能够从海量数据中提炼出有价值的信息&#xff0c;为决策提供依据。本章将深入探讨Elasticsearch的聚合功能&#xff0c;从基本概念到常见类型的实践&#xff0c;让你掌握如…...

【网络安全】修改Host文件实现域名解析

场景 开发一个网站或者服务&#xff0c;需要在本地测试时&#xff0c;可以将线上的域名指向本地开发环境的IP地址。从而模拟真实环境中的域名访问&#xff0c;方便调试和开发。 步骤 1、以管理员身份打开命令提示符 2、编辑hosts文件&#xff1a; 输入以下命令打开hosts文…...

Spring Boot 全面解析:从入门到实践案例

引言&#xff1a; Spring Boot 是由 Pivotal 团队提供的全新框架&#xff0c;旨在简化 Spring 应用的初始搭建以及开发过程。它基于 Spring 平台&#xff0c;通过“约定优于配置”的原则&#xff0c;尽可能自动化配置&#xff0c;减少XML配置&#xff0c;使得开发者能够快速启…...

222222222

2222222...

Boost 智能指针

scoped_ptr 不能被复制或赋值给其他 scoped_ptr 对象&#xff0c;不能与其他指针比较 (除了 nullptr) scoped_ptr 用例 template <typename T> class scoped_ptr { public:// 构造函数&#xff1a;初始化 scoped_ptr 并接管指针的所有权explicit scoped_ptr(T* ptr n…...

在WSL Ubuntu中启用root用户的SSH服务

在 Ubuntu 中&#xff0c;默认情况下 root 用户是禁用 SSH 登录的&#xff0c;这是为了增加系统安全性。 一、修改配置 找到 PermitRootLogin 行&#xff1a;在文件中找到 PermitRootLogin 配置项。默认情况下&#xff0c;它通常被设置为 PermitRootLogin prohibit-password 或…...

C语⾔数据类型和变量

C语⾔数据类型和变量 1.数据类型介绍1.1 字符型1.2 整型1.3 浮点型1.4 布尔类型1.5 各种数据类型的长度1.5.1 sizeof操作符1.5.2 数据类型长度1.5.3 sizeof中表达式不计算 2. signed 和 unsigned3. 数据类型的取值范围4. 变量4.1 变量的创建4.2 变量的分类 5. 算术操作符&#…...

运行时类型信息(RTTI)

在计算机编程中,运行时类型信息(Runtime Type Information,简称RTTI)或运行时类型标识(Runtime Type Identification)是某些编程语言(如C++、Object Pascal、Ada)的一个特性,它允许在程序运行时获取对象的数据类型信息。RTTI可以用于所有类型,也只能用于显式启用RTTI…...

使用 NVivo 定性数据分析软件指导癌症护理研究

您是否曾因进行全面文献综述所需的大量研究而感到不知所措&#xff1f;在比较和整理大量冗长的出版物时&#xff0c;您是否不知道从哪里开始&#xff1f;幸运的是&#xff0c;这正是定性研究专家 Heidi Rishel Brakey 硕士擅长的领域&#xff0c;我们将在本案例研究中介绍这一点…...

R语言 | 使用ggplot绘制柱状图,在柱子中显示数值和显著性

原文链接&#xff1a;使用ggplot绘制柱状图&#xff0c;在柱子中显示数值和显著性 本期教程 获得本期教程示例数据&#xff0c;后台回复关键词&#xff1a;20240628。&#xff08;PS&#xff1a;在社群中&#xff0c;可获得往期和未来教程所有数据和代码&#xff09; 往期教程…...

第十四届蓝桥杯省赛C++B组D题【飞机降落】题解(AC)

解题思路 这道题目要求我们判断给定的飞机是否都能在它们的油料耗尽之前降落。为了寻找是否存在合法的降落序列&#xff0c;我们可以使用深度优先搜索&#xff08;DFS&#xff09;的方法&#xff0c;尝试所有可能的降落顺序。 首先&#xff0c;我们需要理解题目中的条件。每架…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

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

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

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...