算法沉淀——动态规划之回文串问题（上）（leetcode真题剖析）

在这里插入图片描述

算法沉淀——动态规划之回文串问题

  • 01.回文子串
  • 02.最长回文子串
  • 03.分割回文串 IV
  • 04.分割回文串 II
  • 05.最长回文子序列
  • 06.让字符串成为回文串的最少插入次数

01.回文子串

题目链接：https://leetcode.cn/problems/palindromic-substrings/

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成

思路

  1. 预处理回文信息： 创建一个 dp 表，其中 dp[i][j] 表示字符串 s 中子串 s[i:j+1] 是否是回文串。

  2. 状态转移方程： 对于回文串，分析两头的元素：

    • 如果 s[i] != s[j]，则不可能是回文串，dp[i][j] = 0；

    • 如果

      s[i] == s[j]

      ，则根据长度分三种情况讨论：

      • 如果长度为 1，即 i == j，则一定是回文串，dp[i][j] = true；
      • 如果长度为 2，即 i + 1 == j，则也一定是回文串，dp[i][j] = true；
      • 如果长度大于 2，则需要看 [i + 1, j - 1] 区间的子串是否回文，dp[i][j] = dp[i + 1][j - 1]。

  3. 初始化： 由于状态转移方程已经考虑了各种情况，无需额外初始化。

  4. 填表顺序： 根据状态转移方程，从下往上填写每一行。

  5. 返回值： 根据状态表达和题目要求，返回 dp 表中 true 的个数。

代码

class Solution {
public:
    int countSubstrings(string s) {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));

        int sum=0;
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                if(dp[i][j]) sum++;
            }
        }
        return sum;
    }
};

02.最长回文子串

题目链接：https://leetcode.cn/problems/longest-palindromic-substring/

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

思路

和上一题思路基本一致，但这里我们要返回字串，所以我们需要在原有算法上标记字串的开始位置和子串的长度。

代码

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));

        int len=1,begin=0;
        for(int i=n-1;i>=0;--i){
            for(int j=i;j<n;++j){
                if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                if(dp[i][j]&&j-i+1>len) len=j-i+1,begin=i;
            }
        }
        return s.substr(begin,len);
    }
};

03.分割回文串 IV

题目链接：https://leetcode.cn/problems/palindrome-partitioning-iv/

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例 1：

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

提示：

  • 3 <= s.length <= 2000
  • s 只包含小写英文字母。

思路

其实这里我们可以依照第一题的解法将所有的子串都进行统计，再遍历计算每个分割位置组成的3个子串是否都符合回文子串即可。

代码

class Solution {
public:
    bool checkPartitioning(string s) {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        for(int i=n-1;i>=0;--i)
            for(int j=i;j<n;j++)
                if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true;
        
        for(int i=1;i<n-1;i++)
            for(int j=i;j<n-1;++j)
                if(dp[0][i-1]&&dp[i][j]&&dp[j+1][n-1]) return true;
        return false;
    }
};

04.分割回文串 II

题目链接：https://leetcode.cn/problems/palindrome-partitioning-ii/

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

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

示例 1：

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

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

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

思路

  1. 状态表达： 以 i 位置为结尾，定义状态表达 dp[i] 表示字符串 s 中 [0, i] 区间上的字符串，最少分割的次数。

  2. 状态转移方程： 通常考虑最后一个位置的信息。设 0 <= j <= i，那么可以根据 [j, i] 位置上的子串是否是回文串分成以下两类：

    • 如果 [j, i] 位置上的子串能够构成一个回文串，那么 dp[i] 就等于 [0, j - 1] 区间上最少回文串的个数 + 1，即 dp[i] = dp[j - 1] + 1；
    • 如果 [j, i] 位置上的子串不能构成一个回文串，此时 j 位置就不用考虑。

    由于求的是最小值，因此需要循环遍历 j 的取值，取最小值。

  3. 优化： 在状态转移方程中，需要快速判断字符串中的子串是否回文。因此，可以先处理一个 dp 表，其中保存所有子串是否回文的信息。

  4. 初始化： 在循环遍历 j 之前，处理 j == 0 的情况。此时，表示的区间是 [0, i]。如果 [0, i] 区间上的字符串已经是回文串了，最小的回文串就是 1，j 往后的值就不用遍历了。为防止在求 min 操作时，0 干扰结果，将表中的值初始化为「无穷大」。

  5. 填表顺序： 从左往右填写。

  6. 返回值： 根据状态表达，返回 dp[n - 1]。

代码

