首页 > 编程语言 >leetcode 6356 最长回文子串长度,最长回文子串 C/C++ 动态规划方案 同样的用例,测试执行代码通过,提交不通过 问题解决

leetcode 6356 最长回文子串长度,最长回文子串 C/C++ 动态规划方案 同样的用例,测试执行代码通过,提交不通过 问题解决

时间:2022-09-05 16:56:08浏览次数:62  
标签:子串 int max 最长 dp 回文

对dp 变量需要执行初始化,否者LeetCode 会出现同样的用例,单独执行可以通过,提交代码执行不通过的情况。   下面是找最长回文串的动态规划代码。 class Solution { public:     string longestPalindrome(string s) {         int dp[1000][1000] ={0};  // d[i][j]  i 位置开始,j位置结束的子串 是否是回文串 ,这里需要初始化,否提交代码时不通过         int max = 1;         // 保存最大的回文串长度         int i_max = 0;         for(int j = 1; j< s.size();j++){             dp[j][j]=1;           //初始化,自己肯定是回文串。             if(s[j-1] == s[j]) {  // 处理回文串为2的情况。                 dp[j-1][j] = 1;                 if(max < 2){                         max = 2;                         i_max = j-1;                 }             }             for(int i = j-2;i >=0; i--){  // 从回文串至少是3的地方开始                 if(s[i] == s[j] && dp[i+1][j-1]){                     dp[i][j]=1;                     if(max < (j-i + 1)){                         max = j - i + 1;                         i_max = i;                     }                 }             }         }         return s.substr(i_max,max);     } };

标签:子串,int,max,最长,dp,回文
From: https://www.cnblogs.com/daniel123/p/16658753.html

相关文章

  • 1048. 最长字符串链
    给出一个单词数组 words ,其中每个单词都由小写英文字母组成。如果我们可以 不改变其他字符的顺序 ,在wordA 的任何地方添加恰好一个字母使其变成 wordB ,那么我们......
  • codeforces.ml/contest/932/problem/D 树上找最长上升子序列长度 倍增算法
    D.Treetimelimitpertest2secondsmemorylimitpertest512megabytesinputstandardinputoutputstandardoutputYouaregivenanodeofthetreew......
  • leetcode 674 最长连续递增序列 C/C++ 动态规划,动态规划空间优化,双指针 三种解法,初识
    #if 0class Solution {  //动态规划public:    int findLengthOfLCIS(vector<int>& nums) {        vector<int> dp(nums.size());     ......
  • 滑动窗口-区间长度最大值-6169. 最长优雅子数组
    问题描述给你一个由正整数组成的数组nums。如果 nums的子数组中位于不同位置的每对元素按位与(AND)运算的结果等于0,则称该子数组为优雅子数组。、返回最长......
  • LeetCode 131 分割回文串
    classSolution{public:vector<vector<string>>res;vector<string>path;boolis(strings,intstart,intend){for(inti=start,j=......
  • [LC646]最长数对链
    题目概述给出 n 个数对。 在每一个数对中,第一个数字总是比第二个数字小。现在,我们定义一种跟随关系,当且仅当 b<c 时,数对(c,d) 才可以跟在 (a,b) 后面。我们......
  • 信息学一本通 1309:【例1.6】回文数(Noip1999)
    时间限制:1000ms      内存限制:65536KB提交数:17647   通过数:7270【题目描述】若一个数(首位不为零)从左向右读与从右向左读都是一样,我们就将其......
  • letcode算法--9.最长公共前缀
    编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。示例1:输入:strs=["flower","flow","flight"]输出:"fl"示例2:输入:strs=["dog......
  • 687. 最长同值路径
    687.最长同值路径给定一个二叉树的 root ,返回 最长的路径的长度,这个路径中的 每个节点具有相同值 。这条路径可以经过也可以不经过根节点。两个节点之间的路......
  • letcode算法--7.回文数
    给你一个整数x,如果x是一个回文整数,返回true;否则,返回false。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121是回文,而123不是。来源:力扣(Leet......