学步园

这三道题是大摩实习现场面试时候的笔试题。

Valid Parentheses：

Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are
all valid but "(]" and "([)]" are
not.

比较简单的栈操作，但是居然还是发现有问题。一个是switch语句不会写 - -， 二个是又是拉掉一些小细节，比如匹配了之后应当出栈，又忘了，最后要判断为空也忘了，哎，算起来100分的话也就能得30分了。。。。。

class Solution {
public:
    bool isValid(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int n=s.length();
	    stack<char> st;
	    for(int i=0;i<n;i++)
	    {
		    switch(s[i])
		    {
			case '(':
			case '[':
			case '{':
				st.push(s[i]);
				break;
			case ')':
				if ( st.empty() || st.top()!='(')
					return false;
                st.pop();
				break;
			case ']':
				if ( st.empty() || st.top()!='[')
					return false;
				st.pop();
                break;
			case '}':
				if ( st.empty() || st.top()!='{')
					return false;
				st.pop();
                break;
			default:
				return false;
		    }
	    }
	    return st.empty();
    }
};

Generate Parentheses:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))",
"(()())", "(())()", "()(())", "()()()"

写的时候又犯了好几个错误，哎。尤其是rec(n+1)这里老是忘了+1.

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    rec=vector<vector<string> >(n+1);
	solve(n );
	return rec[n];	
    }
    vector<vector<string> > rec;
    void solve(int n)
    {
	    if ( rec[n].size()!=0 )
		    return;
	    if ( n==0)
	    {
		    rec[0]=vector<string> (1,string());
		    return;
	    }
	    else if ( n==1 )
	    {
		    rec[1]=vector<string> (1,string("()"));
		    return;
	    }
	    else
	    {
		    for(int k=0;k<n;k++)
		    {
			    solve(k);
			    solve(n-1-k);
			    vector<string>& in=rec[k];
			    vector<string>& out=rec[n-1-k];
			    int inNum=rec[k].size();
			    int outNum=rec[n-1-k].size();
			    string tmp;
			    for(int i=0;i<inNum;i++)
				    for(int j=0;j<outNum;j++)
				    {
					    tmp.clear();
					    tmp.push_back('(');
					    tmp.append(in[i]);
					    tmp.push_back(')');
					    tmp.append(out[j]);
					    rec[n].push_back(tmp);
				    }
		    }
	    }
    }
};

Longest Valid Parentheses：

Given a string containing just the characters '(' and ')',
find the length of the longest valid (well-formed) parentheses substring.

For "(()",
the longest valid parentheses substring is "()",
which has length = 2.

Another example is ")()())",
where the longest valid parentheses substring is "()()",
which has length = 4.

两种方法，一种是利用栈：

class Solution {
public:
    int longestValidParentheses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        typedef pair<char,int> record;
	    stack<record> st;
	    st.push(record('#',-1));
	    int ans=0;
	    int n=s.length();
	    for(int i=0;i<n;i++)
		    if ( s[i]==')'&&st.top().first=='(')
			    st.pop();
	    	    else
		    {
			    ans=max(ans,i-st.top().second-1);
			    st.push(record(s[i],i));
		    }
	    ans=max(ans,n-st.top().second-1);
	    return ans;
    }
};

第二种方法类似DP，思路见http://blog.csdn.net/a83610312/article/details/8639790：

class Solution {
public:
    int longestValidParentheses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int n=s.length();
        vector<int> right(n,-1);
	    for(int i=n-1;i>=0;i--)
	    {
		    if( s[i]=='(')
		    {
			    int j=i+1;
			    while( j<n&&right[j]!=-1)
				    j=right[j]+1;
			    if ( j<n && s[j]==')')
				    right[i]=j;
		    }
	    }
	    int ans=0;
	    for(int i=0;i<n;i++)
	    	if ( right[i]!=-1)
		{
			int j=right[i]+1;
			while(j<n&&right[j]!=-1)
				j=right[j]+1;
			ans=max(ans,j-i);
		}
	    return ans;
    }
};