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

2023-03-31:如何计算字符串中不同的非空回文子序列个数?

2023-03-31:给定一个字符串 s,返回 s 中不同的非空 回文子序列 个数,
通过从 s 中删除 0 个或多个字符来获得子序列。
如果一个字符序列与它反转后的字符序列一致,那么它是 回文字符序列。
如果有某个 i , 满足 ai != bi ,则两个序列 a1, a2, … 和 b1, b2, … 不同。
注意:结果可能很大,你需要对 10^9 + 7 取模。

答案2023-03-31:

题目要求计算一个给定字符串中不同的非空回文子序列个数,并对结果取模。我们可以使用动态规划来解决这个问题。

首先定义一个二维数组dp,其中dp[i][j]表示从第i个字符到第j个字符中所有可能的回文子序列数量。

对于每个i和j,如果s[i]=s[j],则有三种情况:

1.空字符串或两个字符本身(如"aa");
2.单个字符或两个字符本身(如"a"或"aaa");
3.包含左右两个字符的回文子序列,同时需要减去内部相同字符的回文子序列数量。
因此,我们可以将dp[i][j]初始化为0并按照以下公式更新:

dp[i][j] = dp[i+1][j-1] * 2 - dp[l+1][r-1] + 2 或
dp[i+1][j-1] * 2 + 1 或
dp[i+1][j-1] * 2 - dp[l+1][r-1]

其中l和r分别表示字符串中从第i个字符到第j个字符之间的一个相同字符的最左侧位置和最右侧位置。例如,在字符串"bccb"中,当i=0且j=3时,l=1,r=2。

如果s[i]!=s[j],则有两种情况:

1.包含右边字符的回文子序列数量;
2.包含左边字符的回文子序列数量。
同时需要注意重复计算的空回文子序列数量。因此,我们可以将dp[i][j]初始化为0并按照以下公式更新:

dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]

最后,我们可以使用哈希表来存储每个位置左侧和右侧相同字符的最后出现位置,这样可以将空间复杂度降至O(n)。在进行模运算时,直接对所有中间结果进行取模可能会导致整数溢出,因此可以在计算过程中每一步都进行取模操作,也可以使用Rust中提供的取模运算符%=。

时间复杂度:

1.预处理左侧和右侧相同字符最后出现位置的时间复杂度为O(n)。
2.动态规划的过程中,需要计算长度从2到n的所有可能情况,因此时间复杂度为O(n^2)。
3.因此,总时间复杂度为O(n^2)。

空间复杂度:

1.需要使用一个二维数组dp存储回文子序列数量,因此空间复杂度为O(n^2)。
2.此外,还需要使用两个一维数组left和right分别存储每个位置左侧和右侧相同字符的最后出现位置,因此空间复杂度为O(n)。
3.因此,总空间复杂度为O(n^2)。

rust代码如下:

use std::collections::HashMap;fn count_palindromic_subsequences(s: &str) -> i32 {let mod_value = 1000000007;let s_chars: Vec<char> = s.chars().collect(); // 将字符串转成字符数组let n = s_chars.len() as i32; // 计算字符数组长度let mut right = vec![0; n as usize]; // 存储每个位置右侧相同字符的最后出现位置let mut left = vec![0; n as usize]; // 存储每个位置左侧相同字符的最后出现位置let mut last = HashMap::new();for i in 0..n {left[i as usize] = *last.get(&s_chars[i as usize]).unwrap_or(&(-1)); // 获取当前字符左侧相同字符的最后位置last.insert(s_chars[i as usize], i); // 更新当前字符的最后出现位置}last.clear();for i in (0..n).rev() {right[i as usize] = *last.get(&s_chars[i as usize]).unwrap_or(&n); // 获取当前字符右侧相同字符的最后位置last.insert(s_chars[i as usize], i); // 更新当前字符的最后出现位置}let mut dp = vec![vec![0i64; n as usize]; n as usize]; // 存储回文子序列数量的二维数组for i in 0..n {dp[i as usize][i as usize] = 1; // 单个字符为回文子序列}for i in (0..n - 1).rev() {for j in i + 1..n {if s_chars[i as usize] == s_chars[j as usize] {// 如果左右两个字符相同let l = std::cmp::min(j, right[i as usize]); // 计算内部回文子序列的左边界let r = std::cmp::max(i, left[j as usize]); // 计算内部回文子序列的右边界if l > r {// 内部没有相同字符dp[i as usize][j as usize] = dp[i as usize + 1][j as usize - 1] * 2 + 2;// 新增的两个字符,以及空字符串和两个字符本身两种情况} else if l == r {// 内部只有一个相同字符dp[i as usize][j as usize] = dp[i as usize + 1][j as usize - 1] * 2 + 1;// 新增的两个字符,以及单个字符和两个字符本身三种情况} else {// 内部有两个或以上相同字符dp[i as usize][j as usize] = dp[i as usize + 1][j as usize - 1] * 2 // 包含左右字符的回文子序列数量- dp[(l + 1) as usize][(r - 1) as usize] // 减去内部相同字符的回文子序列数量+ mod_value; // 模运算}} else {// 如果左右两个字符不同dp[i as usize][j as usize] = dp[i as usize][j as usize - 1] // 包含右边字符的回文子序列数量+ dp[i as usize + 1][j as usize] // 包含左边字符的回文子序列数量- dp[i as usize + 1][j as usize - 1] // 重复计算的空回文子序列数量+ mod_value; // 模运算}dp[i as usize][j as usize] %= mod_value; // 模运算}}dp[0][n as usize - 1] as i32 // 返回包含所有字符的回文子序列数量
}fn main() {let s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba";println!("{}", count_palindromic_subsequences(s));
}

