AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 3624. 三值字符串    原题链接    简单

作者: 作者的头像   JOHNYXU ,  2021-06-04 10:29:23 ,  所有人可见 ,  阅读 220


0


算法1

合并

我们把相邻的且相同的字符合并,并记录合并了多少个相同的字符,放入vec中
那么对于可能的答案,必定是vec中长度为3的一组连续子序列
假如长度为3的连续字序列中包含1,2,3,它的长度为len=2+中间那个字符的个数(2指的是头尾各取一个字符)
res=max(res,len)更新答案

字节camp第一题我就是这么写的,结果一直WA心态崩了,随缘等个好心人康康有没有问题吧

时间复杂度O(n)

C++ 代码

#include<iostream>
#include<map>
#include<vector>
using namespace std;
const int INF = 0x3f3f3f3f;
int cnt[3];
struct info
{
    char c;
    int cnt;
};
void solve()
{
    vector<info> vec;
    string str;
    cin >> str;
    char last = 0;
    int cnt = 0;
    for (int i = 0; i < str.size();i++)
    {
        char c = str[i];
        if(c!=last)
        {
            if(cnt)
                vec.push_back({last, cnt});
            last = c;
            cnt = 1;
        }
        else
            cnt++;
    }
    vec.push_back({last, cnt});
    int res = INF;
    for (int i = 0; i < vec.size();i++)
    {
        bool f1, f2, f3;
        f1 = f2 = f3 = false;
        for (int j = i; j < i + 3 && j < vec.size();j++)
        {
            if(vec[j].c=='1')
                f1 = true;
            if(vec[j].c=='2')
                f2 = true;
            if(vec[j].c=='3')
                f3 = true; 
        }
        if(f1&&f2&&f3)
        {
            res = min(res, vec[i + 1].cnt + 2);
        }
    }
    if(res==INF)
        res = 0;
    cout << res << endl;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

算法2

简单双指针,2021字节camp第一题

时间复杂度 $O(n)$

C++ 代码

#include<iostream>
#include<map>
using namespace std;
const int INF = 0x3f3f3f3f;
int cnt[3];
void solve()
{
    string str;
    cin >> str;
    cnt[0] = cnt[1] = cnt[2] = 0;
    int res = INF;
    for (int i = 0,j = 0; j < str.size();j++)
    {
        cnt[str[j]-'1']++;
        while(cnt[str[i]-'1']>1)
            cnt[str[i++] - '1']--;
        if(cnt[0]&&cnt[1]&&cnt[2])
            res = min(res, j - i + 1);
    }
    if(res==INF)
        res = 0;
    cout << res << endl;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息