TODO：
- 自己实现堆
- 熟练使用priority_queue
- 熟练使用快排
- 熟练使用二分法
一、 最小的k个数(简单)
❗ 下次得自己写大顶堆
top-k问题感觉一般用堆就好,或者快排的变体?
但是我好像还不会自己实现堆排序...只会priority_queue<int>
优先队列默认是大顶堆,即降序排列
其具体用法可以参考:
https://blog.csdn.net/lym940928/article/details/89635690
https://www.cnblogs.com/huashanqingzhu/p/11040390.html
关于堆:
https://blog.csdn.net/xiaolinnulidushu/article/details/104629479
方法1 堆排序
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if(k ==0 || arr.size()<k) return{};
if(arr.size()==k) return arr;
priority_queue<int> t;
for(auto it:arr){
if(t.size() >= k){
if(t.top() > it){
t.pop();
}else{
continue;
}
}
t.push(it);
}
vector<int> res;
while(!t.empty()){
res.push_back(t.top());
t.pop();
}
return res;
}
};
方法2 快排的变体 (这次会了可能下次就忘了)
class Solution {
public:
void quickSort(vector<int>&arr, int left, int right, int k){
int i = left, j = right;
while(i < j){
while(i<j && arr[j] >= arr[left]) j--;
while(i<j && arr[i] <= arr[left]) i++;
swap(arr[i],arr[j]);
}
swap(arr[left],arr[i]);
if(i > k) return quickSort(arr,left,i-1,k);
if(i < k) return quickSort(arr,i+1,right,k);
return ;
}
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if(arr.size()<=k) return arr;
quickSort(arr,0,arr.size()-1,k);
vector<int> res;
res.assign(arr.begin(),arr.begin()+k);
return res;
}
};
二、 旋转数组的最小数字(简单)
太简单了，但是应该可以更快，用二分的方法
方法1 遍历
class Solution {
public:
int minArray(vector<int>& numbers) {
for(int i = 1; i < numbers.size(); i++){
if(numbers[i-1] > numbers[i]) return numbers[i];
}
return numbers[0];
}
};
方法2 二分法(不大熟练）⭐
看leetcode题解中的这两个图比较方便理解
image.png
image.png
class Solution {
public:
int minArray(vector<int>& numbers) {
int n = numbers.size();
int left = 0, right = n-1;
while(left < right){
int mid = left + ( right - left)/2;
if(numbers[mid] < numbers[right]){
right = mid;
}else if(numbers[mid] > numbers[right]){
left = mid+1;
}else{right--;}
}
return numbers[left];
}
};
三、最长不含重复字符的子字符串（中等）
自己做出来了，不过最开始又想错了。
一开始想的是创建一个set，当有相同元素时，就清空set，从新开始计数。
但是遇到如dvdf的情况，就只能只能计数为dv，2。清空后从第二个d开始计数，然后df最后求出来的子字符串的个数就只是2。
因此换了一个思路，类似于用双指针构建滑动窗口，指定一个区间，让区间中的字符串都无重合。利用map记录`a-z'的最新坐标，t为区域的长度，只要在区域内有重复的，就更新区域的长度和最新字符的坐标。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0,t = 0;
unordered_map<char,int> idx;
for(int i = 0; i < s.size(); i++){
char it = s[i];
if(idx.find(it) == idx.end() || idx[it] < i -t){
t ++;
idx[it] = i;
ans = max(ans,t);
}else{
t = i - idx[it];
idx[it] = i;
}
}
return ans;
}
};
