-
PAT——A1040 Longest Symmetric String(最长回文串 动态规划 还是hash的解法后面补充)
2018-08-21 10:22:28题目链接: #include <iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std;...in...#include <iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define maxn 1010 string S; int dp[maxn][maxn]; int main() { getline(cin,S); int len=S.length(); int ans=1; for(int i=0;i<len;i++) { dp[i][i]=1; if(i<len-1) { if(S[i]==S[i+1]) { dp[i][i+1]=1; ans=2; } } } for(int L=3;L<=len;L++) { for(int i=0;i+L-1<len;i++) { int j=i+L-1; if(S[i]==S[j]&&dp[i+1][j-1]) { dp[i][j]=1; ans=L; } } } printf("%d\n",ans); return 0; }
不懂为啥pat过不了gets的编译
getline又不能用char类型的字符数组
-
python最长回文子串动态规划_最长回文子串问题
2021-01-29 23:26:15问题描述回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。输入一个字符串Str,输出Str里最长回文子串的长度。方法一:暴力求解遍历每一...方法二:动态规划法用一个二维的数组ai来表示从第i位到第j位的子...问题描述
回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str,输出Str里最长回文子串的长度。
方法一:暴力求解
遍历每一个子串,再判断这个子串是不是回文串,最后判断这个串是不是最长的回文子串。
遍历子串的复杂度是O(n^2),判断是不是回文串的复杂度是O(n),所以这个算法的复杂度是O(n^3)。
方法二:动态规划法
用一个二维的数组ai来表示从第i位到第j位的子串是不是回文串,在判断从i到j的子串是不是回文串时,可以先看i+1到j-1是不是回文串,再判断i位和j位是不是相同。这个算法中,遍历子串的复杂度仍然是O(n^2),但是判断是不是回文串的复杂度降到了O(1),所以这个算法的复杂度是O(n^2)。但是这个算法占据了O(n^2)的空间。
方法三:中心扩展法
顾名思义,任何一个回文串都有一个对称轴,从这个中心的位置开始,向两边扩展,可以得到以此为中心的最长回文串。但是要注意,这个对称轴的位置,可能是一个字符,也可能是两个字符中间。遍历对称轴的位置,复杂度是O(n),找到以此对称轴为中心的最长回文串,其复杂度是O(n),所以此算法的复杂度是O(n^2)。这个算法比动态规划好的地方是其空间复杂度只有O(1)。
#include
#include
using namespace std;
#define LEN 1000
int main(){
char str[LEN];
cin>>str;
int len=strlen(str);
int maxlen=0,mx;
for(int i=0;i
mx=1;
for(int j=1;(i-j>=0)&&(i+j
if(str[i-j]==str[i+j])
mx+=2;
else break;
}
maxlen=maxlen>mx?maxlen:mx;
}
for(int i=0;i
mx=0;
for(int j=0;(i-j>=0)&&(i+j+1
if(str[i-j]==str[i+j+1])
mx+=2;
else break;
}
maxlen=maxlen>mx?maxlen:mx;
}
cout<
return 0;
}
方法四:manacher算法
预处理
在字符串的开始加上一个'$'符,然后在每个字符中间插上一个'#'。比如,字符串ss='abac',处理之后是str='$#a#b#a#c#'。接下来的计算针对处理后的字符串。
len数组
然后定义一个len数组,len[i]表示的是以str[i]为中心的最长回文串的半径。
仍以上面的字符为例。str='$#a#b#a#c#',以str[0]为中心的最长回文串是'$',其半径是1;以str[4]为中心的最长回文串是'#a#b#a#',其半径是4;len数组为{1,1,2,1,4,1,2,1,2,1}。可以发现,len[i]-1的值,就是原字符串ss中对应的回文串的长度(以#为中心的是偶长度的回文串,以字符为中心的是奇长度的回文串)。
计算len数组
算法的关键在于在计算len数组时,可以利用前面的结果进行优化。
引入变量maxright表示当前访问到的所有回文子串,所能触及的最右一个字符的位置;同时记录maxright所对应的回文串的对称轴的位置,记为pos。
复杂度分析
考虑p的值的变化,在计算的过程中,p只会增加不会减少,当p增加到strlen(str)时,每个位置的len数组的值都可以立即计算得出。所以算法的复杂度是O(n)。
#include
#include
#include
using namespace std;
#define N 100004
string str,ss;
int len[2*N+1];
int main()
{
cin>>ss;
str="$#";
for(unsigned int i=0;i
{
str+=ss[i];
str+="#";
}
// cout<
int pos=0,p=0,j=0;
len[0]=1;
for(unsigned int i=1;i
{
j=2*pos-i;
if(p>i)
len[i]=(len[j]>p-i)?(p-i):(len[j]);
else
len[i]=1;
while(i+len[i]=0&&str[i+len[i]]==str[i-len[i]])
len[i]++;
if(i+len[i]>=p)
{
pos=i;
p=i+len[i];
}
}
int ans=0;
for(int i=0;i
{
// cout<
ans=(len[i]-1>=ans)?len[i]-1:ans;
}
// cout<
cout<
return 0;
}
-
最长回文子串动态规划_最长回文子串(动态规划)
2020-12-03 03:07:09题目:给定一个字符串s,找到s中最长的回文子串。你可以假设s的最大长度为 1000。示例1:输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。示例2:输入: "cbbd"输出: "bb"解题思路:举个例子,“b”是一个...题目:
给定一个字符串
s
,找到s
中最长的回文子串。你可以假设s
的最大长度为 1000。示例1:
输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。
示例2:
输入: "cbbd"输出: "bb"
解题思路:
举个例子,“b”是一个回文子串,左右两边同时加入“a”,则“aba”也一定是回文子串,如此可以得出一个结论:在回文子串左右加入相同的字符,新的子串也一定是回文子串。
长度为1的字符是回文子串。
长度为2的字符串,如果左右字符相同,则该字符串为回文子串。
由1-3的结论可以通过动态规划思想来解此题。
Python代码:
class Solution: def longestPalindrome(self, s: str) -> str: s_length = len(s) # 记录每一个字符片段是否是回文子串 status = [[False] * s_length for _ in range(s_length)] result = "" # length是字符串片段的长度 for length in range(s_length): # i, j 分别指向字符串片段的左右两端 for i in range(s_length): j = i + length if j >= s_length: break if length == 0: status[i][j] = True elif length == 1: status[i][j] = (s[i] == s[j]) else: status[i][j] = status[i + 1][j - 1] and (s[i] == s[j]) if status[i][j] and length + 1 > len(result): result = s[i:j + 1] return result
--END--
-
最长回文子串动态规划_算法 - 动态规划 - 最长回文子串
2020-11-23 10:33:30题目Given a string s, find the longest ...给定一个字符串s,知道到字符串中的最长回文子串。假定字符串最大长度为1000. 分析这个题目有很多中算法。这里只讲动态规划的算法。 其他的算法可以自己去leetcod...题目
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
给定一个字符串s,知道到字符串中的最长回文子串。假定字符串最大长度为1000.
分析
这个题目有很多中算法。这里只讲动态规划的算法。 其他的算法可以自己去leetcode上去找。
动态规划的套路就是你需要先假定你已经找到了答案,然后分析答案的特点。然后给出状态转移方程。只要能够写出递归的状态转移方程,剩下的编码就是小case了。
假定最长的回文子串已经找到: S[i] S[i+1]...S[j-1]S[j] ,那么一个很明显的规律就是,如果S[i,j] 是回文的话,那么S[i] == S[j] 并且 S[i+1]...S[j-1] 肯定也是回文。
状态转移方程:
基本条件:
示例图
以 ABBA为例,计算的过程 代码
public
-
最长回文子串动态规划_经典面试题:最长回文子串
2020-12-03 03:07:12预计阅读时间:5 分钟回文串是面试常常遇到的问题(虽然问题本身没啥意义),本文就告诉你回文串问题的核心思想是什么。首先,明确一下什:回文串就是正着读和反着读都一样的字符串。比如说字符串aba和abba都是回文串... -
最长回文子串动态规划_【算法刷题】最长回文子串
2020-12-03 03:07:10动态规划法4. Manacher 算法所谓回文串,就是正序和逆序都相同的子串。(上海自来水来自海上)子串是原字符串的连续部分,这区别于子序列。1. 暴力枚举法时间复杂度:O(n^3)空间复杂度:O(1)classSolution{public:... -
最长回文子串动态规划_最长回文子串——马拉车算法
2020-11-22 15:05:05简介马拉车算法(Manacher‘s Algorithm)是用来查找一个字符串的最长回文子串的线性方法,由一个叫 Manacher 的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性。这个算法最厉害的地方是在于... -
最长回文子串动态规划_leetcode No.5 最长回文子串
2020-11-28 23:38:01题目链接:最长回文子串 - 力扣(LeetCode)leetcode-cn.com题目描述:给定一个字符串 s,找到 s 中最长的回文子串...输出: "bb"解题思路:要找到字符串中的最长回文子串,显然可以用暴力循环解决,遍历所有可能的... -
最长回文串(动态规划)
2019-12-31 09:41:27给定一个字符串 s,找到 s 中最长的回文子串。你可以假设s 的最大长度为 1000。 示例 1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2: 输入: "cbbd" 输出: "bb" 思路一:翻转字符串法。... -
最长回文子串动态规划_大厂笔试题——LeetCode05最长回文子串
2020-11-24 11:19:00示例 2:输入: "cbbd"输出: "bb"普通暴力分析:求最长的回文串。而回文串又有奇数串和偶数串两种形式,我们只需要对有所情况从左到右进行枚举,然后返回最长的串即可。在编写代码的同时注意边界的问题不能越界... -
最长回文子串动态规划_BAT 高频面试题 | 最长回文子串
2020-12-01 05:03:55最长回文子串leetcode-cn.com题目描述:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1:输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。示例 2:输入: "cbbd" ... -
最长回文子串动态规划_九章算法 | 微软面试题:最长回文子串
2020-12-03 03:07:09给出一个字符串(假设长度最长为1000),求出它的最长回文子串,你可以假定只有一个满足条件的最长回文串。在线评测地址:LintCode 领扣样例 1:输入:"abcdzdcab" 输出:"cdzdc"样例 2:输入:"aba" 输出:"aba"【题解】 ... -
最长回文子串动态规划_每天一道算法题:最长回文子串
2020-12-03 03:07:13输入:"babad"输出:"bab"注意:"aba"也是一个有效答案输入:"cbbd"输出:"bb"思路:暴力法列举出所有的子串,时间复杂度:O(n^2)检查每一个子串是否为回文串,每一个子串所需时间复杂度:O(n)总共时间复杂度:O(3^n... -
最长回文子串动态规划_LeetCode5最长回文子串
2020-11-28 22:04:33这两天被这个题弄得是有些崩溃了,...题目如下:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。示例 1:输入: "babad"输出: "bab"注意: "aba"也是一个有效答案。示例 2:输入: "cbbd"... -
最长回文子串 动态规划
2020-06-20 22:39:30寻找二维动态规划表达式dp[i][j],如果直接用dp[i][j]表示子符串从S[i]到S[j]的最长回文子串长度无法得出递推表达式。 令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串,是则为1,不是为0; if(s[i]==s[j]) dp[i... -
最长回文子串动态规划_【前端学算法】最长回文子串
2020-12-03 03:07:07给定一个字符串s,找到s中最长的回文子串。你可以假设s的最大长度为1000。示例输入:"babad"输出:"bab"注意:"aba"也是一个有效答案。动态规划法思路动态规划的思想,是希望把问题划分成相关联的子问题;然后从最... -
【最长回文子串 动态规划】
2020-09-18 15:56:58问题描述 VJ原题 输入一个字符串Str,输出Str里最长回文子串的长度。 回文串:指aba、abba、cccbccc、aaaa这种左右对称的字符串。 串的子串:一个串的子串指此(字符)串中连续的一部分...使用动态规划。如果str[i][j] -
最长回文子串动态规划_leetcode 5 最长回文子串(c++)
2020-11-28 23:38:19### 题目给定一个字符串 s,找到 s 中最长的回文子串。你可以假设s的最大长度为1000。示例 1:输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。示例 2:输入: "cbbd"输出: "bb"### 思路主要是要找好动态转移... -
最长回文子串动态规划_你必须掌握动态规划——LeetCode题目5:最长回文子串
2020-12-03 03:07:13原题描述+给定一个字符串s,找到s中最长的回文子串。你可以假设s的最大长度为1000。示例 1输入:"babad"输出:"bab"注意: "aba" 也是一个有效答案。示例 2输入:"cbbd"输出:"bb"原题链接:... -
python最长回文子串动态规划_Leetcode(5)-最长回文子串(包含动态规划以及Manacher算法)...
2020-12-11 03:17:17示例 2:输入: "cbbd"输出: "bb"自己的思路:求一个字符串的最长回文子串,我们可以将以每个字符为首的子串都遍历一遍,判断是否为回文,如果是回文,再判断最大长度的回文子串。算法简单,但是算法复杂度太高,O(n^... -
leetcode 5 最长回文子串 动态规划 python深浅复制
2020-07-28 23:06:22leetcode 5 最长回文子串 动态规划 python深浅复制 知识准备——动态规划 动态规划思想本质上是分治与递归。 四大部分 划分状态,即将父问题划分为可以递归的若干相同模式的子问题。 状态表示,即将子问题用计算机... -
LeetCode 5:最长回文子串 动态规划解法
2020-01-27 14:51:10LeetCode 5:最长回文子串 动态规划解法 【传送门】 题目描述 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效... -
最长回文子串动态规划_Leetcode5: Longest Palindromic Substring-最长回文子串
2020-12-01 05:09:34一、题目描述给定一个字符串s,找到s中最长的回文子串。你可以假设 s的最大长度为 1000。示例 1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2: 输入: "cbbd" 输出: "bb"二、解题思路参考... -
刷题 最长回文子串 动态规划
2019-06-12 18:15:14思路: 假设串长为N 先建立一个N*N的二维数组arr. arr[i][j] = 1 代表 s[i.....j]子串为回文串。 初始arr的值全为0; A. arr[i][i] = 1,单个字母是回文串。 B. 若s[i]==s[i+1]... -
动态规划之最长回文串
2020-01-16 19:48:502.动态规划 dp[i][j]表示“以s[i]开始s[j]结尾的回文串的长度。如果这个字符串不是回文串,让dp[i][j]=0”。显然,j>=i,只需往dp填j>=i的部分即可。 dp[i][j]的递推公式可以这么表述: (1)首先对dp的对... -
动态规划-最长回文串
2018-07-06 17:52:501. 最长回文串 给定一个字符串 s,找到 s 中最长的回文子串。假设 s 的最大长度为1000。 示例 1: 输入: &quot;babad&quot; 输出: &quot;bab&quot; 注意: &quot;aba&... -
动态规划 最长回文串
2020-04-02 16:22:26dp[i][j]:表示S[i]到S[j]是否是回文串,是为1,不是为0 状态转移方程: dp[i][j] = dp[i+1][j-1] ,S[i]==S[j] dp[i][j] = 0, ,S[i]!=S[j] 1.边界:dp[i][i] = 1,dp[i][i+1] = (S[i] == S[i+1]) ? 1:0 2.枚举:...