给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"
class Solution {//动态规划 二维 超时 O(n^3) public: int longestValidParentheses(string s) { if(s.size()<=1)return 0; int res=0; vector<vector<bool>>dp(s.size(),vector<bool>(s.size(),false)); for(int i=0;i<s.size()-1;++i) if(s[i]=='('&&s[i+1]==')'){ dp[i][i+1]=true; res=2; } for(int j=3;j<s.size();++j){ for(int i=j-3;i>=0;i-=2){ //if((j-i)&1==0)continue; if(s[i]=='('&&s[j]==')'&&dp[i+1][j-1]){ dp[i][j]=true; res=max(res,j-i+1); continue; } for(int k=i+1;k<j-1;k+=2){ //if((k-i)&1==0)continue; if(dp[i][k]&&dp[k+1][j]){ dp[i][j]=true; res=max(res,j-i+1); break; } } } } return res; } }; class Solution {//举例：（）（（）（） public: int longestValidParentheses(string s) { if(s.size()<=1)return 0; int res=0; int leCnt=0,riCnt=0; for(int i=0;i<s.size();++i){//左边to右边 if(s[i]=='(')++leCnt; else ++riCnt; if(riCnt>leCnt){// leCnt=0; riCnt=0; } else if(leCnt==riCnt){ res=max(res,riCnt<<1); } } leCnt=0,riCnt=0; for(int i=s.size()-1;i>=0;--i){//右边to左边 if(s[i]=='(')++leCnt; else ++riCnt; if(riCnt<leCnt){// leCnt=0; riCnt=0; } else if(leCnt==riCnt){ res=max(res,riCnt<<1); } } return res; } };实现Bit-map，要求能够表示的最大值为10,000,000
位图(Bit-map)的原理就是使用位数组来表示某些元素是否存在，由于采用了bit为单位来存储数据，因此在存储空间方面，可以大大节省，故适用于海量数据的快速查找、判断、删除等
假设数值范围是[0,7]，有5个元素(4,7,2,5,3)。需要对这5个元素排序，如果使用位图来排序，总共需要8位，因为0~7一共8个数字，处理步骤如下：
设置位图状态：遍历数组，如果包含0~7中某个元素，则设置位图8个位中相应的位为1遍历位图，输出结果：遍历位图，输出排序结果假设有100亿个数(10,000,000,000)，如果使用int(4字节)数组实现位图，每个int可以表示32个数，那么可以使用100亿/8，大约1GB左右的空间就能存下所有100亿个数注意，由于位图每位只有0和1，所以只能表示1个元素是否存在，如果数组包含相同元素，位图没有办法记录。位图很适合在海量数值中查找某个数值是否存在。如果希望用位图记录一个数字是否多次出现，可以用2bit位图（00不存在，01存在，10出现多次，11无意义） template<class T> class bitMap{//1bit表示是否存在这个数据 vector<T>b; vector<T>config={32,5,31};//T=int 32位，>>5 除以32，&31 模32 //T=long long 64位，>>6 除以64，&63 模64 public: bitMap(T maxNum){ b.resize(maxNum/config[0]+1,0); }; void set1(T t){ b[t>>config[1]]|=1<<(t&config[2]); }; void set0(T t){ b[t>>config[1]]&=~1<<(t&config[2]); }; bool find(T t){ return (b[t>>config[1]]>>(t&config[2]))==1; } }
template<class T> class bitMap{//2bit:00不存在，01存在一次，10存在多次，11无意义 vector<vector<T>>b; vector<T>config={32,5,31};//T=int 32位，>>5 除以32，&31 模32 //T=long long 64位，>>6 除以64，&63 模64 public: bitMap(T maxNum){ b.resize(2,vector<T>(maxNum/config[0]+1),0); }; void set1(T t){ auto con=find(t); if(con[0]==0&&con[1]==0) b[0][t>>config[1]]|=1<<(t&config[2]); else if(con[0]==0) b[0][t>>config[1]]&=~1<<(t&config[2]),b[1][t>>config[1]]|=1<<(t&config[2]); }; vector<T> find(T t){ return (b[0][t>>config[1]]>>(t&config[2])&1,b[1][t>>config[1]]>>(t&config[2])&1); } }
