首页 > 试题广场 >

【2021】360编程题ab串

[编程题]【2021】360编程题ab串
  • 热度指数：1269 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

小明得到一个只包含a,b两个字符的字符串，但是小明不希望在这个字符串里a出现在b左边。现在他可以将”ab”这样的子串替换成”bba”，在原串中的相对位置不变。输出小明最少需要操作多少次才能让一个给定字符串所有a都在b的右边。


输入描述:
一个只包含a,b字符的字符串，长度不超过100000。


输出描述:
最小的操作次数。结果对1000000007取模。
示例1

输入

ab

输出

1

说明

ab到bba
示例2

输入

aab

输出

3

说明

aab到abba到bbaba到bbbbaa
算法知识视频讲解
添加回答
zerone.头像 zerone.
找了好久都没有python的，那就自己造个轮子吧 
li = str(input())
tmp = 0
res = 0
mod = 1000000007
for i in range(len(li)-1, -1, -1):
    if li[i] == 'b':
        tmp += 1
    if li[i] == 'a':
        res = res + tmp
        tmp = tmp * 2
print(res%mod)

发表于 2021-07-29 23:33:39 回复(0)
寒冰-侠客头像 寒冰-侠客
由后向前扫描字符串，碰到a就要做交换，但每次交换都会新增一个b。因此a会把其后所有b变为原来的2倍。 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    long long bnum=0,ans=0,mod=1000000007;
    string s;
    cin>>s;
    for(i=s.size()-1;i>=0;i--)
    {
        if(s[i]=='b')
            bnum++;
        else if(s[i]=='a')
        {
            ans=(ans+bnum)%mod;
            bnum=bnum*2%mod;
        }
    }
    cout<<ans;
    return 0;
}


发表于 2021-06-29 22:26:29 回复(0)
pein531头像 pein531
从后往前遍历字符串，遍历的过程中我们记录一下当前位置及其右边所有字符中b的个数：
（1）遇到b字符其计数就自增1；
（2）遇到a字符就进行一次逻辑上的“替换”操作。
遇到a的时候相当于遇到了一次ab子串，这时候将其“替换”为bba就会使得b字符增加一个。因此，替换操作的次数只与b字符的数量相关，替换一次，就增加一个b，所以操作数每次加上b的个数即可。而此时将a移动到了右边去，可能右边还会存在ab子串，因此右边还需要继续进行替换操作。
在向右替换的过程中，这个a字符需要不断地通过替换操作向右传递，直到自己的右边已经全部是a，这时候它已经经过了之前右边所有的b字符，而每经过一次b字符，就因为替换操作使得b字符增加一个，因此当它无法再往右边移动时，总共使得右边b字符的数量翻了一番。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static final int MOD = 1000000007;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().trim().toCharArray();
        int countB = 0;
        int res = 0;
        for(int i = str.length - 1; i >= 0; i--){
            if(str[i] == 'b'){
                countB ++;
            }else{
                // 此时需要替换
                res = (res + countB) % MOD;
                countB = countB * 2 % MOD;
            }
        }
        System.out.println(res);
    }
}

编辑于 2021-08-23 11:10:35 回复(0)
旧岸头像 旧岸
无需添加数组这些操作，只需将字符中的ab替换成bba，迭代替换的操作，直至没有ab的字符串。然后看迭代后的字符数量和原本的字符数量差，就可以知晓替换了多少次，代码贴一下：
publicclassMain {
 
    public static void main(String[] args) {
        String aa = "aaaaabaabababaaaaaba";
        int vvvvvv = aaaaaa(aa);
        System.out.println(vvvvvv);
    }
 
    private static int aaaaaa(String aa) {
        String vvvvvv = vvvvvv(aa);
        return vvvvvv.length() - aa.length();
    }
 
    private static String vvvvvv(String str) {
        String replace = str.replace("ab", "bba");
        if(replace.equals(str)){
            returnreplace;
        }
        return vvvvvv(replace);
    }
 
}

发表于 2021-05-25 23:37:17 回复(1)
牛客257319613号头像 牛客257319613号 
Max = 1000000007
s = input()
nb = 0
res = 0
for i in range(len(s)-1, -1, -1):
    if s[i] == 'a':
        res += nb
        nb *= 2
    else:
        nb += 1
