首页 > 试题广场 >

橡皮泥斑马

[编程题]橡皮泥斑马
  • 热度指数:2545 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小易很喜欢斑马,因为它们身上黑白相间的花纹。
一天小易得到了一串橡皮泥,这串橡皮泥只有黑色和白色,小易想把这串橡皮泥重新拼凑一下,让这个橡皮泥串中最长的连续的黑白相间的子串最长,但是小易有强迫症,所以他可以对橡皮泥串进行以下的操作0次或多次:
把橡皮泥串从某个地方切割开,将两个得到的两个串同时翻转,再拼接在一起。
这个橡皮泥串可能太长了,所以小易没有办法计算最终可以得到的最长的连续的黑白相间的子串的长度,希望你能帮他计算出这个长度。

输入描述:
一个字符串s,只包含字母'b'和字母'w',分别表示黑色和白色的橡皮泥块。
满足1 <= |s| <= 105,|s|代表字符串的长度。


输出描述:
一个整数,表示改变之后最长的连续的黑白相间的子串的长度。
示例1

输入

bwbwb

输出

5
示例2

输入

wwb

输出

3
该变换规则不影响相对位置,计数时记得把头尾可拼接的情况考虑进去。
s = list(input())
n = len(s)

res = 0
pre = 0
post = n-1
if s[0] != s[-1]:
    while(s[pre] != s[pre+1]):
        pre += 1
    while(s[post] != s[post-1]):
        post -= 1
    res = n - post + pre + 1
tmp = 1
for i in range(n-1):
    if s[i]!=s[i+1]:
        tmp += 1
    else:
        res = max(res,tmp)
        tmp = 1
res = max(res,tmp)
print(res)


编辑于 2019-08-24 16:35:44 回复(0)
"""
将串首尾相连成环(简化为将S加上一个首字符),计算最长子串
能通过本题的所有测试用例
"""

if __name__ == "__main__":
    s = input().strip()
    s = s + s[0]
    ans, tmp = 0, 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            ans = max(ans, tmp)
            tmp = 1
        else:
            tmp += 1
    ans = max(ans, tmp)
    print(ans)

编辑于 2019-08-24 16:27:40 回复(5)
两个子橡皮泥串同时翻转就相当于把后面的子串拼到前面去。因此可以将原始橡皮泥串重复两遍,然后计算最长黑白相间的子串长度。但是这个长度不能超过原始橡皮泥串的长度。
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();
        str += str;
        int maxLen = 0;
        for(int i = 0; i < str.length(); i++){
            int j = i + 1;
            while(j < str.length() && str.charAt(j) != str.charAt(j - 1))
                j ++;
            // 不能超过原字符串长度
            if(j - i <= str.length() / 2)
                maxLen = Math.max(maxLen, j - i);
            else
                break;
        }
        System.out.println(maxLen);
    }
}


发表于 2021-01-30 18:42:49 回复(0)
看大家都是环  恍然大悟 。。鄙人思路和代码相当复杂,但也能过。
#include<bits/stdc++.h>
using namespace std;
string s;

string op(string s, int pos) {
	//在pos位置对字符串s进行题目所示操作
	if(pos >= s.length()) return s;
    string ls = s.substr(0, pos);
    string rs = s.substr(pos);
	reverse(ls.begin(), ls.end());
	reverse(rs.begin(), rs.end());
    return ls + rs;
}

vector<int> cal_length(string s) { //找到最长间隔串并返回长度和左右坐标
	int len = 1, res = 1, cur_l = 0, cur_r = -1;
	char last = s[0];
	for(int i = 1; i < s.length(); i++) {
		if(s[i] != last) len++;
		else {cur_l = i; len = 1; }
		if(len > res) {res = len; cur_r = i; }
		last = s[i];
	}
	vector<int> ve;
	if(res == 1) res = 0;
	ve.push_back(res);
	ve.push_back(cur_l);
	ve.push_back(cur_r);
	return ve;
}

