7.8 科大讯飞笔试 编程第三题 好串

小红定义一个字符串是“好串”,当且仅当该字符串的长度不小于2,且首尾相同。例如"arcaea"是好串。

小红拿到了一个字符串(该字符串不一定是好串),她准备把这个字符串切割成若干个好串,你可以帮小红求出好串的最多数量吗?

输入描述

一个仅包含小写字母的字符串,长度不超过200000。

输出描述

如果无法切割且该字符串本身不是好串,请输出-1。否则输出最终的好串数量。

------------------------------------------------------

用了滑动窗口+贪心,但0%。。。

    string s;
    cin >> s;

    if (s.size() <= 1)
    {
        cout << -1;
        return 0;
    }

    int count = 0;
    bool meethead = false;

    for (int i = 0; i < s.size(); ++i)
    {
        char head = s[i++];
        meethead = false;
        while (i < s.size() && !meethead)
        {
            if (s[i] == head)
            {
                meethead = true;
                break;
            }
            ++i;
        }

        if (meethead)
            ++count;
    }

    if (count > 0)
        cout << count;
    else
        cout << -1;

    return 0;

全部评论
正常dp转移是n^2的,写不过去很正常;所以用dp+堆维护,复杂度nlogn;dpi表示以1-i中最大分割次数,且合法的情况,堆维护dpi由合法状态转移的最大值。这题确实有点东西。
7 回复 分享
发布于 2023-07-09 13:16 四川
直接dp就行,dpi=最大值dpj + (ai==aj),n方过40,记个前面出现的字符就成on了,以前遇到过这种题
2 回复 分享
发布于 2023-07-09 14:40 北京
感觉不像贪心像DP,但是也不知道咋写
1 回复 分享
发布于 2023-07-08 21:30 北京
同滑动窗口加贪心但是5%
点赞 回复 分享
发布于 2023-07-08 21:28 江苏
我python回溯超时了,过了40%
点赞 回复 分享
发布于 2023-07-08 21:47 湖北
感觉比上周第三题好做点,至少有个回溯思路保底
点赞 回复 分享
发布于 2023-07-08 22:10 上海
dp吧
点赞 回复 分享
发布于 2023-07-08 22:17 安徽
感觉是题目理解的有问题,看用例2可以知道题目是要求所有分割出来的子串都是好串,而不是子串种包含好串的最大值。你这么做反而难了(我一开始也是lz你的思路,写到一半感觉不对了)
点赞 回复 分享
发布于 2023-07-09 00:02 上海
非凡计划?
点赞 回复 分享
发布于 2023-07-09 01:10 安徽
我用的dp,遍历字符串每个字符,如果这个字符及其之前的部分构成了好串就对后面部分递归调用这个函数算出这种分割的好串总数,然后维护一个最大值,但是提示内存超了,只过了40%的用例
点赞 回复 分享
发布于 2023-07-09 09:24 湖北
不会 最后贪心10%
点赞 回复 分享
发布于 2023-07-10 01:53 北京
这个不是贪心,这个有点像分割回问子串的dfs,但是dfs只能过50,dp应该可以a
点赞 回复 分享
发布于 2023-07-15 09:13 陕西
请问编程题可以用python吗?还是只能java和C++呀?
点赞 回复 分享
发布于 2023-07-20 19:43 广东

相关推荐

11-01 20:03
已编辑
门头沟学院 算法工程师
Amazarashi66:这种也是幸存者偏差了,拿不到这个价的才是大多数
点赞 评论 收藏
分享
斑驳不同:还为啥暴躁 假的不骂你骂谁啊
点赞 评论 收藏
分享
3 16 评论
分享
牛客网
牛客企业服务