刷代码随想录有感(66):回溯算法——组合问题的优化(剪枝)

代码:将for循环中i的搜索范围进行缩小,免去多余的不可能符合条件的操作。

for(int i = start; i <= n-(k-tmp.size())+1;i++)

实质是剪枝,拿n=4,k=4作比较:

显然结果只可能是[1,2,3,4],选取顺序只可能是1-2-3-4,但是程序还是会以1后面也即2,3,4为开头暴力搜寻一遍。所以需要给搜寻规定范围来进行优化:

1.已经选择的元素个数:tmp.size();

2.为满足条件还需要:k - tmp.size()个元素;

3.所以至多从n - (k - tmp.size()) + 1 处开始遍历,再往后挪就不可能符合条件了。

比如n = 4, k = 3, tmp.size() = 1:

n - (k - tmp.size()) + 1 = 3,在for循环中(i = start; i <= n - (k - tmp.size()) + 1; i++),说明此时i至多从3开始搜,结果是[1,3,4],而不能从4开始搜,这样只能是[1,4](不符合条件)。

为什么要在n - (k - tmp.size()) 后面加1,举个例子,当n = k = 4,tmp.size() = 0时,此时n - (k - tmp.size()) = 0,但题目要求是[1,n]范围,所以必须从1开始,故+1。如果范围是[0,n]的话就直接n - (k - tmp.size())即可

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/627495.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Kafka 核心属性速览

目录 1. 背景 2. Kafka的核心属性 2.1. Broker 2.2. Partitions 2.3. Replicas 3. 实践 4. 参考 1. 背景 Kafka是一个流行队列组件&#xff08;在AWS上叫MSK&#xff09;&#xff0c;其他的队列还有rocketMQ、rabbitMQ。就我个人而言&#xff0c;我只是一个使用…

图文详解JUC:Wait与Sleep的区别与细节

目录 一.Wait() 二.Sleep() 三.总结Wait()与Sleep()的区别 一.Wait() 在Java中&#xff0c;wait() 方法是 Object类中的一个方法&#xff0c;用于线程间的协作。当一个线程调用wait() 方法时&#xff0c;它会释放对象的锁并进入等待状态&#xff0c;直到其他线程调用相同对…

Ps 滤镜:素描

Ps菜单&#xff1a;滤镜/滤镜库/素描 Filter/Filter Gallery/Sketch “素描”滤镜组中的滤镜可以将纹理添加到图像上&#xff0c;还适用于创建美术或手绘外观。许多“素描”滤镜在重绘图像时使用前景色和背景色。 半调图案 Halftone Pattern “半调图案”滤镜通过创建一种特定图…

【微信小程序开发(从零到一)【婚礼邀请函】制作】——任务分析和效果实现的前期准备(1)

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…

【069】基于SpringBoot+Vue实现的企业资产管理系统

系统介绍 基于SpringBootVue实现的企业资产管理系统管理员功能有个人中心&#xff0c;用户管理&#xff0c;资产分类管理&#xff0c;资产信息管理&#xff0c;资产借出管理&#xff0c;资产归还管理&#xff0c;资产维修管理。用户可以对资产进行借出和归还操作。因而具有一定…

详解lighthouse通过命令行方式运行并生成html测试报告的方法

lighthouse可以通过命令行的方式运行并生成html报告&#xff0c;我们可以通过lighthouse --help 命令查看命令行的详细用法&#xff0c;在这里我仅列出最常用的命令行使用方法&#xff01; 常用lighthouse命令行参数详解 * --chrome-flags&#xff1a;传递自定义标志给Chrome…

动态el-form表单以及动态禁用

当右侧下拉框选中为 长期有效,那么左侧输入框为禁用状态; <el-form-item label"证明有效期" class"is-required"><div v-for"(item,index) in form.arrayDat" :key"index" style"width: 100%;display: flex;justify-co…

记录一期Typecho WebShell木马渗透的经历

我创建了一个Typecho的轻量博客,之前一直是本地运行,最近才上了公网,平时自己也是粗心大意,把密码也写在第一篇博文里面 有一天,我突发奇想的想要提交更新,本博客是通过git进行代码版本管理的避免自己修改官方源码出现了问题,无法还原,也定时备份SQL, 然后莫名其妙的发现多了…

html--地图

