一? 有效的括號
給定一個只包括?
(，)，{，}，[，]?的字符串?s?，判斷字符串是否有效。有效字符串需滿足：
- 左括號必須用相同類型的右括號閉合。
- 左括號必須以正確的順序閉合。
- 每個右括號都有一個對應的相同類型的左括號。
示例 1：
輸入：s = ( )
輸出：true
示例 2：
輸入：s = ( ) [ ] { }
輸出：true
示例 3：
輸入：s = ( ]
輸出：false
示例 4：
輸入：s = ( [ ] )?
輸出：true
提示：
1 <= s.length <= 104s?僅由括號?'()[]{}'?組成
解題思路
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這個函數
 到 Scalar)
