【C++ 算法进阶】算法提升八
复杂计算 （括号问题相关递归套路 重要）
题目
给定一个字符串str str表示一个公式 公式里面可能有整数 + - * / 符号以及左右括号 返回最终计算的结果
题目分析
本题的难点主要在于可能会有很多的括号 而我们直接模拟现实中的算法的话code会难写 要考虑的情况很多
那么我们首先写出加入没有括号应该怎么计算呢
我们这里只需要首先计算乘法和除法 再计算加法和减法
代码
int process(string& s1) {// s1 表示计算的公式stack<string> st;int cur = 0;for (int i = 0; i < s1.size(); i++) {if (s1[i] < '0' || s1[i] > '9'){if (!st.empty()) {string test = st.top();if (test == "*" || test == "/") {string op = st.top();st.pop();int left = stoi(st.top());st.pop();int right = cur;if (op == "*") {cur = left * right;}else{cur = left / right;}}}st.push(to_string(cur));string ops = string(1, s1[i]);st.push(ops);cur = 0;}else{cur = cur * 10 + (s1[i] - '0');}}string test = st.top();if (test == "*" || test == "/") {string op = st.top();st.pop();int left = stoi(st.top());st.pop();int right = cur;if (op == "*") {cur = left * right;}else{cur = left / right;}}st.push(to_string(cur));stack<string> st2;while (!st.empty()){st2.push(st.top());st.pop();}// 最后我们按照顺序计算栈里面的结果while (st2.size() != 1){int left = stoi(st2.top());st2.pop();string op = st2.top();st2.pop();int right = stoi(st2.top());st2.pop();if (op == "+") {st2.push(to_string(left + right));}else{st2.push(to_string(left - right));}}return stoi(st2.top());
}
如果遇到括号怎么办呢
比如说我们现在计算到* 之后 遇到了一个 (
此时我们不进行继续的计算 而是使用递归 将这个括号里的内容传递给下个函数进行计算 我们只需要知道返回值即可
当然只知道返回值是不够的 因为我们还需要知道递归函数返回之后需要从哪一个位置开始计算
所以说递归函数的返回值要返回一个数组 数组里面存储着括号内计算的数值以及指针走到的位置
vector<int> process(string& s1 , int n ) {// s1代表字符串int i = n;int cur = 0;stack<string> st;while (i < s1.size() && s1[i] != ')'){if ((s1[i] < '0' || s1[i] > '9' ) && s1[i] != '('){if (!st.empty()) {string test = st.top();if (test == "*" || test == "/") {string op = st.top();st.pop();int left = stoi(st.top());st.pop();int right = cur;if (op == "*") {cur = left * right;}else{cur = left / right;}}}st.push(to_string(cur));string ops = string(1, s1[i]);st.push(ops);cur = 0;i++;}else if (s1[i] >= '0' && s1[i] <= '9'){cur = cur * 10 + (s1[i] - '0');i++;}else{vector<int> ans = process(s1 , i + 1);i = ans[1];cur = ans[0];}}// 走到这里说明碰到了边界了string test = st.top();if (test == "*" || test == "/") {string op = st.top();st.pop();int left = stoi(st.top());st.pop();int right = cur;if (op == "*") {cur = left * right;}else{cur = left / right;}}st.push(to_string(cur));stack<string> st2;while (!st.empty()){st2.push(st.top());st.pop();}// 最后我们按照顺序计算栈里面的结果while (st2.size() != 1){int left = stoi(st2.top());st2.pop();string op = st2.top();st2.pop();int right = stoi(st2.top());st2.pop();if (op == "+") {st2.push(to_string(left + right));}else{st2.push(to_string(left - right));}}return { stoi(st2.top()), i + 1 };
}
我们只需要在遇到左括号的时候将计算的任务丢给递归函数 也就是调用下面这段代码
else{vector<int> ans = process(s1 , i + 1);i = ans[1];cur = ans[0];}
即可
装最多水的容器 （贪心）
题目
本题为LC原题 题目如下
题目分析
装水的容积由两个部分决定
- 两块板子之间的宽度
- 两块板子中较小的那块板子的高度
所以说 只要我们找出每个宽度的最大值 最后对比一下 我们就能得出最终答案
所以说我们一开始自然是用最左和最右边的板子装水
之后宽度-- 那么我们要想得到最大值是不是要在高度上花心思
我们肯定要舍弃掉较为短的一块板子
之后用代码实现上述内容即可
代码
class Solution {
public:int maxArea(vector<int>& height) {int left = 0;int right = height.size() - 1;int ans = 0;while (left < right) {int h = min(height[left] , height[right]);int w = right - left;ans = max(w * h , ans);if (height[left] < height[right]) {left++;}else {right--;}}return ans;}
};
蛇走格子问题 （动态规划）
题目
假设现在有一个二维数组 每个位置存放着一个整数 （可以为负）
现在有一条蛇要从这个数组的最左边开始找出一条整数相加为最大值的路径
蛇只能往右上 右 右下走
如果叠加到负数则蛇立刻死亡（之前成绩归为-1）
蛇有一种能力 只能发动一次 可以让格子的值变成相反数
题目分析
这是一道经典的动态规划问题 我们可以设计一个如下的函数
// 数组arr上返回i j位置的info信息
// info信息 使用了能力和没有使用能力返回的最大值
info process(vector<vector<int>>& arr, int i, int j) {
}
之后只要跟着递归三部走
- 找终止条件
- 找可能性
- 返回最终结果
即可
终止条件为 当J == 0的时候 我们只有此时用不用能力这两种选择
可能性就有很多了 总体可以分为两类
- 没用能力
- 用了能力
当然 用了能力还要区分 是不是这次用的
之后如果前面的结果有-1 我们则要将其排除出可能性（即答案设置为-1）
代码
// 数组arr上返回i j位置的info信息
// info信息 使用了能力和没有使用能力返回的最大值
info* process(vector<vector<int>>& arr, int i, int j) {if (j == 0){// 不使用能力 -1表示可能达到int no = arr[i][j] >= 0 ? arr[i][j] : -1;int yes = -arr[i][j] >= 0 ? -arr[i][j] : -1;return new info(no, yes);}// 真正的可能性// 首先肯定有左边int preno = -1;int preyes = -1;auto info1 = process(arr, i, j);preno = max(info1->_no, preno);preyes = max(info1->_yes, preyes);if (i > 0){auto info1 = process(arr, i - 1, j - 1);preno = max(info1->_no, preno);preyes = max(info1->_yes, preyes);}if (i < arr.size() - 1){auto info1 = process(arr, i + 1, j - 1);preno = max(info1->_no, preno);preyes = max(info1->_yes, preyes);}// 列可能性int p1 = preno + arr[i][j];if (p1 < 0){p1 = -1;}if (preno = -1){p1 = -1;}int p2 = preyes + arr[i][j];int p3 = preno - arr[i][j];p2 = max(p2, p3);if (p2 < 0){p2 = -1;}if (preyes = -1){p2 = -1;}if (preno = -1){p3 = -1;}return new info(p1, p2);
}int _process(vector<vector<int>>& arr) {int ans = 0;for (int i = 0; i < arr.size(); i++) {for (int j = 0; j < arr[0].size(); j++){auto res = process(arr, i, j);ans = max(ans, max(res->_no, res->_yes));}}return ans;
}路径问题 （动态规划）
题目
给定你一个二维数组 二维数组中存放着a~z的二十六个字符 再给你一个字符串str
现在请问 从这个二维数组中的任意一个位置开始找 是否能找到一条路径能组成字符串str
- 如果路径可以重复是否可以组成
- 如果路径不能重复是否可以组成
题目分析
凡是动态规划的题目我们首先来想思路 因为题目中是一个二维数组 所以我们肯定要使用两个变量来标识唯一一个位置
此外对于字符串str 我们也需要一个变量来确定位置
// 这个函数的意义是从i j位置开始 arr中的字符能不能组成包括str[K]位置及其往后所有位置
bool process(vector<vector<char>>& arr, int i, int j, int k) {
}
我们验证当前字符是否符合之后 只需要调用递归函数查看下一个函数是否符合即可
// 这个函数的意义是从i j位置开始 arr中的字符能不能组成包括str[K]位置及其往后所有位置
bool process(vector<vector<char>>& arr, string& str,int i, int j, int k) {if (k == str.size()){return true;}if (i < 0 || i > arr.size() - 1 || j < 0 || j > arr[0].size() - 1 || arr[i][j] != str[k]){return false;}bool ans = false;// 可能性 走到这里说明前面都符合if (process(arr, str, i + 1, j + 1, k + 1) || process(arr, str, i + 1, j - 1, k + 1) || process(arr, str, i - 1, j + 1, k + 1)|| process(arr, str, i - 1, j - 1, k + 1)){ans = true;}return ans;
}
如果不允许路径重复呢？
这个问题的难点实际在于我们如何标记之前走过的路径
这里推荐使用回溯法
我们每次走过一个路径的之后将当前格子标0
之后验证完毕之后再将格子改回去就行
bool process(vector<vector<char>>& arr, string& str,int i, int j, int k) {if (k == str.size()){return true;}if (i < 0 || i > arr.size() - 1 || j < 0 || j > arr[0].size() - 1 || arr[i][j] != str[k]){return false;}arr[i][j] = 0;bool ans = false;// 可能性 走到这里说明前面都符合if (process(arr, str, i + 1, j + 1, k + 1) || process(arr, str, i + 1, j - 1, k + 1) || process(arr, str, i - 1, j + 1, k + 1)|| process(arr, str, i - 1, j - 1, k + 1)){ans = true;}arr[i][j] = str[k];return ans;
}