首页 > 试题广场 >

交错01串

[编程题]交错01串
  • 热度指数：35316 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
如果一个01串任意两个相邻位置的字符都是不一样的,我们就叫这个01串为交错01串。例如: "1","10101","0101010"都是交错01串。
小易现在有一个01串s,小易想找出一个最长的连续子串,并且这个子串是一个交错01串。小易需要你帮帮忙求出最长的这样的子串的长度是多少。

输入描述:
输入包括字符串s,s的长度length(1 ≤ length ≤ 50),字符串中只包含'0'和'1'


输出描述:
输出一个整数,表示最长的满足要求的子串长度。
示例1

输入

111101111

输出

3
算法知识视频讲解
添加回答
小学作业多头像 小学作业多
大家写的都好麻烦，遍历一遍数组记录最长的01交错子串长度就完了 

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        while (in.hasNext()) {
            String str = in.next();
            int maxLen = 1;
            int len = 1;
            for (int i = 1; i < str.length(); i++) {
                if (str.charAt(i - 1) != str.charAt(i)) {
                    len++;
                    if (len > maxLen) {
                        maxLen = len;
                    }
                } else {
                    len = 1;
                }
            }
            System.out.println(maxLen);
        }
    }
}

编辑于 2017-08-13 10:01:02 回复(12)
C/C++
卷积神经网络哦头像 卷积神经网络哦

笔试遇到这种送分题一定要做对而且不能浪费时间。。扫一遍O(n)即可

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string s;
int main(){
    cin>>s;
    int max_len = 1, len = 1;
    for(int i=0; i<s.length()-1; i++){
        if(s[i+1] != s[i]) {len++; max_len = max(max_len, len);}
        else len = 1;
    }
    cout<<max_len<<endl;
    return 0;
}
发表于 2019-03-01 20:53:47 回复(0)
Python
华科平凡头像 华科平凡

python解法

遍历字符串，记录每个位置的最大01串长度。

string = input()
res, tmp_max = 1, 1
for i in range(len(string) - 1):
    if string[i] != string[i + 1]:
        tmp_max += 1
        res = max(res, tmp_max)
    else: # 如果下个位置组不成01串，则从下个位置重新开始记录当前最大长度
        tmp_max = 1
print(res)
发表于 2019-03-02 11:04:36 回复(4)
小利子头像 小利子 

//javascript语言处理这样的问题很简单，使用正则表达式
var str=readline();
var reg=/0?(10)*1?/g;
var relArr=str.match(reg);
var max=0;
for(var i=0;i<relArr.length;i++){
    if(relArr[i].length>max){
        max=relArr[i].length;
    }
}
print(max);

发表于 2017-08-14 15:45:39 回复(5)
改个名字解解毒...头像 改个名字解解毒... 
#!/usr/bin/env python
#-*- coding:utf8 -*-
def findNum(nums):
    n = len(nums)
    if len(set(nums)) == 0:
        return 0
    num , Max = 0, 0
    for i in range(1, n):
        if nums[i] != nums[i-1]:
            num += 1
        else:
            num = 0
        Max = max(Max, num)
    return Max+1
 
 
if __name__ == '__main__':
    nums = raw_input()
    print findNum(nums)

发表于 2017-08-14 14:48:36 回复(5)
笑忘书生头像 笑忘书生 
#include<iostream>
#include <string>
using namespace std;

int main()
{
	string str;
	cin >> str;
	int res = 0;
	for (int i = 1; i < str.size();) {
		int k = i-1;
		while ( i < str.size()) {
			if (str[i] != str[i - 1])
				i++;
			else
				break;
		}
		if (res < i - k)
			res = i - k;
		i++;
	}
	cout << res << endl;
}

发表于 2017-08-12 22:15:21 回复(4)
元气の悟空头像 元气の悟空 
//AC代码：
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
    char s[100];
    int i;
    while(scanf("%s",s)!=EOF){
        int Max=1,pre=1;
        for(i=1;s[i]!='\0';i++){
            if(s[i]!=s[i-1]) pre++;
            else pre=1;
            Max=max(Max,pre);
        }
        printf("%d\n",Max);
    }
}

