2022/7/17

原题链接：剑指 Offer 58 - II. 左旋转字符串

solution:

        递归

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(),s.begin() + n);
        reverse(s.begin() + n,s.end());
        reverse(s.begin(),s.end());
        return s;
    }
};

 原题链接：剑指 Offer 58 - I. 翻转单词顺序 

solution：

        分割字符串，重新组合。

class Solution {
public:
    string reverseWords(string s) {
        auto words = split(s, ' ');
        int n = words.size();
        string res;
        for(int i = n - 1;i >= 0;i--) {
            res += words[i];
            if(i) res += " ";
        }
        return res;
    }

    vector<string> split(string s, char t) {
        int n = s.size();
        vector<string> res;
        for(int i = 0;i < n;i++) {
            int j = i;
            string item;
            while(j < n && s[j] != t) {
                item += s[j];
                j++;
            }
            if(item != "") res.push_back(item);
            i = j;
        }
        return res;
    }
};

        每遍历一个单词翻转该单词,最后总的翻转一遍 

class Solution {
public:
    string reverseWords(string s) {
        int k = 0;
        int n = s.size();
        for(int i = 0;i < n;i++) {
            if(s[i] == ' ') continue;   //跳过前导空格则跳过
            int j = i,t = k;
            while(j < n && s[j] != ' ') s[t++] = s[j++];    //保存单词
            reverse(s.begin() + k, s.begin() + t);  //翻转单词
            s[t++] = ' ';   //添加一个空格
            k = t,i = j;
        }
        if(k) k--;
        s.erase(s.begin() + k, s.end());    //将最后多余部分删掉
        reverse(s.begin(), s.end());
        return s;
    }
};

剑指 Offer 59 - I. 滑动窗口的最大值

solution:

        单调栈+滑动窗口

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> que; //单调栈使用的双端队列
        vector<int> res;

        for(int i = 0;i < n;i++) {
            //超过窗口大小
            if(!que.empty() && i - que.front() + 1 > k) que.pop_front();

            while(!que.empty() && nums[que.back()] <= nums[i]) que.pop_back();
            que.push_back(i);
            if(i + 1 >= k) res.push_back(nums[que.front()]);             
        }
        return res;

    }
};

        优先队列

class Solution {
public:
    typedef pair<int,int> PII;
    struct cmp {
        bool operator() (PII &a, PII &b) {
            return a.first < b.first;
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        if(!n) return {};
        vector<int> res;    //定义返回值
        priority_queue<PII, vector<PII>, cmp> heap; //构造优先队列
        
        for(int i = 0;i < k;i++) heap.emplace(nums[i], i);
        res.push_back(heap.top().first);

        for(int i = k;i < n;i++) {
            heap.emplace(nums[i], i);

            while(heap.top().second < i - k + 1) {
                heap.pop();
            }  
            res.push_back(heap.top().first);
        }
        return res;
    }
};

剑指 Offer 59 - II. 队列的最大值

solution:
        一个队列实现push和pop操作,另一个双端队列维护队列中的最大值

class MaxQueue {
public:
    queue<int> que;
    deque<int> deq;
    int maxv = 0;
    MaxQueue() {

    }
    
    int max_value() {
        if(deq.empty()) return -1;
        else return deq.front();
    }
    
    void push_back(int value) {
        que.push(value);
        while(!deq.empty() && deq.back() <= value) deq.pop_back();
        deq.push_back(value);
    }
    
    int pop_front() {
        if(que.empty())
            return -1;
        int t = que.front();
        que.pop();
        if(t == deq.front())
            deq.pop_front();
        return t;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */