![](https://csdnimg.cn/release/download_crawler_static/86336192/bg6.jpg)
5. 最长回文子串
思路
(双指针)
1、枚举数组中的每个位置 i ,从当前位置开始向两边扩散
2、当回文子串的长度是奇数时,从 i - 1 , i + 1 开始往两边扩散
3、当回文子串的长度是偶数时,从 i , i + 1 开始往两边扩散
4、找到以 i 为中心的最长回文子串的长度,若存在回文子串比以前的长,则更新答案。
图示:
时间复杂度分析:枚举数组中的每个位置 i 需要 的时间复杂度,求回文子串需要 的时间复杂
度,因此总的时间复杂度为 。
c++代码
11. 盛最多水的容器
思路
(双指针扫描)
过程如下:
1、定义两个指针 i 和 j ,分别表示容器的左右边界,初始化 i = 0 , j = h.size() - 1 ,容器大小
为 min(i, j)*(j - i) 。
2、若 h[i] < h[j] ,则 i++ ,否则 j-- ,每次迭代更新最大值。
证明:
容器大小由短板决定, 移动长板的话, 水面高度不可能再上升, 而宽度变小了, 所以只有通过移动短板, 才有
可能使水位上升。
时间复杂度分析: 两个指针总共扫描 次,因此总时间复杂度是 。
}
}
return f[n][m];
}
};
15
16
17
18
19
class Solution {
public:
string longestPalindrome(string s) {
string res;
for(int i = 0; i < s.size(); i++){
int l = i, r = i + 1; //回文串长度为偶数
while(l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
l = i - 1, r = i + 1; //回文串长度为奇数
while(l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15