代码随想录day46dp13

647. 回文子串

题目链接
文章讲解
回溯法

class Solution {
public:int count = 0;// 检查字符串是否是回文bool isPalindrome(string& s, int start, int end) {while (start < end) {if (s[start] != s[end]) return false;start++;end--;}return true;}// 回溯法,尝试从每个位置生成子串void backtrack(string& s, int start) {int n = s.size();for (int end = start; end < n; end++) {if (isPalindrome(s, start, end)) {  // 如果是回文count++;  // 增加回文子串的计数}}}int countSubstrings(string s) {int n = s.size();for (int i = 0; i < n; i++) {backtrack(s, i);  // 从每个字符开始,回溯生成子串}return count;}
};

暴力

class Solution {
public:int count = 0;// 检查字符串是否是回文bool isPalindrome(string& s, int start, int end) {while (start < end) {if (s[start] != s[end]) return false;start++;end--;}return true;}int countSubstrings(string s) {int n = s.size();for (int i = 0; i < n; i++) {for(int j=i;j<n;j++){if(isPalindrome(s,i,j))count++;}}return count;}
};

dp

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int result = 0;for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序for (int j = i; j < s.size(); j++) {if (s[i] == s[j]) {if (j - i <= 1) { // 情况一 和 情况二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情况三result++;dp[i][j] = true;}}}}return result;}
};

516.最长回文子序列

题目链接
文章讲解
在这里插入图片描述

class Solution {
public:int longestPalindromeSubseq(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n,0));for(int i=0;i<n;i++) dp[i][i]=1;for(int i=n-1;i>=0;i--){for(int j=i+1;j<n;j++){if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);}}return dp[0][n-1];}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/pingmian/90638.shtml
繁体地址,请注明出处:http://hk.pswp.cn/pingmian/90638.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

学习随笔录

#61 学习随笔录 今日的思考 &#xff1a; 反思一下学习效率低下 不自律 或者 惰性思维 懒得思考 又或者 好高婺远 顶级自律从不靠任何意志力&#xff0c;而在于「平静如水的野心」_哔哩哔哩_bilibili 然后上面是心灵鸡汤合集 vlog #79&#xff5c;程序员远程办公的一天…

python-函数进阶、容器通用方法、字符串比大小(笔记)

python数据容器的通用方法#记住排序后容器类型会变成list容器列表 list[1,3,5,4,6,7] newListsorted(list,reverseTrue) print(newList) [7, 6, 5, 4, 3, 1]list[1,3,5,4,6,7] newListsorted(list,reverseFalse) print(newList) [1, 3, 4, 5, 6, 7]字典排序的是字典的key字符串…

关闭chrome自带的跨域限制,简化本地开发

在开发时为了图方便,简化本地开发,懒得去后端配置允许跨域,那就可以用此方法1. 右键桌面上的Chrome浏览器图标&#xff0c;选择“创建快捷方式”到桌面。2. 在新创建的快捷方式的图标上右键&#xff0c;选择“属性”。3. 在弹出窗口中的“目标”栏中追加&#xff1a; --allow-r…

C++___快速入门(上)

第一个C程序#include<iostream> using namespace std; int main() {cout << "hello world !" << endl;return 0; }上边的代码就是用来打印字符串 “hello world !” 的&#xff0c;可见&#xff0c;与C语言还是有很大的差别的&#xff0c;接下来我…

构建企业级Docker日志驱动:将容器日志无缝发送到腾讯云CLS

源码地址:https://github.com/k8scat/docker-log-driver-tencent-cls 在现代云原生架构中,容器化应用已经成为主流部署方式。随着容器数量的快速增长,如何高效地收集、存储和分析容器日志成为了一个关键挑战。传统的日志收集方式往往存在以下问题: 日志分散在各个容器中,难…

Kafka——消费者组重平衡能避免吗?

引言 其实在消费者组到底是什么&#xff1f;中&#xff0c;我们讲过重平衡&#xff0c;也就是Rebalance&#xff0c;现在先来回顾一下这个概念的原理和用途。它是Kafka实现消费者组&#xff08;Consumer Group&#xff09;弹性伸缩和容错能力的核心机制&#xff0c;却也常常成…

使用爬虫获取游戏的iframe地址

如何通过爬虫获取游戏的iframe地址要获取网页中嵌入的游戏的iframe地址&#xff08;即iframe元素的src属性&#xff09;&#xff0c;您可以使用网络爬虫技术。iframe是HTML元素&#xff0c;用于在当前页面中嵌入另一个文档&#xff08;如游戏页面&#xff09;&#xff0c;其地址…

NTLite Ent Version

NTLite是一款专业的系统安装镜像制作工具&#xff0c;通过这款软件可以帮助用户快速生成镜像文件打好补丁&#xff0c;很多朋友在安装电脑系统的时候一般都安装了windows系统的所有Windows组件&#xff0c;其实有很多Windows组件你可能都用到不到&#xff0c;不如在安装系统时就…

Maven之依赖管理

