剑指offer 58与59


剑指offer 58与59

1.面试题58 - I. 翻转单词顺序

跳过前面的空格。

从非空格开始遍历。

使用[j,i)表示每一个单词,将其入栈。

最后一个单词是否入栈做个判断。

将栈顶的所有空字符串弹出。

开始拿出栈种字符串进行拼接。

class Solution {
public:
    string reverseWords(string s) {
        string res = "";
        int i=0,j=0;
        stack<string> st;
        while(i<s.size() && s[i]==' ') {
            i++;
            j++;
        }

        while(i<s.size()) {
            if(s[i]==' ') {
                if(s[j]!=' ') {
                    st.push(s.substr(j,i-j));
                    st.push(" "); 
                }
                j=i+1;
            }
            i++;
        }
        // 最后一个是个字符串
        if(j<s.size()) st.push(s.substr(j,i-j));
        // 排除空串引起错误
        while(!st.empty() && st.top()==" ") {
            st.pop();
        }
        while(!st.empty()) {
            res+=st.top();
            st.pop();
        }

        return res;
    }
};

2.面试题58 - II. 左旋转字符串

method1:分割两个部分字符串,后面拼接前面。

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        // 0~s.size()-1
        int k = n%(s.size());

        string res1(s.begin()+k,s.end());
        string res2(s.begin(),s.begin()+k);
        return res1+res2;
    }
};

3.面试题59 - I. 滑动窗口的最大值

method1:暴力法。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        int r;
        int i=0,j=k-1;
        while(j<nums.size()) {
            r = nums[i];
            for(int k=i+1;k<=j;k++) {
                r = max(r,nums[k]);
            }
            res.push_back(r);
            i++;
            j++;
        }
        return res;
    }
};

method2:单调递增队列。双端队列,最左边保存当前滑动窗口的最大值,当队尾元素小于等于当前元素的时候,队尾依次出队。保证双端队列是个单调递减队列。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> dq;
        for(unsigned int i=0;i<nums.size();i++) {
            //从后面依次弹出队列中比当前num值小的元素,同时也能保证队列首元素为当前窗口最大值下标
            while(!dq.empty() && nums[dq.back()]<=nums[i]) {
                dq.pop_back();
            }
            //当当前窗口移出队首元素所在的位置,即队首元素坐标对应的num不在窗口中,需要弹出
            while(!dq.empty() && i-dq.front()+1 > k) {
                dq.pop_front();
            }
            dq.push_back(i); //把每次滑动的num下标加入队列

            // 排除k=0特殊条件,k=0时应该返回空。
            if(k && i+1>=k) { //当滑动窗口首地址i大于等于size时才开始写入窗口最大值
                res.push_back(nums[dq.front()]);
            }
        }   
        return res;
    }
};

4.面试题59 - II. 队列的最大值

使用queue保存正常数据流,使用deque保存当前及下一个最大值。

class MaxQueue {
private:
    queue<int> q;
    deque<int> dq;
public:
    MaxQueue() {

    }

    int max_value() {
        return dq.empty() ? -1 : dq.front();
    }

    void push_back(int value) {
        q.push(value);
        while(!dq.empty()&&dq.back()<value) {
            dq.pop_back();
        }
        dq.push_back(value);
    }

    int pop_front() {
        if (q.empty()) return -1;
        int cur = q.front();
        q.pop();
        if(cur==dq.front()) {
            dq.pop_front();
        }
        return cur;
    }
};

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

更多内容,订阅公众号

文章作者: light-city
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 light-city !
评论
  目录