在这里插入图片描述

相关文章:

2023-03-31:如何计算字符串中不同的非空回文子序列个数?

2023-03-31&#xff1a;给定一个字符串 s&#xff0c;返回 s 中不同的非空 回文子序列 个数&#xff0c; 通过从 s 中删除 0 个或多个字符来获得子序列。 如果一个字符序列与它反转后的字符序列一致&#xff0c;那么它是 回文字符序列。 如果有某个 i , 满足 ai ! bi &#xff…...

D. The Number of Imposters(二分图染色)

Problem - D - Codeforces Theofanis开始玩名为“Among them”的新网络游戏。然而&#xff0c;他总是和塞浦路斯球员一起踢球&#xff0c;他们都有一个相同的名字:“安德烈亚斯”(塞浦路斯最常见的名字)。在每个游戏中&#xff0c;Theofanis和n个其他玩家一起玩。因为它们都有相…...

图片太大怎么改小kb?简单的图片压缩方法分享

平时当我们在朋友圈分享一些有趣的照片或者使用图片素材进行上传的时候&#xff0c;经常遇到图片大小kb超出平台限制的情况&#xff0c;这时就无法正常上传了&#xff0c;遇到这种情况我们就需要想办法降低图片大小kb&#xff0c;那么有什么办法能够压缩图片大小呢&#xff1f;…...

【python-leecode刷题】动态规划类问题----以53. 最大子数组和为例

作者&#xff1a;20岁爱吃必胜客&#xff08;坤制作人&#xff09;&#xff0c;近十年开发经验, 跨域学习者&#xff0c;目前于海外某世界知名高校就读计算机相关专业。荣誉&#xff1a;阿里云博客专家认证、腾讯开发者社区优质创作者&#xff0c;在CTF省赛校赛多次取得好成绩。…...

Idea常用快捷键设置

设置来源于尚硅谷宋红康老师 第1组&#xff1a;通用型 说明 快捷键 复制代码-copy ctrl c 粘贴-paste ctrl v 剪切-cut ctrl x 撤销-undo ctrl z 反撤销-redo ctrl shift z 保存-save all ctrl s 全选-select all ctrl a 第2组&#xff1a;提高编写速度&#xff08;上…...

【新2023Q2模拟题JAVA】华为OD机试 - 分苹果

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:分苹果 题目 AB两个人把苹果…...

【博学谷学习记录】超强总结,用心分享丨人工智能 自然语言处理 BERT、GPT、ELMO对比学习简记

目录三模型架构BERTGPTELMO三者差异点三模型架构 BERT 优点 在11个NLP任务上取得SOAT成绩.利用了Transformer的并行化能力以及长语句捕捉语义依赖和结构依赖.BERT实现了双向Transformer并为后续的微调任务留出足够的空间. 缺点 BERT模型太大, 太慢.BERT模型中的中文模型是以…...

【嵌入式Bluetooth应用开发笔记】第四篇:初探蓝牙HOST及应用开发(持续更新ing)

概念 蓝牙HOST(Bluetooth Host)是指能够连接到其他蓝牙设备并控制它们的设备。在蓝牙技术中,通常有两种类型的设备:蓝牙HOST和蓝牙SLAVE。蓝牙HOST通常是指拥有控制权的设备,它可以主动连接其他蓝牙设备并向其发送命令。相反,蓝牙SLAVE则是指被动连接的设备,它接受来自…...

GORM 基础 -- CRUD 接口

