首页 > 试题广场 >

彩色瓷砖

[编程题]彩色瓷砖

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

牛牛喜欢彩色的东西,尤其是彩色的瓷砖。牛牛的房间内铺有L块正方形瓷砖。每块砖的颜色有四种可能:红、绿、蓝、黄。给定一个字符串S, 如果S的第i个字符是'R', 'G', 'B'或'Y',那么第i块瓷砖的颜色就分别是红、绿、蓝或者黄。
牛牛决定换掉一些瓷砖的颜色,使得相邻两块瓷砖的颜色均不相同。请帮牛牛计算他最少需要换掉的瓷砖数量。

输入描述:

输入包括一行,一个字符串S,字符串长度length(1 ≤ length ≤ 10),字符串中每个字符串都是'R', 'G', 'B'或者'Y'。

输出描述:

输出一个整数,表示牛牛最少需要换掉的瓷砖数量

示例1

输入

RRRRRR

输出

算法知识视频讲解

C/C++

谁主沉浮

  #include <iostream> 
  #include <string> 
  using namespace std; 
  int main() 
  { 
       string str; 
       getline(cin,str,'\n'); 
       int k = 0; 
       string tmp; 
       string tmp0; 
       for(int i=0;i<str.length()-1;i++) 
       { 
           tmp = str[i]; 
          tmp0 = str[i+1]; 
          if(tmp == tmp0) 
          { 
              k++; 
               i++; 
          } 
      } 
      cout<<k<<endl; 
      return0; 
  } 

编辑于 2017-08-01 11:17:26 回复(4)

Java

8965471

