完美走位
2026华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 100分题型
华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解
其它语言题解链接
华为OD机试真题 - 完美走位 (Python & C++ & JAVA & JS & GO)
题目描述
在第一人称射击游戏中，玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动，从而完成走位。
假设玩家每按动一次键盘，游戏任务会向某个方向移动一步，如果玩家在操作一定次数的键盘并且各个方向的步数相同时，此时游戏任务必定会回到原点，则称此次走位为完美走位。
现给定玩家的走位（例如：ASDA），请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位。其中待更换的连续走位可以是相同长度的任何走位。
请返回待更换的连续走位的最小可能长度。
如果原走位本身是一个完美走位，则返回0。
输入描述
输入为由键盘字母表示的走位s，例如：ASDA
输出描述
输出为待更换的连续走位的最小可能长度。
用例1
输入
WASDAASD输出
1说明
将第二个A替换为W，即可得到完美走位
示例二
输入
AAAA输出
3说明
将其中三个连续的A替换为WSD，即可得到完美走位.题解
思路
本题采用滑动窗口解决：
题目对于完美走位定义其实就是字符串中
ASWD字母数量相同。对于一个不完美走位的字符串通过修改
一段连续的走位要想变成完美走位，那么这段连续走位必须满足包含所有多于平均数量的字符，并且每种多余平均数量的字符 在一段连续走位中数量大于等于多余部分数量。可能有点抽象，举个例子，例如现在A多两个，B多一个。找的区间必须满足这段区间至少包含两个A和一个B。满足上述条件的最短区间就是这道题的结果。对于这类题可直接采用
滑动窗口进行解决：计算
AWSD每个字符在原字符串中的数量，以及超过的数量。如果都等于平均数量则已经是完美走位，输出0，否则进行下面逻辑。定义
left = 0, right = 0, right开始不断右移，直到区间内满足上述2分析的要求时，这时候要寻求最短区间，尝试左边界右移，缩小边界，直到不满足3的要求时，继续尝试right右移。记录上述逻辑满足条件的最短窗口长度就是结果。
code
#include<stdio.h>#include<string.h>intmain(){// 长度可以根据输入长度变换chars[100010];scanf("%s",s);intn=strlen(s);// 不可能有解，冗余处理if(n%4){printf("-1\n");return0;}inttarget=n/4;// 记录每个字符的数量intcount_A=0,count_S=0,count_D=0,count_W=0;// 统计每个字符的数量for(inti=0;i<n;i++){switch(s[i]){case'A':count_A++;break;case'S':count_S++;break;case'D':count_D++;break;case'W':count_W++;break;}}// 计算多余数量intexcess_A=(count_A>target)?count_A-target:0;intexcess_S=(count_S>target)?count_S-target:0;intexcess_D=(count_D>target)?count_D-target:0;intexcess_W=(count_W>target)?count_W-target:0;// 已经是完美走位if(excess_A+excess_S+excess_D+excess_W==0){printf("0\n");return0;}// 滑动窗口intmin_len=n;intwindow_A=0,window_S=0,window_D=0,window_W=0;intleft=0;for(intright=0;right<n;right++){// 更新窗口计数switch(s[right]){case'A':window_A++;break;case'S':window_S++;break;case'D':window_D++;break;case'W':window_W++;break;}// 当窗口满足条件时收缩， 满足条件（窗口内所有字符大于等于 对应字符超过平均的数量）while(left<=right&&window_A>=excess_A&&window_S>=excess_S&&window_D>=excess_D&&window_W>=excess_W){intlen=right-left+1;if(len<min_len)min_len=len;// 左指针移动，更新窗口计数switch(s[left]){case'A':window_A--;break;case'S':window_S--;break;case'D':window_D--;break;case'W':window_W--;break;}left++;}}printf("%d\n",min_len);return0;}
