当前位置：首页 > article >正文

华为OD机试真题---获得完美走位

article 2024/11/1 6:02:28

华为OD机试真题中的“获得完美走位”题目，主要考察的是对字符串的处理和算法设计能力。以下是对该题目的详细解析及解题思路：

一、题目描述

在第一人称射击游戏中，玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动，从而完成走位。假设玩家每按动一次键盘，游戏人物会向某个方向移动一步，如果玩家在操作一定次数的键盘并且各个方向的步数相同时，此时游戏人物必定会回到原点，则称此次走位为“完美走位”。

现给定玩家的走位（例如：ASDA），请通过更换其中一段连续走位的方式使得原走位能够变成一个“完美走位”。其中待更换的连续走位可以是相同长度的任何走位。请返回待更换的连续走位的最小可能长度。如果原走位本身是一个“完美走位”，则返回0。

二、输入描述

输入为由键盘字母表示的走位s，例如：ASDA。

走位长度1 ≤ s.length ≤ 10^5。
s.length是4的倍数。
s中只含有A，S，D，W四种字符。

三、输出描述

输出为待更换的连续走位的最小可能长度。

四、解题思路

字符频率统计：
- 首先，我们需要统计字符串中每个字符（A、S、D、W）的频率。这可以通过遍历字符串并使用哈希表来实现。
计算目标频率：
- 由于完美走位要求四个方向的步数相同，因此每个字符的目标频率应为字符串总长度除以4。
滑动窗口与替换策略：
- 接下来，我们使用滑动窗口来尝试替换字符串中的连续子串。窗口的左边界和右边界分别表示当前考虑的子串的起始和结束位置。
- 在每次移动右边界时，我们更新当前窗口内各个字符的频率。如果当前窗口内的字符频率满足完美走位的要求（即每个字符的频率都等于目标频率），则尝试通过移动左边界来缩小窗口，并记录当前窗口的长度作为可能的替换长度。
- 为了确保替换后的子串长度与原子串相同，我们在移动左边界时，需要同时更新被替换字符的频率。
特殊情况处理：
- 如果原字符串已经是一个完美走位，则直接返回0。这可以通过在统计字符频率后检查是否所有字符的频率都等于目标频率来判断。
优化与边界条件：
- 由于字符串长度可能很大（最多可达10^5），我们需要确保算法的时间复杂度尽可能低。使用滑动窗口和哈希表可以有效地降低时间复杂度。
- 同时，我们还需要注意处理边界条件，例如当字符串长度为1或4时（即最简单的情况），算法应该能够正确返回结果。

五、代码实现



import java.util.HashMap;
import java.util.Map;

public class PerfectMovement {

    /**
     * 计算将字符串s转换为每个字符出现次数均为s.length()/4的最少替换长度
     *
     * @param s 输入的字符串
     * @return 返回最少替换的长度
     */
    public static int minReplacementLength(String s) {
        // 字符串长度
        int n = s.length();
        // 计算每个字符的目标出现次数
        int targetCount = n / 4;

        // 统计字符频率
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        // 找出多余的字符（频率超过目标频率的字符）
        Map<Character, Integer> extraChars = new HashMap<>();
        for (char c : freqMap.keySet()) {
            if (freqMap.get(c) > targetCount) {
                extraChars.put(c, freqMap.get(c) - targetCount);
            }
        }

        // 初始化最小替换长度为字符串长度
        int minReplacementLength = n;

        // 使用滑动窗口
        int left = 0;
        for (int right = 0; right < n; right++) {
            char rightChar = s.charAt(right);
            if (extraChars.containsKey(rightChar)) {
                extraChars.put(rightChar, extraChars.get(rightChar) - 1);
            }

            // 当窗口内的多余字符满足要求时，尝试缩小窗口
            while (isPerfect(extraChars)) {
                minReplacementLength = Math.min(minReplacementLength, right - left + 1);
                char leftChar = s.charAt(left);
                if (extraChars.containsKey(leftChar)) {
                    extraChars.put(leftChar, extraChars.get(leftChar) + 1);
                }
                left++;
            }
        }

        // 返回最小替换长度
        return minReplacementLength;
    }