<!DOCTYPE html> <html lang"en"> <head><meta charset"utf-8"><title>ECharts</title><!--Step:1 引入一个模块加载器&#xff0c;如esl.js或者require.js--><script src"js/esl.js"></scr…

【Doris的安装与部署】

1 集群规划和环境准备 Doris作为一款MPP架构的OLAP数据库&#xff0c;可以在绝大多数主流的商用服务器上运行。 1.1 环境要求 一般推荐使用Linux系统&#xff0c;版本要求是CentOS 7.1及以上或者Ubuntu 16.04及以上&#xff0c;这也是目前服务器市场最主流的操作系统。 操作…

3月份太阳镜行业线上市场销售数据分析

在消费者行为方面&#xff0c;太阳镜不仅仅是视力保护工具&#xff0c;更逐渐成为一种时尚单品。随着人们对健康和美容重视程度的提高&#xff0c;太阳镜作为体现个人风格的单品&#xff0c;其市场需求得到了进一步的推动。此外&#xff0c;全球旅行和旅游业的恢复&#xff0c;…

小程序|手写签名功能如何开启?

老师们可以利用易查分的手写签名功能&#xff0c;在发布查询后&#xff0c;让学生或家长签字确认知晓。下面教大家如何使用吧。 &#x1f4cc;使用教程 &#x1f50e;在哪里开启手写签名&#xff1f; 按照正常流程创建查询后&#xff0c;在查询管理页找到需要开启签名功能的查…

python实现读取串口数据-使用LibModbus库实现一个实时读取串口数据

在工业自动化领域&#xff0c;Modbus协议因其简单、可靠和广泛支持而备受青睐。其中&#xff0c;Modbus RTU&#xff08;串行通信&#xff09;以其低成本和易实施性在许多场景中发挥着重要作用。 01 Modbus RTU协议简介 Modbus RTU是一种基于串行通信的Modbus协议&#xff0c;…

SQL——SERVER的建表主要操作

目录 一&#xff1a;数据存储问题 1.表的相关数据 2.表&#xff0c;字段&#xff0c;记录 二&#xff1a;建表 1.创建表头 2. 数据类型 3.保存数据 4.数据冗余 5.使用命令重置表 7.设置主键 一&#xff1a;数据存储问题 1.表的概念 表是数据库的基本单位&#xff…

运维别卷系列 - 云原生监控平台 之 03.prometheus label 实践

文章目录 [toc]label 简介自定义标签relabel_configsregexrelabel_action metric_relabel_configs两者的区别 实践 label 简介 label 对于 Prometheus 来说&#xff0c;属于数据处理的方式&#xff0c;Prometheus 是通过指定的 label 来查询数据 Prometheus 的 target 中实例&…

elasticsearch-head 源码运行

1、下载安装nodejs 地址&#xff1a;Node.js — Run JavaScript Everywhere 2、git下载 elasticsearch-head 源码 地址&#xff1a;GitHub - mobz/elasticsearch-head: A web front end for an elastic search cluster 3、使用cmd 进入 elasticsearch-head 目录 4、依次执…

代码随想录算法训练营Day 42| 动态规划part04 | 01背包问题理论基础I、01背包问题理论基础II、416. 分割等和子集

代码随想录算法训练营Day 42| 动态规划part04 | 01背包问题理论基础I、01背包问题理论基础II、416. 分割等和子集 文章目录 代码随想录算法训练营Day 42| 动态规划part04 | 01背包问题理论基础I、01背包问题理论基础II、416. 分割等和子集01背包问题理论基础一、01背包问题二、…

Redis-如何保证与Mysql数据一致性

文章目录 Redis与Mysql数据一致性的情况有哪些&#xff1f;Redis与Mysql数据保持一致性的方案&#xff1f;同步双写机制删除缓存重新加载机制延迟双删机制利用MQ保持数据一致性 本篇小结 更多相关内容可查看 Redis与Mysql数据一致性的情况有哪些&#xff1f; Redis和MySQL是两…

Dart 3.4 发布:Wasm Native Macros(宏)

Google I/O 的结束&#xff0c;除了 Flutter 3.22 的发布 &#xff0c;Dart 3.4 也迎来了它是「史诗级」的更新&#xff0c;之所以这么说&#xff0c;就是因为 Wasm Native 的落地和 Macros 的实验性展示。 在此之前&#xff0c;其实我也提前整理过一些对应的内容&#xff0c;…

Web课外练习7

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>照片墙</title><style>body {display: …