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

【划分型 DP-最优划分】【腾讯笔试压轴】【hard】力扣132. 分割回文串 II

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

返回符合要求的 最少分割次数 。

示例 1:
输入:s = “aab”
输出:1
解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。

示例 2:
输入:s = “a”
输出:0

示例 3:
输入:s = “ab”
输出:1

提示:
1 <= s.length <= 2000
s 仅由小写英文字母组成

动态规划

class Solution {
public:int minCut(string s) {int n = s.size();vector<vector<bool>> g(n, vector<bool>(n, true));for(int i = n-1; i >= 0; i--){for(int j = i+1; j < n; j++){g[i][j] = s[i] == s[j] && g[i+1][j-1];}}vector<int> f(n, INT_MAX);for(int j = 0; j < n; j++){if(g[0][j]){f[j] = 0;}else{for(int i = 0; i < j; i++){if(g[i+1][j]){f[j] = min(f[j], f[i] + 1);}}}}return f[n-1];}
};

时间复杂度:O(n^2)
空间复杂度:O(n^2)

这道题最关键的部分是我们要对字符串s进行处理,我们通过一个二维数组来记录字符串的各个部分是否是回文字符串。
我们定义一个二维数组g[i][j]来表示字符串[i…j]这一段是否是回文串。在检查是否是回文串的时候,我们只需要判断s[i]和s[j]是否相等,如果相等的话,那么[i+1,…,j-1]是否是回文串,如果也是的话,就说明g[i][j]是true。在处理回文串的时候,需要注意我们要初始化g[i][j]都为true,这是为了避免额外判断:若初始化为 false,则需要额外处理长度为 1 或 2 的子串,代码的复杂度会增加。初始化为 true 可以确保所有的单字符子串都被认为是回文,代码逻辑更加简洁。

预处理完字符串后,我们定义一个动态数组f[i],他代表字符串[0,…,i]的最小分割次数是多少。我们先遍历j从0到n-1,也就是我们要找出从 0到1,0到2,…,0到(n-1)字符串的最小分割次数是多少。因为我们最终的目的就是求从0到(n-1)的字符串的最小分割次数,那么我们求0到j的最小分割次数就可以从前面的状态转换而来。

那么如何进行状态转换,f[j]如何从之前计算过的状态转换而来?我们这时候遍历下标i,目的是判断从i+1到j这字符串是否是回文,如果是回文的话,那么从0到j这个字符串的最小分割次数,不就是0到i的最小分割次数加上1吗。然后我们不断寻找状态转换后的f[j]的最小值并记录。

最后返回f[n-1]即可。

相关文章:

【划分型 DP-最优划分】【腾讯笔试压轴】【hard】力扣132. 分割回文串 II

给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是回文串。 返回符合要求的 最少分割次数 。 示例 1&#xff1a; 输入&#xff1a;s “aab” 输出&#xff1a;1 解释&#xff1a;只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子…...

Kubernetes-镜像加速篇-01-加速工具

[友情链接]加速三剑客 镜像加速&#xff1a;https://github.com/DaoCloud/public-image-mirror 二进制文件加速&#xff1a;https://github.com/DaoCloud/public-binary-files-mirror Helm 加速&#xff1a;https://github.com/DaoCloud/public-helm-charts-mirror 二进制文件…...

字母的异位数

做leetcode242题时出现了一个错误&#xff1a; bool isAnagram(string s, string t) {map<char,int> cnt;bool ans true;int lens s.length();int lent t.length();for(int i 0;i < lens;i){cnt[s[i]] 1;cout << cnt[s[i]] << endl;}for(int i 0;i…...

达梦数据库DM Exception字符串截断错误,略坑~

前言 我之前在使用达梦数据库的时候&#xff0c;遇到了很多很多的问题&#xff0c;主要对达梦数据库也不是很熟悉&#xff0c;它的语法和我所熟悉的mysql和postgresql有很大的区别。 今天&#xff0c;讲一下我之前遇到的一个问题。这个问题的起因是用达梦数据库迁移工具&…...

vue实现图片无限滚动播放

本人vue新手菜鸡&#xff0c;文章为自己在项目中遇到问题的记录&#xff0c;如有不足还请大佬指正 文章目录 实现效果代码展示总结 因为刚接触vue&#xff0c;本想着看看能不能用一些element的组件实现图片的轮播效果&#xff0c;尝试使用过element-UI里的走马灯Carouse&#x…...

python爬虫指南——初学者避坑篇

目录 Python爬虫初学者学习指南一、学习方向二、Python爬虫知识点总结三、具体知识点详解和实现步骤1. HTTP请求和HTML解析2. 正则表达式提取数据3. 动态内容爬取4. 数据存储5. 反爬虫应对措施 四、完整案例&#xff1a;爬取京东商品信息1. 导入库和设置基本信息2. 获取网页内容…...

Vivado+Vscode联合打造verilog环境

一、Vivado下载安装 详细参考我另一篇文章&#xff1a; Vivado2022.2下载安装_fpga vivado下载-CSDN博客https://blog.csdn.net/weixin_61081689/article/details/143460790?spm1001.2014.3001.5501 二、Vscode下载安装 详细参考我另一篇文章&#xff1a; VscodeAnacond…...

