《算法设计与分析》第一周作业

标签（空格分隔）： 课堂作业

---

姓名：李**
学号：16340114
题目：Valid Parentheses（https://leetcode.com/problems/valid-parentheses/description/）

题目概要：给定一串只包含’(‘, ‘)’, ‘{‘, ‘}’, ‘[’ , ‘]’的字符串，判断该字符串中的括号是否合法地闭合。

思路：发现一对合法的子字符串，如’()’,’{}’,’[]’，就将该子字符串消去，再对修改后的输入字符串进行该操作，直到字符串无法继续进行消去操作，如字符串完全被消掉则输入合法，反之输入不合法。

具体实现：可以利用数据结构–栈来实现这个思路，而不用真的对输入字符串进行消去操作。
逐个字符读取输入字符串，如果栈不为空且栈顶与当前输入字符配对，则将栈顶出栈，否则将输入字符压栈。整个字符串读取完毕后，栈为空则输入合法，栈不空则输入不合法。

心得：利用恰当的数据结构可以很好地解决实际问题。
到leetcode上逛了一圈，发现hard难度的题目看了答案也看不懂┑(￣Д ￣)┍
有一题叫找两个数列的中位数，那个证明跟复变函数里的有得一拼，看着实在头疼
部分medium好像也想不出来
看来没点算法基础还是别想碰那些题了，接下来还是好好学算法吧

源码：

class Solution 
{
public:
    bool isValid(string s) 
    {
        stack<char> validator;
        for (int i = 0; i < s.length(); ++i)
        {
            if (!validator.empty() && (s[i] - validator.top() == 1 || s[i] - validator.top() == 2))
                //ascii of ')' minus '(' is 1
                //ascii of ']' minus '[' is 2
                //ascii of '}' minus '{' is 2
            {
                validator.pop();
            }
            else
                validator.push(s[i]);
        }
        if (validator.size() != 0)
            return false;
        else
            return true;
    }
};