自学内容网 自学内容网

394. 字符串解码 && 739. 每日温度(LeetCode热题100)

394. 字符串解码 - 力扣(LeetCode)
image.png
curr_str:遍历整个字符串时

  • 如果左边有[,且无相应右括号和其匹配,那么curr_str就表示该[到当前位置的解码字符串
  • 如果左边的[]已经匹配,或者没有[],curr_size就表示第一个字符到当前位置的解码字符串
    遇到字符,追加到curr_str中
    遇到数字,将数字入cnt栈,注意多位数的情况
    遇到[,将curr_str入strs栈并清空curr_str
    遇到],取出strs栈的第一个字符串str,同时取出cnt栈的栈顶数字cnt,将curr_str追加到str后,追加cnt次。最后:执行curr_str = str,以维护curr_str的含义
    最后返回curr_str即可
func decodeString(s string) string {
    var strs []string
    var cnt []int
    var curr_str string
    for i := 0; i < len(s); i++ {
        if s[i] >= 'a' && s[i] <= 'z' {
            curr_str += string(s[i])
        } else if s[i] >= '0' && s[i] <= '9' {
            c := 0
            for ; s[i] >= '0' && s[i] <= '9'; i++ {
                c = c * 10 + int(s[i] - '0')
            }
            cnt = append(cnt, c)
            i--;
        } else if s[i] == '[' {
            strs = append(strs, curr_str)
            curr_str = ""
        } else if s[i] == ']' {
            str := strs[len(strs) - 1]
            strs = strs[:len(strs) - 1]
            c := cnt[len(cnt) - 1]
            cnt = cnt[:len(cnt) - 1]
            for c != 0 {
                str += curr_str
                c--
            }
            curr_str = str
        }
    }
    return curr_str
}

739. 每日温度 - 力扣(LeetCode)
image.png

遍历数组,将元素与下标push进栈,如果当前元素大于栈顶元素,出栈直到当前元素小于栈顶元素,维护ans数组,ans[出栈元素的下标] = 当前元素下标 - 出栈元素下标
如果最后有剩余元素,这些元素的ans为0

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<pair<int, int>> stk;
        vector<int> ans(temperatures.size());
        for (size_t i = 0; i < temperatures.size(); i++) {
            if (!stk.empty() && temperatures[i] > stk.top().first) {
                while (!stk.empty() && temperatures[i] > stk.top().first) {
                    auto t = stk.top();
                    stk.pop();
                    ans[t.second] = i - t.second;
                }
            }
            stk.push({temperatures[i], i});
        }
        return ans;
    }
};

原文地址:https://blog.csdn.net/weixin_61432764/article/details/140378193

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!