1、Create 1.1 创建纪录 user : User{Name: "Jinzhu", Age: 18, Birthday: time.Now()}result : db.Create(&user) // pass pointer of data to Createuser.ID // 回填插入数据的主键 result.Error // 返回的 error 信息 result.RowsAffect…...

为什么0代码自动化测试越来越受欢迎?一文2000字解析

目录 01、什么是零代码自动化测试 02、为什么零代码自动化测试越来越受欢迎 03、有代码和零代码自动化有什么区别 04、零代码自动化测试可以帮助你做什么 05、零代码自动化测试方法&#xff1a;NLP&#xff08;自然语言处理&#xff09; 06、为什么我们需要零代码自动化测…...

cleanmymac最新2023版 mac清理软件CleanMyMac X4.12.5 中文版功能介绍

CleanMyMac X4.12.5 中文版只需两个简单步骤就可以把系统里那些乱七八糟的无用文件统统清理掉&#xff0c;节省宝贵的磁盘空间。cleanmymac x个人认为X代表界面上的最大升级&#xff0c;功能方面有更多增加&#xff0c;与最新macOS系统更加兼容&#xff0c;流畅地与系统性能更加…...

pyhon部署注意事项

前言&#xff1a;相信看到这篇文章的小伙伴都或多或少有一些编程基础&#xff0c;懂得一些linux的基本命令了吧&#xff0c;本篇文章将带领大家服务器如何部署一个使用django框架开发的一个网站进行云服务器端的部署。 文章使用到的的工具 Python&#xff1a;一种编程语言&…...

宣城x移动云,打造“城市级物联感知平台”

随着新一代信息技术与城市现代化的深度融合&#xff0c;智慧城市建设的重要性也愈发凸显。而在智慧城市建设中&#xff0c;物联网感知体系扮演着中枢神经系统的角色。 安徽宣城紧抓长三角城市群一体化发展机遇&#xff0c;为构建“数字宣城”建设发展新模式&#xff0c;携手移…...

英伟达Jetson NX套件刷机,配置Ubuntu20。

0. 前言 人并没有眼见得那么光鲜亮丽&#xff0c;博客也是。 今天推荐一本书《一百个人的十年》&#xff0c;没错就是我们的那十年&#xff08;60年代&#xff09;。写得很真实&#xff0c;牛棚猪圈&#xff0c;确实如此。 1. SdkManager安装 官网下载。 打开终端 执行命令sud…...

Vue计算属性

计算属性 ​ 计算属性的重点突出在属性两个字上(属性是名词)&#xff0c;首先它是个属性其次这个属性有计算的能力(计算是动词)&#xff0c;这里的计算就是个函数;简单点说&#xff0c;它就是一个能够将计算结果缓存起来的属性(将行为转化成了静态的属性)&#xff0c;仅此而已…...

代码随想录刷题-字符串-反转字符串

文章目录反转字符串习题双指针swap 的两种方式反转字符串 本节对应代码随想录中&#xff1a;代码随想录&#xff0c;讲解视频&#xff1a;字符串基础操作&#xff01; | LeetCode&#xff1a;344.反转字符串_哔哩哔哩_bilibili 习题 题目链接&#xff1a;344. 反转字符串 - …...

14-链表练习-剑指 Offer II 021. 删除链表的倒数第 n 个结点

题目 给定一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], n 2 输出&#xff1a;[1,2,3,5] 示例 2&#xff1a; 输入&#xff1a;head [1], n 1 输出&#xff1a;[] 示例 3&…...

用Java解决华为OD机试考题,真的高效,真的强,来吧,清单奉上,祝你上岸

华为 OD 机试题最新&#xff08;Java&#xff09;清单&#xff08;机试题库还在逐日更新&#xff09; 题库目录 直接在本页使用 CtrlF&#xff0c;输入题目名称就可以进行检索。 序号文章分值1【华为OD机试真题JAVA】快递装载问题_国服第二切图仔的博客-CSDN博客1002【华为…...

【Stable Diffusion】Stable Diffusion免安装在线部署教程

一、开启Google Colab网址 官网&#xff1a;https://colab.research.google.com/ 点击添加代码&#xff1a; 二、执行如下代码指令 !pip install --upgrade fastapi0.90.1 !git clone https://github.com/AUTOMATIC1111/stable-diffusion-webui !git clone https://github.…...

Jetson设备如何接调试串口工具查看内核打印信息

方便小白使用如下教程。 一、认识USB转串口调试工具转接小板 和硬件连接方式 如图&#xff0c;是一款USB TO TTL转换板&#xff0c;这款小板支持3种供电模式&#xff1a;对外输出5V、对外输出3.3V和由外部供电。正面有一个跳帽&#xff0c;跳帽跳到3V3&#xff0c;小板由US…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...