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

leetcode 热题100(131. 分割回文串)c++

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

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 

回文串

 。返回 s 所有可能的分割方案。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

思路

        首先一看到数据范围这么小,很明显就是要我们dfs搜索的,然后这题还是求最大回文串的,那么我们知道肯定得先判断一下当前数组是否是回文串,不是的话就不添加,否则就添加进去。

判断回文串我们知道可以用记忆化搜索,如果我们之前搜过了当前子串,我们可以给他赋值1和-1,

1表示当前子串是回文串,-1表示不是,这样子我们就可以很快的判断是否是回文串了,就直接套回溯dfs模板直接写即可

代码

class Solution {
public:vector<vector<string>> res;vector<string> ans;int n;int f[18][18];void dfs(int p,string s){cout<<p<<endl;if(p>=s.size()){    //已经到达右端点无需遍历了,直接添加res.push_back(ans);return;}for(int i=1;i<=n;i++){//表示枚举的长度if(p+i<=n && isflag(p,p+i-1,s)==1){ //当前子串是回文串, ans.push_back(s.substr(p,i));dfs(p+i,s);ans.pop_back();}}}int isflag(int i,int j,string s){if(f[i][j]) return f[i][j];if(i>=j) return f[i][j]=1;return f[i][j]=(s[i]==s[j])?isflag(i+1,j-1,s):-1;}vector<vector<string>> partition(string s) {n = s.size();dfs(0,s);return res;}};

相关文章:

leetcode 热题100(131. 分割回文串)c++

链接&#xff1a;131. 分割回文串 - 力扣&#xff08;LeetCode&#xff09; 给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。 示例 1&#xff1a; 输入&#xff1a;s "aab" 输出&#xff…...

vs2022编译opencv 4.10.0

参考&#xff1a;Windosw下Visual Studio2022编译OpenCV与参考区别在于&#xff0c;没有用cmake GUI&#xff0c;也没有创建build目录&#xff0c;直接用vs2022打开了C:\code\opencv目录&#xff0c;即CMakeLists.txt所在根目录。没有修改默认下载地址&#xff0c;采用手动下载…...

Bash 中的 2>1 | tee 命令详解

Bash 中的 2>&1 | tee 命令详解 在 Linux 和 Unix 系统中&#xff0c;命令行提供了强大的输出控制功能&#xff0c;能够灵活地处理标准输入&#xff08;stdin&#xff09;、标准输出&#xff08;stdout&#xff09;和标准错误&#xff08;stderr&#xff09;。本文将详…...

MySQL数据库的日志

一、概论 日志&#xff08;log&#xff09;是一种记录系统运行时各种状态和事件的文件。 它通常用于系统监控、故障排查、安全审计和性能分析。日志文件可以记录用户操作、系统错误、应用程序行为等信息。日志文件通常包含时间戳、事件类型、事件描述等关键信息&#xff0c;以…...

DataCap 2024.4.1 版本发布:MongoDB 驱动支持、工作流引擎升级

尊敬的 DataCap 用户&#xff1a; DataCap 2024.4.1 版本现已正式发布。本次更新包含多项重要功能升级和性能优化&#xff0c;现将主要更新内容公布如下&#xff1a; 核心功能升级 数据库功能增强 (实现功能) 新增数据库管理功能&#xff1a;支持创建、删除和切换数据库完善表…...

二十三种设计模式-单例模式

单例模式&#xff08;Singleton&#xff09;&#xff1a;确保一个类只有一个实例&#xff0c;并提供一个全局访问点。 单例模式两种实现方法&#xff1a;懒汉式和饿汉式。 懒汉式&#xff08;Lazy Initialization&#xff09; 懒汉式单例模式在第一次被使用时才创建实例&…...

【微服务】SpringBoot 国际化适配方案使用详解

目录 一、前言 二、国际化概述 2.1 微服务中的国际化是什么 2.1.1 国际化概念 2.1.2 为什么需要国际化 2.2 微服务中常用的国际化方法 2.2.1 资源文件分离 2.2.2 使用国际化框架 2.2.3 使用动态模板 2.2.4 使用数据库存储 2.2.5 API设计结合配置中心 三、SpringBoot…...

太阳能电池板缺陷识别数据集,使用yolo,coco json,pasical voc xml格式标注,可识别旁路二极管,电池故障,热点,2234张原始图片

太阳能电池板缺陷识别数据集&#xff0c;使用yolo&#xff0c;coco json&#xff0c;pasical voc xml格式标注&#xff0c;可识别旁路二极管,电池故障,热点,2234张原始图片 以下是该项目的一些用例&#xff1a; 太阳能发电厂监控&#xff1a;该模型可用于自动化检查和识别大型…...

客户案例:基于慧集通平台集成打通小满CRM+金蝶云星空+钉钉

一、引言 本案例原型公司是一家生物科技公司&#xff0c;公司自开创以来专注于体外诊断生物活性原材料的研究、生产、销售和服务&#xff0c;致力于为全球体外诊断试剂生产企业提供领先且具有竞争力的核心原料和相关辅助产品服务。公司以卓越的产品和优质的服务赢得了客户的广…...

ubuntu 如何使用vrf

在Ubuntu或其他Linux系统中&#xff0c;您使用ip命令和sysctl命令配置的网络和内核参数通常是临时的&#xff0c;这意味着在系统重启后这些配置会丢失。为了将这些配置持久化&#xff0c;您需要采取一些额外的步骤。 对于ip命令配置的网络接口和路由&#xff0c;您可以将这些配…...

Debian-linux运维-ssh配置(兼容Jenkins插件的ssh连接公钥类型)

系统版本&#xff1a;Debian 12.5、11.1 1 生成密钥对 可以用云服务商控制台生成的密钥对&#xff0c;也可以自己在客户端或者服务器上生成&#xff0c; 已经有密钥对就可以跳过这步 用户默认密钥文件路径为 ~/.ssh/id_rsa&#xff0c;可以在交互中指定路径&#xff0c;也可…...

K8S详解(5万字详细教程)

目录 ​编辑 一、集群管理命令 二、命名空间 1. 获取命名空间列表 2. 创建命名空间 3. 删除命名空间 4. 查看命名空间详情 三、Pod 1. Pod概述 2. Pod相位状态 3. 管理命令 3.1 获取命名空间下容器(pod)列表 3.2 查看pod的详细信息 3.3 创建 && 运行 3.4 …...

Redis6为什么引入了多线程?

大家好&#xff0c;我是锋哥。今天分享关于【Redis6为什么引入了多线程&#xff1f;】面试题。希望对大家有帮助&#xff1b; Redis6为什么引入了多线程&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 Redis 6 引入了多线程的主要目的是提高性能&#…...

KMP 2024 年总结,Kotlin 崛起的一年

2024 Google I/O 上正式官宣了 KMP&#xff08;Kotlin Multiplatform&#xff09;项目&#xff0c;它是 Google Workspace 团队的一项长期「投资」项目&#xff0c;由 JetBrains 开发维护和开源的项目&#xff0c;简单来说&#xff0c;JetBrains 主导&#xff0c;Google Worksp…...

leecode188.买卖股票的最佳时机IV

这道题目我在买卖股票III就已经得出规律了&#xff0c;具体可看买卖股票的最佳时机||| class Solution { public:int maxProfit(int k, vector<int>& prices) {int nprices.size();vector<vector<int>> dp(n,vector<int>(2*k1,0));for(int j1;j&l…...

分布式消息队列RocketMQ

一、RocketMQ概述 1.1 MQ 概述 MQ&#xff0c;Message Queue&#xff0c;是一种提供消息队列服务的中间件&#xff0c;也成为消息中间件&#xff0c;是一套提供了消息生产、存储、消费全过程API的软件系统。消息即数据 1.2 MQ 用途 MQ的用途总结起来可分为以下三点 限流削峰…...

诗韵--代码之外的生活:2025 元旦歌

2025 元旦歌 1 说明2 正文3 简评 1 说明 又是一年元旦&#xff0c;在公司抽个空&#xff0c;写首诗纪念一下。 本系列博客&#xff1a;诗韵–代码之外的生活 2 正文 2025 元旦歌 一年又一年&#xff0c; 又到新元旦。 恍若零五年&#xff0c; 已是二五年。 工作忙连连&#x…...

SpringBoot项目启动的时候,指定jvm内存大小的3种方式

1. 通过命令行固定参数 在命令行中运行 Spring Boot 应用程序时&#xff0c;可以使用 -Xms 和 -Xmx 选项指定初始和最大堆内存大小。例如&#xff1a; java -Xms512m -Xmx1024m -jar mySpringBootApp.jar 优点&#xff1a; 简单明了 缺点&#xff1a; 是写死的&#xff0c;…...

学习vue3的笔记

一、vue和react的对比 1、基础介绍 vue&#xff1a;https://cn.vuejs.org/ vue3是2020年创建的 react&#xff1a;https://react.dev/ react是一个2013年开源的JavaScript库&#xff0c;严格意义上来说不是一个框架 2、diff算法 两个框架采用的都是同级对比策略 两节点对…...

MySQL UNION

关于《MySQL UNION》的操作&#xff0c;我查找到了一些有用的信息。 MySQL的UNION操作符用于将两个或多个SELECT语句的结果组合到一个结果集中&#xff0c;并去除重复的行。每个SELECT语句的列数和对应位置的数据类型必须相同。其基本语法格式如下&#xff1a; SELECT column…...

OpenClaw安全指南:千问3.5-27B本地化执行权限管控

OpenClaw安全指南&#xff1a;千问3.5-27B本地化执行权限管控 1. 为什么需要OpenClaw安全管控&#xff1f; 去年冬天的一个深夜&#xff0c;我被一阵急促的键盘敲击声惊醒。走进书房时&#xff0c;发现OpenClaw正在自动执行我三天前测试的爬虫脚本——由于没有设置运行时间限…...

2026届必备的五大AI辅助写作方案推荐榜单

Ai论文网站排名&#xff08;开题报告、文献综述、降aigc率、降重综合对比&#xff09; TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 在人工智能技术参与进来之后&#xff0c;学术论文写作在效率方面有了明显的大幅提升&#xf…...

用Multisim复刻经典:手把手教你搭建一个带分数显示的四人抢答器(附仿真文件)

用Multisim复刻经典&#xff1a;手把手教你搭建一个带分数显示的四人抢答器&#xff08;附仿真文件&#xff09; 在电子工程的学习和实践中&#xff0c;没有什么比亲手搭建一个完整的数字电路系统更能让人兴奋的了。尤其是对于那些对经典74系列芯片情有独钟的工程师和爱好者来说…...

Beyond ChatGPT: Building Physical World AI with PaLM-E and VoxPoser (Hands-on Guide)

从语言模型到物理世界操作&#xff1a;PaLM-E与VoxPoser实战指南 当ChatGPT在对话中展现出惊人的语言理解能力时&#xff0c;一个更激动人心的问题浮现&#xff1a;如何让AI系统突破虚拟界限&#xff0c;在物理世界中执行复杂任务&#xff1f;这正是PaLM-E与VoxPoser这类多模态…...

BYD 高通8155 OTA项目 我写的一篇专利

草根不要在BYD写专利&#xff0c;我24年1月初开始撰写&#xff0c;24年6月份才提交到专利公司&#xff0c;被驳回是因为有对比文件公开了我的发明点&#xff0c;是重庆赛力斯 4月份公开的&#xff0c;部门内部流程审核极慢&#xff0c;集团IPR找各种理由能拖上你半年&#xff0…...

定制属于自己的AS-I总线

本公司自己已经完成AS-I总线主站、电源、从站模块的纯国产化&#xff0c;可以基于AS-I总线的基础上进行拓展&#xff0c;欢迎有需求的、有想法的各类人士一起撑起AS-I国产化一片天...

Python原生AOT编译2026架构设计图(含C-API二进制兼容性矩阵+GC停顿压缩至≤80μs实证)

第一章&#xff1a;Python原生AOT编译2026架构全景概览Python原生AOT&#xff08;Ahead-of-Time&#xff09;编译在2026年已演进为一套融合语言语义、运行时契约与硬件感知能力的系统级基础设施。它不再依赖传统解释器或JIT中间态&#xff0c;而是通过静态类型推导、控制流图全…...

seo sem公司如何制定营销策略

SEO SEM公司如何制定有效的营销策略 在当今数字化时代&#xff0c;SEO&#xff08;搜索引擎优化&#xff09;和SEM&#xff08;搜索引擎营销&#xff09;已经成为企业推广和品牌建立的关键组成部分。无论是中小企业还是大型跨国公司&#xff0c;它们都需要高效、精准的营销策略…...

使用Image - To - image条件生成对抗网络评估乳腺癌新辅助化疗反应的动态对比增强MRI血管渗透性映射

论文总结1、提出了一种基于条件生成对抗网络&#xff08;cGAN&#xff09;的新方法&#xff0c;用于将动态对比增强磁共振成像&#xff08;DCE MRI&#xff09;快速转换为药代动力学&#xff08;PK&#xff09;血管通透性参数图&#xff08;Ktrans&#xff09;&#xff0c;以早…...

抖音批量下载终极指南:免费无水印,一键搞定视频、音乐、合集

抖音批量下载终极指南&#xff1a;免费无水印&#xff0c;一键搞定视频、音乐、合集 【免费下载链接】douyin-downloader A practical Douyin downloader for both single-item and profile batch downloads, with progress display, retries, SQLite deduplication, and brows…...