Python 微服务架构

Python 微服务架构 目录 &#x1f6e0; 微服务架构的基本概念与设计原则⚡ Python 在微服务中的应用&#xff08;Flask、FastAPI等框架&#xff09;&#x1f680; 微服务的自动化部署与运维&#x1f50d; 服务发现与负载均衡&#x1f4ca; 微服务中的日志集中管理与监控&…...

Android JNI 技术入门指南

引言 在Android开发中&#xff0c;Java是一种主要的编程语言&#xff0c;然而&#xff0c;对于一些性能要求较高的场景&#xff08;如音视频处理、图像处理、计算密集型任务等&#xff09;&#xff0c;我们可能需要使用到C或C等语言来编写底层的高效代码。为了实现Java代码与C…...

实在智能受邀出席柳州市智能终端及机器人产业发展合作大会

10 月 27 日至 28 日&#xff0c;由中共柳州市委员会与柳州市人民政府主办的2024柳州市智能终端及机器人产业发展合作大会在柳州莲花山庄隆重举行。大会充分整合各方资源&#xff0c;持续深化与柳州在重大战略规划、重大平台建设、重点产业培育等领域的合作。作为智能体行业的知…...

算法求解(C#)-- 寻找包含目标字符串的最短子串算法

1. 引言 在字符串处理中&#xff0c;我们经常需要从一个较长的字符串中找到包含特定目标字符串的最短子串。这个问题在文本搜索、基因序列分析等领域有着广泛的应用。本文将介绍一种高效的算法来解决这个问题。 2. 问题描述 给定一个源字符串 source 和一个目标字符串 targe…...

AscendC从入门到精通系列(二)基于Kernel直调开发AscendC算子

本次主要讨论下AscendC算子的开发流程&#xff0c;基于Kernel直调工程的算子开发。 1 AscendC算子开发的基本流程 使用Ascend C完成Add算子核函数开发&#xff1b; 使用ICPU_RUN_KF CPU调测宏完成算子核函数CPU侧运行验证&#xff1b; 使用<<<>>>内核调用符…...

DAO模式的理解

目录 DAO模式 含义 DAO模式 的理解 分层思维 分层含义 分层目的 dao层 dao包&#xff08;对接的是操作数据库的接口&#xff09; dao包下lmpl 包&#xff08;dao包中接口的实现类&#xff09; 补充 1 你创建的实体类需要和数据库中建的表一一对应。 总结 DAO模式 含义…...

使用GitHub Actions实现CI/CD流程

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 使用GitHub Actions实现CI/CD流程 GitHub Actions 简介 创建仓库 配置工作流 示例工作流文件 触发和运行工作流 部署应用 最佳实…...

机器人助力Bridge Champ游戏:1.4.2版本如何提升玩家体验

在Bridge Champ游戏中&#xff0c;机器人扮演着桥牌游戏的“无名英雄”角色&#xff0c;默默地提升玩家体验。凭借智能化的设计&#xff0c;这些机器人不仅能够陪练&#xff0c;也大大提升了比赛的流畅度与趣味性。 Bridge Champ是什么 Bridge Champ是一个基于Ignis公链的在线…...

滑动窗口(单调队列维护窗口)-acwing

题目&#xff1a; 154. 滑动窗口 - AcWing题库 代码&#xff08;删除队列窗口多余的>单调队列&#xff09; 判断最值是否滑出窗口可以放在 入队的后面。 但是&#xff0c;判断&#xff0c;准备入队元素比前面小&#xff0c;要从队尾出队&#xff0c;放在入队前。 总之&a…...

ALB搭建

ALB: 多级分发、消除单点故障提升应用系统的可用性&#xff08;健康检查&#xff09;。 海量微服务间的高效API通信。 自带DDoS防护&#xff0c;集成Web应用防火墙 配置&#xff1a; 1.创建ECS实例 2.搭建应用 此处安装的LNMP 3.创建应用型负载均衡ALB实例 需要创建服务关联角…...

c# 动态lambda实现二级过滤(支持多种参数类型和模糊查询)

效果 调用方法 实体类&#xff08;可以根据需求更换&#xff09; public class ToolStr50 {public bool isSelected { get; set; }public string toolStr1 { get; set; }public string toolStr2 { get; set; }public string toolStr3 { get; set; }public string toolStr4 { …...

第J5周:DenseNet+SE-Net实战

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 任务&#xff1a; ●1. 在DenseNet系列算法中插入SE-Net通道注意力机制&#xff0c;并完成猴痘病识别 ●2. 改进思路是否可以迁移到其他地方呢 ●3. 测试集acc…...

Intern大模型训练营(五):书生大模型全链路开源体系笔记

观看视频&#xff0c;可以比较详细地了解到书生大模型全链路开源体系。 其中有几个印象比较深的点&#xff1a; 这张图讲述了书生浦语大模型开源的发展史&#xff0c;同时与主流的llama和Chatgpt模型进行比较&#xff0c;可以看出在参数上&#xff0c;InterLM在努力追赶甚至超…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...