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所有字元的最短連續子字元串的長度