LeetCode20——有效的括号

　　在记事本中写算法题和在纸上写其实感觉差不多，反正是不能进行调试。想起某高手的话，写代码要做到“人机合一”，写高级语言时（指的是 C 和 C++）脑海中要知道当前写的代码对应的反汇编代码，也就是要深入了解编译器对高级语言的处理。什么时候能达到这样的境界呢？

LeetCode 题库的第 20 题——有效的括号

　　我做题的习惯跟考试的习惯差不多，先找会做的，然后再慢慢啃不会的。本着一个原则，不用编译器，不去找答案，不会说明基础不牢固，继续补基础。

　　题目我截图过来。

　　上面的图是题目和给出的示例，示例是用来补充题目的，看着示例就知道什么时候应该返回 true ，什么时候返回 false 了。

解题思路

　　LeetCode 都会给出每个题的函数定义，比如这个题的定义如下：

 bool isValid(char* s) {

 }

　　我选择的是 C 语言来答题。

　　这个题中告诉我们：

　　1、正确的括号包括括弧、方括号和花括号；

　　2、括号需要成对出现；

　　3、函数传递过来的是字符串。

　　那么，我的思路是：

　　1、获得字符串的长度，用来申请一块堆空间和遍历括号；

　　2、申请一块同样大小的堆内存空间做数组，用来模拟堆栈数据结构；

　　3、用一个变量来记录栈顶的位置，其实就是数组当前的下标；

　　4、然后遍历括号，如果是 ( [ { ，那么就进入堆栈，并修改栈顶的位置；

　　5、如果是 ) ] } 那么就去和当前数组位置的前一个值进行比较，如果能够闭合，那么就让前一个出栈，并且修改栈顶的位置；

　　6、如果无法闭合，那么就返回假；

　　7、循环完成后，如果堆栈为空，说明括号都可以闭合，就返回 1，C 语言中非0 为真；

　　8、如果堆栈不为空，说明有尚未闭合的括号，就返回0， C 语言中 0 为假。

解题答案

　　这个题就是数据结构中堆栈的应用，还是比较简单的。完整代码如下：

 bool isValid(char* s) {

     int len = strlen(s);

     int i;

     int pos = ;

     char *pArr = (char*)malloc(len * sizeof(char));

     for ( i = ; i < len; i ++ ) {

         if (s[i] == '(' || s[i] == '[' || s[i] == '{') {

             pArr[pos ++] = s[i];

         }

         if (s[i] == ')') {

             if ( pArr[pos - ] != '(' ) {

                 return ;

             } else {

                 pos--;

             }

         } else if (s[i] == '}') {

             if ( pArr[pos - ] != '{' ) {

                 return ;

             } else {

                 pos--;

             }

         } else if (s[i] == ']') {

             if ( pArr[pos - ] != '[' ) {

                 return ;

             } else {

                 pos--;

             }

         }

     }

     if ( pos !=  ) {

         return ;

     }

     return ;

 }

　　代码写的好不好就不管了，很多题都是主调函数释放空间，所以答题时，没有将堆空间释放掉，同样的申请堆空间后，也没有判断内存是否申请成功。有很多地方写的不严谨，以后改正。

我的微信公众号：“码农UP2U”

巴特西

LeetCode20——有效的括号

最新文章

热门文章