    /**
     * 检查给定的字符映射中，所有字符的出现次数是否都为0
     * 这个方法用于判断是否所有额外的字符都已经被使用完毕
     *
     * @param extraChars 一个映射，其键为字符，值为该字符的出现次数
     * @return 如果所有字符的出现次数都为0，则返回true；否则返回false
     */
    private static boolean isPerfect(Map<Character, Integer> extraChars) {
        // 遍历映射中的所有字符出现次数
        for (int count : extraChars.values()) {
            // 如果有字符的出现次数大于0，则表示不是所有的额外字符都已经被使用完毕
            if (count > 0) {
                // 此时，返回false
                return false;
            }
        }
        // 如果所有字符的出现次数都为0，则表示所有额外字符都已经被使用完毕，返回true
        return true;
    }

    public static void main(String[] args) {
        String s1 = "WASDAASD";
        System.out.println("Input: " + s1 + ", Min Replacement Length: " + minReplacementLength(s1)); // 输出: 2

        String s2 = "AAAA";
        System.out.println("Input: " + s2 + ", Min Replacement Length: " + minReplacementLength(s2)); // 输出: 3

        String s3 = "WWWWWWWW";
        System.out.println("Input: " + s3 + ", Min Replacement Length: " + minReplacementLength(s3)); // 输出: 6

        String s4 = "WWWWWWWWWWWWWWWW";
        System.out.println("Input: " + s4 + ", Min Replacement Length: " + minReplacementLength(s4)); // 输出: 12
    }
}

在代码实现中，我们需要注意以下几点：

使用HashMap来存储字符频率，以便快速更新和查询。
使用两个指针（left和right）来表示滑动窗口的左右边界。
在每次移动右边界时，更新当前窗口内字符的频率，并检查是否满足完美走位的要求。
如果满足要求，则尝试移动左边界来缩小窗口，并记录当前窗口的长度。
在移动左边界时，需要同时更新被替换字符的频率。
最后返回记录的最小替换长度。

六、运行示例解析

代码解析

1、统计字符频率：

使用 freqMap 统计原始字符串中每个字符的频率。
使用 extraChars 记录频率超过目标频率的字符及其超出的数量。
2、滑动窗口：
使用两个指针 left 和 right 来表示当前窗口的左右边界。
在 right 指针向右移动时，更新 extraChars 中对应字符的频率。
当 extraChars 中所有字符的频率都不超过目标频率时，说明当前窗口是一个完美走位窗口。
记录当前窗口的长度，并尝试通过移动 left 指针来缩小窗口，以找到更小的完美走位窗口。
3、辅助函数 isPerfect：
检查 extraChars 中是否有任何字符的频率超过目标频率。
如果所有字符的频率都不超过目标频率，则返回 true，否则返回 false。

测试用例 1

输入：s1 = "WASDAASD"
期望输出：Min Replacement Length: 1
解析：
- 原始字符串中，每个方向的字符数并不相等。
- 通过将第二个字符A替换为W（或其他任意三个方向中的一个字符，使得总数平衡），可以得到一个完美走位，例如WWSDAASD。
- 因此，最小替换长度为1。

测试用例 2

输入：s2 = "AAAA"
期望输出：Min Replacement Length: 3
解析：
- 原始字符串中，只有A字符。
- 要使其变成完美走位，需要替换其中的3个字符为S、D、W（或它们的任意组合），例如WASD。
- 因此，最小替换长度为3。

测试用例 3

输入：s3 = "WWWWWWWW"
期望输出：Min Replacement Length: 6
解析：
- 原始字符串中，只有W字符。
- 要使其变成完美走位，需要将其中6个字符替换为A、S、D（每种2个），例如WWASDWSD。
- 因此，最小替换长度为6（因为需要替换6个字符才能达到平衡）。

测试用例 4

输入：s4 = "WWWWWWWWWWWWWWWW"
期望输出：Min Replacement Length: 12
解析：
- 原始字符串中，只有W字符。
- 要使其变成完美走位，需要将其中12个字符替换为A、S、D（每种4个），例如WWWWASDWSDASDW。
- 因此，最小替换长度为12（因为需要替换12个字符才能达到平衡）。