c. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
class Solution {
public:
int m[300];
bool isValid(string s) {
stack<char> st;
m[']']='[', m[')']='(', m['}']='{';
for (char c : s) {
if (c=='(' || c=='{' || c=='[') st.push(c);
else {
if (st.empty() || st.top()!=m[c]) return false;
st.pop();
}
}
return st.empty();
}
};
b. 平衡括号字符串的最少插入次数
任何左括号 '(' 必须对应两个连续的右括号 '))'；左括号 '(' 必须在对应的连续两个右括号 '))' 之前。
可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。返回让 s 平衡的最少插入次数。
class Solution {
public:
int minInsertions(string s) {
int l=0, ans=0, n=s.size();
for (int i=0; i<n; i++) {
if (s[i]=='(') {
l++;
} else { //处理到这个位置，i前面的位置一定是平衡的了
if (i+1<n && s[i+1]==')') i++;
else ans++; //到这里要么是："()("或者"()"（i=1)，此时都需要添加一个)（最优）
if (l) l--; //到这里一定有两个右括号等着匹配
else ans++; //实际上要写l++, l--，但等于没写
}
}
if (l) ans+=2*l;
return ans;
}
};
b. 有效的括号字符串
写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
- 任何左括号 ( 必须有相应的右括号 )。
- 任何右括号 ) 必须有相应的左括号 ( 。
- 左括号 ( 必须在对应的右括号之前 )。
- * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
- 一个空字符串也被视为有效字符串。
思路
写蹦了，50/58...
class Solution {
public:
bool checkValidString(string s) {
int star=0, l=0, r=0, n=s.size();
for (int i=0; i<n; i++) {
if (s[i]=='(') {
l++;
if (r>l) return false;
} else if (s[i]==')') {
r++;
if (l<=0 && star<=0)
return false;
if (l>0) l--, r--;
else if (star>0) star--, r--;
} else {
star++;
}
}
if ((abs(l-r)>=1 && star<abs(l-r))) return false;
return true;
}
};
算法并不严谨，如果abs(l-star)次数恰好和缺失的)个数一样，上面的算法也会返回true，这是因为没有考虑star出现的位置，比如："(*)*((" 就是不合法的，所以还需要从后往前检查一波)+star和(的关系
#define N 258
class Solution {
public:
int lm[N], rm[N];
bool checkValidString(string s) {
int n=s.length();
for (int i=0; i<n; i++) {
lm[s[i]]++;
if (lm['(']+lm['*']<lm[')']) return false;
rm[s[n-i-1]]++;
if (rm[')']+rm['*']<rm['(']) return false;
}
return true;
}
};
a. 删除无效的括号
删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
思路
bfs枚举所有删除情况，bfs中只要遇到合法的串就添加进ans中，后面的状态都不必添加了，因为操作次数都比这个要多;
break bfs 后只需要检查队列中同层其它元素的合法性即可
class Solution {
public:
bool valid(string& s) {
int l=0;
for (char c : s) {
if (c=='(') l++;
else if (c==')' && --l<0) return false;
}
return l==0;
}
vector<string> bfs(string& s) {
queue<string> q;
unordered_map<string, bool> vis;
q.push(s), vis[s]=1;
vector<string> ans;
while (!q.empty()) {
auto now=q.front(); q.pop();
if (valid(now)) {
ans.push_back(now);
break;
}
for (int i=0; i<now.length(); i++) if (!isalpha(now[i])) {
string nx=now.substr(0,i)+now.substr(i+1);
if (!vis[nx]) {
q.push(nx);
vis[nx]=1;
}
}
}
while (!q.empty()) {
auto t=q.front(); q.pop();
if (valid(t))
ans.push_back(t);
}
return ans;
}
vector<string> removeInvalidParentheses(string s) {
return bfs(s);
}
};
b. 压缩算法（20届tx校招）
字符串中连续的m个相同字符串S将会压缩为[m|S] (m为一个整数且1<=m<=100)，
例如字符串HGBCACABCACABCACAF将会被压缩为HG[3|B[2|CA]]F，
现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？
思路
用栈可记录一对[]的最近的开始和结尾，遇到一个最近的]时就开始处理[...]中间的字符
#include<bits/stdc++.h>
using namespace std;
string toString(char c) {
char t[2]={c,0};
return string(t);
}
string uncode(string& s) {
int p=s.find('|'), c=stoi(s.substr(0,p));
string ans, t=s.substr(p+1);
while (c--) ans+=t;
return ans;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
string s,ans; cin>>s;
stack<char> st;
for (int i=0; i<s.length(); i++) { //遇到'['就压栈
if (s[i]=='[') {
st.push(s[i]);
} else if (s[i]==']') {
string t;
while (!st.empty() && st.top()!='[') {
t=toString(st.top())+t, st.pop();
}
st.pop(), t=uncode(t);
if (st.empty()) ans+=t;
else for (char c : t) st.push(c); //栈不空就代表有[]对中的数据没处理完
} else {
if (st.empty()) ans+=toString(s[i]);
else st.push(s[i]);
}
}
cout<<ans;
return 0;
}
能否再优化？但是题目需保证输入字符串的合法性
#include<bits/stdc++.h>
using namespace std;
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
string s; cin>>s;
stack<int> st;
for (int i=0; i<s.length(); i++) {
if (s[i]=='[' || s[i]=='|') {
st.push(i);
} else if (s[i]==']'){
int p=st.top(); st.pop(); //|的位置
int lp=st.top(); st.pop();//[的位置
int c=stoi(s.substr(lp+1,p-lp));
string t=s.substr(p+1,i-p-1), rep_t;
while (c--) rep_t+=t;
s=s.replace(lp, i-lp+1, rep_t);
i=lp+rep_t.size()-1;
}
}
cout<<s;
return 0;
}
按格式处理字符串（2018阿里秋招笔试编程题）
输入字符串：[aaaa[bbb[ccc]]]
输出:
obj ={
value:'aaa',
child:{
value:'bbb',
child:{
value:'ccc',
child:{}
}
}
}
**思路 **