(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 循环横向遍历,递归纵向遍历 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安装
接上一篇,继续安装istio的dashboard。 先到istio-1.22.0/samples/addons目录下,把yaml文件中的镜像仓库地址修改了,修改地址参考我之前写的CSDN里的镜像对照表。不然直接执行kubectl apply -f samples/addons这个命令后,依据会出…...

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

Apollo 配置中心的部署与使用经验
前言 Apollo(阿波罗)是携程开源的分布式配置管理中心。 本文主要介绍其基于 Docker-Compose 的部署安装和一些使用的经验 特点 成熟,稳定支持管理多环境/多集群/多命名空间的配置配置修改发布实时(1s)通知到应用程序支…...
Perl中的设计模式革新:命令模式的实现与应用
Perl中的设计模式革新:命令模式的实现与应用 在面向对象编程中,设计模式是解决特定问题的成熟模板。命令模式作为行为设计模式之一,它将请求封装为对象,从而允许用户根据不同的请求对客户进行参数化。本文将深入探讨如何在Perl中…...
Java8-求两个集合取交集
在Java8中,求两个集合的交集可以使用不同的三种方式:传统的循环遍历、使用Stream API的filter操作和使用Stream API的Collection操作。 方法一:传统的循环遍历 首先,我们创建两个集合list1和list2,并给它们添加一些元…...

爬虫学习4:爬取王者荣耀技能信息
爬虫:爬取王者荣耀技能信息(代码和代码流程) 代码 # 王者荣耀英雄信息获取 import time from selenium import webdriver from selenium.webdriver.common.by import By if __name__ __main__:fp open("./honorKing.txt", "…...
在Ubuntu 14.04上安装和使用Memcache的方法
前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。 简介 随着您的网站的增长和流量的增加,最快显示压力的组件之一是后端数据库。如果您的数据库没有分布式和配置来处理高负载…...
PCDN技术如何降低运营成本?
PCDN技术通过以下几种方式降低运营商的运营成本: 1.利用用户设备作为缓存节点: PCDN技术将用户设备纳入内容分发网络,利用这些设备的闲置带宽和存储资源来缓存和分发内容。这种方式不需要运营商投入大量的高成本服务器和带宽资源,从而降低了硬件和带宽…...

服务器数据恢复—V7000存储硬盘故障脱机的数据恢复案例
服务器存储数据恢复环境: 某品牌P740小型机AIXSybaseV7000磁盘阵列柜,磁盘阵列柜中有12块SAS机械硬盘(其中包括一块热备盘)。 服务器存储故障: 磁盘阵列柜中有一块磁盘出现故障,运维人员用新硬盘替换掉故障…...

BSV区块链在人工智能时代的数字化转型中的角色
发表时间:2024年6月13日 企业数字化转型已有约30年的历史,而人工智能(以下简称AI)将这种转型提升到了一个全新的高度。这并不难理解,因为AI终于使企业能够发挥其潜力,实现更宏大的目标。然而࿰…...
android audio 相机按键音:(二)加载与修改
相机按键音资源,加载文件路径: frameworks/av/services/camera/libcameraservice/CameraService.cpp 按键音,加载函数: 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 数据清除软件的授权代理商。近日,上海某网络科技有限公司采购 HDShredder 7 企业版x4,为公司数据存储资产的安全清除工作流程配备高效的执行工具。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、代码实现🚀写在最后 1、需求 在 Vue 2 和 Element UI 中,要实现从 Excel 复制空格分隔的数据,并在粘贴到输入框(el-input)时自动转换为逗号分隔的数据…...

Chapter18 基于物理的渲染——Shader入门精要学习
Chapter18 基于物理的渲染 一、PBS理论和数学基础1.光是什么微表面模型 2.渲染方程3.精确光源4.双向反射分布函数 BRDF5.漫反射项(Lambert 模型)Lambertian BRDF为:Disney BRDF中漫反射项 6.高光反射项微面元理论BRDF的高光反射项①菲涅尔反射…...

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

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

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

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

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出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多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...

SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

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