【代码随想录】【算法训练营】【第11天】 [20]有效的括号 [1047]删除字符串中的所有相邻重复项 [150]逆波兰表达式求值
前言
思路及算法思维，指路 代码随想录。
题目来自 LeetCode。
day 11，周六，又开始变的困难了~
题目详情
[20] 有效的括号
题目描述
20 有效的括号
解题思路
前提：括号匹配
思路：利用栈的后入先出特性，进行匹配。
重点：栈的使用。
代码实现
C语言
bool isValid(char* s) {int len = strlen(s);char stack[len];memset(stack, 0, len);int top = -1;for (int i = 0; i < strlen(s); i++){if ((s[i] == '(') || (s[i] == '[') || (s[i] == '{')){stack[++top] = s[i];}else{if (top < 0){return false;}if (((s[i] == ')') && (stack[top] != '(')) || ((s[i] == ']') && (stack[top] != '[')) || ((s[i] == '}') && (stack[top] != '{'))){return false;}top--;}}if (top >= 0){return false;}return true;
}
可以进一步过滤字符串长度为奇数的情况……
bool isValid(char* s) {int len = strlen(s);if (len % 2 != 0){return false;}char stack[len];memset(stack, 0, len);int top = -1;for (int i = 0; i < strlen(s); i++){if ((s[i] == '(') || (s[i] == '[') || (s[i] == '{')){stack[++top] = s[i];}else{if (top < 0){return false;}if (((s[i] == ')') && (stack[top] != '(')) || ((s[i] == ']') && (stack[top] != '[')) || ((s[i] == '}') && (stack[top] != '{'))){return false;}top--;}}if (top >= 0){return false;}return true;
}
[1047] 删除字符串中的所有相邻重复项
题目描述
1047 删除字符串中的所有相邻重复项
解题思路
前提：删除相邻重复字母
思路：利用栈的后入先出的特性，进行匹配
重点：注意当前字母需要与栈顶元素比较。
代码实现
C语言
char* removeDuplicates(char* s) {int slen = strlen(s);char *stack = (char *)malloc(sizeof(char) * slen);memset(stack, 0, slen);int top = -1;for (int i = 0; i < slen; i++){if ((top >= 0) && (s[i] == stack[top])){stack[top] = '\0';top--;}else{stack[++top] = s[i];}}return stack;
}
[150] 逆波兰表达式求值
题目描述
150 逆波兰表达式求值
解题思路
前提：逆波兰表达式
思路：利用栈的后入先出特性实现。
重点：注意数值可能出现负数，自实现string转换数值时，需要考虑负数情况；也可以直接使用atoi函数。
代码实现
C语言
int evalRPN(char** tokens, int tokensSize) {int stack[tokensSize];int top = -1;for (int i = 0; i < tokensSize; i++){// 判断该元素是否为算符if ((strlen(tokens[i]) == 1) && ((tokens[i][0] == '*') || (tokens[i][0] == '/') || (tokens[i][0] == '+') || (tokens[i][0] == '-'))){if (top < 1){return 0;}int val2 = stack[top--];int val1 = stack[top--];int res = 0;if (tokens[i][0] == '*'){res = val1 * val2;}else if (tokens[i][0] == '/'){res = val1 / val2;}else if (tokens[i][0] == '+'){res = val1 + val2;}else{res = val1 - val2;}stack[++top] = res;continue;}// 该元素不为算符，需要注意负数的情况int len = strlen(tokens[i]);int val = 0;for (int j = 0; j < len; j++){if (tokens[i][j] != '-'){val = val * 10 + (tokens[i][j] - '0');}}if (tokens[i][0] != '-'){stack[++top] = val;}else{stack[++top] = 0 - val;}}return stack[top];
}
也可以直接使用atoi函数转换……
int evalRPN(char** tokens, int tokensSize) {int stack[tokensSize];int top = -1;for (int i = 0; i < tokensSize; i++){// 判断该元素是否为算符if ((strlen(tokens[i]) == 1) && ((tokens[i][0] == '*') || (tokens[i][0] == '/') || (tokens[i][0] == '+') || (tokens[i][0] == '-'))){if (top < 1){return 0;}int val2 = stack[top--];int val1 = stack[top--];int res = 0;if (tokens[i][0] == '*'){res = val1 * val2;}else if (tokens[i][0] == '/'){res = val1 / val2;}else if (tokens[i][0] == '+'){res = val1 + val2;}else{res = val1 - val2;}stack[++top] = res;continue;}// 该元素不为算符stack[++top] = atoi(tokens[i]);}return stack[top];
}
今日收获
- 栈的使用。