首页 > 试题广场 >

最长区间

[编程题]最长区间
  • 热度指数:4507 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
拉齐有一个 01 序列,他可以对这个序列进行任意多次变换,每次变换都是把序列的最后若干个元素放到最前面,例如:010011,将最后 个元素 011 放到最前面,序列变为 011010 。所有变换结束后,拉齐需要挑出一个全为 的连续区间,要求最大化区间长度。

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

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


输出描述:
一个整数,表示最长区间的长度。
示例1

输入

11011

输出

4

说明

把最后两个 1 放到最前面,形成一个长度为 4 的全 1 区间 
    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)
把字符串与自身拼接,找新字符串中的连续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)
#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)
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)
#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)
//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)
一次遍历
先记录开头连续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)
#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)

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)
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)
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)