当前位置: 首页 > 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…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...