1.最长回文子串 力扣第五题
子串：子串必须要是连续的,区别于子序列的概念
子序列：
对于暴力解法可以优化的地方：只在子串的长度>当前最大的长度的时候，才会去判断回文，
还有没有可以改进的地方呢
class Solution {
public:
bool ishuiwen(string s){
if(s.size()==1) return true;
int i=0;
int j=s.size()-1;
while(i<=j){
if(s[i]!=s[j]){
return false;
}
++i;
--j;
}
return true;
}
string longestPalindrome(string s) {
int n=s.size();
int maxlength=0;
int res_i=0;
int i=0;
for(;i<n;++i){
for(int len=1;len<=n-i;++len){
cout<<"i="<<i<<" len="<<len<<endl;
if(len>maxlength){
string temp=s.substr(i,len);
if(ishuiwen(temp)){
res_i=i;
maxlength=len;
}
}
}
}
cout<<"res_i="<<res_i<<" maxlength="<<maxlength<<endl;
return s.substr(res_i,maxlength);
}
};
动态规划解法：注意maxlength初始化为1 不然“ac”这个用例无法通过，终于通过了，感动，然后需要注意这里的j-i<3的条件 j-i+1<4.
双指针的方式i,j之间的长度为j-i+1, 长度小于4,则可能的长度为1,2,3，在这个else下s[i]==s[j]了，那么一定是回文子串了
这里的maxlength要以1初始化的原因？？因为在下面的这两个嵌套的for循环中，maxlength有可能没有被更新，依然维持了0值，就会产生不正确的结果
也可以对长度为2的字符串进行一个单独的处理？？或许可以
class Solution {
public:
string longestPalindrome(string s) {
if(s.size()<2) return s;
int n=s.size();
vector<vector<int>> dp(n,vector<int>(n)); // 这样的话就全部初始化为0了？ //int dp[n][n];
//i,j分别代表左右边界 状态转移方程 dp[i][j]=1 if(s[i]==s[j] && dp[i+1]dp[) 对于j-i<3的即长度为2或3的子串，不需要dp[i+1】【j-1】的值了
for(int i=0;i<n;++i){//这块写错了！！
dp[i][i]=1;
}
int maxlength=1, res_i=0;
for(int j=1;j<n;++j){
for(int i=0;i<j;++i){
if(s[i]!=s[j]){
dp[i][j]=0;
}
else{
if(j-i<3){
dp[i][j]=1;
}
else{
if(dp[i+1][j-1]==1){
dp[i][j]=1;
}
}
}
if(j-i+1>maxlength && dp[i][j]==1){
res_i=i;
maxlength=j-i+1;
}
}
}
return s.substr(res_i,maxlength);
}
};
2.最长公共子串
对于两个字符串求最长的公共子串
str1.find(str2)在str1里找str2 见有道云笔记上面的记录
还有一种暴力方法，
可以记住这种写法，利用了两个指针i和j 再两个指针m和k
while(m<length1 && k<length2 &&str1[m]==str2[k]) 这一句关键，我们需要用保证m和k的合法性
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str1,str2;
str1="helloworld";
str2="loop";
//cin>>str1;
//cin>>str2;
int length1=str1.size(), length2=str2.size();
int m,k,len,maxlength=0,res_i;
for(int i=0;i<length1;++i){
for(int j=0;j<length2;++j){
m=i;
k=j;
len=0;
while(m<length1 && k<length2 &&str1[m]==str2[k]){
++m;
++k;
++len;
}
if(len>maxlength){
maxlength=len;
res_i=i;
}
}
}
cout<<maxlength<<endl;
cout<<str1.substr(res_i,maxlength);
//cout << "Hello world!" << endl;
return 0;
}
动态规划的解法1：
实际上这个解法下面的数组最好不要命名为dp
为了一遍就获得结果，应该做一些优化
class Solution {
public:
/**
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
string LCS(string str1, string str2) {
// write code here
int m=str1.size(), n=str2.size();
vector<vector<int>> dp(m,vector<int>(n,0));
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(str1[i]==str2[j]){
dp[i][j]=1;
}
}
}
int maxlength=0,res_i=0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
int temp=0;
int u=i, v=j;
while(u<m && v<n && dp[u][v]==1){
++temp;
++u;
++v;
}
if(temp>maxlength){
maxlength=temp;
res_i=i;
}
}
}
return str1.substr(res_i,maxlength);
}
};
改进一下：
if(str1[i]!=str2[j]){
dp[i][j]=0;}
else{
if(i==0 || j==0) dp[i][j]=1;
else dp[i-1][j-1]+1;
}
3.最长公共子序列
也是要用到动态规划的解法，1.确定dp数组以及下标的含义 2.确定状态转移方程
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m=text1.size();
int n=text2.size();
string a="@";
text1=a+text1;
cout<<text1<<endl;
text2=a+text2;
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i=1;i<m+1;++i){
for(int j=1;j<n+1;++j){
if(text1[i]==text2[j]){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
for(auto i:dp){
for(auto j:i){
cout<<j<<" ";
}
cout<<endl;
}
return dp[m][n];
}
};
4.要用到滑动窗口算法的是：
Minimum window substring
给定两个字符串S和T，求S中包含T所有字符的最短连续子字符串的长度