力扣题3：无重复字符的最长子串
思考：通过逻辑上的双指针和哈希表进行配合，时间复杂度可以化简到O(n)，暴力的话需要找到每个子串O(n^2)，然后查询是否有重复元素O(n)，复杂度是n^3以上。所以用滑动窗口来做是很好的算法。
官方解释：
「滑动窗口」来解决这个问题了：
我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的?每一步的操作中，我们会将左指针向右移动一格，表示我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；
在枚举结束后，我们找到的最长的子串的长度即为答案。
判断重复字符
在上面的流程中，我们还需要使用一种数据结构来判断 是否有重复的字符，常用的数据结构为哈希集合（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）。在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
来源：力扣（LeetCode）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//哈希集合，记录每个字符是否出现过
unordered_set<char> occ;
//rk 是左指针，ans是最大子串长度
int rk=-1,ans=0;
int n = s.size();
for(int i = 0;i<n;i++){
//移动左指针后，把字符从哈希表中除去
if(i!=0){
occ.erase(s[i-1]);
}
//如果有指针下一个位置还有字符，并且在哈希表中没有存储过该字符
while(rk+1<n&&!occ.count(s[rk+1])){
//将下一个字符插入到哈希表
occ.insert(s[rk+1]);
//有指针移动
rk++;
}
//和上一次的答案进行比较取最大
//从i到rk的子串数目
ans = max(ans,rk-i+1);
}
return ans;
}
};
力扣第5题：最长回文子串
方法：动态规划法
时间复杂度O(n^2)
空间复杂度O(n^2)
对于一个子串而言，如果它是回文串，并且长度大于?2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串?“ababa”，如果我们已经知道?“bab”是回文串，那么?“ababa”一定是回文串，这是因为它的首尾两个字母都是?“a”。根据这样的思路，我们就可以用动态规划的方法解决本题。
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
//如果字符串长度为1，则他就是回文串。
if(n<2) return s;
int maxlen=1;
int begin = 0;
//定义二维数组，行列都是n
vector<vector<int>> dp(n,vector<int>(n));
//只有一个字符的子串是回文串
for(int i= 0;i<n;i++){
dp[i][i] = true;
}
//枚举所有子串长度
for(int L=2;L<=n;L++){
//枚举左边界
for(int i=0;i<n;i++){
//通过长度和左边界计算有边界
int j = L+i-1;
//如果有边界越界，则直接结束当前判断
if(j>=n) break;
//如果子串收尾字符不相等，则不是回文串
if(s[i]!=s[j])dp[i][j]=false;
else{
//如果子串字符相等，并且长度只有两个，则是回文子串
if(j-i<3)dp[i][j]=true;
else{
//通过长度比较短的子串来计算长度比较长的子串
dp[i][j]=dp[i+1][j-1];
}
}
//如果当前子串是回文串，并且长度大于先前记录的最大回文串的长度，则更新记录
if(dp[i][j]&&j-i+1>maxlen){
maxlen = j-i+1;
begin = i;
}
}
}
//返回回文串
return s.substr(begin,maxlen);
}
};
AcWing 786 ：第k个数
算法时间复杂度O(n)
思路：用分治递归的思想，把大问题逐渐转化为小问题，然后利用小问题来求解最后的答案。
#include<iostream>
using namespace std;
const int N = 1e5+10;
int q[N];
int n,k;
int quick_sort(int l,int r,int k){
//如果数组就一个数，因为k肯定在数组中所以该数就是要返回的数
if(l==r) return q[l];
int i = l-1,j = r+1,x = q[l];
//利用i ， j把比分界点小的数放到左边，把比分界点大的数放到右边，并返回分界点的下标位置。
while(i<j){
while(q[++i]<x);
while(q[--j]>x);
if(i<j)swap(q[i], q[j]);
}
//获得分界点左边的数的个数
int sl = j-l+1;
//递归处理小区间，如果k在左边的区间，注意一定要包含=k不然会出错
//k-sl表示k在右边区间的下标。
if(sl>=k) return quick_sort(l, j, k);
return quick_sort(j+1, r,k-sl);
}
int main(){
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>q[i];
}
cout<<quick_sort(0,n-1,k)<<endl;
return 0;
}
|