当前位置: 首页 > 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 更新…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...