Day14 1047删除相邻字符 150逆波兰表达式求值 239滑动窗口最大值

发布时间:2023年12月20日

1047 删除相邻字符

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

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

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

示例:

  • 输入:"abbaca"
  • 输出:"ca"
  • 解释:例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。

? ? ? ? ?既然做过昨天那个括号题,很明显这道题用栈来解决是最好的,我们在删除相邻重复项的时候,用栈来存放遍历过的元素,当再次遍历时,去栈里看看上一个是不是和当前一样的,注意最后将栈里的元素取到字符串里是倒序的,这里还要reverse一下,代码如下,时间复杂度为n:

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> result;
        for(int i = 0; i < s.size(); i++)
        {
            if(result.empty() || s[i] != result.top())
            {
                result.push(s[i]);
            }
            else
                result.pop();
        }
        string F = "";
        while(!result.empty())
            {
                F += result.top();
                result.pop();
            }
        reverse(F.begin(), F.end());
        return F;
    }
};

? ? ? ? 当然我们也可以不借用栈,而是直接使用一个字符串来当栈,这个字符串可以头尾都对元素进行操作,并且不用来回折腾,更加的方便。代码如下;
?

class Solution {
public:
    string removeDuplicates(string s) {
        string result = "";
        for(char S : s)
        {
            if(result.empty() || S != result.back())
                result.push_back(S);
            else
                result.pop_back();
        }
        return result;
    }
};

150 逆波兰表达式求值

?

根据 逆波兰表示法,求表达式的值。

有效的运算符包括?+ ,? - ,? * ,? /?。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

示例?1:

  • 输入: ["2", "1", "+", "3", " * "]
  • 输出: 9
  • 解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

示例?2:

  • 输入: ["4", "13", "5", "/", "+"]
  • 输出: 6
  • 解释: 该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

示例?3:

  • 输入: ["10", "6", "9", "3", "+", "-11", " * ", "/", " * ", "17", "+", "5", "+"]

  • 输出: 22

? ? ? ? ?逆波兰表达式其实就是后缀表达式,也就是运算符写在后面,适合用栈操作,遇到数字就入栈,遇到运算符则取出两个元素进行运算,并将结果压入栈中。

? ? ? ? 这个过程其实就是一个二叉树的后续遍历过程,但是在这里先不用在意。本题与上一题的不同之处是运算元素而不消除元素。首先创建一个栈(因为力扣里数据有很大,所以创建stack时最好用long long类型),依次遍历字符串里的元素,如果遇到加减乘除,就弹出两个元素进行运算,再将结果返回栈中,全部遍历完以后栈里面一定只剩下一个数,这个时候取出来return即可。注意将结果压入栈时,要用stoll处理字符串到数字的过程。代码如下时间复杂度为n:

class Solution {
public:
    int evalRPN(vector<string>& token) {
        stack<long long> s;
        for(int i = 0; i < token.size(); i++)
        {
            if (token[i] == "+" || token[i] == "-" || token[i] == "*" || token[i] == "/") {
                long long num1 = s.top();
                s.pop();
                long long num2 = s.top();
                s.pop();
                if (token[i] == "+") s.push(num2 + num1);
                if (token[i] == "-") s.push(num2 - num1);
                if (token[i] == "*") s.push(num2 * num1);
                if (token[i] == "/") s.push(num2 / num1);
            }
            else
                s.push(stoll(token[i]));
            
        }
        long long result = s.top();
        return result;
    }
};

239 滑动窗口最大值

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

? ? ? ? 这里一看这个题很简单啊,只要两层循环就可以解决了,一层循环用来遍历nums里的元素,另一层用来每次提取k个值。将每次k个数里的最大值返回到result容器中即可,但是由于两层循环,时间复杂度为nxk,导致超出时间限制了,代码如下:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int>result;
        for(int i = 0; i + k -1 < nums.size(); i++)
        {
            int j = k;
            vector<int>tmp;
            int tmp_max;
            while(j)
            {
                tmp.push_back(nums[k-j+i]);
                j--;
            }
            tmp_max = *max_element(tmp.begin(), tmp.end());
            result.push_back(tmp_max);
        }
        return result;
    }
};

? ? ? ? 这里我们就要考虑使用别的方法了,每次移动窗口的时候,push新的pop旧的,再把front返回为最大值,那就好了,这里我们要创建一个维护元素单调递减的队列就叫做单调队列,c++里没有这个队列,所以我们自己来实现这个单调队列,在这个类里要有以下几个成员函数:

? ? ? ? pop(value):如果窗口移除元素value等于单调队列的出口元素,那么队列弹出元素,否则没有操作。因为如果等于出口元素,就说明后面加的数都没有前面的数大,这个数是被挤出去的,否则的话,队里面一定不够k个元素。例如4321,这是个降序,无奈,只能消灭4了,否则就什么也不用做。

? ? ? ? push(value):如果窗口加入的元素大于入口元素的数值,就得把入口元素吃掉直到遇到吃不掉的元素,再把窗口加入的元素加到队列里,这样就把小的没用的数消灭掉,例如532,在加入4时,就变成了54。

? ? ? ? max_front():返回队前面的元素,这肯定是最大值,因为是上面处理过的了。

? ? ? ? ?这里我们要使用deque而不是queue,因为队列的尾端也要进出。接下来就是处理的过程,首先前k个元素特殊处理一下,直接按照新定义的push方法插入元素,将值返回到result中,从第k个元素开始,就要先push后back再front这个流程了,当然push和back可以交换顺序,结果不会变,时间复杂度为n,代码如下:

class Solution {
private:
    class Myqueue
    {
    public:
        deque<int> que;

        void pop(int value)
        {
            if(!que.empty() && value == que.front())
            {
                que.pop_front();
            }
        }

        void push(int value)
        {
            while(!que.empty() && value > que.back())
            {
                que.pop_back();
            }
            que.push_back(value);
        }

        int max_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++)
       {
           que.push(nums[i]);
       }
        result.push_back(que.max_front());
        for(int i = k; i < nums.size(); i++)
        {
            que.push(nums[i]);
            que.pop(nums[i-k]);
            result.push_back(que.max_front());
        }
        return result;
    }
};

? ? ? ? ?当然cpp里面还有一个multiset,是一个有序的可重复集合,如果用这个的话会更方便一些。一样,前k-1次特殊处理,到了第k次的时候,就开始往result里加元素了,但是他会自动帮我们排好序,所以此时就直接能找到最大的,后面的话每次也要pop出最小的,也就是首元素。这个更加的方便简洁,代码如下:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        multiset<int> st;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            if (i >= k) st.erase(st.find(nums[i - k]));
            st.insert(nums[i]);
            if (i >= k - 1) ans.push_back(*st.rbegin());
        }
        return ans;
    }
};

? ? ? ? 今天主要是完成了两个栈的应用,比较类似。但是这个单调队列是第一次接触到,比较灵活,后续要多加注意。

文章来源:https://blog.csdn.net/2303_77739929/article/details/135107434
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。