print(res%Max)
累加b的数量即可
发表于 2021-10-19 21:41:22 回复(0)
可爱抱抱呀😥头像 可爱抱抱呀😥 
import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]) throws IOException{
        Read sc=new Read();
        //int n=sc.nextInt();
        String s=sc.next();
        List<Integer> list=new ArrayList<>();
        long ans=0;
        long sum=0;
        for(int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)=='b'){
                sum++;
            }
            else{
                ans=(ans+sum)%mod;
                sum=(sum*2)%mod;
            }
        }
        sc.print(ans);
        sc.bw.flush();
        sc.bw.close();
    }
}
//记住看数字范围，需要开long吗，需要用BigInteger吗，需要手动处理字符串吗，复杂度数量级控制在1e7或者以下了吗
//开数组的数据范围最高不能超过1e7，数据范围再大就要用哈希表离散化了
//基本数据类型不能自定义sort排序，二维数组就可以了，顺序排序的时候是小减大，注意返回值应该是int
class Read{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public Read(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        // 确定下一个@可爱抱抱 只有一个字符的时候再用
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public byte nextByte() throws IOException{
        return Byte.parseByte(next());
    }
    public short nextShort() throws IOException{
        return Short.parseShort(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public void println(int a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
    public void print(int a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(String a) throws IOException{
        bw.write(a);
        bw.newLine();
        return;
    }
    public void print(String a) throws IOException{
        bw.write(a);
        return;
    }
    public void println(long a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
    public void print(long a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(double a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
    public void print(double a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void print(BigInteger a) throws IOException{
        bw.write(a.toString());
        return;
    }
    public void print(char a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(char a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
}

发表于 2022-10-05 15:37:27 回复(0)
zymcc头像 zymcc 
        string s;
    cin>>s;
    
    
    long tim=0,tim0=tim;
    for(int i=s.size()-1;i>-1;i--){
        if(s[i]=='b'){
            tim0++;
        }
        else{
            tim+=tim0;
            tim0*=2;
        }
    }
    tim=tim%1000000007;
    cout<<tim<<endl;
设初始值tim0=0，从字符串末尾开始，逢b则tim0+1，逢a则tim0为当前a需要变换的次数，加到总和tim上并把tim*2
问题是为啥只能通过4个用例。
发表于 2021-10-18 11:32:36 回复(0)
笔寞头像 笔寞 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//f[i][j] 表示从 i - j 这一段变成回文串的最小代价
/*
    转移方程举例子：

f[i][j] = Math.min(f[i][j], f[i][j - 1] + Math.min(  inc[ c[j] - '0' ] , dec[ c[j] - '0' ] ));

为可以这样 我们是枚举len长度下的最下代价，也已知了 j = i + len - 1也就是i-j长度就是len的 这部分使我们要去求的

但是f[i][j - 1]的最小代价我们是上一步 len - 1长度枚举的时候就已经求了 f[i + 1][j - 1]是len - 2的长度，当然我们更早求了



因此有 c[i] == c[j] 时候 我们f[i + 1][j - 1]早就算出了， 那么必然有f[i][j] = f[i + 1][j - 1]这样才最小

但是当c[i] != c[j]  举例子 xxxxx1 反正其他的不管这个5个x = xxxxx我们早就知道了最小代价。那么多了一个1

直接删除变成xxxxxx  或者在添加一个1 -> 1xxxxxx1 也就是：

f[i][j] = Math.min(f[i][j], f[i][j - 1] + Math.min(  inc[ c[j] - '0' ] , dec[ c[j] - '0' ] ));



*/
public class Main  {
     static String t = "";
     static int N = 110, INF = (int)10e9;
     static int[][] f = new int[N][N];
     static int[] inc = new int[]{-1, 100,200,360,220};
     static int[] dec = new int[]{-1, 120,350,200,320};
     public static void main(String[] args) throws IOException {
          BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
          t = bf.readLine();
          char[] c = t.toCharArray();
          for(int i = 0; i < c.length; i ++) {
               Arrays.fill(f[i], INF);
               f[i][i] = 0;
          }
          for(int len = 2; len <= c.length; len ++)  //枚举区间长度
               for(int i = 0; i + len - 1 < c.length; i ++){  //枚举左边端点
                     int j = i + len - 1;  //右边端点
                     if(c[i] == c[j] ){
                          f[i][j] = len == 2 ? 0 : f[i + 1][j - 1];
                     }else if(c[i] != c[j]){
                        
                          f[i][j] = Math.min(f[i][j], f[i][j - 1] + Math.min(  inc[ c[j] - '0' ] , dec[ c[j] - '0' ] ));
                          f[i][j] = Math.min(f[i][j], f[i + 1][j] + Math.min(  inc[ c[i] - '0' ] , dec[ c[i] - '0' ] ));
                     }
               }
          System.out.println(f[0][c.length - 1]);
     }
}

发表于 2021-07-04 18:05:55 回复(0)
30curry30头像 30curry30
首先最后的结果一定是 所有的 b 都在 a 的前面，看一个例子：aaab, 可以分解成 aa(ab)
对于(ab) 需要交换一次生成 bba，每一次交换会导致 b 变成两倍
所以 对于 a(a)bba中的 a 需要交换2次，同理，第一个a则需要 1 * 2 * 2 = 4次。
易得到规律，对于 aaa.....a b变成所有的a在b后面需要 1 + 2 + 4 + 。。。+2^(n - 1)次交换。 
把整个问题拆解成 aa。。。ab子问题，此时则变成了等比求和问题，只需要统计在遇到b之前的a的个数就可以了。
手写快速幂是为了保证结果不溢出，特别注意的是，前缀的 b 不需要再管。 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;


ll quick_power(ll a, ll n, int mod=1000000007){
	if(n == 0){
		return 1;
	}

	if(n == 1){
		return a;
	}

	ll temp = a * a % mod;
	if(n % 2 == 1){
		return a * quick_power(temp, (n - 1) / 2) % mod;
	}
	else{
		return quick_power(temp, n / 2) % mod;
	}
}

int main(){
	ll res = 0;
	int index = 0, a_count = 0, mod = 1000000007;
	string s;

	cin >> s;

	while(s[index] == 'b'){
		index ++;
	}

	while(index < s.size()){
		while(index < s.size() && s[index] == 'a'){
			a_count ++;
			index ++;
		}

		if(index == s.size()){
			break;
		}

		// cout << index << " " << a_count << endl;
		ll temp = quick_power(2, a_count) - 1;
		// cout << temp << endl;
		res = (res + temp) % mod;

		index ++;
	}

	cout << res << endl;

	return 0;
}


发表于 2021-06-29 20:41:04 回复(0)
一颗苹果OAOA头像 一颗苹果OAOA
可以理解为这是一道智力题，我师姐还是强的。思路是这样的，对于给定字符串 s ，倒叙遍历字符串，若遇到 "b" 则 ans++，相当于把一个 "b" 放在 "a" 前面需要移动一次，并且一个 "b" 会变成两个 "b" ；若遇到 "a"，则此时该 "a" 后面包含了 2 倍的移动过的 "b" 的次数（因为是把"ab"替换为“bba”，如果替换为是 "bbba"，那就是 3 倍 ），所以遇到 "a" 时就应该把之前移动过的 "b" 的次数加到 结果 res 中，并且将移动过的 "b" 的次数乘 2，表示该 "a" 之后的 "b" 还需要移动这么多次才能到这个 "a" 前面去，代码如下： 
#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s("aab");
    int res=0, tmp =0;
    int len = s.size();
    for (int i = len - 1; i >= 0; i--){
        if (s[i] == 'b') {
            tmp++;
        }
        else if(s[i] == 'a'){
            res = res + tmp;
            tmp = tmp * 2;
            }
    }
    cout << res << endl;
    return res;
}

发表于 2021-06-29 11:20:40 回复(0)
牛客12312341头像 牛客12312341
没有人写题解，那本程序媛写一下吧。

”ab”子串替换成”bba”。 
感性得理解一下，将a移动到后面去，a每移动一位就相当在其前面增加个b。
我们可以证明：无论那个a先开始移动，最终的移动次数都是一样的。

假设我们要将第k-1,k,k+1个a移动在一起，其中第k个a与第k-1一个a中间有M个a，第k个a与第k+1一个a中间有N个a，
当将第k移动到第k+1旁边时在原来的位置上增加N个数量，已经移动了N次，那么现在第k-1个与第k个a有M+2*N个数量，再将将第k-1移动到第k旁边时是移动次数为N+(M+2*N)=M+3*N

同理先移动第k-1个a 再移动第k个a,将他们聚在一起的移动次数为M+3*N发现是一样的，即证明了我们的结论。

我们在考虑时空复杂度的同时也要考虑代码的复杂度呀！
我们干脆从后面开始枚举a的位置，当a面对b的个数移动到最右边时，b的数量会多一倍，我们只需遇到a记录一下b个数对于答案的贡献就可以啦！！！ 

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
 
const int N=1e5+100;
const int mod=1e9+7;
char ss[N];
 
int main(){
    ios::sync_with_stdio(false);
    cin>>ss+1;
    int n=strlen(ss+1);
    ll cnt=0;//累积b个数
    ll ans=0;//答案
    for(int i=n;i;i--){
        if(ss[i]=='b') cnt++;
        else{
            ans=(ans+cnt)%mod;
            cnt=cnt*2%mod;//当a移动过去了，其后面的b会多一倍
        }
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2021-05-11 01:46:21 回复(1)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 360集团 数据分析师 Java工程师
上传者：小小
难度：
11条回答 5281浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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