Day5 最小的k个数+旋转数组的最小数字+最长不含重复字符的子

TODO：

1. 自己实现堆
2. 熟练使用priority_queue
3. 熟练使用快排
4. 熟练使用二分法

一、 最小的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;

    }
};