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

代码随想录训练营第二十三天 39组合总和 40组合总和II 131分割回文串

第一题:
原题链接:39. 组合总和 - 力扣(LeetCode)

思路:

终止条件:

用一个sum值来记录当前组合中元素的总和。当sum的值大于target的时候证明该组合不合适,直接return。当sum的值等于target的时候将组合添加到组合集合中。

for循环中注意本题中的元素是可以重复选取的,因此下层递归中的startIndex还是i。

剩下的就是回溯的模板。

代码如下:

class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {if(candidates.size() == 0) return {};backtracking(candidates, target, 0, 0);return res;}
private:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex){if(sum > target){return;}if(sum == target){res.push_back(path);return;}for(int i = startIndex; i < candidates.size(); i++){path.push_back(candidates[i]);sum += candidates[i];backtracking(candidates, target, sum, i);sum -= candidates[i];path.pop_back();}}
};

第二题:

原题链接:40. 组合总和 II - 力扣(LeetCode)

思路:

本题要注意的是去重的逻辑。

首先我们对数组进行排序,让相同的元素紧挨着。方便我们进行去重的逻辑。

Carl提到了树层和树枝去重的概念,这个概念很便于理解。本题要注意的就是树层去重的逻辑。树枝上不需要去重,因为树枝上的元素对应的是不同的元素。而树层上的元素必须要去重,因为在树枝上前一个相同的元素的遍历会包含当前元素的所有遍历结果,因此如果在同一层中当前的元素和前一个元素相同并且前一个元素没有被使用过的情况下,该元素直接跳过。

同时我们需要一个bool类型的数组来记得什么元素已经使用过了。当我们使用过的话将该数组对应的位置置为true;

代码如下:

class Solution {
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());vector<bool> used(candidates.size(), false);backtracking(candidates, target, 0, 0, used);return res;}
private:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used){if(sum > target)return;if(sum == target){res.push_back(path);return;}for(int i = startIndex; i < candidates.size(); i++){if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false){continue;}path.push_back(candidates[i]);used[i] = true;sum += candidates[i];backtracking(candidates, target, sum, i + 1, used);used[i] = false;sum -= candidates[i];path.pop_back(); }}
};

第三题:

原题链接:131. 分割回文串 - 力扣(LeetCode)

思路:

需要一根指针来指向当前分割的位置。

for循环是用来看在以startIndex为分割线,以i为结束的子串是否为回文串。

在递归的逻辑中是将startIndex的位置向后移动一位。

代码如下:

class Solution {
public:vector<vector<string>> partition(string s) {backtracking(s, 0);return res;}
private:vector<vector<string>> res;vector<string> path;void backtracking(string s, int startIndex){if(startIndex == s.size()){res.push_back(path);return;}for(int i = startIndex; i < s.size(); i++){if(!isHuiwen(s, startIndex, i)) continue;string st = s.substr(startIndex, i - startIndex + 1);path.push_back(st);backtracking(s, i + 1);path.pop_back();}}bool isHuiwen(const string& s, int start, int end){while(start < end){if(s[start] == s[end]){start++;end--;}else{return false;}}return true;}
};

相关文章:

代码随想录训练营第二十三天 39组合总和 40组合总和II 131分割回文串

第一题&#xff1a; 原题链接&#xff1a;39. 组合总和 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 终止条件&#xff1a; 用一个sum值来记录当前组合中元素的总和。当sum的值大于target的时候证明该组合不合适&#xff0c;直接return。当sum的值等于target的…...

【C++】数组、字符串

六、数组、字符串 讨论数组离不开指针&#xff0c;指针基本上就是数组的一切的基础&#xff0c;数组和指针的相关内容参考我的C系列博文&#xff1a;【C语言学习笔记】四、指针_通过变量名访问内存单元中的数据缺点-CSDN博客【C语言学习笔记】三、数组-CSDN博客 1、数组就是&…...

MySQL InnoDB支持几种行格式

数据库表的行格式决定了一行数据是如何进行物理存储的&#xff0c;进而影响查询和DML操作的性能。 在InnoDB中&#xff0c;常见的行格式有4种&#xff1a; 1、COMPACT&#xff1a;是MySQL 5.0之前的默认格式&#xff0c;除了保存字段值外&#xff0c;还会利用空值列表保存null…...

Day6: 344.反转字符串 541. 反转字符串II 卡码网:54.替换数字

题目344. 反转字符串 - 力扣&#xff08;LeetCode&#xff09; void reverseString(vector<char>& s) {int len s.size();int left 0;int right len - 1;while (left < right){swap(s[left], s[right--]);}return;} 题目541. 反转字符串 II - 力扣&#xff0…...

kubekey 离线安装高可用 kubernetes 集群

1. 准备环境 版本&#xff1a; kubernetes: v1.29.2 kubesphere: v3.4.1 kubekey: v3.1.1 说明&#xff1a; kubekey 只用于安装 kubernetes&#xff0c;因为 kubesphere 的配置在安装时经常需要变动&#xff0c;用 ks-installer 的 yaml 文件更好管理&#xff1b;ks-installe…...

大数据面试题之Hive(2)

目录 Hive的join操作原理&#xff0c;leftjoin、right join、inner join、outer join的异同? Hive如何优化join操作 Hive的mapjoin Hive语句的运行机制&#xff0c;例如包含where、having、group by、orderby&#xff0c;整个的执行过程? Hive使用的时候会将数据同步到HD…...

求推荐几款http可视化调试工具?