发表于 2017-08-23 17:51:51 回复(0)
JavaScript
Orange。头像 Orange。 
//直接遍历整个字符串，记录每次的长度，并取最大值
while(line = readline()){
    var str = line.trim();
    var len = str.length;
    if(len<=1){
        console.log(len);
    }else{
        var k=1;
        var max=1;
        for(var i=0; i<str.length-1; i++){
            if(str[i] !== str[i+1]){
                k++;
            }else{
                k=1;
            }
            if(k > max){
                max = k;
            }
        }
        console.log(max);       
    }   
}

编辑于 2017-08-13 10:21:13 回复(0)
LaGuZai头像 LaGuZai
Java语言。
思路：使用动态规划的思想，定义一个dp数组，dp【i】表示以下标为i的字符结尾的最长交错01串，显然
当i和i-1位置上的字符相等时，dp【i】 = 1；否则，dp【i】=dp【i-1】+1；最后求出dp数组中的极大值即可；
有错误或者建议欢迎指出，感谢。
代码：
importjava.util.*; 
publicclassMain{ 
       
    publicstaticvoidmain(String[] args){ 
        Scanner in = newScanner(System.in); 
        while(in.hasNext()){ 
            String s = in.nextLine();
            int[] dp = newint[s.length()];
            dp[0] = 1;
            for(inti=1;i<dp.length;i++){
                if(s.charAt(i-1) != s.charAt(i))
                    dp[i] = dp[i-1]+1;
                else
                    dp[i] = 1;
            }
            intmax = 0;
            for(inti : dp){
                if(i>max)
                    max = i;
            }
            System.out.println(max);
        } 
    } 
}
发表于 2017-08-12 23:02:05 回复(3)
Rudy.fan头像 Rudy.fan
个人觉得本题暴力双重循环可以求解，但是时间复杂度高。可以采用异或的思想，时间复杂度只需要O(n)。对二进制数中，每一个位加上后一位，如果等于1，则这两位是不同的；否则等于0或者2都是相同的。例如：1110101，采用前一位加后一位的思想则是，221111（最后一位可以与前一位相加）。 


s=input()
num=len(s)
s=[int(val) for val in s]
for i in range(num-1):
    s[i]=s[i]+s[i+1]
s[-1]=s[-1]+s[-2]
count=0
tmp=[]
for i in range(num-1):
    if s[i]==1:
        count+=1
    if s[i]==1 and s[i+1]!=1:
        tmp.append(count)
        count=0
if tmp:
    print(max(tmp)+1)
else:
    print(1)

编辑于 2019-04-24 15:10:08 回复(0)
学不会7头像 学不会7
用c语言编写成功的第一个程序，留个纪念！
#include <stdio.h>
#include<string.h>

int main() {
int sum = 1, len = 1;
char str[50];
scanf("%s", str);
for (int i = 1; i < strlen(str); i++) {
if (str[i-1] != str[i]) {
sum = sum + 1;
            if (sum > len) 
len = sum;
}else {
sum = 1;
}
}
printf("%d\n", len);
return 0;
}

发表于 2017-08-19 09:39:39 回复(0)
JavaScript
luluy头像 luluy 
var str = readline();
var count = 0;
var tem = 1;
for(var i = 0,len = str.length; i<len-1; i++){   
    if(str[i] !== str[i+1]){
        tem++;
    }else{
        count = Math.max(count,tem);
        tem = 1;
    }
}
count = Math.max(count,tem);
print(count);
编辑于 2017-08-13 17:06:51 回复(0)
pein531头像 pein531
直接使用双指针进行求解就行了 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine().trim();
        System.out.println(solve(str));
    }
    
    private static int solve(String str) {
        int left = 0, right = 1;
        int maxLen = 0;
        while(right < str.length()) {
            maxLen = Math.max(maxLen, right - left);       // 每次迭代都更新一下最大交错串的长度
            if(str.charAt(right) != str.charAt(right - 1)){
                // 如果right位置的字符和前一个位置不相同就右移
                right ++;
                if(right == str.length())
                    break;
            }else{
                // 否则将左指针移动到right，并将right右移一位重新计算后续的交错串长度
                left = right;
                right ++;
                if(right == str.length())
                    break;
            }
        }
        // 防止最长交错串以原始字符串的末尾结尾，最后还要更新一下长度
        maxLen = Math.max(maxLen, right - left);
        return maxLen;
    }
}


发表于 2021-02-15 17:53:16 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    int t=1, Max=0;
    for(int i=1;i<s.length();i++){
        if(s[i]!=s[i-1]){
            t++;
        }else{
            Max = max(Max, t);
            t = 1;
        }
    }
    Max = max(Max, t);
    printf("%d\n", Max);
    return 0;
}

