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

(C++回溯01) 组合

77、组合

回溯题目三步走

1. 确定参数

2. 确定终止条件

3. for 循环横向遍历,递归纵向遍历

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(int n, int k, int startIndex) {if(path.size() == k) {result.push_back(path);return;}for(int i = startIndex; i <= n; i++) {path.push_back(i);backtracking(n, k, i + 1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return result;}
};

剪枝操作:

公式:n - (k - path.size()) + 1

k - path.size() 意思是还可选取多少元素

n - (k - path.size()) 意思是去掉可选取元素个数后的位置

n - (k - path.size()) + 1 为当前可以组合的最后一个位置

剪枝后代码:

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(int n, int k, int startIndex) {if(path.size() == k) {result.push_back(path);return;}for(int i = startIndex; i <= n; i++) {int flag = n - (k - path.size()) + 1;if(i > flag) {return;}path.push_back(i);backtracking(n, k, i + 1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return result;}
};

216、组合总和 III

class Solution {
public:vector<vector<int>> result;vector<int> path;int count = 0;void backtracking(int k, int n, int startIndex) {if(path.size() == k) {if(count == n)result.push_back(path);return;}for(int i = startIndex; i < 10; i++) {path.push_back(i);count += i;backtracking(k, n, i + 1);path.pop_back();count -= i;}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 1);return result;}
};

剪枝操作:

class Solution {
public:vector<vector<int>> result;vector<int> path;int count = 0;void backtracking(int k, int n, int startIndex) {if(path.size() == k) {if(count == n)result.push_back(path);return;}for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {count += i;if(count > n) {count -= i;return;}path.push_back(i);backtracking(k, n, i + 1);path.pop_back();count -= i;}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 1);return result;}
};

17、电话号码的字母组合

