首页 > 试题广场 >

字符串替换

[编程题]字符串替换
  • 热度指数：3155 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解

给定一个仅由小写字母x和y组成且长度不超过105的字符串，每次可以将字符串中的一个子串xy替换成字符串yyx，那么至少要替换多少次才能让字符串中不存在子串xy？


输入描述:
输入给定的字符串。


输出描述:
输出最少替换次数对109+7取模后的结果。
示例1

输入

xxy

输出

3
算法知识视频讲解
添加回答
白色纯度头像 白色纯度
1.将“xy”变为“yyx”，本质就是将“x”向后移动，只有‘y’在增加，‘x’的数目从没变过。
2. 每次遇到一个“y”,统计一下这个“y”前面的“x”的数目num，移动次数就是2^(num)-1.
这里感谢大佬的思路 @写意自风流 ，幂次运算会超时，所以2^(num)-1可以优化为代码中的
X = (2*X+1) % (10 ** 9 + 7) 
def solution(string):
    num = 0
    count = 0
    if string[0] == 'x':
        count = 1
    X = count
    for i in range(1, len(string)):
        if string[i] == 'x':
            X = (2*X+1) % (10 ** 9 + 7)
        else:
            num = (num + X) % (10 ** 9 + 7)
    return int(num % (10 ** 9 + 7))
if __name__ == '__main__':
    string = raw_input().strip()
    print(solution(string))
发表于 2019-08-19 20:07:42 回复(4)
恶灵退散~头像 恶灵退散~ 
"""
思路：
- 题目本质是将x移动到y的后面需要多少次
- 从后往前统计y的数量
- 假设第一次检测到x时，有2个y在后面，x移动需要两次
- 该x移动后y的个数会成倍增长变成2y，所以要将当前y的个数更新为2*y
- 依次统计最后得到需要移动的次数，即y的总数
"""
import sys
strs = input().strip()

lens = len(strs)
count = 0
res = 0
for i in range(lens-1, -1, -1):
    if strs[i] == 'y':
        count += 1
    if strs[i] == 'x':
        res += count
        count = count*2
print(res % (10**9+7))

编辑于 2019-10-04 21:42:57 回复(0)
祝福大家(●◡●)ﾉ❤头像 祝福大家(●◡●)ﾉ❤ 
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
using namespace std;
const long long mod = pow(10,9) + 7;
int main() {
	string str;
	cin >> str;
	long long pow_2_x = 0;
	long long res = 0;
	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] == 'x')
			pow_2_x = ((pow_2_x << 1) +1) % mod;
		else {
			res = (res + pow_2_x) % mod;
		}
	}
	cout << res << endl;
	//system("pause");
	return 0;
}

发表于 2019-08-29 15:44:21 回复(0)
Python
LitterF头像 LitterF
暴力模拟法从后往前算一下就行了，秒A的题
从后往前数，是x就挪到y的后面，然后挪的时候xy变成了yyx，y的数量翻了一倍，xyy就变成yyyyx。 
s = input()
cur_y = 0
res = 0
mo = 10**9+7
for i in s[::-1]:
    if i=='y':
        cur_y+=1
    if i=='x':
        res+=cur_y
        cur_y*=2
print(res%mo)


发表于 2019-10-28 23:04:25 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int main(){
    string s;
    cin>>s;
    int t=0, sum=0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='x')
            t = ((t<<1)+1)%MOD;
        else
            sum = (sum+t)%MOD;
    }
    cout<<sum<<endl;
    return 0;
}

发表于 2019-10-31 00:55:00 回复(1)
是哥哥啊头像 是哥哥啊 
import sys

instr = sys.stdin.readline().strip()

mode = 10**9 + 7
instr = instr.lstrip('y')
instr = instr.rstrip('x')
instr = instr.split('y')[:-1]

count = 1
for x in instr[::-1]:
    count = 2 ** len(x) * count + 1
count = (count - 1 - len(instr)) % mode
print(count)

发表于 2020-06-05 00:01:15 回复(0)
yingmiling头像 yingmiling 
//思路参考的别的大佬的,java版本
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String s=sc.nextLine();
		int len=s.length();
		int count=0,res=0;
		for(int i=len-1;i>=0;i--){
			if(s.charAt(i)=='y'){
				count+=1;
			}
			//要注意数据类型的转换
			if(s.charAt(i)=='x'){
				res=(res+count)%(1000000007);
				count=(count*2)%(1000000007);
			}
		}
		System.out.println(res%(1000000007));	
 	}
}

发表于 2020-06-04 11:11:56 回复(3)
GeerF头像 GeerF
遍历字符串，每次遇到y时，统计y之前的x的数量为p，将x全部移到y之后需要的替换次数为：2^p-1
当x的数量多时，整数溢出，使用快速幂的模运算。 
package main

import (
    "bufio"
    "os"
    "strings"
    "fmt"
)

func main() {
    reader := bufio.NewReader(os.Stdin)
    input, _ := reader.ReadString('\n')
    input = strings.TrimSpace(input)
    
    var xNum, result int64
    xNum, result = 0, 0
    for i := 0; i < len(input); i++ {
        if input[i] == 'x' {
            xNum++
            continue
        }else {
            result += fastPow(2, xNum) - 1
        }
    }
    fmt.Println(result%(1000000007))
}


func fastPow(a, n int64) int64 {
    var result, base int64
    result, base = 1, a % 1000000007
    for n != 0 {
        if n & 1 == 1 {
            result = (base * result) % 1000000007
        }
        base = (base * base) % 1000000007
        n = n >> 1
    }
    return result
} 

发表于 2019-07-13 10:35:41 回复(0)
提交观点

问题信息

C++工程师 动态规划 度小满 字符串 模拟 2019 Java工程师
来自：度小满2019秋招研发岗试卷
上传者：小小
难度：
8条回答 8721浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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