int main() {
	cin>>s;
	int s_len = s.length();
    vector<int> v_cur = cal_length(s);
	int best = v_cur[0];
	while(v_cur[0] != s_len && s[0] != s[s_len - 1]) { //满足换了之后可以增加长度
		string cur_s1 = op(s, v_cur[2]+1); // 在当前最长的右边节点换
		string cur_s2 = op(s, v_cur[1]); // 当前最长的左边节点换
		vector<int> v1 = cal_length(cur_s1); 
		vector<int> v2 = cal_length(cur_s2);
		if(v1[0] > 0 && v1[0] >= v2[0] && v1[0] > v_cur[0]) {
			best = v1[0]; s = cur_s1; v_cur = v1;
		} else if(v2[0] > 0 && v1[0] < v2[0] && v2[0] > v_cur[0]) {
			best = v2[0]; s = cur_s2; v_cur = v2;
		} else {
			break;
		}
	} 
	cout<<best<<endl;
}
/*
bwbwb
wwb
*/

发表于 2020-01-18 16:14:21 回复(2)
//因为可以成环,因此最长的结果为两种情况
//1.正常扫描下来最长的结果
//2.以序列头开始的连续部分和以序列末尾结束的连续部分之和(序列头和序列尾不同)
//取这两种情况中的最大值
#include <stdio.h>
#include <string.h>

const int N = 1e5;
char str[N+5];

int max(int a,int b){
    return a>b?a:b;
}

int main(){
    scanf("%s",str);
    int len = strlen(str);
    if(len==1) puts("0");
    else if(len==2){
        if(str[0]==str[1]) puts("0");
        else puts("2");
    }else{
        int headLen = 1, tailLen = 1;
        int start = 0, end = len-1;
        //开头连续的最长长度
        for(;start<end;start++){
            if(str[start]==str[start+1]) break;
            headLen++;
        }
        //扫描到结尾说明整个串都满足
        if(start==end) printf("%d\n",headLen);
        else{
            //结尾连续最长长度
            for(;end>start;end--){
                if(str[end]==str[end-1]) break;
                tailLen++;
            }
            //序列头开始和序列尾结束的两段已经算出来了
            int res = max(headLen,tailLen);
            int tmpLen = 1;
            //中间部分最长的
            for(start++,end--;start<end;start++){
                if(str[start]==str[start+1]) {
                    res = max(res,tmpLen);
                    tmpLen = 1;
                }else tmpLen++;
            }
            //序列头尾不同,比较中间最长和头尾拼起来的结果
            if(str[0]!=str[len-1]) res = max(res,headLen+tailLen);
            printf("%d\n",res);
        }
    }
    return 0;
}
编辑于 2019-08-13 17:12:07 回复(0)
s = raw_input()
s = s + s
res = 0
for i in range(len(s)):   
    j = 1
    while i < len(s)-1 and s[i] != s[i+1]:
        j += 1
        i += 1
    if j > res:
        res = j
if res > len(s)/2:
    res = len(s)/2
print res

发表于 2019-05-29 19:46:50 回复(0)
字符串翻转,可以将其理解为环形结构,相对位置不变
发表于 2019-05-02 14:26:35 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    int Max=0,t=1;
    s += s[0];
    for(int i=1;i<s.length();i++){
        if(s[i]!=s[i-1])
            t++;
        else{
            if(t>Max)
                Max = t;
            t = 1;
        }
    }
    if(t>Max)
        Max = t;
    cout<<Max<<endl;
    return 0;
}

