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

笔记:代码随想录算法训练营day46:LeetCode647. 回文子串\516.最长回文子序列

学习资料:代码随想录

647. 回文子串

力扣题目链接

其实个人感觉这里的动规也是一个双指针的方法

// 定义:dp[i][j]表示区间范围为[i,j]左闭右闭的子串是否为回文子串,布尔类型
// 递推公式:如过s[i]==s[j],那么i,j包括两个数或1个数的情况是回文子串,如果包含超过两个数,那么dp[i+1][j-1]是true的话,也返回true,当然不相等就直接false了
// 初始化:可以先都初始化为false
// 遍历顺序:看递推公式
// 打印

// 定义:dp[i][j]表示区间范围为[i,j]左闭右闭的子串是否为回文子串,布尔类型
// 递推公式:如过s[i]==s[j],那么i,j包括两个数或1个数的情况是回文子串,如果包含超过两个数,那么dp[i+1][j-1]是true的话,也返回true,当然不相等就直接false了
// 初始化:可以先都初始化为false
// 遍历顺序:看递推公式
// 打印
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();i>=0;i--){
            for(int j=i;j<s.size();j++){
                if(s[i]==s[j]){
                    if(j-i<=1){
                        dp[i][j]= true;
                        result++;
                    }
                    else if(dp[i+1][j-1]){
                        dp[i][j]=true;
                        result++;
                    }
                }
            }
        }
        return result;
    }
};

双指针:从中心往两边扩散,以一个数为中心时处理的是奇数的回文子串,以两个数为中心时处理的是偶数的回文子串

class Solution {
public:
    int countSubstrings(string s) {
        int result = 0;
        for(int i=0;i<s.size();i++){
            result+=extend(s,i,i,s.size());     //处理奇数回文子串,如aba
            result+=extend(s,i,i+1,s.size());   //处理偶数回文子串,如abba
        }
        return result;
    }
    int extend(const string& s,int i,int j,int n){
        int res;
        while(i>=0&&j<n&&s[i]==s[j]){
            i--;
            j++;
            res++;
        }
        return res;
    }
};

516.最长回文子序列

力扣题目链接

思路:

// 定义:dp[i][j]表示区间[i][j]左闭右闭内的最长回文子序列

// 递推公式:如果s[i]==s[j],那么当前的长度是上一状态dp[i+1][j-1]再加上两个长度,有一种向两侧扩散比较的感觉,否则,就比较去掉s[i]或s[j]的状态,继承dp[i+1][j]或dp[i][j-1].

// 初始化:dp[i][j]在i=j的时候都得是1,首先看递推公式,i=0的话访问j如果从0开始遍历,那访问-1肯定是访问不到,j从j+1开始遍历,这样的话,dp[i][i] 的情况是遍历不到的.或者就单看dp[i][j] = dp[i + 1][j - 1] + 2,也没有遍历dp[i][i]的准备

// 遍历顺序,j要从i+1开始遍历了

// 打印

// 定义:dp[i][j]表示区间[i][j]左闭右闭内的最长回文子序列
// 递推公式:如果s[i]==s[j],那么当前的长度是上一状态dp[i+1][j-1]再加上两个长度,有一种向两侧扩散比较的感觉,否则,就比较去掉s[i]或s[j]的状态,继承dp[i+1][j]或dp[i][j-1].
// 初始化:dp[i][j]在i=j的时候都得是1,首先看递推公式,i=0的话访问j如果从0开始遍历,那访问-1肯定是访问不到,j要从j+1开始遍历,这样的话,dp[i][i] 的情况是遍历不到的.或者就单看dp[i][j] = dp[i + 1][j - 1] + 2,也没有遍历dp[i][i]的准备
// 遍历顺序,j要从i+1开始遍历了
// 打印
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
        for(int i=0;i<s.size();i++){
            dp[i][i] = 1;
        }

        for(int i=s.size()-1;i>=0;i--){
            for(int j=i+1;j<s.size();j++){
                if(s[i]==s[j]){
                    dp[i][j]=dp[i+1][j-1]+2;
                }
                else{
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
                }
            }
        }
        return dp[0][s.size()-1];
    }
};

其实也可以用上一题的方法来初始化,也AC了

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
        // for(int i=0;i<s.size();i++){
        //     dp[i][i] = 1;
        // }

        for(int i=s.size()-1;i>=0;i--){
            for(int j=i;j<s.size();j++){
                if(s[i]==s[j]){
                    if(i==j) dp[i][j]=1;       //把初始化放在这里了
                    else{
                    dp[i][j]=dp[i+1][j-1]+2;
                    }
                }
                else{
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
                }
            }
        }
        return dp[0][s.size()-1];
    }

http://www.kler.cn/a/588622.html

相关文章:

  • 03 介绍ffmpeg 视频解码流程
  • Ubuntu服务器安装JupyterNotebook,以便通过浏览器访问Jupyter
  • 【数据分析】索引与数据筛选(1)
  • 【Prometheus】k8s集群内部署的prometheus如何监控kubernetes集群
  • centos steam8 部署k8s
  • JavaScript性能优化实战指南
  • 腾讯云CloudStudio使用笔记(三)
  • 如何减少跨团队交付摩擦?——基于 DevOps 与敏捷的最佳实践
  • 如何用AI制作PPT,轻松生成高效演示文稿
  • 软件架构设计、详细设计和开发编码的过程中提高性能的技巧和方法
  • REDIS生产环境配置
  • Git使用和原理(3)
  • Git的基本指令
  • C# WPF 基础知识学习(三)
  • Leetcode-1278.Palindrome Partitioning III [C++][Java]
  • 使用 Flask 进行简单服务器改造的详细步骤和代码
  • 在 React 中使用 Web Components 的实践操作
  • Blender-MCP服务源码1-项目解读
  • Linux find 命令完全指南
  • 接口测试中常见的bug有哪些?