第一题:逆波兰表达式求值
逆波兰表达式的核心在于,每每碰到运算符,运算符操作的对象就是前面两个数字,需要注意的是,使用栈stack能快速找到当前运算符之前的两个数字。当然,下面代码可以使用switch简化。
- class Solution {
- public:
- int evalRPN(vector
& tokens) { - stack<long> ans;
- for (int i = 0; i < tokens.size(); ++ i) {
- string& c = tokens[i];
- if(tokens[i] == "+") {
- long n1 = ans.top();
- ans.pop();
- long n2 = ans.top();
- ans.pop();
- ans.push(n2 + n1);
- }else if (tokens[i] == "-") {
- long n1 = ans.top();
- ans.pop();
- long n2 = ans.top();
- ans.pop();
- ans.push(n2 - n1);
- }else if (tokens[i] == "*") {
- long n1 = ans.top();
- ans.pop();
- long n2 = ans.top();
- ans.pop();
- ans.push(n1 * n2);
- }else if (tokens[i] == "/") {
- long n1 = ans.top();
- ans.pop();
- long n2 = ans.top();
- ans.pop();
- ans.push(n2 / n1);
- }else {
- ans.push((long)atoi(c.c_str()));
- }
- }
- return ans.top();
- }
- };
第二题:行星碰撞
思路:行进方向相对的星球才可以进行碰撞,这道题目核心问题如下:
1. 何时进行碰撞操作?:一正一负两个数字顺序排列时,如{5, -1} = {5}
2. 碰撞后的结果有三种,保留正数(没有任何操作);抵消(pop);保留负数。其中保留负数的情况需要循环判断,直至被撞碎 or 抵消 or 没有任何星球可以撞了(也就是到了数组下标为0的位置)
3. 如何快速获取上一个星球的信息?:使用栈,top和pop的操作
整理逻辑:
a. 向右移动的星球不需要操作,只需要被动等待碰撞即可
b. 向左移动的星球 cur,当前星球左边的星球统一记作 cur (会变)
c. 从栈中取出的结果是逆序的,填入ans数组中后需要翻转
- class Solution {
- public:
- vector<int> asteroidCollision(vector<int>& asteroids) {
- stack<int> stk;
- vector<int> ans;
- for (auto& as : asteroids) {
- // 1
- if (as >= 0) {
- stk.push(as);
- }else {
- // 2
- while (stk.size() && stk.top() > 0 && stk.top() < -as) {
- stk.pop();
- }
- // 3
- if (stk.size() && stk.top() == -as) {
- stk.pop();
- }else if (stk.size() == 0 || (stk.size() && stk.top() < 0)) {
- stk.push(as);
- }
- }
- }
-
- while (stk.size()) {
- ans.push_back(stk.top());
- stk.pop();
- }
- reverse(ans.begin(), ans.end());
- return ans;
- }
- };
题目要求从字符串中删除连续出现k次的相同字符,我们只需要记录连续相同字符的数目,然后进行erase操作即可。
a. 当前字符和前一个字符相同时,记录加1;否则添加新元素1,表示发现了一个不同的字符,出现频次为1;
b. 用栈最为直观,top表示前一个字符出现的频次,如果字符相同,只需要将top的值加1即可;否则直接push(1);当然用vector也可以,数组最后一个元素和栈的栈顶是一个意思。
- class Solution {
- public:
- string removeDuplicates(string s, int k) {
- stack<int> nums;
- for (int i = 0; i < s.size(); ++ i) {
- if (i == 0 || s[i] != s[i - 1]) {
- nums.push(1);
- }else {
- nums.top() ++ ;
- if (nums.top() == k) {
- s.erase(i - k + 1, k);
- nums.pop();
- i = i - k;
- }
- }
- }
- return s;
- }
- };
第四题:移除无效的括号
有效括号的两条准则
a. 所有前缀中,左括号的数目大于等于右括号的数目
b. 所有括号,左括号的数目等于右括号的数目
根据这两条准则,声明cnt 记录左右括号数目的差值,第一遍从左向右遍历,保证每一个前缀中左括号数目大于等于右括号数目;第二遍基于第一遍的结果从右向左遍历,保证每一个前缀中右括号的数目大于等于左括号数目(此时 left <= right, right <= left, so left = right),到此满足a和b。
- class Solution {
- public:
- string minRemoveToMakeValid(string s) {
- int cnt = 0;
- string ans;
- for (auto& c : s) {
- if (c == '(') {
- cnt += 1;
- ans += c;
- }else if (c == ')') {
- if (cnt > 0) {
- cnt -= 1;
- ans += c;
- }
- }else {
- ans += c;
- }
- }
- cnt = 0;
- s = ans;
- ans = "";
- reverse(s.begin(), s.end());
- for (auto& c : s) {
- if (c == ')') {
- cnt += 1;
- ans += c;
- }else if (c == '(') {
- if (cnt > 0) {
- cnt -= 1;
- ans += c;
- }
- }else {
- ans += c;
- }
- }
- reverse(ans.begin(), ans.end());
- return ans;
- }
- };