[C++知识库]最多子序列（c++求法）

最多子序列（c++求法）

TIPS：

• 蒟蒻题解，有提供详细思路，用的是递归，有点呆，仅供参考，有什么问题欢迎评论哦

题目：

• Lambda 指挥官度过了令人难以置信的成功一周：她完成了她的 LAMBCHOP 世界末日装置的第一次试运行，她俘获了 Bunny Rebellion 的六名关键成员，并在俄罗斯方块中打破了她的个人最高分。为了庆祝，她为每个人都点了蛋糕——即使是最底层的奴才！但是奴才之间的竞争非常激烈，如果你不为每个人切出完全相同的蛋糕，你就会遇到大麻烦。

• 蛋糕是圆形的，边缘用 M&M 巧克力装饰。但是，虽然蛋糕的其余部分是统一的，但 M&Ms 却不是：有多种颜色，每个仆从必须得到完全相同的 M&Ms 序列。 Lambda 指挥官讨厌浪费，不会容忍任何剩菜剩饭，因此您还想确保您可以供应整块蛋糕。

• 为了帮助您最好地切蛋糕，您已将蛋糕上 M&Ms 的颜色序列变成了一个字符串：每个可能的字母（a 和 z 之间）对应一种独特的颜色，并且 M&Ms 的序列按顺时针方向给出（装饰在蛋糕的外边缘形成一个圆圈）。

• 编写一个名为 answer(s) 的函数，给定一个 长度小于 200 个字符 的非空字符串来描述 M&Ms 的序列，返回可以从蛋糕上切下的最大数量的相等部分，而不会留下任何剩菜。

（分割线）-----------------------------------------------（分割线）

（手动高亮） 好了，重点都给你们斜体加粗了，下面我先讲一下思路

//由于不会留下任何剩菜，所以父序列首字符一定是子序列的首个字符(只能全部平均分，或者不分）

• ①//循环找到与第一个字符相同的字符的索引temp2，

  • ②For(int j=0;j<strlen(str)/temp2;j++) （以temp2为子序列长度，对str进行划分，每个划分里面都做一次判断：
    • ③在未来长度为k的子序列里面搜索是否str[k]==str[y]，即对应位置元素相同
      • ④如果有str[k]!=str[y]，则从索引k开始往后找到第一个,与第一个字符(str[0])相同的字符索引j(搜索范围不超过str/2),判断：
        • ⑤如果在str/2里找不到,即蛋糕不能切，一整个作为子序列
        • ⑤否则以j为子序列新的起点，长度temp2改为j-1，total=1,返回②
    • ③total+=1(每个划分为1个total)

（分割线）-----------------------------------------------（分割线）

• tips:上面的思路我有进行缩进处理，仿照代码的思路
• 下面直接上代码~

#include <bits/stdc++.h>
using namespace std;

char s[250];
int temp2;
int total=1;
bool flag;
bool flag2;
bool flag3;
void answer(int k)
{
    int y=0;    //y标记str[0]
    flag = true;    //flag表示对应位置元素值是否相同
    flag2 = true;   //flag2代表是否找到子序列下一个开始的索引
    flag3 = true;   //flag3表示k是否已经遍历完整个父序列
    temp2 = k;
    for(int j=0;j<strlen(s)/temp2;j++)//划分几块就做几次循环
    {
        for(int d=0;d<temp2;d++)//划分里面有多少元素就判断几次
        {
            if(s[k++]==s[y++]&&k<strlen(s))//如果对应位置元素相同且下一个k没到父序列末尾
                continue;
            else
            {
                if(s[k-1]!=s[y-1])
                {
                    flag = false;   //flag表示对应位置元素值不同
                    break;
                }
                if(k>=strlen(s))
                {
                    flag3=false;    //flag3表示k已经遍历完整个父序列
                    break;
                }
            }
        }
        total+=1;   //每遍历完一个划分，total+1
        if(!flag||!flag3)   //出现特判情况，需要跳出循环
            break;
    }
    if(!flag)   //flag表示对应位置元素值不同
    {
        while(temp2<=(strlen(s)/2)) //则从上一个相同字符的位置开始，找到下一个相同字符的位置(与s[0]相同)
        {
            temp2++;
            if(s[0]==s[temp2])
            {
                flag2 = false;  //flag2代表是否找到子序列下一个开始的索引
                total = 1;  //total回到最小值,total至少为1
                answer(temp2);  //递归
                break;
            }
        }
        if(flag2&&!flag)   //如果flag2仍是true则表示没找到（这里很奇怪，不加！flag的话，他在前面判断完!flag之后，居然会跳进这个if里）
        {
            total = 1;
            return ;
        }
    }
}



int main()
{
    cin>>s;
    int z=0,k;
    //clock_t start = clock();
    char temp = s[z++]; //用temp记录s[0]的元素值
    while(z<strlen(s))
    {
        if(s[z]==temp)//循环找到与第一个字符相同的字符的索引k
        {
            k=z;
            answer(k);
            break;
        }
        z+=1;
    }
    cout<<total<<endl;
    //clock_t endx = clock();
    //cout<<(double)(endx-start)/CLOCKS_PER_SEC<<endl;
    //测试了一下运行时间
    return 0;
}

• 听学长说这是谷歌的面试题之一，我就说怎么网上稍微搜了几下都没找到求相同长度子序列数量最多情况的算法，反而一搜一大把最长子序列（也可能是我不知道这个算法有其他的学名…>^<）