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

找工作准备刷题Day10 回溯算法 (卡尔41期训练营 7.24)

回溯算法今天这几个题目做过,晚上有面试,今天水一水。

第一题:Leetcode77. 组合

题目描述

解题思路

从题目示例来看,k个数是不能重合的,但是题目没有明确说明这一点。

使用回溯算法解决此问题,利用树形结构。

回溯算法终止条件:有了k个数;

遍历过程:由于k个数不能重合,需要使用一个变量来标志遍历从何处开始。

题解

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

优化方式

剪枝:i从now遍历到n - (k - path.size()) + 1,而不是遍历到 n。这个式子确定方法:假设n为9,k为3,在开始时path为空,第一次遍历是从 1~7,7正好是9-3+1。(说白了,这里只需要举个例子,就能知道n-(k-path,size())后面需要加个1。

第二题:216. 组合总和 III

题目描述

解题思路

需要从1~9中选出所有 k个不重复组合、k个数字之和为n。

在回溯时,需要目标和n、现在的和 NowSum作为函数参数,还需要startNumber表示遍历开始位置。

题解

class Solution {
public:vector<vector<int>> ans;vector<int> path;vector<vector<int>> combinationSum3(int k, int n) {bT(n, k, 1, 0);return ans;}// targetSum为目标总和,k为数字个数,startNumber为遍历开始数字,NowSum为现在总和void bT(int targetSum, const int k, int startNumber, int NowSum) {if (path.size() == k && targetSum == NowSum) {ans.push_back(path);return;}if (path.size() >= k || NowSum > targetSum)return;for (int i = startNumber; i <= 9 - (k - path.size()) + 1; i++) {path.push_back(i);bT(targetSum, k, i + 1, NowSum + i);path.pop_back();}}
};

技巧

剪枝:当遍历的数字大于等于k 或者现有的数字和已经超过targetSum时,可以不继续遍历(这一步需要在检查数字和为targetSum之后);i遍历不用从startNumber到9,而是 9-(k-path.size())+1,同第一题,举个例子就行。

回溯技巧:利用函数传值,不用修改NowSum,而是在NowSum+i(雕虫小技)。

第三题:Leetcode17. 电话号码的字母组合

题目描述

解题思路

对于digits的每一位数字,依次遍历即可。需要一个变量标志目前遍历到哪一位。

对于每个数字对应的字母,由于数字是以string形式给定,所以使用unordered_map<char,string>存储。

由于存在digits为0,因此,在调用回溯之前先判断digits。

题解

class Solution {
public:vector<string> ans;string str;unordered_map<char, string> ump;vector<string> letterCombinations(string digits) {if (digits.length() == 0)returnump['2'] = "abc";ump['3'] = "def";ump['4'] = "ghi";ump['5'] = "jkl";ump['6'] = "mno";ump['7'] = "pqrs";ump['8'] = "tuv";ump['9'] = "wxyz";backTracking(digits, 0);return ans;}void backTracking(const string digits, int startIdx) {if (str.length() == digits.length()) {ans.push_back(str);return;}for (int i = 0; i < ump[digits[startIdx]].length(); i++) {str.push_back(ump[digits[startIdx]][i]);backTracking(digits, startIdx + 1);str.pop_back();}}
};

相关文章:

找工作准备刷题Day10 回溯算法 (卡尔41期训练营 7.24)

回溯算法今天这几个题目做过&#xff0c;晚上有面试&#xff0c;今天水一水。 第一题&#xff1a;Leetcode77. 组合 题目描述 解题思路 从题目示例来看&#xff0c;k个数是不能重合的&#xff0c;但是题目没有明确说明这一点。 使用回溯算法解决此问题&#xff0c;利用树形…...

如何有效的进行小程序的优化

如今小程序已经成为了许多开发者开展业务&#xff0c;提供服务的重要平台 。所以如何有效的优化小程序成为了开发者关注的首要问题&#xff0c;以下是一份详细的小程序优化方案&#xff1a; 一、目标设定 明确小程序优化的主要目标&#xff0c;例如提高用户留存率、增加用户活…...

FPGA-ROM IP核的使用(2)

前言 接着昨天的进行一个小的实验验证ROM IP核。 实验效果 读取上一期生成的IP核中的数据&#xff0c;并将其显示在数码管上。 具体流程 ROM IP核存放数据0~255&#xff0c;之后每隔0.2s&#xff0c;从0的地址开始读数据&#xff0c;并显示在数码管上&#xff1b;接着先后…...

Manticore Search(es轻量级替代)

概念&#xff1a; Manticore Search 是一个使用 C 开发的高性能搜索引擎&#xff0c;创建于 2017 年&#xff0c;其前身是 Sphinx Search 。Manticore Search 充分利用了 Sphinx&#xff0c;显着改进了它的功能&#xff0c;修复了数百个错误&#xff0c;几乎完全重写了代码并保…...

测试开发面试题---计算机网络

计算机网络模型 OSI模型&#xff1a;七层模型 物理层&#xff1a;定义电气特征&#xff0c;机械特征等功能规范&#xff0c;传递实际比特流数据链路层&#xff1a;物理地址寻址&#xff08;MAC&#xff09;&#xff0c;帧的传输&#xff0c;错误检测和纠正网络层&#xff1a;…...

Wonder3D 论文学习

论文链接&#xff1a;https://arxiv.org/abs/2310.15008 代码链接&#xff1a;https://github.com/xxlong0/Wonder3D 解决了什么问题&#xff1f; 随着扩散模型的提出&#xff0c;3D 生成领域取得了长足进步。从单张图片重建出 3D 几何是计算机图形学和 3D 视觉的基础任务&am…...

【MySQL进阶之路 | 高级篇】显式事务和隐式事务

使用事务有两种方式&#xff1a;显式事务和隐式事务。 1. 显式事务 步骤1&#xff1a; START TRANSACTION或者BEGIN&#xff0c;作用是显式开启一个事务。 START TRANSACTION语句相较于BEGIN特别之处在于&#xff0c;后面能跟几个修饰符。比如&#xff1a; READ ONLY&…...

Ruby、Python、Java 开发者必备:Codigger之软件项目体检

在编程的广阔天地里&#xff0c;Ruby、Python 和 Java 开发者们各自凭借着独特的语言特性&#xff0c;构建着精彩纷呈的应用世界。然而&#xff0c;无论使用哪种语言&#xff0c;确保项目的高质量始终是至关重要的目标。而 Codigger 项目体检则成为了实现这一目标的得力助手&am…...

day05 Router、vuex、axios

配置 router和vuex需要在创建vue项目的时候&#xff0c;开始的时候选择Manually select features&#xff0c;于是就可以在下一个创建配置讯问中选择router和vuex。 axios则需要执行命令行&#xff1a; npm install axios -S 之后再在需要发送请求的view导入即可。 router…...

yolov5-7在opencv里跑自己的onnx模型

先把模型放在如下目录 运行如下代码 import cv2 import numpy as npclass Onnx_clf:def __init__(self, onnx:strdnn_model1/plane02.onnx, img_size640, classlist:list[plane]) -> None: func: 读取onnx模型,并进行目标识别para onnx:模型路径img_size:输出图片大小,和模…...

JVM 11 的优化指南:如何进行JVM调优,JVM调优参数有哪些

这篇文章将详细介绍如何进行JVM 11调优&#xff0c;包括JVM 11调优参数及其应用。此外&#xff0c;我将提供12个实用的代码示例&#xff0c;每个示例都会结合JVM启动参数和Java代码。 本文已收录于&#xff0c;我的技术网站 java-broke.site&#xff0c;有大厂完整面经&#x…...

nginx的配置和使用

一、nginx支持win和linux版本的下载&#xff0c;选择合适的版本进行安装 二、配置文件注解 重点的几个参数进行注释&#xff1a; 1、listen 要监听的服务的端口&#xff0c;符合这个端口的才会被监听 server_name要监听的服务地址&#xff0c;可能是ip,也可能是域名&#xf…...

mysql面试(六)

前言 本章节详细讲解了一下mysql执行计划相关的属性释义&#xff0c;以及不同sql所出现的不同效果 执行计划 一条查询语句经过mysql查询优化器的各种基于成本和各种规则优化之后&#xff0c;会生成一个所谓的 执行计划&#xff0c;这个执行计划展示了这条查询语句具体查询方…...

6.乳腺癌良性恶性预测(二分类、逻辑回归、PCA降维、SVD奇异值分解)

乳腺癌良性恶性预测 1. 特征工程1.1 特征筛选1.2 特征降维 PCA1.3 SVD奇异值分解 2. 代码2.1 逻辑回归、二分类问题2.2 特征降维 PCA2.3 SVD奇异值分解 1. 特征工程 专业上&#xff1a;30个人特征来自于临床一线专家&#xff0c;每个特征和都有医学内涵&#xff1b;数据上&…...

Vue3响应式高阶用法之markRaw()

Vue3响应式高阶用法之markRaw() 文章目录 Vue3响应式高阶用法之markRaw()一、简介二、使用场景2.1 避免性能开销2.2 防止意外修改 三、基本使用3.1 标记对象 四、功能详解4.1 markRaw与reactive的区别4.2 markRaw与ref的区别 五、最佳实践及案例5.1 使用大型第三方库对象5.2 静…...

免费SSL证书的安全性与获取指南

SSL证书是一种数字凭证&#xff0c;用于加密用户与网站之间的信息交换&#xff0c;以确保传输的数据不被第三方窃取。它像是一个数字版的密封印章&#xff0c;为数据的传输过程提供了一层保护膜。 免费的SSL证书通常由CA机构提供&#xff0c;它们同样可以提供基础数据的加密服…...

【CN】Argo 持续集成和交付(一)

1.简介 Argo 英 [ˈɑ:ɡəu] 美 [ˈɑrˌɡo] Kubernetes 原生工具&#xff0c;用于运行工作流程、管理集群以及正确执行 GitOps。 Argo 于 2020 年 3 月 26 日被 CNCF 接受为孵化成熟度级别&#xff0c;然后于 2022 年 12 月 6 日转移到毕业成熟度级别。 argoproj.github.i…...

Unity3D 自定义Debug双击溯源问题详解

前言 在Unity3D的开发过程中&#xff0c;经常需要处理各种交互和事件&#xff0c;其中双击事件是常见的需求之一。然而&#xff0c;由于Unity自带的双击检测机制并不完善&#xff0c;开发者往往需要自定义实现以满足特定需求。本文将详细介绍如何在Unity3D中自定义Debug双击溯…...

环境搭建-Docker搭建ClickHouse

Docker搭建ClickHouse 一、前言二、ClickHouse安装2.1 拉取镜像运行ClickHouse服务 三、测试安装3.1 进入clickhouse容器3.2 命令补充说明 四、测试连接五、设置CK的用户名密码 一、前言 本文使用的Docker使用Windows搭建&#xff0c;Linux版本的搭建方式一样。 Windows系统搭…...

深入理解CSS中的变量(概念篇)

CSS变量,也称为自定义属性,是一种在CSS中定义和重用值的方式。它们允许开发者在一个地方定义样式值,然后在整个样式表中引用这些值,从而提高代码的可维护性和可读性。 1、定义和使用CSS变量 CSS变量的定义和使用非常简单。变量名以两个连字符开头,变量值为任何有效的CSS…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...