【day2】数据结构刷题栈

一有效的括号

给定一个只包括 (，)，{，}，[，] 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = ( )

输出：true

示例 2：

输入：s = ( ) [ ] { }

输出：true

示例 3：

输入：s = ( ]

输出：false

示例 4：

输入：s = ( [ ] )

输出：true

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

解题思路
1 首先要排除两种特殊的情况就是当这个括号为空或者首个括号就是闭括号的两个情况
2 这里是需要用到栈的思想，我的解答是没有用到STL库里面的给的栈，而是用了string类型
3 当我遇到左括号的时候，我就用string的运算法则，把这个左括号放到最后面，当遇到右括号的时候，就进行匹配是不是右括号的左括号，如果不是就直接返回false
4 最后我们还要检查是不是所有的括号都进行了匹配，才可以返回true，否则就是返回false

代码
class Solution {
public:bool isValid(string s) {if (s.empty()) return true;if (s[0] == ']' || s[0] == ')' || s[0] == '}') return false; int num1 = 0;string str = "";for (int i = 0; i < s.length(); i++) { if (s[i] == '(' || s[i] == '{' || s[i] == '[') {str.push_back(s[i]);num1++;} else {if (num1 == 0) return false; // 如果没有开括号可匹配，返回 falsechar index = str.back(); str.pop_back(); num1--;// 判断是否匹配if ((s[i] == ')' && index != '(') ||(s[i] == ']' && index != '[') ||(s[i] == '}' && index != '{')) {return false;}}}return num1 == 0; // 如果所有开括号都匹配上了，返回 true}
};
语法学习
string常用的功能
push_back( ) back( ) pop_back( ) empty( )

二计算器

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格。整数除法仅保留整数部分。

示例 1：
输入："3+2*2"
输出：7
示例 2：
输入：" 3/2 "
输出：1
示例 3：
输入：" 3+5 / 2 "
输出：5
说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

解题思路
1 把一个式子分成几项来看，这样就可以进行+和-的操作，比如5+6*8，这个就是把6*8看成一项
2 我们要用一个字符来存储这个一个式子的上一个运算符号，初始的运算符号要是+，这样才可以进行初始化
代码
#include <cctype>class Solution {
public:int calculate(string s) {int result = 0;  // 最终结果int num = 0;     // 当前数字int temp = 0;    // 临时结果，用于处理乘除法char lastOp = '+';  // 上一个运算符，初始为 '+'for (int i = 0; i < s.length(); i++) {char c = s[i];// 如果是数字，累积到 numif (isdigit(c)) {num = num * 10 + (c - '0');}// 如果是运算符或者到达字符串末尾if ((!isdigit(c) && c != ' ') || i == s.length() - 1) {// 根据上一个运算符处理当前数字if (lastOp == '+') {result += temp;  // 将临时结果累加到最终结果temp = num;      // 开始新的临时结果} else if (lastOp == '-') {result += temp;  // 将临时结果累加到最终结果temp = -num;     // 开始新的临时结果（负数）} else if (lastOp == '*') {temp *= num;  // 乘法直接计算} else if (lastOp == '/') {temp /= num;  // 除法直接计算}// 更新上一个运算符lastOp = c;num = 0;  // 重置当前数字}}// 将最后的临时结果累加到最终结果result += temp;return result;}
};
这个我们可以举一个例子来进行解释
例子3+2*2

我们的temp和result初始化一定是要为0，初始化的操作符是用来把第一个数字加到最初始的地方的
我们是把一整个式子拆分很多项来进行加，减法的时候直接读取-num就好了，下一次加的时候就是减了

三设计栈

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

解题思路，这个就是很简单的栈的操作

#include <stdlib.h>
#include <limits.h>typedef struct {int* data;       // 动态数组存储栈元素int maxsize;     // 栈的最大容量int num;         // 栈顶指针，初始化为-1
} MinStack;/** 初始化栈 */
MinStack* minStackCreate() {MinStack* temp = (MinStack*)malloc(sizeof(MinStack));temp->num = -1;temp->maxsize = 100;temp->data = (int*)malloc(temp->maxsize * sizeof(int));return temp;
}/** 压入元素 */
void minStackPush(MinStack* obj, int x) {if (obj->num == obj->maxsize - 1) {// 栈满时动态扩容obj->maxsize *= 2;obj->data = (int*)realloc(obj->data, obj->maxsize * sizeof(int));}obj->data[++(obj->num)] = x;
}/** 弹出元素 */
void minStackPop(MinStack* obj) {if (obj->num == -1) return; // 栈空时直接返回obj->num--;
}/** 获取栈顶元素 */
int minStackTop(MinStack* obj) {if (obj->num == -1) return -1; // 栈空时返回特定值return obj->data[obj->num];
}/** 获取栈中最小值 */
int minStackGetMin(MinStack* obj) {if (obj->num == -1) return -1; // 栈空时返回特定值int min = obj->data[0];for (int i = 0; i <= obj->num; i++) {if (obj->data[i] < min) {min = obj->data[i];}}return min;
}/** 释放栈 */
void minStackFree(MinStack* obj) {free(obj->data);free(obj);
}

扩容的操作不要忘记了还有relloc这个函数，然后不断地加这个索引进行赋予元素进入数组

总结
有效地括号
这个是利用string进行高效地操作，最关键的一步就是要不断地取最后的那一个进行跟闭括号进行比对，从而得出结果
情况1 没有元素
情况2 开始就是闭括号
情况3 没有全部处理完

计算器
要把计算器的的result和lastop和num都初始化为0，然后进行分项，分别利用加法加入到result里面
情况1 在过程进行相加
情况2 在末尾进行相加
乘法和除法可以先用项来进行保存，然后后面遇到加法和减法的时候就直接加这个项数了

设计栈
这里的操作跟我们一般的栈操作差不多
我们要设计出一个可以扩栈的操作可以利用relloc这个函数