import java.util.Scanner;
/*
两两判断，碰到相同的直接替换就可以，因为有四块砖，保证替换的那块跟它的前面和后面都不相同就可以，所以
一定可以找到一个与前面不同同时与后面不同的替换，因此可以直接替换。
对字符串进行两两判断，找到相邻两个相同的，就将计数器加一，然后直接跳过这两个，从下一个开始判断，就是两两判断
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            String str = sc.next();
            System.out.println(replaceBrick(str));
        }
    }

    private static int replaceBrick(String str) {
        int len = str.length();
        int count = 0;
        char[] cStr = str.toCharArray();
        for (int i = 1; i < len; i++) {
            if(cStr[i]==cStr[i-1]){
                count++;
                i++;
            }
        }
        return count;
    }
}

发表于 2017-08-08 22:00:16 回复(5)

perhaps789

// javascript 版本
while(line=readline()) {
    var count = 0;
    for(var i = 1, len = line.length; i < len;) {
        if(line[i] == line[i-1]) {
            count++;
            i += 2;
        } else {
            i++;
        }
    }
    print(count);
}

编辑于 2017-09-10 21:17:52 回复(0)

牛客1988270号

var str = readline();

var count =0;

for (var i=1;i<str.length;i++) {

if (str.charAt(i) == str.charAt(i-1))

{

count++;

i++;

}

console.log(count);

//javascript 8

发表于 2017-07-26 19:07:36 回复(2)

C.A.Y.P

#include <stdio.h>
#include <string.h>

int main(){
    int i ;
    int index=0;
    char str[10];
    scanf("%s",&str);
    for(i=0;i<9;i++){
        if(str[i]=='\0')break;
        if(str[i]==str[i+1]){
            index++;
            i++;
        }
    }
    printf("%d",index);
    return 0;

}

两两比较，如果相同，index记1.然后移两位开始比较，以此类推，

发表于 2018-01-08 14:47:59 回复(0)

Java

我相信：

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        char[] c = s.toCharArray();
        int count = 0;

        for(int i=0; i<c.length-1; i++){
            if(c[i] == c[i+1]){
                count++;
                i++;
            }
        }
        scanner.close();
        System.out.println(count);
    }

发表于 2017-09-07 22:18:15 回复(3)

髻

s=list(input())
count=1
listc=[]
for i in range(len(s)-1):
    if s[i]==s[i+1]:
        count+=1
    else:
        listc.append(count)
        count=1
    if i+1==len(s)-1:
        listc.append(count)
            
exchange=[0,0,1,1,2,2,3,3,4,4,5] #分别是连续串长度为0的时候要换的瓷砖数量，为i的时候要换的瓷砖数量...
ans=0
for i in listc:
    ans+=exchange[i]
print(ans)

投机取巧了，最长才10个字母

1.事先把连续串长度等于0~10对应所需置换的数量，人工算出来，存在数组里

2.先把连续串找出来

3.对每个连续串要用多少个瓷砖查一下数组就可得

发表于 2017-09-04 18:50:30 回复(0)

C/C++

太阳石

  //是不是最短哈哈 
  
 
  #include <iostream> 
  #include <string> 
  using namespace std; 
  intmain() 
  { 
      string str; 
      while(cin >> str) 
      { 
          intnum = 0; 
          for(inti = 0; i < str.length()-1; i++) 
          { 
              if(str[i] == str[i + 1]) 
              { 
                  num++; 
                  i++; 
              } 
    
          } 
          cout << num << endl; 
      } 
      return0; 
  } 

发表于 2017-08-16 15:41:58 回复(3)

麦田的守护者

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{    
    int count = 0;
    string str;
    cin >> str;
    vector<int> vec(str.size(),1);
    for(int i = 1;i < str.size();++i)    
	{
        if(str[i] != str[i-1])
            vec[i]++;
    }        
    for(int i = 1;i < vec.size();++i)
	{
        if(vec[i] == 1)
        {
            count++;
            ++i;
        }            
    } 
    cout << count;
}

发表于 2017-08-15 13:17:47 回复(0)

元气の悟空

#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
int Min=99999999;
void dfs(string,int,int);
int main(){
	string in;
	while(cin>>in){
		Min=99999999;
		dfs(in,1,0);
		printf("%d\n",Min);
	}
}
void dfs(string x,int index,int step){
	if(index==x.length()){
		//cout<<x<<endl;
		if(Min>step) Min=step;
	}else{
		int i,j;
		if(x[index]==x[index-1]){
			char color[100]="RGBY";
			for(j=0;j<4;j++)
				if(color[j]!=x[index-1]){
					string tmp=x;
					tmp[index]=color[j];
					//cout<<"tmp:"<<tmp<<" i:"<<i<<endl;
					dfs(tmp,index+1,step+1);
				}
		}else dfs(x,index+1,step);
	}
}

发表于 2017-08-02 18:28:29 回复(0)

633_重庆森林

参考本人博客地址http://www.jianshu.com/p/e3d4223f757e

直接判断即可，两两判断，因为有四块瓷砖，所以碰到相同的直接替换就可以，而且一定可以找到一个与前面不同同时与后面不同的替换，所以只要直接替换，不用考虑其他，找到相邻两个相同的，就将计数器加一，然后直接跳过这两个，从下一个开始判断，就是两两判断

代码

import java.util.*; public class Main { public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String s = in.nextLine(); in.close();

        System.out.println(replace(s,s.length()));

    } private static int replace(String s, int len) { int count = 0; for(int i=1;i<len;i++) { if(s.charAt(i) == s.charAt(i-1)) {
                count++;
                i++;
            }
        } return count;
    } 

}

 数据结构与算法

发表于 2017-07-27 18:22:25 回复(0)

Python

牛客J

# -*-coding:utf-8-*-
import sys
import re
s=sys.stdin.readline().strip('\n')

pattern = re.compile('RR+|GG+|BB+|YY+')
temp = pattern.findall(s)
print(temp)
outNum=0
for i in temp:
    lenSubStr=len(i)
    outNum +=lenSubStr//2
print(outNum)

发表于 2017-07-26 17:30:40 回复(0)

小利子

var str=readline(); var tmp=str.match(/(RR|GG|BB|YY)/g); print(tmp.length);

编辑于 2017-07-26 10:51:55 回复(0)

dqrzgrzdy

正则表达式Pattern p=Pattern.compile("(.)\\1+") 匹配相邻字符个数大于1的子串

将匹配的子串全放入List容器中，遍历容器，找到串长度最大值即可。。。

发表于 2017-07-27 14:36:00 回复(0)

笑忘书生


	#include <iostream>



	#include <string>



	using namespace std;



	 



	intmain()



	{



	    string str;



	    cin >> str;



	    intcount = 0;



	    for(inti = 1; i < str.size(); ++i)



	    {



	        if(str[i] == str[i - 1]) {



	            count++;



	            ++i;



	        }



	    }



	    cout << count << endl;



	}

发表于 2017-07-26 08:41:22 回复(0)

徐老大

只要相邻两块不相同即可

importjava.util.*;

publicclassMain{

publicstaticvoidmain(String[] args){

Scanner scanner = newScanner(System.in);

String s = scanner.next();

intcount = 0;

intleft = 0,right = 1;

while(left < right && right < s.length()){

if(s.charAt(left) == s.charAt(right)){

count += 1;

left = right;

right = right + 1;

}

left++;

right++;

}

System.out.println(count);

}

发表于 2021-09-19 21:22:28 回复(0)

佛约不可说

fscanf(STDIN, "%s", $a);

$color= array('R','G','B','Y');

$n= 0;

for($i= 0, $j= strlen($a) - 1; $i< $j; $i++){

$i_1= $i+ 1;

$i_2= $i+ 2;

if($a[$i] == $a[$i_1]){

if($i< $j- 1){

$tempColor= array();

$tempColor[] = $a[$i];

$tempColor[] = $a[$i_2];

$yuColor= array_diff($color, $tempColor);

$a[$i_1] = array_pop($yuColor);

$n= $n+ 1;

}else{

$tempColor= array();

$tempColor[] = $a[$i];

$yuColor= array_diff($color, $tempColor);

$a[$i_1] = array_pop($yuColor);

$n= $n+ 1;

}

    echo$n;

发表于 2018-08-27 11:28:33 回复(0)

牛客7255048号

发表于 2018-04-15 17:19:41 回复(0)

张政zzzz

受dp启发，将序列看成三个一组的情况从头到尾遍历。每一组中有三种情况，使得这三个出现两个相邻有三种情况：（1）三个一样，（2）第一个第二个相同，与第三个不同，（3）第二个和第三个相同，与第一个不一样。对于（1）只需将第二个改成不同颜色即可，（2）将第一个改成其他颜色即可，（3）这种情况之前没有到最后一个组合，可以先不管，因为如果下一组可能会出现（1）的情况。这样从头到尾遍历一遍就有了答案

发表于 2018-04-10 00:19:18 回复(0)

Sunward

  importjava.util.Scanner; 
  publicclassMain{ 
        
      public static int minSwap(String str){ 
          int length = str.length(); 
          int count = 0; 
          for(int i=0;i+1<length;){ 
              if(str.charAt(i)==str.charAt(i+1)){ 
                  i = i+2; 
                  count++; 
              }else{ 
                  i++; 
              } 
          } 
          return count; 
      } 
      public static void main(String[] args){ 
          Scanner scanner = newScanner(System.in); 
          String str = scanner.nextLine(); 
          System.out.println(minSwap(str)); 
      } 
  } 