【代码随想录】【算法训练营】【第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];
}

今日收获

1. 栈的使用。