首页 > 试题广场 >

最长区间

[编程题]最长区间

热度指数：4569 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：输入序列长度满足 $1 \le n \le 50000 \$

输入描述:

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

输出描述:

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

示例1

输入

输出

说明

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

算法知识视频讲解

燃情雪201904281453989

    const delay = str => {
      if (typeof str !== 'string') {
        return '请输入字符串'
      }

      const arr = str.match(/1+/g)
      return arr === null ? 0 : Math.max( ...arr, arr[0].concat(arr[arr.length -1]) ).toString().length
    }

发表于 2019-11-09 14:05:13 回复(1)

炊烟晚霞

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int len = str.length();
        int max = 0;
        char[] arr = str.toCharArray();
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (arr[i] == '0') {
                max = Math.max(max, count);
                count = 0;
            } else {
                count++;
            }
        }
        max = Math.max(max, count);
        if (max == len) {
            System.out.println(max);
            return;
        }
        count = 0;
        int i = 0;
        if (arr[0] == '1' && arr[len-1] == '1') {
            while (arr[i++] == '1') count++;
            i = len-1;
            while (arr[i--] == '1') count++;
        }
        max = Math.max(max, count);
        System.out.println(max);
    }
}

发表于 2020-07-29 02:53:08 回复(0)

亚洲舞王智海

st=input()*2#同评论区大佬的*2思路
ans=count=0
if st.find('0')==-1:#也可以 if '0' not in st :   时间会短一点
    print(int(len(st)/2))#加int是不知道为什么输出1.0这样的小数
else :
    for i in st :
        if i=='1' :
            count+=1
            ans=max(ans,count)
        else : count = 0
    print(ans)

编辑于 2019-12-26 16:55:32 回复(0)

JavaScript

苏寒yy

把字符串与自身拼接，找新字符串中的连续1的区间长度，考虑原字符串全为1或全为0的情况，

var input=readline();
if(!input.includes(0)){
     var l=input.length;
        print(l);
    }else if(!input.includes(1)){
        print(0);
    }else{
        var str=input+input;
        foo(str);
    }
function foo(str){
        var arr=str.match(/1{1,}/g);
        var len=[];
        arr.map(()=>{
	        for(var i=0;i<arr.length;i++){
		         len[i]=arr[i].length
	      }
	        return len;
    });
len.sort((a,b)=>{
	return b-a;
	});
print(len[0]);
}

编辑于 2019-08-12 15:22:54 回复(0)

give米一个offer吧！

#include<iostream>
#include<string>
using namespace std;
int main(){
string str;
cin>>str;
int size = 0;
int maxsize = 0;
int a = 0;
int len = str.size();
string str2 = str+str;
for(int i=a;i<2*len;i++){
if(str2[i]=='1'){
size++;
if(size > maxsize){
maxsize = size;
}
}else{
size = 0;
}
}
if(maxsize>len){
cout<<len<<endl;
}else{
cout<<maxsize<<endl;
}

}

把两个输入的字符串连接起来，然后求整个字符串中连续1的最大长度，要考虑全部为1的情况哦！

发表于 2019-07-13 10:36:48 回复(0)

JavaScript

牛客793971400号

JS V8 来了！

while (line = readline()) {
    var s1 = line;
    var c = 0;
    var l = 0;
    if (s1.indexOf(0) != -1) {
        var s2 = s1 + s1;
        for (let i = 0; i < s2.length; i++) {
            if (s2[i] != 0) {
                c++;
                if (c > l) {
                    l = c
                }
            } else {
                c = 0
            }
        }
        print(l)
    } else {
        print(s1.length)
    }
}

发表于 2020-02-13 11:27:07 回复(3)

白色纯度

最好的办法就行将字符串首尾相连，一次遍历查找就行。不过我们也可以将字符串乘2，然后一次遍历查找最长连续1的长度。双指针遍历很容易找得到的。Python2的代码：

