这道题感觉很简单,但是吧,做起来还真不简单。对于人类来说理解判断似乎不难,但是对于计算机来说可能就比较麻烦了。起初我写了很多判断,但是依旧无法实现。经过党明学姐的启发,我觉得使用栈,官方题解上使用的是数组,其实数组就可以做一个简单的栈。不过数组很可能造成内存的浪费,经过李涛的启(qī)发(piàn)自己搓了一个链式栈。
题干
[力扣-有效的括号]
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例 1:
示例 2:
示例 3:
示例 4:
示例 5:
栈
思路
起初我写了很多判断,但是依旧无法实现。经过党明学姐的启发,我觉得使用栈,官方题解上使用的是数组,其实数组就可以做一个简单的栈。不过数组很可能造成内存的浪费,经过李涛的启(qī)发(piàn)自己搓了一个链式栈。
做法是首先判断是否为空字符串,为空则返回true
,不为空则遍历字符数组,当匹配到左括号{
、[
、(
时候,将左括号入栈。
继续遍历,发现右括号后将其和栈顶的左括号匹配,匹配成功则将其出栈,继续进行循环,直到读取到'\0'
为止。
如果
- 没有任何括号入栈
- 遍历结束后栈不为空
则返回false
代码
官方题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| char pairs(char a) { if (a == '}') return '{'; if (a == ']') return '['; if (a == ')') return '('; return 0; }
bool isValid(char* s) { int n = strlen(s); if (n % 2 == 1) { return false; } int stk[n + 1], top = 0; for (int i = 0; i < n; i++) { char ch = pairs(s[i]); if (ch) { if (top == 0 || stk[top - 1] != ch) { return false; } top--; } else { stk[top++] = s[i]; } } return top == 0; }
|
我的题解
由于手搓了一个链式栈,所以代码很长
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196
| #include <stdio.h> #include <stdbool.h> #include <string.h> #include <malloc.h>
typedef struct _Node { char value; struct _Node *next; struct _Node *last; } Node;
typedef struct _Stack { Node *top; } Stack;
void stackPush(Stack *st, char val); char stackPop(Stack *st); bool isOdd(int num); Stack *stackInit(char in); void bracketsTableInit(); char bracketsTable(char ch);
char table[126] = { 0, };
bool isValid(char *s) { int LENGTH = strlen(s); bool ret = true;
if (!isOdd(LENGTH)) { bracketsTableInit(); if (bracketsTable(*s)) { Stack *st = stackInit(*s); s++; bool hasR = false; for (int i = 1; i < LENGTH; i++, s++) { if (bracketsTable(*s)) { stackPush(st, *s); } else { hasR = true; char inSt = bracketsTable(stackPop(st)); if (inSt != *s) { ret = false; break; } else { continue; } } } if (!hasR) { ret = false; } if (st->top != NULL) { ret = false; } } else { ret = false; } } else { ret = false; }
return ret; }
Stack *stackInit(char in) { Node *newNode = (Node *)malloc(sizeof(Node)); Stack *newSt = (Stack *)malloc(sizeof(Stack)); newNode->value = in; newNode->next = NULL; newNode->last = NULL; newSt->top = newNode; return newSt; }
void stackPush(Stack *st, char val) { Node *newNode = (Node *)malloc(sizeof(Node)); newNode->value = val; newNode->next = NULL; newNode->last = NULL; if (st->top != NULL) { st->top->next = newNode; newNode->last = st->top; } st->top = newNode; }
char stackPop(Stack *st) { char ret = '\0';
if (st->top != NULL) { if (st->top->last == NULL) { ret = st->top->value; st->top = NULL; } else { Node *del = st->top; st->top = del->last; st->top->next = NULL; del->last = NULL; ret = del->value; free(del); del = NULL; } }
return ret; }
bool stackCanPop(Stack *st) { return (st->top != NULL); }
bool isOdd(int num) { return num & 1 ? true : false; }
void bracketsTableInit() { table['('] = ')'; table['['] = ']'; table['{'] = '}'; }
char bracketsTable(char ch) { return table[ch]; }
|
这次只使用了C语言,因为C#反转链表应该不难,list.Reverse();
(逃)
结果
仅有一次循环,使用迭代的方法还是蛮快的,完成了力扣的任务。但是递归我实在不会,甚至不能很好的区分它们。所以暂时就没有写递归方法。

最后
这道题的话还是比较简单的,毕竟画起图来感觉不难,但是实际写起来还是有一定挑战性的。通过这道题顺手复习了忘干净的链表,也是非常好的。链表的题先画图理解一下有很大帮助,尤其是自己用笔手动遍历一下,利于理解过程。
评论加载中