最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

当前焦点!Leetcode Practice --- 栈和队列

来源：博客园
目录
  • 155. 最小栈
    • 思路解析
  • 20. 有效的括号
    • 思路解析
  • 1047. 删除字符串中的所有相邻重复项
    • 思路解析
  • 1209. 删除字符串中的所有相邻重复项 II
    • 思路解析
    • 删除字符串中出现次数 >= 2 次的相邻字符
  • 剑指 Offer 09. 用两个栈实现队列
  • 239. 滑动窗口最大值
    • 思路解析

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。


【资料图】

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

提示：

  • \(-2^{31}\) <= val <= \(2^{31}\) - 1

  • pop、top 和 getMin 操作总是在 非空栈 上调用

  • push, pop, top, and getMin最多被调用 \(3 * 10^4\) 次

  • 思路解析

因为会不断的入栈和出栈，那就要保证，不论入栈还是出栈，我时刻知道，到栈中当前位置的最小值是谁。

["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]

对于上述输入，-2入栈时，最小值是-2，0入栈是，最小值是-2，-3入栈是最小值是-3

也就是我需要两个栈，一个栈用于存储元素，完成元素的push和pop操作；一个栈用于存储当前最小值，如果最小值更新就存入最小栈。

class MinStack {public:    MinStack() {    }        void push(int val) {        if (val <= getMin()) {            minStack.emplace(val);        }        valStack.emplace(val);    }        void pop() {        if (valStack.empty()) {            return;        }        int ret = valStack.top();        valStack.pop();        if (ret == getMin()) {            minStack.pop();        }    }        int top() {        return valStack.top();    }        int getMin() {        if (minStack.empty()) {            return INT_MAX;        }        return minStack.top();    }private:    stack valStack;    stack minStack;};

20. 有效的括号

给定一个只包括 "("，")"，"{"，"}"，"["，"]" 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。

  • 左括号必须以正确的顺序闭合。

  • 每个右括号都有一个对应的相同类型的左括号。

  • 思路解析

将匹配项做一个map单独存储，这样子有更好的扩展性。

遇到左括号就入栈，遇到右括号，判断是否与栈顶元素配对，配上就出栈，否则就返回false。

class Solution {public:    bool isValid(string s) {        stack bracketsStack;        for (auto &iter : s) {            // 遇到左括号就入栈，遇到右括号，判断栈顶是否为其对应的左括号，如果是则出栈            if (typeMap.count(iter) != 0) {                bracketsStack.emplace(iter);            } else {                if (bracketsStack.empty() || iter != typeMap[bracketsStack.top()]) {                    return false;                }                bracketsStack.pop();            }        }        if (bracketsStack.empty()) {            return true;        }        return false;    }private:    unordered_map typeMap = {        {"(", ")"},        {"[", "]"},        {"{", "}"}    };};

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

输入："abbaca"输出："ca"输入："abbbaca"输出："abaca"

  • 思路解析

string提供了两个操作

  • front：访问第一个字符
  • back：查询最后一个字符
  • pop_back：弹出尾巴字符，实现：length - 1即可
  • push_back：插入元素
string removeDuplicates(string s) {    string res;    for (auto &iter : s) {        if (!res.empty() && iter == res.back()) {            res.pop_back();        } else {            res.push_back(iter);        }    }    return res;}

1209. 删除字符串中的所有相邻重复项 II

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

输入：s = "deeedbbcccbdaa", k = 3输出："aa"解释： 先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"再删除 "bbb"，得到 "dddaa"最后删除 "ddd"，得到 "aa"

  • 思路解析

遍历到某个字符的时候，判断当前字符与栈顶字符是否相同

  • 如果不同，则直接入栈并开始计数
  • 如果相同，则判断当前栈顶元素累积了多少个该元素，如果累积的个数小于k-1，则继续累积，如果累积到了k-1个，当前又相同了，那么栈顶元素就可以弹出了。
string removeDuplicates(string s, int k) {    stack> pairStack; // 每个元素存储当前的元素及有几个连续的值    for (size_t i = 0; i < s.length(); i++) {        if (!pairStack.empty() && pairStack.top().first == s[i]) {            // 此时，看一下栈中是否已经有k-1个s[i]相同的元素，如果有，则pop出这k-1个，如果没有，则push进去            if (pairStack.top().second == k - 1) {                pairStack.pop();            } else {                pairStack.top().second++;            }        } else {            pairStack.emplace(std::pair(s[i], 1));        }    }    string res;    while(!pairStack.empty()) {        while (pairStack.top().second-- > 0) {            res += pairStack.top().first;        }        pairStack.pop();    }    reverse(res.begin(), res.end());    return res;}

删除字符串中出现次数 >= 2 次的相邻字符

第二次出现的时候，说明出现次数大于2了，这时候就可以删除了，同时跳过s中后续与当前字符相同的元素即可。

string removeDuplicates(string s, int k) {    string res; // 每个元素存储当前的元素及有几个连续的值    for (size_t i = 0; i < s.length(); ) {        if (!res.empty() && res.back() == s[i]) {            // 此时，说明已经出现过的字符第二次出现了            char currChar = s[i];            while(s[i] == currChar) {                // 跳过s中其他相同的字符                i++;            }            res.pop_back();        } else {            res.push_back(s[i]);            i++;        }    }    return res;}

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

class CQueue {public:    CQueue() {    }        void appendTail(int value) {        stackIn.emplace(value);    }        int deleteHead() {        if (stackOut.empty()) {            while (!stackIn.empty()) {                stackOut.emplace(stackIn.top());                stackIn.pop();            }        }        if (stackOut.empty()) {            return -1;        }        auto ret = stackOut.top();        stackOut.pop();        return ret;    }private:    stack stackOut; // 输出栈，元素按照输入顺序的栈    stack stackIn; // 输入元素存放栈，与输入顺序相反的栈};

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3输出：[3,3,5,5,6,7]解释：滑动窗口的位置                最大值---------------               -----[1  3  -1] -3  5  3  6  7       3 1 [3  -1  -3] 5  3  6  7       3 1  3 [-1  -3  5] 3  6  7       5 1  3  -1 [-3  5  3] 6  7       5 1  3  -1  -3 [5  3  6] 7       6 1  3  -1  -3  5 [3  6  7]      7

  • 思路解析

假设窗口为[left, right]，那么只要nums[i]比nums[j]小，则nums[i]就不纳入考虑范围。所以，当right进入窗口的时候，前面比nums[right]小的元素统统可以移除考虑范围了；这样子，留下的元素是从大到小有序的。

因为我们要移除比当前元素小的元素，也要获取最大的元素作为当前窗口最大值，因此，可以使用双端队列来实现。

// 移除比当前元素小的所有元素,只留下比当前元素大的元素while (!dQ.empty() && nums[i] >= nums[dQ.back()]) {    dQ.pop_back();}// 获取当前窗口最大值,放入结果中resVec.emplace_back(nums[dQ.front()]);// 如果最大值应该要移除了，则移除if (dQ.front() + k <= i) {    dQ.pop_front();}

完整的实现代码如下：

vector maxSlidingWindow(vector& nums, int k) {    deque dQ;    for (size_t i = 0; i < k; i++) {        // 当前队列中仅保留比当前元素大的元素的位置,队列中下标对应的元素由大到小        while (!dQ.empty() && nums[i] >= nums[dQ.back()]) {            dQ.pop_back();        }        dQ.emplace_back(i);    }    vector resVec = {nums[dQ.front()]};    for (size_t i = k; i < nums.size(); i++) {        // 当前队列中仅保留比当前元素大的元素的位置        while (!dQ.empty() && nums[i] >= nums[dQ.back()]) {            dQ.pop_back();        }        dQ.emplace_back(i);        if (dQ.front() <= i - k) {            dQ.pop_front();        }        resVec.emplace_back(nums[dQ.front()]);    }    return resVec;}

需要完整版练习笔记，可关注公众号后台私信~~

关键词：