列表

详情


JD21. 最长区间

描述

拉齐有一个 01 序列,他可以对这个序列进行任意多次变换,每次变换都是把序列的最后若干个元素放到最前面,例如:010011,将最后 个元素 011 放到最前面,序列变为 011010 。所有变换结束后,拉齐需要挑出一个全为 的连续区间,要求最大化区间长度。

数据范围:输入序列长度满足

输入描述

共一行,一个01串,仅包含0或1。序列长度不超过50000。

输出描述

一个整数,表示最长区间的长度。

示例1

输入:

11011

输出:

4

说明:

把最后两个 1 放到最前面,形成一个长度为 4 的全 1 区间

原站题解

C++14 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-07-28

#include<stdio.h>
#define MAX 50000
int main()
{
    int i,j,num=0;
    int temp=0;
    int head = 0,tail=0;
    char a[MAX];
    scanf("%s",a);
    while(a[i++]=='1')
    {
        head++;
    }
      
    while(a[i]!='\0')
    {
        if(a[i]=='1')
        {
            temp++;
            tail++;
        } 
        else if(a[i]=='0')
        {
            temp = 0;
            tail = 0;
        }
        if(num<temp)
        {
            num = temp;
        }
        i++;
    }
    if(head!=0)
    {
        temp = tail+head;
        if(temp>num)
            num = temp;
    }
    printf("%d",num);
    return 0;
}

C++14 解法, 执行用时: 2ms, 内存消耗: 500KB, 提交时间: 2020-04-27

#include<stdio.h>
#define MAX 50000
int main()
{
    int i,j,num=0;
    int temp=0;
    int head = 0,tail=0;
    char a[MAX];
    scanf("%s",a);
    while(a[i++]=='1')
    {
        head++;
    }
     
    while(a[i]!='\0')
    {
        if(a[i]=='1')
        {
            temp++;
            tail++;
        }  
        else if(a[i]=='0')
        {
            temp = 0;
            tail = 0;
        }
        if(num<temp)
        {
            num = temp;
        }
        i++;
    }
    if(head!=0)
    {
        temp = tail+head;
        if(temp>num)
            num = temp;
    }
    printf("%d",num);
    return 0;
}

上一题