京东9.3编程最后一题O(n)做法
全为左右括号的字符串，定义其对应的值为最长有效括号子序列的字符数，如())())最长有效括号子序列()()，因此对应的值为4
求字符串所有子串对应的值的和
例子1：())())
输出1：26
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
string str;
cin >> str;
vector<int> count_vec; // 如())())的count_vec为{1, 2, 1, 2}
count_vec.emplace_back(1);
for(int i = 1; i < str.size(); i++){
if(str[i] == str[i - 1]) count_vec.back()++;
else count_vec.emplace_back(1);
}
long long res = 0, weight = 0, count = count_vec[0];
char last_char = str[0];
for(int i = 1; i < count_vec.size(); i++){
if(last_char == '('){
last_char = ')';
weight += 2 * count;
}
else last_char = '(';
res += weight * count_vec[i];
count += count_vec[i];
}
cout << res;
return 0;
} 原来的做法一直0%可能就是时间超了？考完了才写出来O(n)做法。
#京东##笔试##秋招#
查看1道真题和解析