发表于 2020-09-05 00:43:05 回复(0)
Java
CR7M12头像 CR7M12
Java 语言     看代码说话 
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin=new Scanner (System.in);
		String str=cin.nextLine();//读入字符串
		int n=str.length();
	   int temp=1;//暂时变量
	   int out=1;//要输出的变量
	   for(int i=1;i<n;i++) {
		   if(str.charAt(i) !=str.charAt(i-1)) {
			   temp++;
			  // System.out.println(i+" "+str.charAt(i));
		   }
		   else {
			   out=Math.max(temp, out);
			   temp=1;
		   }
           
	   }
        out=Math.max(temp, out);
	   System.out.print(out);

	}

}


编辑于 2019-11-04 16:45:13 回复(0)
C/C++
viva-la头像 viva-la
dpa 表示当前以0结尾连续最大符合条件串长度， dpb表示以1结尾最大符合条件串长度。 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 判断排序后是否构成等差数列
int main(){
    string s;
    cin>>s;
    // dpa 代表第i个位置以0为结尾连续10串 dpb以1为结尾
    int len = s.length();
    int ret=0, dpa=0, dpb=0;
    for(int i=0;i<len;i++){
        if(s[i] == '1'){
            dpa = dpb + 1;
            ret = max(ret, dpa);
            dpb = 0;
        }
        else{
            dpb = dpa + 1;
            ret = max(ret, dpb);
            dpa = 0;
        }
    }
    cout<<ret<<endl;
    return 0;
}

发表于 2019-06-10 21:32:06 回复(0)
紫魂的海角头像 紫魂的海角
即查找相邻元素不同的最长子串，相邻元素不同则子串长度加1，否则长度更新为1，简单遍历即可 
public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        String string = sc.next();
        int maxlen = 1;
        int index = 1;
        int i = 1;
        while(i< string.length()){
            index = string.charAt(i) == string.charAt(i-1)?1: ++index;
            maxlen = index>maxlen? index:maxlen;
            i++;
        }
        System.out.println(maxlen);
    }
}

编辑于 2019-06-10 21:27:09 回复(0)
Java
Mono_Chrome头像 Mono_Chrome

由于已经只确定输入字符只有0和1，所以用一个变量存储前一个字符，然后每次都跟当前字符进行对比看是否不同，最长字串长度设为count，如果相同则count++，否则count更新为1。

import java.util.Scanner;

public class Main {
    public static int process(String str) {
        if (str.length() < 1) {
            return 0;
        }
        char pre = str.charAt(0);

        int count = 1;
        int max = 0;
        for (int i = 1; i < str.length(); i++) {
            if (str.charAt(i) != pre) {
                pre = str.charAt(i);
                count++;
            } else {
                count = 1;
            }
            max = Math.max(count, max);
        }
        return max;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        System.out.println(process(str));
    }
}
发表于 2019-06-10 14:11:05 回复(0)
offer菜鸟头像 offer菜鸟 
#其实很简单，将当前输入与前一个输入进行比较，
#若不同则子串长度加 1 ；
#若相同则舍弃前一个输入，子串从当前输入开始.
#include <iostream>
 
using namespace std;
 
int main()
{
    int mid,mid2,max=1,count=1;
    cin>>mid;
    while(cin)
    {
        cin>>mid2;
        if(mid2==mid)
        {
            count = 1;
        }
        else
        {
            count++; #记录子串长度
        }
        if(count>max)
        {
            max=count; #记录当前最大子串的长度
        }
        mid=mid2;
    }
    cout<<max<<endl;
    return 0;
}

编辑于 2019-05-13 16:02:14 回复(0)
芝麻开萌头像 芝麻开萌 
s_list=[i for i in input()]
length = 1
while len(s_list)>1:
    for k in range(len(s_list) - 1):
        if s_list[k] == s_list[k + 1]:
            length = max(length, k + 1)
            break
    else:
        length = max(length, k + 2)
    s_list = s_list[1:]
else:
    print(length)

发表于 2019-05-03 21:53:10 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 字符串 前端工程师 算法工程师 测试工程师 PHP工程师 网易 2018 Java工程师
来自：网易2018校招内推编...
上传者：小小
难度：
241条回答 24299浏览

热门推荐

通过挑战的用户

查看代码

相关试题

交错01串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号