发表于 2019-08-28 00:47:29 回复(3)
/*切割并同时旋转拼接 相当于 把切割后 后面的子串 放到 前面 
如wbwwb,切割wbw,wb 后放前 -> wbwbw 与翻转(wbw,bw)后拼接结果一致
故将原字符串扩大2倍,找最长相间子串
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s ; 
    cin >> s ; 
    s += s ;
    int len = s.size() ;
    int res = 0 ; 
    for( int i = 0 ; i < len ; i++ ){
        int j = i + 1 ;
        while( j < len && s[j] != s[j-1] ){
            j ++ ;
        }
        res = max( res , j - i ) ; 
        i = j - 1 ;
    }
    cout << min( res , len / 2 ) << endl ;
    return 0 ; 
}

发表于 2020-02-11 16:20:38 回复(0)
// 取模转圈
#include<bits/stdc++.h>
using namespace std;

int main(){
    string str;
    getline(cin, str);
    str += str[0];
    int len = 0,curlen = 1;
    char pre = str[0];
    int n =str.size();
    for(int i =1; i<n * 2; i++){
        if(str[(i-1)%n] == str[i%n]){
            len = max(len,curlen);
            curlen = 1;
        }else{
            curlen ++;
        }
    }
    len = max(len,curlen);
    cout << len << endl;
    return 0;
}

发表于 2021-09-15 19:43:29 回复(0)
同时翻转是怎么一个翻转法?有哪个可以举一下例子?
发表于 2020-08-19 12:00:19 回复(0)
可以切割开,将两个得到的两个串同时翻转,再拼接在一起,可以看做一个首位相接的串,将串后面在拼接本身就行。然后就是查找最长bw子串问题了.
import java.util.*;
public class Main{
    
    
    public static void main(String[] args){
        
       Scanner s  = new Scanner(System.in); 
       String str = s.nextLine();
       
       StringBuilder sb = new StringBuilder(str);
       sb.append(str);
        
       int len = 1;
       int maxLen = 1;
       for(int i =1;i<sb.length();i++){
           if(sb.charAt(i-1) != sb.charAt(i)){
               len+=1;
           }else{
               len = 1;
           }
           maxLen = maxLen>=len?maxLen:len;
       }
        
       System.out.println(maxLen);
        
    }
}


发表于 2020-08-13 13:29:01 回复(0)
#include <iostream>
#include <string>
using namespace std;

int main(){
    string s;
    cin >> s;
    //如果字符串长度小于2
    if (s.size() <= 1) 
        cout << s.size() << endl;
    //正常情况
    else{
        int res = 1;
        //遍历每一个字符
        for (int i=0;i<s.size();++i){
            int cur = 0;
            //从当前字符开始,计算他的子串长度
            for (int j=0;j<s.size();++j){
                //把首尾相连
                if (s[(i+j)%s.size()] != s[(i+j+1)%s.size()])
                    ++cur;
                else
                    break;
            }
            //之所以➕1,因为虽然最后一个满足条件的字符和下一个字符一样了,但是它和上一个还是不一样的
            //所以这个字符的长度得算进去
            res = res<cur+1?cur+1:res;
        }
        cout << res << endl;
    }
    return 0;
}

发表于 2020-07-15 15:51:55 回复(0)
测试用例不太严谨,我用的错误的方法结果还通过了,我看题解才知道我错了
s = input()
t = s[0]
l_max = 0
l = 1
for i in range(1,len(s)):
    c = s[i]
    if c == t:
        if l_max < l:
            l_max = l
            l_max_0 = i - l + 1
        l = 1
    else:
        l += 1
    t = s[i]
if l_max == 0:
    l_max = l
    l_max_0 = 0
if l_max < l:
    l_max = l
    l_max_0 = i - l + 1
if s[0] != s[-1] and (l_max_0 == 0&nbs***bsp;l_max_0 == len(s) -l):
    l_max += 1
print(l_max)

发表于 2020-07-02 22:57:40 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();

        str += str;

        int res = 0;
        int temp = 1;
        for (int i = 0; i < str.length() - 1; i++) {
            int j = i + 1;
            if (str.charAt(i) != str.charAt(j)){
                temp++;
                res = Math.max(res, temp);
            } else {
                temp = 1;
            }
        }

        if (res == str.length()){
            System.out.println(res / 2);
        } else {
            System.out.println(res);
        }

    }
}

发表于 2020-03-24 17:05:41 回复(0)
import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        input += input;
        char[] s = input.toCharArray();
        int cur = 1, max = 0;
        for (int i = 0; i < s.length - 1; i++) {
            if (s[i] != s[i+1]) {
                cur += 1;
            } else {
                if (cur > max) {
                    max = cur;
                }
                cur = 1;
            }
        }
        System.out.println(max);
    }
}

任意位置分开,旋转,可理解为环形结构。上面的代码本来以为有通不过的,没想到一次通过了所有测试用例,只能说测试用例不完备哈哈。
发表于 2019-07-31 20:44:45 回复(0)
//根据反转前后相对位置不变,相当于在一个环上找最长子串
#include <iostream>
#include <string>
using namespace std;
int main()
{ 
    string s;
    cin >> s;
    int g_l = 0, l_l = 1;
    s += s[0];//在字符串末尾加上第一个字符构成环
    for (int i = 0; i < s.size()-1; i++) {
        if (s[i] != s[i + 1]) {
            l_l++;
        }
        else{
            if (l_l > g_l) {
                g_l = l_l;
            }
            l_l = 1;
        }
    }
    if (l_l > g_l) {
        g_l = l_l;
    }
    cout << g_l;
    return 0;
}

发表于 2019-07-30 10:18:47 回复(0)
 同样的算法思路,java跑过不了,c++能过
                                                                                    
发表于 2019-07-15 10:46:02 回复(0)