Maven之依赖管理一、Maven依赖管理的核心价值二、依赖的基本配置&#xff08;坐标与范围&#xff09;2.1 依赖坐标&#xff08;GAV&#xff09;2.2 依赖范围&#xff08;scope&#xff09;示例&#xff1a;常用依赖范围配置三、依赖传递与冲突解决3.1 依赖传递性示例&#xff1…

【Unity实战100例】Unity资源下载系统开发流程详解(移动端、PC端 ,局域网控制台服务)

目录 一、项目概述 二、服务器开发 1、配置文件设计 1、加载配置 2. 处理客户端请求 3. 文件下载处理 三、客户端开发 1、配置管理 1、配置加载与保存 2、下载任务管理 1、任务类设计 2、下载队列管理 3、核心下载流程 四、UI系统实现 五、部署与测试 1、服务…

[Python] -进阶理解7- Python中的内存管理机制简析

Python(尤其是 CPython)采用自动内存管理机制,核心包括引用计数(Reference Counting)与垃圾回收机制(Garbage Collection),并配合专门的内存池和分配器机制来提升效率与减少碎片。 这套机制隐藏在开发者视线之外,Python 开发者无需手动申请或释放内存。 二、Python 内…

云祺容灾备份系统AWS S3对象存储备份与恢复实操手册

1、创建密钥访问AWS控制台&#xff0c;鼠标移至右上角账户处&#xff0c;在弹出菜单中点击安全凭证&#xff0c;如图1。图1在弹出页面中&#xff0c;下滑找到访问密钥&#xff0c;并点击创建访问密钥&#xff0c;如图2。图2选择其他&#xff0c;并点击下一步&#xff0c;如图3。…

使用 LLaMA 3 8B 微调一个 Reward Model:从入门到实践

本文将介绍如何基于 Meta 的 LLaMA 3 8B 模型构建并微调一个 Reward Model&#xff0c;它是构建 RLHF&#xff08;基于人类反馈的强化学习&#xff09;系统中的关键一环。我们将使用 Hugging Face 的 transformers、trl 和 peft 等库&#xff0c;通过参数高效微调&#xff08;L…

matrix-breakout-2-morpheus靶场攻略

靶场使用将压缩包解压到一个文件夹中&#xff0c;用虚拟机应用新建虚拟机&#xff0c;扫描虚拟机&#xff0c;扫描那个文件夹&#xff0c;就可以把虚拟机扫出来了&#xff0c;然后启动虚拟机这时候靶场启动后&#xff0c;咱们现在要找到这个靶场。靶场是网页形式的&#xff0c;…

MySQL 复制表

MySQL 复制表 概述 在数据库管理中&#xff0c;复制表是一项常用的操作。它允许数据库管理员将一个表中的数据复制到另一个表中&#xff0c;无论是同一个数据库还是不同的数据库。MySQL数据库提供了多种方法来复制表&#xff0c;本文将详细介绍MySQL复制表的过程、方法及其应用…

『哈哥赠书 - 55期』-『码农职场:IT人求职就业手册』

文章目录⭐️ 码农职场&#xff1a;IT人求职就业手册⭐️ 本书简介⭐️ 作者简介⭐️ 编辑推荐这是一本专为广大IT行业求职者量身定制的指南&#xff0c;提供了从职前准备到成功就业的全方位指导&#xff0c;涵盖了职业目标规划、自我技能评估、求职策略、简历准备以及职场心理…

单片机学习课程

单片机学习课程 课程介绍 单片机技术作为现代工业自动化、电子电气、通信及物联网等领域的主流技术&#xff0c;早已深度融入我们生活与生产的各个角落。从常见家电到自动化公共设施&#xff0c;都离不开单片机的支持。同时&#xff0c;它也是学习 ARM 嵌入式系统、FPGA 设计等…

【AcWing 143题解】最大异或对

AcWing 143. 最大异或对 【题目描述】 在查看解析之前&#xff0c;先给自己一点时间思考哦&#xff01; 【题解】 本题要求给定一个整数序列&#xff0c;找出其中任意两个数进行异或运算后&#xff0c;结果的最大值是多少。由于数据规模较大&#xff0c;我们不能简单地通过两…

SQLAlchemy 2.0简单使用

记录一下SQLAlchemy 2.0连接mysql数据库的方法及简单使用 环境及依赖 Python:3.8 mysql:8.3 Flask:3.0.3 SQLAlchemy:2.0.37 PyMySQL:1.1.1使用步骤 1、创建引擎&#xff0c;链接到mysql engine create_engine(mysqlpymysql://{username}:{password}{ip}:3306/{database_name}…

如何创建或查看具有 repo 权限的 GitHub 个人访问令牌(PAT)

要创建或查看具有 repo 权限的 GitHub 个人访问令牌(PAT),请按照以下步骤操作: 一、生成具有 repo 权限的 PAT 登录 GitHub 访问 GitHub 官网,使用你的账户登录。 进入开发者设置 点击右上角头像,选择 Settings(设置) → 左侧菜单中选择 Developer settings(开发者设…