2022/7/17

Original link ： The finger of the sword Offer 58 - II. Left rotation string

solution:

        recursive

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;
    }
};

  Original link ： The finger of the sword Offer 58 - I. Flip word order  

solution：

        Split string , Back together .

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;
    }
};

        Every time you traverse a word, flip the word , Finally, turn it over  

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;   // Skip leading spaces and skip 
            int j = i,t = k;
            while(j < n && s[j] != ' ') s[t++] = s[j++];    // Save words 
            reverse(s.begin() + k, s.begin() + t);  // Flip Words 
            s[t++] = ' ';   // Add a space 
            k = t,i = j;
        }
        if(k) k--;
        s.erase(s.begin() + k, s.end());    // Delete the last superfluous part 
        reverse(s.begin(), s.end());
        return s;
    }
};

The finger of the sword Offer 59 - I. Maximum sliding window

solution:

        Monotonic stack + The sliding window

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> que; // Double ended queue used by monotonic stack 
        vector<int> res;

        for(int i = 0;i < n;i++) {
            // Over the window size 
            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;

    }
};

        Priority queue

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;    // Define the return value 
        priority_queue<PII, vector<PII>, cmp> heap; // Construct priority queues 
        
        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;
    }
};

The finger of the sword Offer 59 - II. The maximum value of the queue

solution:
        A queue implementation push and pop operation , Another double ended queue maintains the maximum value in the queue

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();
 */