首页 > 试题广场 >

丑陋的字符串

[编程题]丑陋的字符串

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

牛牛喜欢字符串,但是他讨厌丑陋的字符串。对于牛牛来说,一个字符串的丑陋值是字符串中相同连续字符对的个数。比如字符串“ABABAABBB”的丑陋值是3,因为有一对"AA"和两对重叠的"BB"。现在给出一个字符串,字符串中包含字符'A'、'B'和'?'。牛牛现在可以把字符串中的问号改为'A'或者'B'。牛牛现在想让字符串的丑陋值最小,希望你能帮帮他。

输入描述:

输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 50),字符串只包含'A','B','?'三种字符。

输出描述:

输出一个整数,表示最小的丑陋值

示例1

输入

A?A

输出

算法知识视频讲解

OSIRISSABER

#include <iostream>
#include <string>
 
using namespace std;
 
int main(){
    string s;
    cin>>s;
    int len=s.size(),res=0;
    int i=0;
    //去除前导的'?'
    while(s[i]=='?') ++i;
    //从去除前导的下一个位置开始计算
    ++i;
    for(;i<len;++i){
        if(s[i]=='?'){
            //若为'?',则根据前一个字母设置'?'为不同的一个字母
            if(s[i-1]=='A') s[i]='B';
            else s[i]='A';
        }else{
            //若不为'?'，且与前一个字母相同，++res
            if(s[i-1]==s[i])
                ++res;
        }
    }  
    cout<<res;
}

发表于 2017-06-19 13:10:55 回复(4)

元气の悟空

#include<stdio.h>
int main(){
    char s[100];
    scanf("%s",s);
    int i,res=0;
    while(s[i]=='?') i++;
    for(;s[i]!='\0';i++){
        if(s[i]=='?') s[i-1]=='A'?s[i]='B':s[i]='A';
        if(s[i]==s[i-1]) res++;
    }
    printf("%d\n",res);
}

发表于 2017-11-11 00:15:29 回复(0)

为啥要起名字

try:
while True:
s=raw_input().strip()
if len(s)<=1:
print(0)
if s.count('?')==len(s):
print(0)
slist=list(s)
k,res=0,0
while slist[k]=='?':
k+=1
del slist[:k]
for i in range(1,len(slist)):
if slist[i]=='?':
if slist[i-1]=='A':
slist[i]='B'
else:
slist[i]='A'
else:
if slist[i]==slist[i-1]:
res+=1
print(res)
except:
pass

发表于 2018-05-24 10:15:50 回复(0)

酱油队长

