前言
这次的周赛做的太菜了，不忍直视，我想图书馆对面那对情侣老是在那里叽叽喳喳，但是本质还是我太菜了。不过还是花了快一个下午时间+找参考资料把B和C过了。所以我再一次认为，多看下优秀的代码真的对自己很有帮助。
先看下题目B
题目B
题意
题意的话我还是直接贴图了。
当然对于这一类字符串去括号或者字符串压缩得题目还是使用stack比较有效。但是我当时就想着用一种新的办法做一下，没有考虑括号可能有没有嵌套得情况，直接就崩了。 所以遇到这类题目还是多注意下隐藏得测试用例好点。关键多思考。
分析
既然明确了思路，就直接使用一个栈来完成，思考入栈和退栈，当需要退栈时都是在遇到”)”时，因为此时我们需要将”（）”内得字符串反转。那就很明显了。 遍历一遍字符串，遇到 “)”时退栈，遇到”(“时停止退栈。将得到的字符串反转在压栈。重复这个过程就可以得到结果了。
note：这里需要注意一点
string tmp=""+'i';//这个代码在mingw环境下输出一个空串。
string tmp="";
tmp=tmp+'i';// 可以输出 i这个我觉得比较奇怪，但是还没有找到原因。 之后再来填吧。 note:2019.9.16 填坑关于昨天这个问题，和班上一个大佬讨论了下，然后查了下资料，这应该是一个关于capacity的问题，string就好比vetcor
ac代码
思路大概清楚，就直接代码了
class Solution {
public:
string reverseParentheses(string s) {
stack<string> str;
s= '('+s+')';
int size=s.size();
// cout<<size<<endl ;
for(int i=0;i<size;i++){
string now="";
now=now+s[i];
str.push(now);
if(s[i]==')'){
string tmp;
str.pop();
while(str.empty()==false && str.top()!="("){
tmp=str.top()+tmp;
str.pop();
}
reverse(tmp.begin(),tmp.end()); //o(n)
if(str.empty()==false)
str.pop(); //pop (
str.push(tmp);
}
}
reverse(str.top().begin(),str.top().end());
return str.top();
}
};//这种方法我觉得应该算是比较快的了。就不贴ac图了。
题目C
题意
还是先贴题目吧
这道题是真的难(对于我来说)。自从之前做了一道叫 求数组的最大自序和之后，我的思路感觉就固化了,就是喜欢直接求整个数组的最大值去了，所以当然就是直接超时了。这道题我参考一些资料后，思路大概是这样的：
解析
如果k为1 直接取最大值。 如果k>1,需要计算出一个数组的和，一个数组左边开始的最大值，一个数组右边开始的最大值。然后分以下几种情况讨论：
- 如果一个数组的和小于等于0，那么最大值应该为一个数组计算所得的最大值和 左边的最大值加右边的最大值进行比较
- 否则的话，需要进行判断比较下列几种情况的最大值 A. k个数组的和 B.左边k-1个数组的和加上最后一个数组的左最大值。 C右边k-1个数组的和加上第一个数组的右最大值。C.中间k-2个数组的和+左右两边的数组的最大值。 比较他们的结果，最终得出最值。
代码
根据上面的思路，就有了整体的代码：
class Solution {
const int BIG=1e9+7;
public:
int kConcatenationMaxSum(vector<int>& arr, int k) {
int size=arr.size();
long max=0,sum=0;
for(int i=0;i<size;i++){
sum=sum+arr[i];
if(max<sum)
max=sum;
if(sum<0)
sum=0;
} //一个子数组最大和
//k==1 直接取最大
if(k==1) return max%BIG;
//k>=2
long lmax=0,rmax=0;
long cntleft=0;
for(int i=0;i<size;i++){
cntleft=cntleft+arr[i];
lmax=std::max(lmax,cntleft);
}//左边最大和
long cntright=0;
for(int i=size-1;i>=0;i--){
cntright=cntright+arr[i];
rmax=std::max(rmax,cntright);
}//右边最大和
//分类讨论
long sumofone=0;
for(auto c: arr)
sumofone+=c;
// cout<<lmax<<" "<<rmax<<" "<<sumofone<<endl;
if(sumofone<0){ //数组的和小于0，则比较max和左最大值加右最大值的和
max=std::max(max,(lmax+rmax));
}else{ //一个的和大于0，则比较第一个右最大值+k-1个数组的和，中间k-2个数组的和+左右两个的左右最大值，左边k-1个数组的和+最后一个数组左最大值。 k个数组的和。
max=std::max(sumofone*k,std::max(sumofone*(k-1)+lmax,sumofone*(k-1)+rmax));
//还有一种情况 中间k-2个的和 加上左右lmax和rmax的最大值在比交
max=std::max(sumofone*(k-2)+lmax+rmax,max);
}
return max%BIG;
}
};