【机考】华为OD2022.11.01机考题目思路与代码

题目一

描述

输入一个长度为4的倍数的字符串，字符串中仅包含WASD四个字母。

将这个字符串中的连续子串用同等长度的仅包含WASD的字符串替换，如果替换后整个字符串中WASD四个字母出现的频数相同，那么我们称替换后的字符串是“完美走位”。

求子串的最小长度。

示例

输入：
WASDAASD

输出：
1

说明：
将第二个A替换为W，即可得到完美走位  
1
2
3
4
5
6
7
8

输入：
AAAA

输出：
3

说明：
将其中三个连续的A替换为WSD，即可得到完美走位  
1
2
3
4
5
6
7
8

思路与代码

这题我并没有AC，用例通过率95.45%，确定是效率问题，经过改进后时间复杂度从O(n^{3)降低为O(n}2)。

首先确定一下如何判断一个子串被替换后可以让整个字符串变成“完美走位”。

假设要替换的子串长度为m，子串前长度n1，子串后长度n2，：

在最开始，用HashMap统计整个字符串中WASD的出现频数，得到map

然后用HashMap统计m子串中WASD的出现频数，得到insideMap

用map各个键的值减去insideMap中对应键的值，可得n1+n2中WASD频数映射，写回insideMap

找到insideMap中最大的值，乘四然后减去所有值的和，就是替换m后成为完美走位需要的m的长度needSteps

如果m的长度大于等于needSteps，m经过替换后整个字符串可以成为完美走位。

最简单的方式就是暴力枚举，检查各个m是否符合要求，取最短的m的长度，即可得到答案：

/**
 * 求需要替换的最小连续走位长度
 * 完美走位：WASD四个字母出现次数相同
 * 输入步数为4的倍数
 */
public class P1 {
    private static Scanner scanner=new Scanner(System.in);

    public static void main(String[] args) {
        String str=scanner.nextLine();

        //获取字符串本身的统计信息
        HashMap map=getAmountMap(str);
        //如果已经是完美走位，输出0，不检查
        if(map.get('A')==map.get('S')&&map.get('S')==map.get('W')&&map.get('W')==map.get('D')){
            System.out.println(0);
            return;
        }

        //记录已知的可行最小替换长度
        int minLen=str.length();
        //对每一个字母开头的序列进行检查
        for(int i=0;i insideMap=getAmountMap(str.substring(i,i+j+1));
                //得到源字符串减去字串后其他部分（外串）的统计信息
                insideMap.put('A',map.get('A')-insideMap.get('A'));
                insideMap.put('S',map.get('S')-insideMap.get('S'));
                insideMap.put('W',map.get('W')-insideMap.get('W'));
                insideMap.put('D'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31