wordpress个人展示网站,成都做一个中小企业网站需要多少钱,名字设计签名免费,人力外包网站409 最长回文串
给定一个包含大写字母和小写字母的字符串 s #xff0c;返回 通过这些字母构造成的 最长的 回文串 的长度。
在构造过程中#xff0c;请注意 区分大小写 。比如 Aa 不能当做一个回文字符串。 示例 1:
输入:s abccccdd 输出:7 解…409 最长回文串
给定一个包含大写字母和小写字母的字符串 s 返回 通过这些字母构造成的 最长的 回文串 的长度。
在构造过程中请注意 区分大小写 。比如 Aa 不能当做一个回文字符串。 示例 1:
输入:s abccccdd 输出:7 解释: 我们可以构造的最长的回文串是dccaccd, 它的长度是 7。 示例 2:
输入:s a 输出:1 解释可以构造的最长回文串是a它的长度是 1。
提示:
1 s.length 2000 s 只由小写 和/或 大写英文字母组成
解题思路注意 区分大小写 。比如 Aa 不能当做一个回文字符串。
把所有偶数的加起来奇数的加上它-1的偶数如果最后长度小于字符串长度说明还可以加一个数。
int longestPalindrome(char* s) {int szstrlen(s);int a[26]{};int b[26]{};for(int i0;isz;i){if(a[i]Aa[i]Z)a[s[i]-A];else b[s[i]-a];}int sum0;for(int i0;i26;i){if(a[i]%20)suma[i];else sumsuma[i]-1;if(b[i]%20)sumb[i];else sumsumb[i]-1;}if(sum!sz)sum;return sum;
} ———————题目分割线—————— 5 最长回文子串
给你一个字符串 s找到 s 中最长的 回文子串。
示例 1
输入s babad 输出bab 解释aba 同样是符合题意的答案。 示例 2
输入s cbbd 输出bb
提示
1 s.length 1000 s 仅由数字和英文字母组成
方法一暴力求解
start:子串起始位置求出最长回文子串后s[startlen]\0,原地修改返回
最后返回sstart
分回文子串是奇数和偶数讨论,注意考虑越界情况
(1)奇数 lefti-1righti1
向两侧扩散 a[left]a[right]left--,right
lenright-left-1与len比大小大于则更新len和start的值
2偶数lefti.righti1
与奇数同理
char* longestPalindrome(char* s) {int szstrlen(s),start0,len0;for(int i0;isz;i){int lefti-1,righti1;while(left0rightszs[left]s[right] ){left--;right;}if(right-left-1len){lenright-left-1;startleft1;}}for(int i0;isz;i){int lefti,righti1;while(left0rightszs[left]s[right]){left--;right;}if(right-left-1len){lenright-left-1;startleft1;}}s[startlen]\0;return sstart;
}
方法二:动态规划
dp[i][j]1表示从i到j是回文串
1、初始化dp[i][i]1
2、依此检测长度为23...s.length的字符串是否是回文串
首尾相等的两种情况
1字符长度为23就一定是回文串
2字符长度3,dp[i][j]dp[i1][j-1]
char* longestPalindrome(char* s) {int szstrlen(s),start0,maxl1;int dp[sz][sz]{};for(int i0;isz;i){dp[i][i]1;}for(int len2;lensz;len){for(int i0;isz;i){int jilen-1;if(jsz)break;//注意越界情况if(s[i]s[j]){if(len2)dp[i][j]1;else dp[i][j]dp[i1][j-1];}if(dp[i][j]1lenmaxl){maxllen;starti;}}}s[startmaxl]\0;return sstart;
}
