day24

【0150.逆波兰表达式求值】

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st1;
        long long temp1;
        long long temp2;
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+") {
                 temp1 = st1.top();
                 st1.pop();
                 temp2 = st1.top();
                 st1.pop();
                 st1.push(temp1 + temp2);
            }
            else if (tokens[i] == "+") {
                 temp1 = st1.top();
                 st1.pop();
                 temp2 = st1.top();
                 st1.pop();
                 st1.push(temp1 - temp2);
            }
            else if (tokens[i] == "*") {
                 temp1 = st1.top();
                 st1.pop();
                 temp2 = st1.top();
                 st1.pop();
                 st1.push(temp1 * temp2);
            }
            else if (tokens[i] == "/") {
                 temp1 = st1.top();
                 st1.pop();
                 temp2 = st1.top();
                 st1.pop();
                 st1.push(temp2 / temp1);
            }
            else {  
                st1.push(stoll(tokens[i]));
            }
        }
        return st1.top();
    }
};

• 运行成功 开始不成功 把 return st1.top(); 改成 int result = st1.top(); return result;成功了 改回去想看看是什么问题结果竟然也成功了 所以上面那段代码是正确的 不知道为什么之前不成功现在却成功了
• 思路没问题 跟之前本科学校老师讲过的一样 就是没实现过 所以代码语句上有些需要留意的
  • 设置成 long long 或者 int 应该都没问题
  • 注意 默认pop()函数只能删除栈顶元素 不能获取栈顶元素值 所以需要获取栈顶元素值就需要top()
  • 当获得的字符数组元素值是’+’ ‘-‘ ‘*’ ‘/’ 时 需要进行对应的操作 但是当前tokens[i]只是字符 并不是运算符号 因此 我就想 有什么函数可以让我获得的tokens[i] 就能进行对应字符 对应的运算效果 但是没有这个函数 。。。自己动手实现这个效果思路很简单 就是if(字符是’+’) 那就temp1 + temp2; if(字符是’-‘) 那就temp1 – temp2; 乘法除法类似。
  • st1.push(stoll(tokens[i])); stoll函数 强制类型转换为long long int型 类似的stol强制转换为long int型。 因为push(元素必须是int 型)
• 卡哥代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
<<<<<<< HEAD
        stack<long long> st;
=======
        // 力扣修改了后台测试数据，需要用longlong
        stack<long long> st; 
>>>>>>> 28f3b52a82e3cc650290fb02030a53900e122f43
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            } else {
                st.push(stoll(tokens[i]));
            }
        }

        int result = st.top();
        st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
        return result;
    }
};

【0239.滑动窗口最大值】

class Solution {
public:
    int maxx(int n1, int n2, int n3) {
        int result = n1;
        if (result < n2)
            result = n2;
        if (result < n3)
            result = n3;
        return result;
    }
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int resultSize = nums.size() - k + 1;
        vector<int> result (resultSize, 0);
        int j = 0;
        queue<int> que1;
        for (int i =0; i < nums.size(); i++) {
            if (i < k) {
                que1.push(nums[i]);
                if (i == k-1) {
                    result[j] = maxx(nums[i], nums[i - 1], nums[i - 2]);
                    j++;
                }
                break;
            }
            que1.pop();
            que1.push(nums[i]);
            result[j] = maxx(nums[i], nums[i - 1], nums[i - 2]);
            j++;
        }
        return result;
    }
};

• break 换成 continue 否则只执行了一次就不再循环了

class Solution {
public:
    int maxx(int n1, int n2, int n3) {
        int result = n1;
        if (result < n2)
            result = n2;
        if (result < n3)
            result = n3;
        return result;
    }
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int resultSize = nums.size() - k + 1;
        vector<int> result (resultSize, 0);
        int j = 0;
        queue<int> que1;
        for (int i =0; i < nums.size(); i++) {
            if (i < k) {
                que1.push(nums[i]); 
                if (i == 0 && nums.size() == 1) {
                    result[j] = nums[i];
                    return result;
                }
                if (i == 1 && nums.size() == 2) {
                    result[j] = nums[i] > nums[i - 1] ? nums[i] : nums[i - 1];
                    return result;
                }
                if (i == k-1) {
                    result[j] = maxx(nums[i], nums[i - 1], nums[i - 2]);
                    j++;
                }
                continue;
            }
            que1.pop();
            que1.push(nums[i]);
            result[j] = maxx(nums[i], nums[i - 1], nums[i - 2]);
            j++;
        }
        return result;
    }
};

• 上面代码运行部分不通过

  输入[1,3,-1,-3,5,3,6,7] 3

  输出[3,3,5,5,6,7]

  预期结果[3,3,5,5,6,7]

  但是 有问题的用例：

  Line 1034: Char 34: runtime error: addition of unsigned offset to 0x602000000210 overflowed to 0x60200000020c (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34

  最后执行的输入：

  [1,-1] 1

• 这个思路 只能说是对了一半 想到了队列 但不会用 这就是当时课堂上 类似课后理论题见过 但代码题没实现过

• 卡哥思路 单调队列能理解 但怎么想到的 怎么在这道题用的 我暂时还没看懂

class Solution {
private:
    class MyQueue { //单调队列（从大到小）
    public:
        deque<int> que; // 使用deque来实现单调队列
        // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
        // 同时pop之前判断队列当前是否为空。
        void pop(int value) {
            if (!que.empty() && value == que.front()) {
                que.pop_front();
            }
        }
        // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
        // 这样就保持了队列里的数值是单调从大到小的了。
        void push(int value) {
            while (!que.empty() && value > que.back()) {
                que.pop_back();
            }
            que.push_back(value);

        }
        // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
        int front() {
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
            que.push(nums[i]);
        }
        result.push_back(que.front()); // result 记录前k的元素的最大值
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]); // 滑动窗口移除最前面元素
            que.push(nums[i]); // 滑动窗口前加入最后面的元素
            result.push_back(que.front()); // 记录对应的最大值
        }
        return result;
    }
};

原文地址：http://www.cnblogs.com/deservee/p/16916528.html