入门力扣自学笔记58 C++ (题目编号730)(未理解)

2023-10-22 22:30

本文主要是介绍入门力扣自学笔记58 C++ (题目编号730)(未理解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

730. 统计不同回文子序列

题目:

给定一个字符串 s,返回 s 中不同的非空「回文子序列」个数 。

通过从 s 中删除 0 个或多个字符来获得子序列。

如果一个字符序列与它反转后的字符序列一致,那么它是「回文字符序列」。

如果有某个 i , 满足 ai != bi ,则两个序列 a1, a2, ... 和 b1, b2, ... 不同。

注意:

结果可能很大,你需要对  + 7 取模 。


示例 1:

输入:s = 'bccb'
输出:6
解释:6 个不同的非空回文子字符序列分别为:'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意:'bcb' 虽然出现两次但仅计数一次。


示例 2:

输入:s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出:104860361
解释:共有 3104860382 个不同的非空回文子序列,104860361 对 + 7 取模后的值。


提示:

1 <= s.length <= 1000
s[i] 仅包含 'a', 'b', 'c' 或 'd' 

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/count-different-palindromic-subsequences
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


思路:

动态规划+记忆化搜索


代码:

class Solution {
public:int countPalindromicSubsequences(string s) {int n = s.size();vector<vector<int>> f(n,vector<int>(n,0));for(int i=0;i<n;i++)f[i][i]=1;const int mod = 1e9+7;for(int i=n-2;i>=0;i--){for(int j=i+1;j<n;j++){if(s[i]!=s[j])f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1];else{f[i][j] = f[i+1][j-1]*2+2;int l=i+1,r=j-1;while(l<=r&&s[l]!=s[i])l++;while(l<=r&&s[r]!=s[i])r--;// 第2.1种情况 中间有1个s[i]if(l==r)f[i][j]--;// 第2.2种情况 中间有≥2个s[i]else if(l<r)f[i][j] -=2+f[l+1][r-1];}f[i][j]=(f[i][j]>=0)?f[i][j]%mod:f[i][j]+mod;}}return f[0][n-1];}
};

这篇关于入门力扣自学笔记58 C++ (题目编号730)(未理解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/263975

相关文章

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

Python Excel实现自动添加编号

《PythonExcel实现自动添加编号》这篇文章主要为大家详细介绍了如何使用Python在Excel中实现自动添加编号效果,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、背景介绍2、库的安装3、核心代码4、完整代码1、背景介绍简单的说,就是在Excel中有一列h=会有重复

Python FastAPI入门安装使用

《PythonFastAPI入门安装使用》FastAPI是一个现代、快速的PythonWeb框架,用于构建API,它基于Python3.6+的类型提示特性,使得代码更加简洁且易于绶护,这篇文章主要介... 目录第一节:FastAPI入门一、FastAPI框架介绍什么是ASGI服务(WSGI)二、FastAP

C++ Primer 标准库vector示例详解

《C++Primer标准库vector示例详解》该文章主要介绍了C++标准库中的vector类型,包括其定义、初始化、成员函数以及常见操作,文章详细解释了如何使用vector来存储和操作对象集合,... 目录3.3标准库Vector定义和初始化vector对象通列表初始化vector对象创建指定数量的元素值

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没