def max_interval(num):
    if num=='1'*len(num):
        return len(num)
    num = num*2
    i,j = 0,0
    res = 0
    while i < len(num):
        while i<len(num) and num[i]=='1':
            i += 1
        res = max(res,i-j)
        i += 1
        j = i
    return res
if __name__=='__main__':
    s = raw_input().strip()
    print(max_interval(s))

发表于 2019-08-09 20:51:50 回复(1)

C/C++

nbgao

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

int main(){
    string s,t;
    int n,r=0;
    cin>>s;
    t = s+s;
    n = t.length();
    for(int i=0;i<n;i++){
        int j = i;
        while(i<n && t[i]=='1')
            i++;
        r = max(r, i-j);
    }
    if(r==2*s.length())
        cout<<r/2<<endl;
    else
        cout<<r<<endl;
    return 0;
}

发表于 2019-11-12 11:26:03 回复(0)

66667

//93.3%通过率，为啥呢
var line = readline();
var h = line.split("");
var y =[];
var u = h.concat(h);
var count = 0;
var a=0;
    for(j=0;j<u.length;j++){
        if(u[j]==1){
            count++;
           a = Math.max(a,count);
        }else{
            count = 0;
            continue;
        }
    }
    y.push(a)
    if(h.length==1&&h[0]==1){
        print(1)
    }else{
        print(Math.max.apply(null, y))}

发表于 2019-09-15 16:09:06 回复(0)

初心者托奇

a = input()
print(len(max((a[a.index('0'):] + a[:a.index('0')]).split('0')))\
      if '0' in a else len(a))

编辑于 2020-03-16 17:54:07 回复(0)

潦草书千行

//字符串*2 处理全1的情况  双指针 取连续区间  记录过程最大值
const fun = (str) => {
  if(str.indexOf(0)==-1){
       return str.length;
  }
  const s = str + str;
  let sum = 0,cur = 0;
  for(let i=0;i<s.length;i++){
      if(s[i]!= 0){
          cur++;
          if(cur > sum){
              sum = cur;
          }
      }else{
          cur = 0;
      }
  }
  return sum;
}

while(line = readline()){
    console.log(fun(line));
}

发表于 2022-05-31 10:57:41 回复(0)

Oliver1234

一次遍历

先记录开头连续1的数量

然后遍历剩余字符串，记录连续1的最大长度

最后计算末尾连续1长度+开头连续1长度，更新最大长度

s = input()
n = len(s)
head = 0 # head记录开头连续1的数量
for i in range(n):
    if s[i] == '1': head += 1
    else: break
res, cnt = 0, 0 # cnt记录当前连续1的数量
for i in range(head,n):
    if s[i] == '1': cnt += 1
    else: # 如果当前数是0，更新最大长度，并将cnt归0
        if cnt > res: res = cnt 
        cnt = 0
cnt += head # 此时cnt值为末尾连续1的数量，加上开头连续1的数量，对比res
if cnt > res: res = cnt 
print(res)

发表于 2022-02-15 19:59:21 回复(0)

忘魂儿

相同字符串拼接完后，以0为划分，找到最长连续含有1的子串长度就是结果

发表于 2022-01-27 21:45:06 回复(0)

C++

牛客409434554号

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;cin>>s;
    if(s=="1")    {cout<<1<<endl;return 0;}
    if(s.find('0')==s.npos)    {cout<<s.length()<<endl;return 0;}
    if(s.find('1')==s.npos)    {cout<<0<<endl;return 0;}
    int maxn=s.find('0')+s.length()-1-s.rfind('0'),sum=1;
    for(int i=0;i<s.length()-1;i++)
    {
        if(s[i]==s[i+1]&&s[i]=='1')    sum++;
        else {maxn=max(maxn,sum);sum=1;}
    }
    cout<<maxn<<endl;
}

发表于 2022-01-21 07:44:37 回复(0)

曾永铭

s = list(map(int, [i for i in input()]))
# print(s)
#找最大中间子串
j = 0
n = len(s)
count = 0
while j < n:
    if s[j] == 1:
        temp = 0
        while j < n and s[j] == 1:
            temp += 1
            j += 1
        count = max(count, temp)
    j += 1
    
