zijing2333...大约 8 分钟

739. 每日温度open in new window

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

主要思路是利用单调栈（monotonic stack）来解决问题。单调栈是一种数据结构，它的特点是栈中元素始终保持单调性（本例中是单调递减）。

  1. 初始化一个大小为 n 的结果数组 ans，用于存放每个温度需要等待的天数，初始化时所有元素值为 0。
  2. 创建一个空的单调栈 st，用于存放待处理的温度的索引。
  3. 遍历输入数组 temperatures 中的每个元素： a. 当栈非空且当前温度 temperatures[i] 高于栈顶索引对应的温度 temperatures[st.top()] 时，执行以下操作： i. 弹出栈顶元素，记为 idx。 ii. 更新结果数组 ans[idx] 为 i - idx，表示从 idx 到 i 需要等待的天数。 b. 将当前温度的索引 i 入栈。
  4. 返回结果数组 ans。
#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
        int n = temperatures.size();
        std::vector<int> ans(n, 0);
        std::stack<int> st;

        for (int i = 0; i < n; i++) {
            while (!st.empty() && temperatures[st.top()] < temperatures[i]) {
                int idx = st.top();
                ans[idx] = i - idx;
                st.pop();
            }
            st.push(i);
        }

        return ans;
    }
};

224. 基本计算器open in new window

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

解题思路

可以维护一个符号状态向量 numC 和当前符号 sign，处理括号和加减法。每次遇到一个数字时，都会将其乘以当前符号并累加到结果中。对于括号，会在进入括号时将当前符号压入 numC，并在退出括号时弹出。这样可以实现括号内的计算。具体操作如下：

  1. 初始化结果变量 res 为 0 和符号变量 sign 为 1。

  2. 创建一个整数向量（vector）numC，其初始值为 {1}。numC 用于存储当前的符号状态，例如在括号内的情况。

  3. 使用 while循环遍历字符串 s 的所有字符：

    a. 如果字符 s[i]不是数字（s[i]小于 '0' 或大于 '9'），则根据字符执行相应操作：

    • 如果是左括号 '('，将当前符号 sign 压入 numC 向量，并将 i 加 1。
    • 如果是加号 '+'，将 sign 设置为 numC 向量的最后一个元素（即栈顶元素），并将 i 加 1。
    • 如果是减号 '-'，将 sign 设置为 numC 向量的最后一个元素的相反数，即取负，然后将 i 加 1。
    • 如果是右括号 ')'，从 numC 向量中弹出最后一个元素（即栈顶元素），然后将 i 加 1。
    • 对于其他情况（如空格），只需将 i 加 1。

    b. 如果字符 s[i] 是一个数字，那么：

    • 初始化一个长整型变量 num 为 0。
    • 使用一个嵌套的 while 循环，当 i 在 s 的范围内且 s[i] 是一个数字时，将 num 更新为 10 * num + s[i] - '0'，然后将 i 加 1。这样可以处理多位数字。 - 累加 sign * num 到结果变量 res。

  4. 当遍历完成后，返回结果变量 res。

class Solution {
public:
    int calculate(string s) {
        int res = 0;
        int sign = 1;
        vector<int> numC = {1};
        int i = 0;
        while(i<s.size()) {
            if(s[i] < '0' || '9' < s[i]) {
                switch(s[i]){
                    case '(': numC.push_back(sign); i++; break;
                    case '+': sign = numC.back(); i++; break;
                    case '-': sign = -numC.back(); i++; break;
                    case ')': numC.pop_back(); i++; break;
                    default: i++; break;
                }
            }else {
                long num=0;
                while(i < s.size() && s[i] >= '0' && '9' >= s[i]){
                    num = 10 * num + s[i] - '0';
                    i++;
                }
                res += sign * num;
            }
        }
        return res;
    }
};

227. 基本计算器 IIopen in new window

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

解题思路

首先，我们声明一个栈 stack 用于存储表达式中的操作数（数字），一个字符变量 sign 用于存储当前数字的符号（默认为 '+'），一个整数变量 num 用于存储当前解析的数字，以及一个整数变量 res 用于存储最终的结果。

遍历输入字符串 s 的每个字符： a. 如果当前字符是数字（'0' 到 '9' 之间），将该字符转换为整数，并将其加到 num 变量中，注意：这里的操作是 num = num * 10 + (s[i] - '0')，因为可能有多位数需要解析。 b. 如果当前字符不是数字且不是空格，或者已经是字符串的最后一个字符，需要将 num 的值按照 sign 的运算符入栈。根据 sign 的值进行不同的操作：

  • 如果 sign 为 '+'，将 num 原值入栈。
  • 如果 sign 为 '-'，将 -num 入栈。
  • 如果 sign 为 '*'，将栈顶元素（最后一个元素）乘以 num，并更新栈顶元素。
  • 如果 sign 为 '/'，将栈顶元素（最后一个元素）除以 num，并更新栈顶元素。 c. 然后，更新 sign 为当前字符，并将 num 重置为 0。

当遍历完输入字符串后，所有操作数已经按正确的顺序和符号存储在栈中。现在，我们只需遍历栈中的所有元素并求和，即可得到表达式的最终结果。

返回最终结果 res。

#include <vector>
#include <string>

class Solution {
public:
    int calculate(std::string s) {
        std::vector<int> stack;
        char sign = '+';
        int num = 0;
        int res = 0;

        for (int i = 0; i < s.size(); ++i) {
            bool isDigit = s[i] <= '9' && s[i] >= '0';
            if (isDigit) {
                num = num * 10 + (s[i] - '0');
            }
            if (!isDigit && s[i] != ' ' || i == s.size() - 1) {
                if (sign == '+') {
                    stack.push_back(num);
                } else if (sign == '-') {
                    stack.push_back(-num);
                } else if (sign == '*') {
                    stack.back() *= num;
                } else if (sign == '/') {
                    stack.back() /= num;
                }
                sign = s[i];
                num = 0;
            }
        }

        for (const auto &i : stack) {
            res += i;
        }
        return res;
    }
};

402. 移掉 K 位数字open in new window

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

class Solution {
public:
    string removeKdigits(string num, int k) {
        int n = num.size();
        vector<char> st;
        for(int i = 0; i < n; i++) {
            while(!st.empty() && st.back() > num[i] && k > 0) {
                st.pop_back();
                k--;
            }
            st.push_back(num[i]);
        }
        int idx = 0;
        while(idx < st.size() && st[idx] == '0') {
            idx++;
        }
        string ans;
        for(int i = idx; i < st.size() - k; i++) {
            ans.push_back(st[i]);
        }
        if(ans == "") {
            return "0";
        }
        return ans;
    }
};
你认为这篇文章怎么样？
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.14.8