【0150.逆波兰表达式求值】
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long long> st1;
long long temp1;
long long temp2;
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] == "+") {
temp1 = st1.top();
st1.pop();
temp2 = st1.top();
st1.pop();
st1.push(temp1 + temp2);
}
else if (tokens[i] == "+") {
temp1 = st1.top();
st1.pop();
temp2 = st1.top();
st1.pop();
st1.push(temp1 - temp2);
}
else if (tokens[i] == "*") {
temp1 = st1.top();
st1.pop();
temp2 = st1.top();
st1.pop();
st1.push(temp1 * temp2);
}
else if (tokens[i] == "/") {
temp1 = st1.top();
st1.pop();
temp2 = st1.top();
st1.pop();
st1.push(temp2 / temp1);
}
else {
st1.push(stoll(tokens[i]));
}
}
return st1.top();
}
};
- 运行成功 开始不成功 把
return st1.top();改成int result = st1.top(); return result;成功了 改回去想看看是什么问题结果竟然也成功了 所以上面那段代码是正确的 不知道为什么之前不成功现在却成功了 - 思路没问题 跟之前本科学校老师讲过的一样 就是没实现过 所以代码语句上有些需要留意的
- 设置成 long long 或者 int 应该都没问题
- 注意 默认pop()函数只能删除栈顶元素 不能获取栈顶元素值 所以需要获取栈顶元素值就需要top()
- 当获得的字符数组元素值是'+' '-' '*' '/' 时 需要进行对应的操作 但是当前tokens[i]只是字符 并不是运算符号 因此 我就想 有什么函数可以让我获得的tokens[i] 就能进行对应字符 对应的运算效果 但是没有这个函数 。。。自己动手实现这个效果思路很简单 就是if(字符是'+') 那就temp1 + temp2; if(字符是'-') 那就temp1 - temp2; 乘法除法类似。
st1.push(stoll(tokens[i]));stoll函数 强制类型转换为long long int型 类似的stol强制转换为long int型。 因为push(元素必须是int 型)
- 卡哥代码
class Solution {
public:
int evalRPN(vector<string>& tokens) {
<<<<<<< HEAD
stack<long long> st;
=======
// 力扣修改了后台测试数据，需要用longlong
stack<long long> st;
>>>>>>> 28f3b52a82e3cc650290fb02030a53900e122f43
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
long long num1 = st.top();
st.pop();
long long num2 = st.top();
st.pop();
if (tokens[i] == "+") st.push(num2 + num1);
if (tokens[i] == "-") st.push(num2 - num1);
if (tokens[i] == "*") st.push(num2 * num1);
if (tokens[i] == "/") st.push(num2 / num1);
} else {
st.push(stoll(tokens[i]));
}
}
int result = st.top();
st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
return result;
}
};
【0239.滑动窗口最大值】
class Solution {
public:
int maxx(int n1, int n2, int n3) {
int result = n1;
if (result < n2)
result = n2;
if (result < n3)
result = n3;
return result;
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int resultSize = nums.size() - k + 1;
vector<int> result (resultSize, 0);
int j = 0;
queue<int> que1;
for (int i =0; i < nums.size(); i++) {
if (i < k) {
que1.push(nums[i]);
if (i == k-1) {
result[j] = maxx(nums[i], nums[i - 1], nums[i - 2]);
j++;
}
break;
}
que1.pop();
que1.push(nums[i]);
result[j] = maxx(nums[i], nums[i - 1], nums[i - 2]);
j++;
}
return result;
}
};
- break 换成 continue 否则只执行了一次就不再循环了
class Solution {
public:
int maxx(int n1, int n2, int n3) {
int result = n1;
if (result < n2)
result = n2;
if (result < n3)
result = n3;
return result;
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int resultSize = nums.size() - k + 1;
vector<int> result (resultSize, 0);
int j = 0;
queue<int> que1;
for (int i =0; i < nums.size(); i++) {
if (i < k) {
que1.push(nums[i]);
if (i == 0 && nums.size() == 1) {
result[j] = nums[i];
return result;
}
if (i == 1 && nums.size() == 2) {
result[j] = nums[i] > nums[i - 1] ? nums[i] : nums[i - 1];
return result;
}
if (i == k-1) {
result[j] = maxx(nums[i], nums[i - 1], nums[i - 2]);
j++;
}
continue;
}
que1.pop();
que1.push(nums[i]);
result[j] = maxx(nums[i], nums[i - 1], nums[i - 2]);
j++;
}
return result;
}
};
-
上面代码运行部分不通过
输入[1,3,-1,-3,5,3,6,7] 3
输出[3,3,5,5,6,7]
预期结果[3,3,5,5,6,7]
但是 有问题的用例：
Line 1034: Char 34: runtime error: addition of unsigned offset to 0x602000000210 overflowed to 0x60200000020c (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34
最后执行的输入：
[1,-1] 1
-
这个思路 只能说是对了一半 想到了队列 但不会用 这就是当时课堂上 类似课后理论题见过 但代码题没实现过
-
卡哥思路 单调队列能理解 但怎么想到的 怎么在这道题用的 我暂时还没看懂
class Solution {
private:
class MyQueue { //单调队列（从大到小）
public:
deque<int> que; // 使用deque来实现单调队列
// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
// 同时pop之前判断队列当前是否为空。
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
// 这样就保持了队列里的数值是单调从大到小的了。
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
int 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++) { // 先将前k的元素放进队列
que.push(nums[i]);
}
result.push_back(que.front()); // result 记录前k的元素的最大值
for (int i = k; i < nums.size(); i++) {
que.pop(nums[i - k]); // 滑动窗口移除最前面元素
que.push(nums[i]); // 滑动窗口前加入最后面的元素
result.push_back(que.front()); // 记录对应的最大值
}
return result;
}
};