京东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)做法。
#京东##笔试##秋招#
全部评论
hi~同学,秋招遇“寒气”,牛客送温暖啦!23届秋招笔面经有奖征集中,参与就得牛客会员7天免费体验,最高赢300元京东卡!戳我去看>>>https://www.nowcoder.com/link/zhengjipinglun
点赞 回复 分享
发布于 2022-09-04 19:50 北京

相关推荐

吴offer选手:学到了,下次面试也放张纸在电脑上,不然老是忘记要说哪几个点
点赞 评论 收藏
分享
05-12 17:28
已编辑
门头沟学院 硬件开发
ldf李鑫:不说公司名祝你以后天天遇到这样的公司
点赞 评论 收藏
分享
评论
3
3
分享

创作者周榜

更多
牛客网
牛客企业服务