class Solution {
public:
    int minCut(string s) {
        int n=s.size();
        vector<vector<bool>> isp(n,vector<bool>(n));
        for(int i=n-1;i>=0;--i)
            for(int j=i;j<n;j++)
                if(s[i]==s[j]) isp[i][j]=i+1<j?isp[i+1][j-1]:true;

        vector<int> dp(n,INT_MAX);
        for(int i=0;i<n;++i){
            if(isp[0][i]) dp[i]=0;
            else{
                for(int j=1;j<=i;j++)
                    if(isp[j][i]) dp[i]=min(dp[i],dp[j-1]+1);
            }
        }
        return dp[n-1];
    }
};

05.最长回文子序列

题目链接：https://leetcode.cn/problems/longest-palindromic-subsequence/

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

思路

  1. 状态表达： 以 i 位置为结尾，定义状态表达 dp[i][j] 表示字符串 s 中 [i, j] 区间内的所有子序列中，最长的回文子序列的长度。

  2. 状态转移方程： 回文子序列和回文子串的分析方式一般都是选择这段区域的「左右端点」的字符情况来分析。因为如果一个序列是回文串的话，「去掉首尾两个元素之后依旧是回文串」，「首尾加上两个相同的元素之后也依旧是回文串」。根据首尾元素的不同，分为以下两种情况：

    • 当 s[i] == s[j] 时，[i, j] 区间上的最长回文子序列，应该是 [i + 1, j - 1] 区间内的那个最长回文子序列首尾填上 s[i] 和 s[j]，此时 dp[i][j] = dp[i + 1][j - 1] + 2。
    • 当 s[i] != s[j] 时，这两个元素就不能同时添加在一个回文串的左右，那么就应该让 s[i] 单独加在一个序列的左边，或者让 s[j] 单独放在一个序列的右边，看看这两种情况下的最大值：
      • 单独加入 s[i] 后的区间在 [i, j - 1]，此时最长的回文序列的长度就是 dp[i][j - 1]；
      • 单独加入 s[j] 后的区间在 [i + 1, j]，此时最长的回文序列的长度就是 dp[i + 1][j]；

    取两者的最大值，于是 dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])。

  3. 初始化： 需要处理两种边界情况：

    • 当 i == j 时，区间内只有一个字符，此时 dp[i][j] = 1；
    • 当 i + 1 == j 时，区间内有两个字符，如果这两个字符相同，dp[i][j] = 2，否则 dp[i][j] = 0。

    在填表的时候，可以同步处理第一种边界情况，对于第二种边界情况，dp[i + 1][j - 1] 的值为 0，不会影响最终的结果，因此可以不用考虑。

  4. 填表顺序： 根据「状态转移」，dp[i + 1] 表示下一行的位置，dp[j - 1] 表示前一列的位置。因此填表顺序应该是「从下往上填写每一行」，「每一行从左往右」。

  5. 返回值： 根据「状态表达」，返回 [0, n -1] 区域上的最长回文序列的长度，因此需要返回 dp[0][n - 1]。

代码

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n));

        for(int i=n-1;i>=0;i--){
            dp[i][i]=1;
            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];
    }
};

06.让字符串成为回文串的最少插入次数

题目链接：https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1：

输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。

示例 2：

输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

示例 3：

输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

提示：

  • 1 <= s.length <= 500
  • s 中所有字符都是小写字母。

思路

  1. 状态表达： 以 i 位置为结尾，定义状态表达 dp[i][j] 表示字符串 s 中 [i, j] 区域成为回文子串的最少插入次数。
  2. 状态转移方程： 回文子序列和回文子串的分析方式一般都是选择这段区域的「左右端点」的字符情况来分析。因为如果一个序列是回文串的话，「去掉首尾两个元素之后依旧是回文串」，「首尾加上两个相同的元素之后也依旧是回文串」。根据首尾元素的不同，可以分为以下两种情况：
    • 当 s[i] == s[j] 时，[i, j] 区间内成为回文子串的最少插入次数，取决于 [i + 1, j - 1] 区间内成为回文子串的最少插入次数。若 i >= j - 1 或 i == j - 1 （ [i + 1, j - 1] 不构成合法区间），此时只有 1 ~ 2 个相同的字符， [i, j] 区间一定是回文子串，成为回文子串的最少插入次数是 0。此时 dp[i][j] = i >= j - 1 ? 0 : dp[i + 1][j - 1]。
    • 当 s[i] != s[j] 时，需要在区间的最右边或最左边插入一个字符，取决于 [i + 1, j] 或 [i, j + 1] 区间内成为回文子串的最少插入次数。此时 dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1。
  3. 初始化： 根据「状态转移方程」，没有不能递推表达的值，无需初始化。
  4. 填表顺序： 根据「状态转移」，dp[i + 1] 表示下一行的位置，dp[j - 1] 表示前一列的位置。因此填表顺序应该是「从下往上填写每一行」，「每一行从左往右」。
  5. 返回值： 根据「状态表达」，返回 [0, n - 1] 区域上成为回文子串的最少插入次数，因此需要返回 dp[0][n - 1]。

代码

