笔试刷题-牛客网2018-08-13

题目描述：

/**
一般的括号匹配问题是这样的：
给出一个字符串，判断这个括号匹配是不是合法的括号匹配。
如"((" 和 "())"都不是合法的括号匹配，但是"()()()"，"(()())()"等就是合法的括号匹配。
这个问题解决起来非常简单，相信大家都知道怎么解决。
现在给出一个加强版的括号匹配问题：
给出n个由括号 '(' 和 ‘)’ 组成的字符串，
请计算出这些字符串中有多少对字符串满足si + sj是合法的括号匹配。
如果si + sj和sj + si都是合法的括号匹配(i ≠ j)，
那么这两种搭配都需要计入答案；
如果对于si，si + si是合法的括号匹配，那么也需要计入答案。
输入描述:
第一行是一个整数n，表示字符串的个数；
接下来n行是n个非空字符串，全部由'('和')'组成。
1 <= n <= 3 * 105，字符串的长度之和不超过3 * 105。
输出描述:
一个整数，表示满足条件的字符串对的数量。
输入例子1:
3
()
(
)
输出例子1:
2
输入例子2:
5
(()
)))))
()()()
(((
))
输出例子2:
1
*/

思路如下：

记录leftBracketNum rightBracketNum 多余的括号数
要匹配的上才行（两个指针的增添过程类似判断合法性的过程）

然后用一个map记录上来即可，两个都多余的情况肯定不可能有人和其匹配，都为0可以左右匹配，具体看代码

代码如下：

#include<stdio.h>
#include<iostream>
#include<string>
#include<map>
 
#define MAX_N 300000
 
typedef long long LL;
 
using namespace std;
 
string strs[MAX_N];
 
int main()
{
    int N;
    map<int, int> cntMap;
    cin>>N;
    for(int i=0; i<N; i++){
        cin>>strs[i];
        int leftBracketNum=0, rightBracketNum=0;
        for(int j=0; strs[i][j]!='\0'; j++){
            if(strs[i][j]!='(' && strs[i][j]!=')')
                return -1;
            if(strs[i][j]=='('){
                leftBracketNum++;
            }
            else if(strs[i][j]==')'){
                if(leftBracketNum>0)
                    leftBracketNum--;
                else
                    rightBracketNum++;
            }
        }
        //leftBracketNum rightBracketNum保证>=0
        if(leftBracketNum && rightBracketNum){
            continue;
        }
        //leftBracketNum rightBracketNum两个均为0
        if(!leftBracketNum && !rightBracketNum){
            if(cntMap.find(0)==cntMap.end())
                cntMap[0]=1;
            else
                cntMap[0]++;
            continue;
        }
         //leftBracketNum rightBracketNum只有一个为0
         if(leftBracketNum){
            if(cntMap.find(leftBracketNum)==cntMap.end())
                cntMap[leftBracketNum]=1;
            else
                cntMap[leftBracketNum]++;
         }
         else if(rightBracketNum){
             //这里用负数表示
             if(cntMap.find(-rightBracketNum)==cntMap.end())
                cntMap[-rightBracketNum]=1;
             else
                cntMap[-rightBracketNum]++;
         }
    }
    LL total=0;
    for(map<int, int>::iterator it=cntMap.begin(); it!=cntMap.end(); it++){
        if(it->first<0)
            continue;
        else if(it->first==0){//计算自身就是合法的情形
            total+=((LL)(it->second)*(it->second));
            //cout<<"first=0"<<" "<<"second="<<it->second<<endl;
        }
        else{
            if(cntMap.find(-it->first)!=cntMap.end()){//计算左右可以匹配的情形
                total+=(it->second)*cntMap[-it->first];
                //cout<<"first="<<it->first<<" "<<"left_second="<<it->second<<" "<<"right_second="<<cntMap[-it->first]<<endl;
            }
        }
    }
    cout<<total<<endl;
    return 0;
}