• stack 相关题目 day 1


    第一题:逆波兰表达式求值

            逆波兰表达式的核心在于,每每碰到运算符,运算符操作的对象就是前面两个数字,需要注意的是,使用栈stack能快速找到当前运算符之前的两个数字。当然,下面代码可以使用switch简化。

    1. class Solution {
    2. public:
    3. int evalRPN(vector& tokens) {
    4. stack<long> ans;
    5. for (int i = 0; i < tokens.size(); ++ i) {
    6. string& c = tokens[i];
    7. if(tokens[i] == "+") {
    8. long n1 = ans.top();
    9. ans.pop();
    10. long n2 = ans.top();
    11. ans.pop();
    12. ans.push(n2 + n1);
    13. }else if (tokens[i] == "-") {
    14. long n1 = ans.top();
    15. ans.pop();
    16. long n2 = ans.top();
    17. ans.pop();
    18. ans.push(n2 - n1);
    19. }else if (tokens[i] == "*") {
    20. long n1 = ans.top();
    21. ans.pop();
    22. long n2 = ans.top();
    23. ans.pop();
    24. ans.push(n1 * n2);
    25. }else if (tokens[i] == "/") {
    26. long n1 = ans.top();
    27. ans.pop();
    28. long n2 = ans.top();
    29. ans.pop();
    30. ans.push(n2 / n1);
    31. }else {
    32. ans.push((long)atoi(c.c_str()));
    33. }
    34. }
    35. return ans.top();
    36. }
    37. };

            第二题:行星碰撞

    思路:行进方向相对的星球才可以进行碰撞,这道题目核心问题如下:

    1. 何时进行碰撞操作?:一正一负两个数字顺序排列时,如{5, -1} = {5}

    2. 碰撞后的结果有三种,保留正数(没有任何操作);抵消(pop);保留负数。其中保留负数的情况需要循环判断,直至被撞碎 or 抵消 or 没有任何星球可以撞了(也就是到了数组下标为0的位置)

    3. 如何快速获取上一个星球的信息?:使用栈,top和pop的操作

    整理逻辑:

    a. 向右移动的星球不需要操作,只需要被动等待碰撞即可

    b. 向左移动的星球 cur,当前星球左边的星球统一记作 cur (会变)

    1. 如果当前的左侧星球 pre 向右移动 且 pre > -1 * cur,没有任何操作;
    2. 如果 pre 向右移动,且 pre < -1 * cur,pre 会消失,这一步需要循环判断(连续碰到向右移动的星球 {1,1,-3});
    3. 从2跳出后,情况1:存在这么一个pre == -1 * cur,相互抵消 pop;情况2:当前星球左边没有星球了,直接插入 cur;情况3:左边的星球也是向左移动,直接插入 cur;

    c. 从栈中取出的结果是逆序的,填入ans数组中后需要翻转

    1. class Solution {
    2. public:
    3. vector<int> asteroidCollision(vector<int>& asteroids) {
    4. stack<int> stk;
    5. vector<int> ans;
    6. for (auto& as : asteroids) {
    7. // 1
    8. if (as >= 0) {
    9. stk.push(as);
    10. }else {
    11. // 2
    12. while (stk.size() && stk.top() > 0 && stk.top() < -as) {
    13. stk.pop();
    14. }
    15. // 3
    16. if (stk.size() && stk.top() == -as) {
    17. stk.pop();
    18. }else if (stk.size() == 0 || (stk.size() && stk.top() < 0)) {
    19. stk.push(as);
    20. }
    21. }
    22. }
    23. while (stk.size()) {
    24. ans.push_back(stk.top());
    25. stk.pop();
    26. }
    27. reverse(ans.begin(), ans.end());
    28. return ans;
    29. }
    30. };

            第三题:删除字符串中的所有相邻重复项 II

            题目要求从字符串中删除连续出现k次的相同字符,我们只需要记录连续相同字符的数目,然后进行erase操作即可。

    a. 当前字符和前一个字符相同时,记录加1;否则添加新元素1,表示发现了一个不同的字符,出现频次为1;

    b. 用栈最为直观,top表示前一个字符出现的频次,如果字符相同,只需要将top的值加1即可;否则直接push(1);当然用vector也可以,数组最后一个元素和栈的栈顶是一个意思。

    1. class Solution {
    2. public:
    3. string removeDuplicates(string s, int k) {
    4. stack<int> nums;
    5. for (int i = 0; i < s.size(); ++ i) {
    6. if (i == 0 || s[i] != s[i - 1]) {
    7. nums.push(1);
    8. }else {
    9. nums.top() ++ ;
    10. if (nums.top() == k) {
    11. s.erase(i - k + 1, k);
    12. nums.pop();
    13. i = i - k;
    14. }
    15. }
    16. }
    17. return s;
    18. }
    19. };

    第四题:移除无效的括号

    有效括号的两条准则

    a. 所有前缀中,左括号的数目大于等于右括号的数目

    b. 所有括号,左括号的数目等于右括号的数目

    根据这两条准则,声明cnt 记录左右括号数目的差值,第一遍从左向右遍历,保证每一个前缀中左括号数目大于等于右括号数目;第二遍基于第一遍的结果从右向左遍历,保证每一个前缀中右括号的数目大于等于左括号数目(此时 left <= right, right <= left, so left = right),到此满足a和b。

    1. class Solution {
    2. public:
    3. string minRemoveToMakeValid(string s) {
    4. int cnt = 0;
    5. string ans;
    6. for (auto& c : s) {
    7. if (c == '(') {
    8. cnt += 1;
    9. ans += c;
    10. }else if (c == ')') {
    11. if (cnt > 0) {
    12. cnt -= 1;
    13. ans += c;
    14. }
    15. }else {
    16. ans += c;
    17. }
    18. }
    19. cnt = 0;
    20. s = ans;
    21. ans = "";
    22. reverse(s.begin(), s.end());
    23. for (auto& c : s) {
    24. if (c == ')') {
    25. cnt += 1;
    26. ans += c;
    27. }else if (c == '(') {
    28. if (cnt > 0) {
    29. cnt -= 1;
    30. ans += c;
    31. }
    32. }else {
    33. ans += c;
    34. }
    35. }
    36. reverse(ans.begin(), ans.end());
    37. return ans;
    38. }
    39. };
  • 相关阅读:
    Linux必学命令之设备管理系列
    工厂人员工装穿戴检测系统
    作为主播如何打造个人IP的7个技巧
    区块链实验室(27) - 区块链+物联网应用案例
    C#流程控制————分支结构
    SAT DPLL CDCL
    【Linux】Linux网络连接方式 + 虚拟机克隆、迁移与删除+虚拟机快照+Linux(CentOS)安装wmtools
    C#底层库--操作Excel帮助类(读取、导出表格)
    centos Hadoop伪分布模式安装-ssh免密登录
    IAR全面支持小华全系芯片,强化工控及汽车MCU生态圈
  • 原文地址:https://blog.csdn.net/xiao_ling_yun/article/details/127964637