首页 > 试题广场 >

丑陋的字符串

[编程题]丑陋的字符串
  • 热度指数：2185 时间限制：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

输出

0
算法知识视频讲解
添加回答
OSIRISSABER头像 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头像 牛客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头像 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快快来头像 保佑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头像 南邮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头像 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头像 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头像 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
发表于 2017-06-17 18:00:54 回复(0)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 字符串 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 c#工程师 数据库工程师 信息技术岗 区块链 测试开发工程师 2019 2020 大数据开发工程师 数据分析师 Java工程师 牛客
来自：【2017】牛客模考（...
难度：
23条回答 5912浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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