2023年华为OD机考真题：递增字符串

算法刷题2年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：递增字符串
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
定义字符串完全由 ‘A’ 和 ‘B’组成，当然也可以全是’A’或全是’B’。如果字符串从前往后都是以字典序排列的，那么我们称之为严格递增字符串。
给出一个字符串s，允许修改字符串中的任意字符，即可以将任何的’A’修改成’B’，也可以将任何的’B’修改成’A’，求可以使s满足严格递增的最小修改次数。0<s的长度<100000。
输入描述：
输入一个字符串： “AABBA”
输出描述：
输出：1
修改最后一位得到AABBB。
示例1
输入：
AABBA
输出：
1
解题思路（由50 percent pain同学提供）：
遍历字符串
1、当字符为B时，直接统计个数countB。（假设之前的子字符串经过修改已满足要求，当前位置的B不会引起字典序变化）
2、当字符为A时：
1）将之前的B全部转化为A，则变化次数为countB。
2）假设之前的字符串经过变化后已满足条件，变化次数为min，当前位置A改为B，则为min+1
3）求出countB和min+1的最小值，则为变化次数的最小值

代码实现一：

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 递增字符串
 * @Description 定义字符串完全由 'A' 和 'B'组成，当然也可以全是'A'或全是'B'。
 * 如果字符串从前往后都是以字典序排列的，那么我们称之为严格递增字符串。
 * 给出一个字符串s，允许修改字符串中的任意字符，即可以将任何的'A'修改成'B'，也可以将任何的'B'修改成'A'，
 * 求可以使s满足严格递增的最小修改次数。0<s的长度<100000。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String string = sc.nextLine();
        int min = 0;
        int countB = 0;
        for (int i = 0; i < string.length(); i++) {
            if (string.charAt(i) == 'B') {
                //假设之前的子字符串经过修改已满足要求，当前位置的B并不会使字典序变化，只统计B的个数
                countB++;
            }
            if (string.charAt(i) == 'A') {
                //方案1 : 把所有之前的B改为A
                int candidate1 = countB;
                //方案2：假设在当前位置以前的子字符串经过修改已满足要求，把当前位置的A改为B,即动态编程思想
                int candidate2 = min + 1;
                min = Math.min(candidate1, candidate2);
            }
        }
        System.out.println(min);
    }
}

代码实现二：Java代码满分实现

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 递增字符串
 * @Description 定义字符串完全由 'A' 和 'B'组成，当然也可以全是'A'或全是'B'。
 * 如果字符串从前往后都是以字典序排列的，那么我们称之为严格递增字符串。
 * 给出一个字符串s，允许修改字符串中的任意字符，即可以将任何的'A'修改成'B'，也可以将任何的'B'修改成'A'，
 * 求可以使s满足严格递增的最小修改次数。0<s的长度<100000。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        char[] s1 = s.toCharArray();
        int b = 0, a = 0;
        int min = Integer.MAX_VALUE;    //思路：先假设将所有A变成B所需要的次数为b，总计数量b,然后从新遍历
        for (char c : s1) {
            if (c == 'A') {
                b++;
            }
        }
        for (char c : s1) {
            if (c == 'A') {   //遇到A就b--；
                b--;
            } else {       //遇到B就a++;
                a++;
            }
            min = Math.min(min, a + b);   //维护最小的a+b；
        }
        System.out.println(min);
    }
}