/*
   提供一种解法：找到？符号组成的连续区间，根据区间长度奇偶行和两边的字符是否相等，判断是否会出现重复；
   
   四种情况：
   （1）区间长度为奇数且两端字符相等：A __ __ __ A  0
   （2）区间长度为奇数且两段字符不等：A __ __ __ B  1
   （3）区间长度为偶数且两端字符相等：A __ __ __ __ A 1
   （4）区间长度为偶数且两端字符不等：A __ __ __ __ B 0
   
   注：__表示？所在位置，0/1表示在问号？处添加字符是否会增加重复度
   
   不要忘了原字符串种AA\BB的固有重复度，参考代码如下：
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<climits>
#include<sstream>
#define eps 1e-9
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define inf -INF
using namespace std;

typedef long long LL;

const int maxn = 1e6 + 10;

struct node{
  int l,r;
}q[100];

string s;

int main(){
    while(cin>>s){
       int cnt = 0;
       for(int i = 0;i < s.size();++ i){//找到？所在区间
          if(s[i] == '?'){
            q[cnt].l = i;
            while(s[i+1] == '?'&& (i+1 < s.size())) i++;
            q[cnt++].r = i;
          }
       }
       int ans = 0;
       for(int i = 0;i < s.size() - 1;++ i){//固有重复度
        if(s[i] == 'A'&&s[i+1] == 'A') ++ans;
        if(s[i] == 'B'&&s[i+1] == 'B') ++ans;
       }
       for(int i = 0;i < cnt;++ i){//？处添加字符可能会增加的重复度
         if((q[i].l == 0)||(q[i].r == s.size()-1)) continue;//两端默认不会重复
         int len = q[i].r - q[i].l + 1;
         if(s[q[i].l-1] == s[q[i].r+1] && (len%2 == 0)) ans++;
         if(s[q[i].l-1] != s[q[i].r+1] && (len&1)) ans++;
       }
       printf("%d\n",ans);
    }
    return 0;
}

发表于 2017-08-22 18:50:18 回复(0)

奶茶的茬丶

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] chars;
        while (sc.hasNext()) {
            String s = sc.next();
            int count = 0;

            if (s.length() == 1) {
                System.out.print(0 + "");
                return;
            } else {
                //去除最前面的所有？
                int j = 0;
                while (j != s.length() && s.charAt(j) == '?') {
                    j++;
                }
                if (j == s.length()) {
                    System.out.print(0 + "");
                } else {
                    s = s.substring(j, s.length());

                    chars = s.toCharArray();
                    for (int i = 1; i < chars.length; i++) {
                        if ('?' == chars[i]) {
                            if (chars[i - 1] == 'A') {
                                chars[i] = 'B';
                            } else {
                                chars[i] = 'A';
                            }
                        } else {
                            if (chars[i - 1] == chars[i]) {
                                count++;
                            }
                        }
                    }
                    System.out.print(count + "");
                }
            }
        }
    }
}

发表于 2017-07-03 17:18:41 回复(0)

C/C++

梦向南

//发现一个简单的算法，供大家参考

#include<string>

#include<iostream>

using namespace std;

int main()

{

string str;

while(cin>>str)

{

int tep, cont=0;

int start=str.find_first_not_of('?');

int found=str.find_first_not_of('?', start+1);

while(found!=string::npos)

{

tep=found-start+str[found]-str[start];

if(tep%2) cont++;

start=found;

found=str.find_first_not_of('?', start+1);

}

cout<<cont<<endl;

}

return 0;

}

发表于 2017-06-28 17:21:42 回复(0)

C/C++

牛客123zxc

#include <iostream>

#include <string>

using namespace std ;

int main( int argc, const char * argv[]) {

string str;

int length;

int n = 0;

cin >>str;

length = ( int )str. length ();

if (length < 3 || length > 50){

cout <<0<< endl ;

return 0;

}

for ( int i=0; i<length; i++) {

if (str[ i ] == '?') {

if (i == 0){

if (str[ i +1]=='A') {

str[ i ] = 'B';

} else if (str[ i +1]=='B'){

str[ i ] = 'A';

} else {

i++;

}

} else if (i == length - 1){

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

str[ i ] = 'B';

} else if (str[ i -1]=='B'){

str[ i ] = 'A';

}

} else {

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

str[ i ] = 'B';

} else if (str[ i -1]=='B'){

str[ i ] = 'A';

}

for ( int i=0; i<length-1; i++) {

if ((str[ i ] == str[ i +1]) && (str[ i ] != '?')) {

n++;

}

cout <<n<< endl ;

return 0;

}

编辑于 2017-06-17 15:53:58 回复(0)

Lama

public static int count(String str){
        //字符串数组化，方便进行更改
        char []chars=str.toCharArray();
        //ret 用来记录丑数对数，i 表示下标
        int ret=0;
        int i=0;
        //从第一个不是？的地方开始
        while(chars[i]=='?'){
            i++;
                //如果全是？ 返回0
            if(i==chars.length){
                return 0;
            }
        }
        //如果没有以？开始的的话，就要从1下标开始遍历
        if(i==0){
            i++;
        }
        //遇到？就根据他的前一个位置的字符，替换成不同的字符
        //不是？就和它的前一个位置字符进行比较，判断是否是和前一个位置的字符构成丑数
        for(;i<chars.length;i++){
            if(chars[i]=='?'){
                chars[i]= chars[i-1]=='A'? 'B':'A';
            }else{
                if(chars[i]==chars[i-1]){
                    ret++;
                }
            }
        }
        return ret;
    }

编辑于 2021-09-29 08:32:32 回复(0)

明月知何人

一直卡在第一个字符是'?'要如何处理，实在是太菜了

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

int main() {
    string s;
    cin >> s;
    int i = 0;
    while(s[i] == '?')
       i++;
    int cnt = 0;
    for( i++; i < s.length(); ++i) {
       if(s[i] == '?') {
           if(s[i-1] == 'A')
               s[i] = 'B';
           else
               s[i] = 'A';
       }
       if(s[i] == s[i-1])
           cnt++;
    }
    cout << cnt << endl;
    return 0;
}

发表于 2020-03-19 21:08:23 回复(0)

保佑offer快快来

import sys
try:
    s = sys.stdin.readline().strip('?')
    if not s:
        print(0)
    else:
        s = list(s)
        count = 0
        for i in range(1,len(s)):
            if s[i]=='?':
                if s[i-1] =='A':
                    s[i] = 'B'
                else:
                    s[i] = 'A'
            else:
                if s[i] ==s[i-1]:
                    count += 1
        print(count)
except:
    pass

发表于 2019-07-22 17:32:50 回复(0)

Python

锵域

# 注意有个测试用例是“??”

import sys

strValue = list(sys.stdin.readline().strip())
leftPoint, strLen = 0,len(strValue)
count = 0
while leftPoint < strLen and strValue[leftPoint]=="?":
leftPoint += 1
leftPoint += 1
while leftPoint<strLen:
if strValue[leftPoint] == "?":
strValue[leftPoint] = "B" if strValue[leftPoint-1] == "A" else "A"
else:
if strValue[leftPoint] == strValue[leftPoint-1]:
count += 1
leftPoint +=1
print(count)

发表于 2019-07-18 16:16:41 回复(0)

一直加油鸭

1.去掉所有的前缀'?'和后缀'?'
2.把所有'?'替换成和前一个字符不相同的字符，同时统计有多少个相邻字符

import java.util.*;
public class Main{      public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        in.close();
        StringBuilder sb = new StringBuilder(str);
        int uglyNum = 0;
        while(sb.length()!=0 && sb.charAt(0)=='?'){
            sb.deleteCharAt(0);
        }
        while(sb.length()!=0 && sb.charAt(sb.length()-1)=='?'){
            sb.deleteCharAt(sb.length()-1);
        }
        for(int i=0; i<sb.length(); i++){
            if(sb.charAt(i)=='?'){
                if(sb.charAt(i-1) == 'A'){
                    sb.setCharAt(i, 'B');
                }
                if(sb.charAt(i-1) == 'B'){
                    sb.setCharAt(i, 'A');
                }
            }
            if(i==0) continue;
            if(sb.charAt(i)==sb.charAt(i-1)){
                uglyNum++;
            }
        }
        System.out.println(uglyNum);
    }
}

编辑于 2018-03-28 09:49:30 回复(0)

南邮kd

import java.util.*;
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			String s=sc.nextLine();
			char array[]=s.toCharArray();
			int count=0;
			for(int i=1;i<array.length-1;i++){
				if(array[i]=='?'){
					if(array[i-1]=='?'){
						array[i]=(array[i+1]=='B')?'A':'B';
					}
					else{
						array[i]=(array[i-1]=='B')?'A':'B';	
					}
				}
			}
			for(int j=0;j<array.length-1;j++){
			if((array[j]==array[j+1])&&array[j+1]!='?'){
					count++;
				}
			}
			System.out.println(count);
		}
		sc.close();
	}

}

编辑于 2017-08-18 15:27:47 回复(1)

小柒木有熙


	//思路：1）如果，字符串最开始是连续的“？”号，则可以肯定不会存在丑陋值



	//      2）否则，如果当前值是“？”号，则设置当前值为与前一个值不同的另一个值；如果当前值与前一个值相同，记录这两个值为丑陋值 



	importjava.util.Scanner;



	



	publicclassMain {



	    publicstaticvoidmain(String[] args) {



	        Scanner scanner = newScanner(System.in);



	        String str = scanner.next();



	        char[] arr = str.toCharArray();



	        intk = 0;  //连续相同的?字符数



	        for(inti = 0; i < arr.length; i++) {



	            if(i == 0)



	                while(i < arr.length && arr[i] == '?')



	                    i++;



	            else



	                if(arr[i] == '?') {



	                    change(arr, i); //和前一个不同



	                }



	                else if(arr[i-1] == arr[i]) {



	                    k++;



	                }



	        }



	        System.out.println(k);



	    }



	    publicstaticvoidchange(char[] arr, inti) {



	        if(arr[i-1] == 'A')



	            arr[i] = 'B';



	        else



	            arr[i] = 'A';



	    }



	}

编辑于 2017-08-08 20:55:28 回复(0)

Asdil

#如果s长度为1，返回0
#如果s全为？，返回0
#上述条件不满足，则找到一个不为？的字母i，
#以i为中心向左走一遍，当下标为j的字母？，则将j变成j+1相反的字母
# 同理向右走一边，当下标为j的字母？，则将j变成j-1相反的字母
def search(s, lenth):
    ret = -1
    for i in range(lenth):
        if s[i] != '?':
            ret = i
            break
    return ret
def f(s):
    lenth = len(s)
    if lenth == 1:
        return 0
    index = search(s, lenth)
    if index == -1:
        return 0
    i = index-1
    while i > -1:
        if s[i] == '?':
            if s[i+1] == 'A':
                s[i] = 'B'
            else:
                s[i] = 'A'
        i -= 1
    i = index + 1
    while i < lenth:
        if s[i] == '?':
            if s[i-1] == 'A':
                s[i] = 'B'
            else:
                s[i] = 'A'
        i += 1
    ret = 0
    for i in range(lenth-1):
        if s[i+1] == s[i]:
            ret += 1
    return ret
if __name__ == '__main__':
    while 1:
        try:
            s = list(raw_input())
        except:
            break
        print f(s)

发表于 2017-07-13 14:40:20 回复(0)

苟有

  intmain(){ 

      string str; 

      getline(cin,str); 

      if(str.length()==1){ cout<<0<<endl; return0;} 

      inti=0,res=0; 

      while(i<str.length() && str[i]=='?') i++; 

      i++; 

      for(;i<str.length();i++){ 

          if(str[i]=='?') str[i] = str[i-1]=='A'?'B':'A'; 

          if(str[i]==str[i-1]) res++; 

      } 

      cout<<res<<endl; 

      return0; 

  }

发表于 2017-07-02 22:06:54 回复(0)

dragonCoding

<?php

$s = trim(fgets(STDIN));

$len = strlen($s);

$num = 0;

$state = 0;

if("^[A?B]{1-50}+$"){

$arr = str_split($s);

for($i=1;$i<$len;$i++){

if($arr[$i]=='?'){

if($arr[$i-1]=='A'){

$arr[$i]='B';

}elseif($arr[$i-1]=='B'){

$arr[$i]='A';

}else{

$state++;

}

for($j=0;$j<$len-1;$j++){

//echo $arr[$j]."\n";

if($arr[$j]==$arr[$j+1]){

$num++;

}

$num = $num-$state;

echo $num;

// return $A;

}else{

$n = trim(fgets(STDIN));

}

发表于 2017-06-23 10:40:35 回复(0)

偶尔刷刷题~

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		while(in.hasNext())
		{
			String str = in.next();
			String str1 = str;
			int l = str.length();
			int count = 0;
			boolean flag = false;
			for (int i = 0; i<l-1; i++)
			{	
				if (!flag && str.charAt(i) == '?')
				{
					str = str.replaceFirst("[?]", "C");
					continue;
				}
				else if (str.charAt(i) == 'A')
				{
					if (str.charAt(i+1) == 'A')
					{
						count = count +1;
					}
					else if (str.charAt(i+1) == 'B')
					{
						continue;
					}
					else if (str.charAt(i+1) == '?')
					{
						str = str.replaceFirst("[?]", "B");					
					}
				}
				else if (str.charAt(i) == 'B')
				{
					flag = true;
					if (str.charAt(i+1) == 'B')
					{
						count = count +1;
					}
					else if (str.charAt(i+1) == 'A')
					{
						continue;
					}
					else if (str.charAt(i+1) == '?')
					{
						str = str.replaceFirst("[?]", "A");
					}
				}
					 
			}
			System.out.println(count);
		}		
	}
}

发表于 2017-06-19 21:31:11 回复(0)

Jimmy_gg

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;
    string str;
    while (cin >> str) {
        int ans = 0;
        int len = str.size();
        int mid = len;
        for (int i = 0; i < len; i++) {
            if (str[i] != '?') {
                mid = i;
                break;
            }
        }
        if (mid == len) {
            ans = 0;
        }
        else {
            for (int i = mid + 1; i < len; i++) {
                if (str[i] != '?' && str[i] == str[i - 1]) {
                    ans++;
                }
                else if (str[i] == '?') {
                    str[i] = str[i - 1] == 'A' ? 'B' : 'A';
                }
            }
            for (int i = mid - 1; i >= 0; i--) {
                if (str[i] != '?' && str[i] == str[i + 1]) {
                    ans++;
                }
                else if (str[i] == '?') {
                    str[i] = str[i + 1] == 'A' ? 'B' : 'A';
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

发表于 2017-06-19 16:23:05 回复(0)

川大鲜于

# coding = utf-8 import sys def main(): #str = "ABABAABBB"  #str = "A??B???AAB?A???A"  str = raw_input()  arr = list(str); for i in range(1,len(arr)): if arr[i] == "?": #如果当前为？  if arr[i-1] == "A": #前一个为“A”就将“？”变为“B”  arr[i] = "B"  elif arr[i-1] == "B": #前一个为“B”就将“？”变为“A”  arr[i] = "A"    length = len(arr)   count = 0  for i in range(0,length-1): #统计连续相同的字符的个数  if arr[i] == arr[i+1] and arr[i]!="?":
            count = count + 1  print count if __name__ == "__main__": #main()  while 1: try:
            main()  except: break