Your Site Title

Leetcode春招课

 
  • Jan 19, 2021

春招冲鸭

数组与字符串

3. 无重复字符的最长子串

分类：滑动窗口

如果右边加入一个字符产生重复，左边吐出一个字符继续判断。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i=0, j=0, maxsize = 0;
        map<char, bool> m;
        while(j<s.size()){
            char c = s[j];
            if(!m[c]){
                m[c] = true;
                j++;
            }else{
                maxsize = max(maxsize, j-i);
                m.erase(s[i]);
                i++;
            }
	    }
	
	    maxsize = max(maxsize, j-i);;
	    return maxsize;
    }
};

class Solution {
public:
	// 道理是一样的，写法不同而已
    int lengthOfLongestSubstring(string s) {
        int i=0, j=0, maxsize = 0;
        map<char, bool> m;
        for(int i=0; i<s.size(); i++){
            while(j<s.size() && !m[s[j]]){
                m[s[j]] = true;
                j++;
            }
            maxsize = max(maxsize, j-i);
            m.erase(s[i]);
        }
	    return maxsize;
    }
};

排序

215. 数组中的第 K 个最大元素

快排的分治思想

class Solution {
public:
    int partion(vector<int>& nums, int l, int r){
        int pivot = nums[l];
        while(l != r){
            while(l<r && pivot<=nums[r]) r--;
            nums[l] = nums[r];
            while(l<r && nums[l]<=pivot) l++;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }

    int find(vector<int>& nums, int l, int r, int k){
        int i = partion(nums, l, r);
        if(i == k){
            return nums[i];
        }else if(i > k){
            return find(nums, l, i-1, k);
        }else {
            return find(nums, i+1, r, k);
        }
    }


    int findKthLargest(vector<int>& nums, int k) {
        return find(nums, 0, nums.size()-1, nums.size()-k);
    }
};
Search