本文主要是介绍代码随想录算法训练营：12/60，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
非科班学习算法day12 | LeetCode150:逆波兰表达式 ，Leetcode239: 滑动窗口最大值
目录
介绍
一、基础概念补充：
1.c++字符串转为数字
1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull（最常用）
2. std::stringstream
3. std::atoi, std::atol, std::atof
2.逆波兰表达式
基本概念
示例
二、LeetCode题目
1.LeetCode150:逆波兰表达式
题目解析
2.Leetcode239:滑动窗口最大值
题目解析
总结
介绍
包含LC的两道题目，还有相应概念的补充。
相关图解和更多版本：
代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF
一、基础概念补充：
1.c++字符串转为数字
在C++中，将字符串转换为数字可以采用多种方法，以下是一些常用的方式：
1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull（最常用）
这些是C++11引入的函数，分别用于将字符串转换为int, long, long long, 无符号long, 无符号long long类型。它们会抛出异常(std::invalid_argument或std::out_of_range)来处理非法输入或范围溢出的情况。
#include <string>
#include <iostream>int main() {std::string str = "123";try {int num = std::stoi(str);std::cout << "Converted to int: " << num << std::endl;} catch (const std::invalid_argument& e) {std::cerr << "Invalid argument: " << e.what() << std::endl;} catch (const std::out_of_range& e) {std::cerr << "Out of range: " << e.what() << std::endl;}return 0;
}2. std::stringstream
std::stringstream是一个流对象，可以从字符串中读取数据，也可以将数据写入字符串。它非常灵活，可以用来转换不同类型的变量。
#include <sstream>
#include <string>
#include <iostream>int main() {std::string str = "456";std::stringstream ss(str);int num;ss >> num;if (!ss.fail()) {std::cout << "Converted to int: " << num << std::endl;} else {std::cerr << "Failed to convert string to int." << std::endl;}return 0;
}3. std::atoi, std::atol, std::atof
这些是C语言遗留下来的函数，分别用于将字符串转换为int, long, 和double。它们不会抛出异常，而是返回0或默认值来表示错误，这可能不如C++11的新函数安全。
#include <cstdlib> // 包含atoi声明
#include <string>
#include <iostream>int main() {std::string str = "789";int num = std::atoi(str.c_str());std::cout << "Converted to int: " << num << std::endl;return 0;
}2.逆波兰表达式
逆波兰表达式（Reverse Polish Notation，简称RPN），又称为后缀表达式，是由波兰逻辑学家J・卢卡西维兹于1929年提出的。与传统的中缀表达式（如 3 + 4 * 2）不同，逆波兰表达式将运算符放在操作数之后，消除了括号的需要，并简化了运算顺序的规则。
基本概念
在逆波兰表达式中，每个运算符都跟在所有需要它的操作数之后。例如，中缀表达式 3 + 4 * 2 转换为逆波兰表达式就是 3 4 2 * +。这样，计算时遇到的第一个符号必然是一个操作数，而运算符则立即对其后面的两个操作数进行运算。
示例
- 中缀表达式：
( 3 + 4 ) * 5 - 逆波兰表达式：
3 4 + 5 * - 计算过程：
- 遇到
3，压栈。 - 遇到
4，压栈。 - 遇到
+，弹出4和3进行加法运算，结果7压栈。 - 遇到
5，压栈。 - 遇到
*，弹出5和7进行乘法运算，结果35为最终答案。
- 遇到
二、LeetCode题目
1.LeetCode150:逆波兰表达式
题目链接：150. 逆波兰表达式求值 - 力扣（LeetCode）
题目解析
根据题目提示和逆波兰表达式的特点，选用栈来解决，主要的方法就是，遇到符号就将两个数计算，类似于遇到条件，就消除两个元素。这也是栈非常擅长的操作。
c++代码如下：
class Solution {
public:int evalRPN(vector<string>& tokens) {// 建立辅助栈stack<int> st;// 遍历字符串for (auto token : tokens) {// 分支判断if (token == "+" || token == "-" || token == "*" || token == "/") {int num_b = st.top();st.pop();int num_f = st.top();st.pop();if (token == "+")st.push(num_f + num_b);if (token == "-")st.push(num_f - num_b);if (token == "*")st.push(num_f * num_b);if (token == "/")st.push(num_f / num_b);} else {st.push(stoi(token));}}//返回栈顶元素return st.top();}
};注意点1：由于题目中要求：答案及所有中间计算结果可以用 32 位 整数表示，所以这里直接使用了int来进行计算
注意点2：关于范围表达式：for (auto token : tokens)其中的tocken并不是字符型，而是字符串型。所以要注意比较的是"+"而不是'+'
注意点3：stoi为字符串转换为int。stoll为字符串转换为long long
2.Leetcode239:滑动窗口最大值
题目链接：239. 滑动窗口最大值 - 力扣（LeetCode）
题目解析
对于数组和滑动窗口有了解之后，不难理解窗口移动的过程。问题就集中在了如何解决窗口内的最大值，如果是使用完全遍历的方式，时间复杂度很高，而且就让滑动窗口可以处理左右两边元素的作用失效了。这里新建一个结构体，用来作为自大到小的单调队列。如何处理单调队列的进出规则来返回窗口的最大值。
C++代码如下：
class Solution {
public:// 创建一个单调队列class My_que {public:// 创建辅助队列deque<int> deq;// 模拟进队列void push(int val) {while (!deq.empty() && val > deq.back()) {deq.pop_back();}deq.push_back(val);}// 模拟弹出队列void pop(int val) {if (!deq.empty() && val == deq.front()) {deq.pop_front();}}// 创建读取参数接口int front() { return deq.front(); }};public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {// 创建结果数组vector<int> res;// 创建队列对象My_que que;// 初始化窗口for (int i = 0; i < k; ++i) {que.push(nums[i]);}res.push_back(que.front());for (int i = k; i < nums.size(); ++i) {que.pop(nums[i - k]);que.push(nums[i]);res.push_back(que.front());}return res;}
};注意点1：和链表或者二叉树取节点时的注意点是一样的，队列在弹出前要检查队列是否为空；在结构体内创建了接口便于直接读取当前窗口的最大值。
注意点2：进队列需要比对的是队列尾端的元素的大小和当前元素的大小，出队列需要比对的是当前元素的大小是否等于头元素大小
总结
打卡第12天，最近实验真的很分散精力，每天感觉算法很难，花了很长时间，但是最终还是很混沌，不过一直在坚持，不过blog好几次没有更新了，正好周末重新再做一遍，看了后面的内容，对语言特性和算法都有长进，不管怎么样，坚持！！！
这篇关于代码随想录算法训练营：12/60的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