class Solution {
public:
    int minInsertions(string s) {
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n));

        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];
                else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
            }
        }
        return dp[0][n-1];
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/415068.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

08 MyBatis之查询专题(返回对象/Map/List封装Map/Map封装Map)+列名与属性名映射的三种方法

08 MyBatis之查询专题(返回对象/Map/List封装Map/Map封装Map)+列名与属性名映射的三种方法

准备: INSERT INTO t_car (id, car_num, brand, guide_price, produce_time, car_type) VALUES (165, 6666, 丰田霸道, 32.00, 2020-11-11, 燃油车); INSERT INTO t_car (id, car_num, brand, guide_price, produce_time, car_type) VALUES (166, 1202, 大众速腾, 30.00, 2020…
阅读更多...
IntelliJ IDEA 2023：创新不止步，开发更自由 mac/win版

IntelliJ IDEA 2023：创新不止步，开发更自由 mac/win版

IntelliJ IDEA 2023激活版是一款强大而智能的集成开发环境(IDE)&#xff0c;为开发者提供了一系列先进的功能和工具&#xff0c;帮助他们更高效地编写、调试和测试代码。 IntelliJ IDEA 2023 软件获取 IntelliJ IDEA 2023继承了其前代版本的优秀基因&#xff0c;并在此基础上进…
阅读更多...
基于AMDGPU-ROCm的深度学习环境搭建

基于AMDGPU-ROCm的深度学习环境搭建

在风起云涌的AI江湖&#xff0c;NVIDIA凭借其CUDA生态和优秀的硬件大杀四方&#xff0c;立下赫赫战功&#xff0c;而另一家公司AMD也不甘示弱&#xff0c;带着他的生态解决方案ROCm开始了与不世出的NVIDA的正面硬钢&#xff0c;"ROCm is the answer to CUDA", AMD官网…
阅读更多...
177基于matlab的基于S函数的变步长自适应滤波算法

177基于matlab的基于S函数的变步长自适应滤波算法

基于matlab的基于S函数的变步长自适应滤波算法&#xff0c;比传统的算法收敛速度更快。传统的LMS算法中&#xff0c;权值向量实时地被更新。这些更新可能会由于噪声的影响而变得不稳定。SVSLMS算法是一种改进的LMS算法&#xff0c;它采用了矢量处理的概念&#xff0c;利用信号和…
阅读更多...
分布式锁的应用与疑惑

分布式锁的应用与疑惑

文章目录 一、为什么需要用分布式锁二、Redis实现分布式锁三、Zookeeper实现分布式锁 一、为什么需要用分布式锁 集群下&#xff0c;普通的锁&#xff0c;无法解决问题 集群下&#xff0c;保证安全需要使用分布式锁 二、Redis实现分布式锁 Redisson内部封装的RedLock实现分…
阅读更多...
yolov9,使用自定义的数据训练推理

yolov9,使用自定义的数据训练推理

[源码 &#x1f40b;]( GitHub - WongKinYiu/yolov9: Implementation of paper - YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information) [论文 &#x1f4d8;](arxiv.org/pdf/2402.13616.pdf) 论文摘要&#xff1a;本文介绍了一种新的目标检测…
阅读更多...
Web服务器群集：OpenEuler 部署 LAMP(LNMP) 基础服务

Web服务器群集：OpenEuler 部署 LAMP(LNMP) 基础服务

目录 一、实验 1.环境 2. 网络配置 3. MobaXterm远程连接 4. apache 2.4.58 源码编译安装 5. php 8.3.1源码编译安装 6.配置httpd 连接 php-fpm 6. nginx 1.24.0源码编译安装 7. mysql 8.0.36安装 二、问题 1.MobaXterm设置右键复制粘贴 2.OpenEuler如何查看CPU的核…
阅读更多...
网络防御保护3

网络防御保护3

一、双击热备 1&#xff0c;根据网段划分配置IP地址和安全区域 2&#xff0c;配置双机热备场景 主备场景配置 抢占延时仅对主设备生效。 hello报文周期时间--- 默认为1S&#xff0c;可以修改&#xff0c;但是&#xff0c;主备设备需要同时修改为相同值。 同步配置 双机热备的…
阅读更多...
【网站项目】424学报稿件管理系统

【网站项目】424学报稿件管理系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…
阅读更多...
一个注解实现频率控制

一个注解实现频率控制

1.概述 抹茶项目是一个即时的IM通信项目&#xff0c;并且有着万人大群。但凡有几个人刷屏&#xff0c;那消息爆炸的场景&#xff0c;都不敢想象。如果我们需要对项目特定的接口进行频率控制&#xff0c;不仅是业务上的功能&#xff0c;同样也保护了项目的监控运行。而频控又是…
阅读更多...
幻兽帕鲁(1.5.0)可视化管理工具（0.5.7 docker版）安装教程

幻兽帕鲁(1.5.0)可视化管理工具（0.5.7 docker版）安装教程

文章目录 局域网帕鲁服务器部署教程帕鲁服务可视化工具安装配置服务器地址&#xff08;可跳过&#xff09;使用工具管理面板 1.5.0服务端RCON错误1.5.0服务端无法启动RCON端口 解决方法第一步&#xff1a;PalWorldSettings.ini配置第二步&#xff1a;修改PalServer.sh配置 局域…
阅读更多...
数据结构--二叉排序树（Binary Search Tree，简称BST）

数据结构--二叉排序树（Binary Search Tree，简称BST）

这里写自定义目录标题 二叉排序树二叉排序树与排序数组没有排序数组&#xff0c;链式存储链表的对比二叉排序树概念对于搜索操作&#xff0c;对于插入操作&#xff0c;对于删除操作&#xff0c; 分析删除节点代码运行结果 二叉排序树 二叉排序树与排序数组没有排序数组&#x…
阅读更多...
python自动化管理和zabbix监控网络设备（防火墙和python自动化配置部分）

python自动化管理和zabbix监控网络设备（防火墙和python自动化配置部分）

目录 前言 一、ssh配置 1.FW1 2.core-sw1 3.core-sw2 二、python自动化配置防火墙 三、验证DNAT 四、验证DNAT 前言 视频演示请访问b站主页 白帽小丑的个人空间-白帽小丑个人主页-哔哩哔哩视频 一、ssh配置 给需要自动化管理的设备配置ssh服务端用户名和密码 1.FW1 …
阅读更多...
Linux NFC 子系统剖析

Linux NFC 子系统剖析

1.总览 linux源码中NFC在net/nfc下&#xff0c;文件结构如下图&#xff1a; hci&#xff1a;Host Controller Interface 主要是针对NFC的主机-控制器接口协议 nci&#xff1a;NFC Controller Interface 主要是NFC的控制器接口协议&#xff0c;用于NFCC(NFC Controller)和DH(…
阅读更多...
进程的控制

进程的控制

文章目录 进程退出进程等待进程程序替换 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 人工智能学习网站&#xff0c; 通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。 点击跳转到网站。 进程退出 进程的退出一共有三种场景。 程序跑完…
阅读更多...
nacos开启鉴权+springboot配置用户名密码

nacos开启鉴权+springboot配置用户名密码

nacos默认没有开启鉴权&#xff0c;springboot无需用户名密码即可连接nacos。从2.2.2版本开始&#xff0c;默认控制台也无需登录直接可进行操作。 因此本文记录一下如何开启鉴权&#xff0c;基于nacos2.3.0版本。 编辑nacos服务端的application.properties&#xff1a; # 开…
阅读更多...
硬件工程师入门基础知识（二）片式电阻、片式网络电阻标识和焊接使用注意事项

硬件工程师入门基础知识（二）片式电阻、片式网络电阻标识和焊接使用注意事项

片式电阻、片式网络电阻标识和使用注意事项 1.概述2.阻值标识2.1 标识原则2.2片式类电阻、片式电阻网络标识方法2.3电阻网络标识方法 3.电阻产品包装3.1片式电阻、片式电阻网络的包装3.2电阻网络的包装 4.使用注意事项4.1 片式电阻推荐焊盘尺寸4.2片式电阻网络推荐焊盘尺寸 5.焊…
阅读更多...
STM32 +合宙1.54“ 电子墨水屏（e-paper）驱动显示示例

STM32 +合宙1.54“ 电子墨水屏（e-paper）驱动显示示例

STM32 合宙1.54“ 电子墨水屏&#xff08;e-paper&#xff09;驱动显示示例 &#x1f4cd;相关篇《Arduino框架下ESP32/ESP8266合宙1.54“ 电子墨水屏&#xff08;e-paper&#xff09;驱动显示示例》&#x1f516;程序是从GooDisplay品牌和微雪电子下同型号规格墨水屏的示例程序…
阅读更多...
Vue项目 快速上手（如何新建Vue项目，启动Vue项目，Vue的生命周期，Vue的常用指令）

Vue项目 快速上手（如何新建Vue项目，启动Vue项目，Vue的生命周期，Vue的常用指令）

目录 一.什么Vue框架 二.如何新建一个Vue项目 1.使用命令行新建Vue项目 2.使用图形化界面新建Vue项目 三.Vue项目的启动 启动Vue项目 1.通过VScode提供的图形化界面启动Vue项目 2.通过命令行的方式启动Vue项目 四.Vue项目的基础使用 常用指令 v-bind 和 v-model v…
阅读更多...
【Unity每日一记】角色控制器Character Contorller

【Unity每日一记】角色控制器Character Contorller

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…
阅读更多...
最新文章

Copyright @ 2022~2023