【华为OD-E卷-获得完美走位 100分（python、java、c++、js、c）】
题目
在第一人称射击游戏中，玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动，从而完成走位。
假设玩家每按动一次键盘，游戏任务会向某个方向移动一步，如果玩家在操作一定次数的键盘并且各个方向的步数相同时，此时游戏任务必定会回到原点，则称此次走位为完美走位。
现给定玩家的走位（例如：ASDA），请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位。其中待更换的连续走位可以是相同长度的任何走位。
请返回待更换的连续走位的最小可能长度。
如果原走位本身是一个完美走位，则返回0。
输入描述
- 输入为由键盘字母表示的走位s，例如：ASDA
输出描述
- 输出为待更换的连续走位的最小可能长度
备注
- 走位长度 1 ≤ s.length ≤ 100000 s.length 是 4 的倍数 s中只含有’A’, ‘S’, ‘D’, ‘W’ 四种字符
用例
用例一：
输入：
WASDAASD
输出：
1
用例二：
输入：
AAAA
输出：
3
python解法
- 解题思路：
- 问题分析：
给定一个只包含字符 “W”, “A”, “S”, “D” 的字符串，要求找到一个最短的子串，使得移除该子串后，剩余字符串中 “W”, “A”, “S”, “D” 的数量均相等。
方法：
首先统计字符串中每个字符的总数。
计算每种字符的过剩数量，即超出目标的部分。
如果没有过剩字符（所有字符数量都已经满足条件），直接返回 0。
使用滑动窗口找到满足条件的最短子串：
滑动窗口的右边界不断扩展，直到包含所有过剩字符。
在满足条件的情况下，尝试通过收缩左边界，找到更短的子串。
滑动窗口细节：
使用两个指针 start 和 end 分别表示窗口的左右边界。
窗口内字符的数量变化由 excess_count 控制。
窗口有效的条件是 excess_count 中所有值均不大于 0。
def min_length_substring(s):
# 统计字符串中各字符的数量
total_count = {"W": 0, "A": 0, "S": 0, "D": 0}
for char in s:
total_count[char] += 1
# 每种字符的目标数量
target = len(s) // 4
# 计算每种字符的过剩数量
excess_count = {char: max(0, count - target) for char, count in total_count.items()}
# 如果没有过剩字符，返回0（不需要移除子串）
if sum(excess_count.values()) == 0:
return 0
# 初始化滑动窗口的指针和最短长度
start, min_len = 0, len(s)
# 遍历字符串，扩展滑动窗口的右边界
for end in range(len(s)):
# 将窗口右边界字符的过剩数量减1
excess_count[s[end]] -= 1
# 当窗口有效（所有字符的过剩数量均小于等于0）时，尝试收缩左边界
while all(count <= 0 for count in excess_count.values()):
# 更新最短长度
min_len = min(min_len, end - start + 1)
# 收缩窗口左边界，恢复左边界字符的过剩数量
excess_count[s[start]] += 1
start += 1
return min_len
# 输入字符串并输出最短子串长度
s = input()
print(min_length_substring(s))
java解法
- 解题思路
- 问题描述：
给定一个只包含字符 A、S、D、W 的字符串，找到一个最短子串，移除该子串后剩下的字符串中这四种字符的数量相等。
方法：
统计字符数量：先统计字符串中 A、S、D、W 各字符的数量。
计算超出部分：确定每种字符需要移除的多余数量，如果字符数量没有超标，直接返回 0。
滑动窗口：利用滑动窗口技术，动态调整子串范围，寻找满足条件的最短子串：
右边界扩展窗口，直到包含所有多余字符；
左边界收缩窗口，尝试找到更短的符合条件的子串。
滑动窗口关键点：
窗口内的字符数量动态变化，满足条件的窗口是：count 数组中所有值小于等于 0。
每次满足条件时，记录当前窗口长度并继续收缩。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入字符串，输出最短子串长度
System.out.println(minReplacementLength(scanner.next()));
}
/**
* 计算需要移除的最短子串长度，使剩余字符串中 A, S, D, W 数量相等
*/
public static int minReplacementLength(String moves) {
int[] count = new int[4]; // 用于记录 'A', 'S', 'D', 'W' 的数量
// 统计字符串中每种字符的数量
for (char move : moves.toCharArray()) {
count[getIndex(move)]++;
}
// 每种字符的目标数量
int avg = moves.length() / 4;
// 计算多余字符的总数
int requiredSteps = 0;
for (int i = 0; i < 4; i++) {
count[i] -= avg; // 计算每种字符的超标数量
if (count[i] > 0) {
requiredSteps += count[i]; // 记录需要移除的多余字符数
} else {
count[i] = 0; // 负数无意义，重置为 0
}
}
// 如果没有多余字符，直接返回 0
if (requiredSteps == 0) return 0;
// 滑动窗口寻找最短子串
int left = 0, right = 0, minLength = moves.length() + 1;
while (right < moves.length()) {
// 窗口右边界扩展，更新当前窗口内的字符数量
count[getIndex(moves.charAt(right))]--;
// 当窗口内所有多余字符数量 <= 0 时，尝试收缩窗口
while (isBalanced(count)) {
// 更新最短长度
minLength = Math.min(minLength, right - left + 1);
// 收缩左边界，恢复被移除的字符数量
count[getIndex(moves.charAt(left))]++;
left++;
}
right++;
}
return minLength; // 返回最短子串长度
}
/**
* 根据字符返回对应的索引
* 'A' -> 0, 'S' -> 1, 'D' -> 2, 'W' -> 3
*/
private static int getIndex(char move) {
switch (move) {
case 'A': return 0;
case 'S': return 1;
case 'D': return 2;
case 'W': return 3;
default: return -1;
}
}
/**
* 检查当前窗口内的多余字符是否都小于等于 0
*/
private static boolean isBalanced(int[] count) {
for (int c : count) {
if (c > 0) return false; // 如果存在未满足条件的字符，返回 false
}
return true; // 所有多余字符 <= 0，窗口有效
}
}
C++解法
- 解题思路
- 问题描述
给定一个由字符 W、A、S 和 D 组成的字符串，要求找到一个最短的子串，移除该子串后，剩余字符串中这四种字符的数量均相等。
方法
统计字符总数：首先统计字符串中每个字符 W、A、S 和 D 的数量。
判断是否已经满足条件：如果所有字符的数量已经相等，直接返回 0。
滑动窗口：
用两个指针 left 和 right 表示窗口的左右边界。
窗口右边界向右扩展，减少窗口内字符的数量。
当窗口内的字符数量满足条件（即剩余字符串中所有字符的数量不超过目标值）时，尝试收缩窗口，寻找更短的子串。
关键点
每次窗口内字符数量发生变化时，判断是否满足剩余字符串中字符均衡的条件。
保持窗口动态变化，直到遍历整个字符串。
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
/**
* 计算最短子串长度，使移除该子串后剩余字符串中字符 'W', 'A', 'S', 'D' 的数量均相等
*/
int find_min_replacement(string &s) {
unordered_map<char, int> count; // 统计字符数量
int n = s.size();
int required = n / 4; // 每种字符的目标数量
// 统计字符串中各字符的数量
for (char c : s) {
count[c]++;
}
// 如果字符已经满足均衡条件，直接返回0
if (count['W'] == required && count['A'] == required &&
count['S'] == required && count['D'] == required) {
return 0;
}
int left = 0, right = 0; // 滑动窗口的左右边界
int min_len = n; // 最短子串长度初始化为字符串长度
// 滑动窗口遍历字符串
while (right < n) {
// 窗口右边界字符计数减一
count[s[right]]--;
// 窗口有效：剩余字符满足均衡条件
while (count['W'] <= required && count['A'] <= required &&
count['S'] <= required && count['D'] <= required) {
// 更新最短子串长度
min_len = min(min_len, right - left + 1);
// 收缩窗口左边界，恢复字符计数
count[s[left]]++;
left++;
}
// 扩展窗口右边界
right++;
}
return min_len; // 返回最短子串长度
}
int main() {
string s;
cin >> s; // 输入字符串
cout << find_min_replacement(s) << endl; // 输出最短子串长度
return 0;
}
C解法
更新中
JS解法
更新中
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