class Solution {
private:string letterMap[10] = {"","","abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};
public:vector<string> result;string path;void backtacking(string& digits, int index) {if(index == digits.size()) {result.push_back(path);return;}string letters = letterMap[digits[index] - '0'];for(int i = 0; i < letters.size(); i++) {path.push_back(letters[i]);backtacking(digits, index + 1);path.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size() == 0) {return result;}backtacking(digits, 0);return result;}
};

相关文章:

(C++回溯01) 组合

77、组合 回溯题目三步走 1. 确定参数 2. 确定终止条件 3. for 循环横向遍历&#xff0c;递归纵向遍历 class Solution { public:vector<vector<int>> result;vector<int> path;void backtracking(int n, int k, int startIndex) {if(path.size() k) {…...

k8s学习笔记——安装istio的仪表盘之prometheus安装

接上一篇&#xff0c;继续安装istio的dashboard。 先到istio-1.22.0/samples/addons目录下&#xff0c;把yaml文件中的镜像仓库地址修改了&#xff0c;修改地址参考我之前写的CSDN里的镜像对照表。不然直接执行kubectl apply -f samples/addons这个命令后&#xff0c;依据会出…...

四、GD32 MCU 常见外设介绍 (7) 7.I2C 模块介绍

7.1.I2C 基础知识 I2C(Inter-Integrated Circuit)总线是一种由Philips公司开发的两线式串行总线&#xff0c;用于内部IC控制的具有多端控制能力的双线双向串行数据总线系统&#xff0c;能够用于替代标准的并行总线&#xff0c;连接各种集成 电路和功能模块。I2C器件能够减少电…...

Apollo 配置中心的部署与使用经验

前言 Apollo&#xff08;阿波罗&#xff09;是携程开源的分布式配置管理中心。 本文主要介绍其基于 Docker-Compose 的部署安装和一些使用的经验 特点 成熟&#xff0c;稳定支持管理多环境/多集群/多命名空间的配置配置修改发布实时&#xff08;1s&#xff09;通知到应用程序支…...

Perl中的设计模式革新:命令模式的实现与应用

Perl中的设计模式革新&#xff1a;命令模式的实现与应用 在面向对象编程中&#xff0c;设计模式是解决特定问题的成熟模板。命令模式作为行为设计模式之一&#xff0c;它将请求封装为对象&#xff0c;从而允许用户根据不同的请求对客户进行参数化。本文将深入探讨如何在Perl中…...

Java8-求两个集合取交集

在Java8中&#xff0c;求两个集合的交集可以使用不同的三种方式&#xff1a;传统的循环遍历、使用Stream API的filter操作和使用Stream API的Collection操作。 方法一&#xff1a;传统的循环遍历 首先&#xff0c;我们创建两个集合list1和list2&#xff0c;并给它们添加一些元…...

爬虫学习4:爬取王者荣耀技能信息

爬虫&#xff1a;爬取王者荣耀技能信息&#xff08;代码和代码流程&#xff09; 代码 # 王者荣耀英雄信息获取 import time from selenium import webdriver from selenium.webdriver.common.by import By if __name__ __main__:fp open("./honorKing.txt", "…...

在Ubuntu 14.04上安装和使用Memcache的方法

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。 简介 随着您的网站的增长和流量的增加&#xff0c;最快显示压力的组件之一是后端数据库。如果您的数据库没有分布式和配置来处理高负载…...

PCDN技术如何降低运营成本?

PCDN技术通过以下几种方式降低运营商的运营成本: 1.利用用户设备作为缓存节点: PCDN技术将用户设备纳入内容分发网络&#xff0c;利用这些设备的闲置带宽和存储资源来缓存和分发内容。这种方式不需要运营商投入大量的高成本服务器和带宽资源&#xff0c;从而降低了硬件和带宽…...

服务器数据恢复—V7000存储硬盘故障脱机的数据恢复案例

服务器存储数据恢复环境&#xff1a; 某品牌P740小型机AIXSybaseV7000磁盘阵列柜&#xff0c;磁盘阵列柜中有12块SAS机械硬盘&#xff08;其中包括一块热备盘&#xff09;。 服务器存储故障&#xff1a; 磁盘阵列柜中有一块磁盘出现故障&#xff0c;运维人员用新硬盘替换掉故障…...

BSV区块链在人工智能时代的数字化转型中的角色

​​发表时间&#xff1a;2024年6月13日 企业数字化转型已有约30年的历史&#xff0c;而人工智能&#xff08;以下简称AI&#xff09;将这种转型提升到了一个全新的高度。这并不难理解&#xff0c;因为AI终于使企业能够发挥其潜力&#xff0c;实现更宏大的目标。然而&#xff0…...

android audio 相机按键音:(二)加载与修改

相机按键音资源&#xff0c;加载文件路径&#xff1a; frameworks/av/services/camera/libcameraservice/CameraService.cpp 按键音&#xff0c;加载函数&#xff1a; void CameraService::loadSoundLocked(sound_kind kind) { ATRACE_CALL(); LOG1("Cam…...

Linux grep技巧 提取log中的json数据

目录 一. 前提1.1 数据准备1.2 需求1.3 分析 二. 数据提取2.1 提取所有的json数据2.2 提取子项目的全部json数据2.3 提取指定项目的json数据 一. 前提 1.1 数据准备 545-1 2024/07/20 18:20:21 [ERROR] MPX001 eventControlleraupay transactionIdA545 {"event":&q…...

HDShredder 7 企业版案例分享: 依照国际权威标准,安全清除企业数据

HDShredder 7 企业版用户案例 天津鸿萌科贸发展有限公司是德国 Miray 公司 HDShredder 数据清除软件的授权代理商。近日&#xff0c;上海某网络科技有限公司采购 HDShredder 7 企业版x4&#xff0c;为公司数据存储资产的安全清除工作流程配备高效的执行工具。HDShredder 7 企业…...

centos系统使用mysqldump数据备份与恢复

文章目录 使用mysqldump备份数据库一、数据库备份1. 基础备份2. 额外选项(一般组合使用) 二、数据库恢复 使用mysqldump备份数据库 一、数据库备份 1. 基础备份 #备份单个数据库 mysqldump -u 用户名 -p 数据库名 > 备份文件.sql#备份多个数据库 mysqldump -u 用户名 -p …...

【element ui】input输入控件绑定粘贴事件,从 Excel 复制的数据粘贴到输入框(el-input)时自动转换为逗号分隔的数据

目录 1、需求2、实现思路:3、控件绑定粘贴事件事件修饰符说明: 4、代码实现&#x1f680;写在最后 1、需求 在 Vue 2 和 Element UI 中&#xff0c;要实现从 Excel 复制空格分隔的数据&#xff0c;并在粘贴到输入框&#xff08;el-input&#xff09;时自动转换为逗号分隔的数据…...

Chapter18 基于物理的渲染——Shader入门精要学习

Chapter18 基于物理的渲染 一、PBS理论和数学基础1.光是什么微表面模型 2.渲染方程3.精确光源4.双向反射分布函数 BRDF5.漫反射项&#xff08;Lambert 模型&#xff09;Lambertian BRDF为&#xff1a;Disney BRDF中漫反射项 6.高光反射项微面元理论BRDF的高光反射项①菲涅尔反射…...

DolphinScheduler学习

1.查看文档 点击访问&#xff1a;https://dolphinscheduler.apache.org/zh-cn/docs 我们可以看到相关的文档简介里有 介绍 DolphinScheduler是Apache DolphinScheduler 是一个分布式易扩展的可视化DAG工作流任务调度开源系统。适用于企业级场景&#xff0c;提供了一个可视化…...

我用Tauri开发的待办效率工具开源了!

开源仓库地址 gitee Git仓库地址:https://gitee.com/zhanhongzhu/zhanhongzhu.git 应用地址 windows应用地址下载 https://kestrel-task.cn 具体内容 也可以看&#x1f389;使用Taurivitekoa2mysql开发了一款待办效率应用 这篇文章。 &#x1f4bb;技术栈 Tauri: Tauri…...

【黑科技】:Laravel 项目性能提升 20 倍

令人激动的黑科技&#xff1a;Laravel 项目性能提升 20 倍 这个项目能够在无需修改任何代码且无需第三方扩展的前提下&#xff0c;将你的 Laravel 项目性能提高 20 倍。它仅依赖于 PHP 原生的 pcntl、posix、fiber 和 sockets。 项目灵感 起因是看到官方发布的 PHP 8.1 更新…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...