Postman 非常流行的API调试工具&#xff0c;适用于构建、测试和文档化APIs。它支持各种HTTP方法&#xff0c;有强大的集合和环境管理功能&#xff0c;以及代码生成能力。 BB-API 是一款旨在提升开发效率的工具&#xff0c;它专注于提供简约、完全免费且功能强大的HTTP模拟请…...

Python逻辑控制语句 之 判断语句--if else结构

1.if else 的介绍 if else &#xff1a;如果 ... 否则 .... 2.if else 的语法 if 判断条件: 判断条件成立&#xff0c;执行的代码 else: 判断条件不成立&#xff0c;执行的代码 &#xff08;1&#xff09;else 是关键字, 后⾯需要 冒号 &#xff08;2&#xff09;存在冒号…...

word2016中新建页面显示出来的页面没有页眉页脚,只显示正文部分。解决办法

问题描述&#xff1a;word2016中新建页面显示出来的页面没有页眉页脚&#xff0c;只显示正文部分。设置了页边距也不管用。 如图1 图1 解决&#xff1a; 点击“视图”——“多页”——“单页”&#xff0c;即可。如图2操作 图2 结果展示&#xff1a;如图3 图3...

8.javaSE基础进阶_泛型generics(无解通配符?+上下界统配符superextends)

文章目录 泛型generics一.泛型简介二.泛型类1.泛型方法 三.泛型接口四.泛型进阶1.*<?>无解通配符*2.上界通配符 < ? extends E>3.下界通配符 < ? super E>4.泛型擦除 泛型generics 一.泛型简介 JDK5引入,一种安全机制,编译时检测不匹配类型 特点: 将数…...

酒店客房管理系统(Java+MySQL)

技术栈 Java: 作为主要编程语言。Swing GUI: 用于开发图形用户界面。MySQL: 作为数据库管理系统。JDBC: 用于连接和操作MySQL数据库。 功能要点 管理登录认证 系统提供管理员登录认证功能。通过用户名和密码验证身份&#xff0c;确保只有授权的用户可以访问和管理酒店客房信…...

S32K3 --- Wdg(内狗) Mcal配置

前言 看门狗的作用是用来检测程序是否跑飞,进入死循环。我们需要不停地喂狗,来确保程序是正常运行的,一旦停止喂狗,意味着程序跑飞,超时后就会reset复位程序。 一、Wdg 1.1 WdgGeneral Wdg Disable Allowed : 启用此参数后,允许在运行的时候禁用看门狗 Wdg Enable User…...

LeetCode 算法:二叉树的层序遍历 c++

原题链接&#x1f517;&#xff1a;二叉树的层序遍历 难度&#xff1a;中等⭐️⭐️ 题目 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;roo…...

博途TIA Portal「集成自动化软件」下载安装,TIA Portal 灵活多变的编程环境

在编程领域&#xff0c;博途TIA Portal以其卓越的编程工具和灵活多变的编程环境&#xff0c;为众多用户提供了前所未有的便利。这款软件不仅支持多种编程语言&#xff0c;如梯形图&#xff08;Ladder Diagram&#xff09;、功能块图&#xff08;Function Block Diagram&#xf…...

火了10年的电脑监控软件有哪些?盘点8款热门的电脑监控软件

电脑监控软件领域经历了多年的发展&#xff0c;一些软件因为其稳定的功能、良好的用户体验和不断更新的技术支持&#xff0c;得以在市场上保持长期的热度和用户基础。以下是几款在过去十年里广受好评且持续流行的内网监控软件&#xff1a; 1.安企神&#xff1a;由河北安企神网络…...

入门Java爬虫:认识其基本概念和应用方法

Java爬虫初探&#xff1a;了解它的基本概念与用途&#xff0c;需要具体代码示例 随着互联网的快速发展&#xff0c;获取并处理大量的数据成为企业和个人不可或缺的一项任务。而爬虫&#xff08;Web Scraping&#xff09;作为一种自动化的数据获取方法&#xff0c;不仅能够快速…...

Flask新手入门(一)

前言 Flask是一个用Python编写的轻量级Web应用框架。它最初由Armin Ronacher作为Werkzeug的一个子项目在2010年开发出来。Werkzeug是一个综合工具包&#xff0c;提供了各种用于Web应用开发的工具和函数。自发布以来&#xff0c;Flask因其简洁和灵活性而迅速受到开发者的欢迎。…...

Grafana-11.0.0 在线部署教程

Grafana-11.0.0 在线部署教程 环境&#xff1a; 操作系统&#xff1a; ubuntugrafana版本&#xff1a; 11.0.0 &#xff08;建议不要按照最新版&#xff09;grafana要求的系统配置不高&#xff0c;建议直接部署在监控服务器上&#xff0c;比如zabbix服务器、prometheus服务器…...

pytorch-01

加载mnist数据集 one-hot编码实现 import numpy as np import torch x_train np.load("../dataset/mnist/x_train.npy") # 从网站提前下载数据集&#xff0c;并解压缩 y_train_label np.load("../dataset/mnist/y_train_label.npy") x torch.tensor(y…...

梦想CAD二次开发

1.mxdraw简介 mxdraw是一个HTML5 Canvas JavaScript框架&#xff0c;它在THREE.js的基础上扩展开发&#xff0c;为用户提供了一套在前端绘图更为方便&#xff0c;快捷&#xff0c;高效率的解决方案&#xff0c;mxdraw的实质为一个前端二维绘图平台。你可以使用mxdraw在画布上绘…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Swagger和OpenApi的前世今生

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

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

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