i = 0
if s[0] == 1:
    while i < n and s[i] == 1:
        i += 1
bn = i

i = n-1
ct = 0
if s[-1] == 1:
    while i >= 0 and s[i] == 1:
        i -= 1
        ct += 1
en = ct

if bn+en >= sum(s):
    print(max(sum(s), count))
else:
    print(max(bn+en, count))

一个渣渣土里土气的思路：因为中间的1子串一旦被0分割开的话，不管怎么捯饬都没法合成更长的子串，所以最长的子串只有可能来自：

a. 串的内部

b. 从头开始的全1子串+从尾开始的全1子串

分别把它们找出来看看哪个更长即可。

注意全1子串用这种方***得到2*#(1)的结果，所以要做一下判断，1子串的长度怎么长也不可能#(s)的

发表于 2021-04-10 15:10:01 回复(1)

春招年薪x冲冲冲

js (node12.18.2)

//js (node12.18.2)
var readline = require("readline");
r1 = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
r1.on("line", function(data) {
  var inputs = data.trim().split("");
  var result = deal(inputs);
  console.log(result);
});
function deal(inputs) {
  let count = 0;
  inputs = inputs.join("");
  if (inputs.indexOf("0") === -1) return (count = inputs.length);
  inputs = inputs + inputs;
  let tempCount = 0;
  for (var j = 0; j < inputs.length; j++) {
    if (inputs.indexOf("1", j) == j) {
      tempCount++;
    } else {
      count = Math.max(tempCount, count);
      tempCount = 0;
    }
  }
  return count;
}

编辑于 2021-03-18 12:05:18 回复(1)

祛年

骗分高手QAQ

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
zero(s);

}
static void zero(String s) {
int len = s.length();
int count = 0;
int sum = 0;
if (s.charAt(0) == '0' || s.charAt(len - 1) == '0') {
for (int i = 0; i < len; i++) {

if (s.charAt(i) == '1') {
if (count >= 1) {
count++;

} else {
count++;
}
sum = Math.max(sum, count);

} else
count = 0;
}
System.out.println(sum);
}
}

}

发表于 2020-08-26 20:58:54 回复(0)

YANZX

var str=readline()

str1=str.concat(str)

var arr=str1.match(/1+/g)

if(arr==null){

console.log(0)

}else{

arr1=arr.sort();

if(arr1.length==1){

console.log(str.length)

}else

{console.log((arr[arr.length-1]).length)}}

发表于 2020-08-25 09:38:54 回复(0)

offer已经发你邮箱了

let str = readline()
if (!str.includes(0)) {
  print(str.length)
} else {
  str += str
  const arr = str.split(0).map(e => e.length)
  print(Math.max(...arr))
}

发表于 2020-08-05 19:20:34 回复(0)

皮蛋秀柚秋

import java.util.*;
public class Main{
    public static void main(String[] args){
        String s = new Scanner(System.in).nextLine();
        int mark = s.length();
        // 数组拼接之后，各种变换应该都会在这个字符串中出现
        s = s+s;
        int i=0,j=0;
        int ans = 0;
        while(j<s.length()){
            while(j<s.length()&&s.charAt(j)=='1')
                ++j;
            ans = Math.max(ans,j-i);
            ++j;
            i = j;
        }
        // 不可能比原始字符串长
        System.out.println(ans>mark?mark:ans);
    }
}

发表于 2020-07-03 21:52:02 回复(0)

提交观点

问题信息

贪心动态规划数组字符串前端工程师京东 2019

上传者：小小

难度：

37条回答 121收藏 11606浏览

通过挑战的用户

查看代码

khadro-jia

2023-03-10 13:08:28
Lonng

2023-02-24 20:55:58
喜欢吃蛋糕起司在创作

2022-10-29 15:18:22
牛客49655...

2022-10-29 12:59:57
页川木子

2022-10-15 17:08:08