华为OD机试 - 获得完美走位（Python/JS/C/C 2024 E卷 200分）

在这里插入图片描述

2025华为OD机试题库（按算法分类）：2025华为OD统一考试题库清单（持续收录中）以及考点说明（Python/JS/C/C++）。

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

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

现给定玩家的走位(例如: ASDA)，请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位。其中待更换的连续走位可以是相同长度的任何走位。

请返回待更换的连续走位的最小可能长度，如果原走位本身是一个完美走位，则返回 0。

二、输入描述

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

三、输出描述

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

四、测试用例

测试用例1

1、输入

WASD

2、输出

3、说明

长度 4，各方向各 1，无多余。

已平衡，无需替换，答案为 0。

测试用例2

1、输入

AAAASSSS

2、输出

3、说明

长度 8，target = 2。统计得 A:4, S:4, W:0, D:0。

多余：A 多 2，S 多 2。

一个最短的子串如 “AASS”（例如从索引 2 到 5）包含 2 个 A 和 2 个 S，长度为 4。

五、解题思路

读取输入的走位字符串 line；
初始化计数变量 numA、numS、numD、numW 分别表示 A、S、D、W 四个方向的步数；
使用循环遍历走位字符串，统计各个方向的步数；
初始化变量 res 为最大整数值，用于记录待更换连续走位的最小可能长度；
计算每个方向需要补充的步数：a = Math.max(numA - p, 0)、w = Math.max(numW - p, 0)、s = Math.max(numS - p, 0)、d =
Math.max(numD - p, 0)，其中 p = line.length() / 4 表示每个方向的平均步数；
如果每个方向需要补充的步数都为0，表示原走位已经是一个完美走位，输出0并结束程序；
使用循环遍历走位字符串，计算每个位置开始的待更换连续走位的最小可能长度；
- 调用 match 方法计算从当前位置开始，补充指定步数后是否能形成完美走位，返回能够形成完美走位的最后位置；
- 更新 res 为最小长度；
输出结果 res；

六、Python算法源码

# 定义函数计算最小替换子串长度，使走位平衡
def balanced_movement(s: str) -> int:
    n = len(s)  # 字符串长度
    target = n // 4  # 每个方向理想步数
    # 初始化各方向计数
    count = {'A': 0, 'S': 0, 'D': 0, 'W': 0}
    for ch in s:
        count[ch] += 1  # 统计每个字符出现次数

    # 计算每个方向的多余步数
    surplus = {
        'A': max(count['A'] - target, 0),
        'S': max(count['S'] - target, 0),
        'D': max(count['D'] - target, 0),
        'W': max(count['W'] - target, 0)
    }
    
    # 如果没有多余步数，则已平衡，返回 0
    if surplus['A'] == 0 and surplus['S'] == 0 and surplus['D'] == 0 and surplus['W'] == 0:
        return 0
    
    res = n  # 初始化结果为最大可能值（字符串长度）
    left = 0  # 滑动窗口左指针
    # 初始化窗口中各方向计数
    window = {'A': 0, 'S': 0, 'D': 0, 'W': 0}
    
    # 右指针遍历字符串
    for right in range(n):
        ch = s[right]
        # 若字符在需要统计的范围内，则增加计数
        if ch in window:
            window[ch] += 1
        # 当窗口内各方向计数满足要求时，尝试缩小窗口
        while left <= right and window['A'] >= surplus['A'] and window['S'] >= surplus['S'] and window['D'] >= surplus['D'] and window['W'] >= surplus['W']:
            res = min(res, right - left + 1)  # 更新最小窗口长度
            left_ch = s[left]  # 获取窗口左边字符
            if left_ch in window:
                window[left_ch] -= 1  # 将左边字符从窗口中移除
            left += 1  # 左指针右移
    return res

# 主函数用于测试
if __name__ == "__main__":
    s = input().strip()  # 从标准输入读取字符串
    print(balanced_movement(s))  # 输出结果

七、JavaScript算法源码

// 定义函数计算最小替换子串长度，使走位平衡
function balancedMovement(s) {
    let n = s.length; // 字符串长度
    let target = Math.floor(n / 4); // 每个方向理想步数
    // 初始化各方向计数
    let count = { 'A': 0, 'S': 0, 'D': 0, 'W': 0 };
    for (let ch of s) {
        count[ch] = (count[ch] || 0) + 1; // 统计字符出现次数
    }
    // 计算每个方向的多余步数
    let surplus = {
        'A': Math.max(count['A'] - target, 0),
        'S': Math.max(count['S'] - target, 0),
        'D': Math.max(count['D'] - target, 0),
        'W': Math.max(count['W'] - target, 0)
    };
    
    // 如果各方向无多余步数，则已平衡，返回 0
    if (surplus['A'] === 0 && surplus['S'] === 0 && surplus['D'] === 0 && surplus['W'] === 0) {
        return 0;
    }
    
    let res = n; // 初始化结果为字符串长度
    let left = 0; // 滑动窗口左指针
    // 初始化窗口内各方向计数
    let window = { 'A': 0, 'S': 0, 'D': 0, 'W': 0 };
    
    // 右指针遍历字符串
    for (let right = 0; right < n; right++) {
        let ch = s[right];
        if (ch in window) {
            window[ch]++; // 更新窗口内计数
        }
        // 当窗口内各方向计数满足要求时，尝试缩小窗口
        while (left <= right &&
               window['A'] >= surplus['A'] &&
               window['S'] >= surplus['S'] &&
               window['D'] >= surplus['D'] &&
               window['W'] >= surplus['W']) {
            res = Math.min(res, right - left + 1); // 更新最小窗口长度
            let left_ch = s[left]; // 获取左侧字符
            if (left_ch in window) {
                window[left_ch]--; // 移除左侧字符计数
            }
            left++; // 左指针右移
        }
    }
    return res; // 返回结果
}

// 以下代码用于 Node.js 环境下的输入输出测试
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
rl.on('line', (line) => {
    console.log(balancedMovement(line.trim())); // 输出测试结果
});

八、C算法源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>

// 定义求最大值的函数
int max(int a, int b) {
    return a > b ? a : b;
}

// 定义求最小值的函数
int min(int a, int b) {
    return a < b ? a : b;
}

// 函数：计算最小替换子串长度，使走位平衡
int balancedMovement(char *s) {
    int n = strlen(s); // 获取字符串长度
    int target = n / 4; // 每个方向理想步数
    
    // 初始化各方向总步数
    int countA = 0, countS = 0, countD = 0, countW = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'A') countA++;
        else if (s[i] == 'S') countS++;
        else if (s[i] == 'D') countD++;
        else if (s[i] == 'W') countW++;
    }
    
    // 计算各方向多余步数
    int surplusA = max(countA - target, 0);
    int surplusS = max(countS - target, 0);
    int surplusD = max(countD - target, 0);
    int surplusW = max(countW - target, 0);
    
    // 如果各方向均无多余步数，则已平衡，返回 0
    if (surplusA == 0 && surplusS == 0 && surplusD == 0 && surplusW == 0) {
        return 0;
    }
    
    int res = n; // 初始化结果为字符串长度
    int left = 0; // 滑动窗口左指针
    // 初始化窗口中各方向计数
    int windowA = 0, windowS = 0, windowD = 0, windowW = 0;
    
    // 右指针遍历字符串
    for (int right = 0; right < n; right++) {
        // 根据字符更新窗口计数
        if (s[right] == 'A') windowA++;
        else if (s[right] == 'S') windowS++;
        else if (s[right] == 'D') windowD++;
        else if (s[right] == 'W') windowW++;
        
        // 当窗口中各方向计数满足所需多余步数时，尝试缩小窗口
        while (left <= right && windowA >= surplusA && windowS >= surplusS && windowD >= surplusD && windowW >= surplusW) {
            res = min(res, right - left + 1); // 更新最小子串长度
            // 根据左侧字符减少窗口计数
            if (s[left] == 'A') windowA--;
            else if (s[left] == 'S') windowS--;
            else if (s[left] == 'D') windowD--;
            else if (s[left] == 'W') windowW--;
            left++; // 左指针右移
        }
    }
    return res; // 返回结果
}

int main(){
    char s[100001]; // 定义字符串数组（假设最大长度不超过 100000）
    scanf("%s", s); // 从标准输入读取字符串
    int ans = balancedMovement(s); // 计算结果
    printf("%d\n", ans); // 输出结果
    return 0;
}

九、C++算法源码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    string s;
    cin >> s;  // 读取输入字符串
    int n = s.size();  // 获取字符串长度
    int target = n / 4;  // 每个方向理想步数
    
    // 初始化各方向总步数
    int countA = 0, countS = 0, countD = 0, countW = 0;
    for (char c : s) {
        if (c == 'A') countA++;
        else if (c == 'S') countS++;
        else if (c == 'D') countD++;
        else if (c == 'W') countW++;
    }
    
    // 计算各方向多余步数
    int surplusA = max(countA - target, 0);
    int surplusS = max(countS - target, 0);
    int surplusD = max(countD - target, 0);
    int surplusW = max(countW - target, 0);
    
    // 如果各方向无多余步数，则已平衡，输出 0
    if (surplusA == 0 && surplusS == 0 && surplusD == 0 && surplusW == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    int res = n;  // 初始化结果为字符串长度
    int left = 0; // 滑动窗口左指针
    // 初始化窗口中各方向计数
    int windowA = 0, windowS = 0, windowD = 0, windowW = 0;
    
    // 右指针遍历字符串
    for (int right = 0; right < n; right++) {
        // 根据当前字符更新窗口计数
        if (s[right] == 'A') windowA++;
        else if (s[right] == 'S') windowS++;
        else if (s[right] == 'D') windowD++;
        else if (s[right] == 'W') windowW++;
        
        // 当窗口满足各方向所需多余步数时，尝试收缩窗口
        while (left <= right && windowA >= surplusA && windowS >= surplusS && windowD >= surplusD && windowW >= surplusW) {
            res = min(res, right - left + 1);  // 更新最小子串长度
            // 根据左侧字符减少窗口计数
            if (s[left] == 'A') windowA--;
            else if (s[left] == 'S') windowS--;
            else if (s[left] == 'D') windowD--;
            else if (s[left] == 'W') windowW--;
            left++;  // 左指针右移
        }
    }
    cout << res << endl;  // 输出结果
    return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

在这里插入图片描述