全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：获得完美走位
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
在第一人称射击游戏中，玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动，从而完成走位。假设玩家每按动一次键盘，游戏人物会向某个方向移动一步，如果玩家在操作一定次数的键盘并且各个方向的步数相同时，此时游戏人物必定会回到原点，则称此次走位为完美走位。
现给定玩家的走位（例如：ASDA）,请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位。其中待更换的连续走位可以是相同长度的任何走位。
请返回待更换的连续走位的最小可能长度。
若果原走位本身是一个完美走位，则返回0。
输入描述：
输入为由键盘字母表示的走位s，例如：ASDA
输出描述：
输出为待更换的连续走位的最小可能长度
补充说明：
1、走位长度1 <= s.length <= 10^5
2、s.length 是 4 的倍数
3、s 中只含有 ‘A’, ‘S’, ‘D’, ‘W’ 四种字符
示例1
输入：
ASDW
输出：
0
说明：
已经是完美走位了
示例2
输入：
AASW
输出：
1
说明：
需要把一个A更换成D，这样可以得到“ADSW”或者“DASW”
示例3
输入：
AAAA
输出：
3
说明：
可以替换后 3 个 ‘A’，得到ASDW。
解题思路：
需要走到原点，就需要 ‘A’, ‘S’, ‘D’, ‘W’ 四种字符的个数相同。
用字符总长度除以4得出每个字符的所需个数。（题目要求输入字符个数是4的倍数）
遍历求出每个字符的总数，求出他们的多余字符个数（总数-步骤1的个数）
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* @title 获得完美走位
* @Description 在第一人称射击游戏中，玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动，从而完成走位。假设玩家每按动一次键盘，游戏人物会向某个方向移动一步，如果玩家在操作一定次数的键盘并且各个方向的步数相同时，此时游戏人物必定会回到原点，则称此次走位为完美走位。
* 现给定玩家的走位（例如：ASDA）,请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位。其中待更换的连续走位可以是相同长度的任何走位。
* 请返回待更换的连续走位的最小可能长度。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/13
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int len = str.length();
int count = len / 4; //求出每个方向所需的个数（题目已规定len是4的倍数）
// key：A、S、D、W四个方向；value：各个方向的个数
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0) + 1);
}
for (Map.Entry<Character, Integer> m : map.entrySet()) {
m.setValue(m.getValue() - count); //计算出各个方向多余的个数
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < len; i++) {
char cIndexI = str.charAt(i);
int res = 0;
Map<Character, Integer> copyMap = new HashMap<>(map); //需要复制一个map，以防影响原始map的数据
if (copyMap.get(cIndexI) > 0) { //大于0，说明此方向有多余，不能到达原点
/**
* 从index=i开始向后遍历
* 遍历到的方向可以变换成任意方向
* 假如此时方向我们进行改变，则map中该方向的个数进行-1，变换的次数+1
* 每次变换完都需要判断map中是否有value值大于0
* 如果有value大于0，则代表还有多余的方向，无法到达原点，继续进行遍历
* 如果没有value大于0，则代表没有多余的方向，可以到达原点，结束遍历
* 以此类推，求出最小的变换次数
*
* 如AAAA，计算出每个方向应该出现1（4/4）次
* map{ key:A, value:3（4-1）}
* 当i=0时，char=A，map.get(A)=3>0，方向多余，不能到达原点;
* 从j=0开始遍历，char=A，map.get(A)-1=3-1=2，res+1=1；
* map中只有A，value=2>0，有方向多余，不能到达原点；
* 向后遍历，j=1，char=A，map.get(A)-1=2-1=1，res+1=2；
* map中只有A，value=1>0，有方向多余，不能到达原点；
* 向后遍历，j=2，char=A，map.get(A)-1=1-1=0，res+1=3；
* map中只有A，value=0==0，没有方向多余，可以到达原点；
* 则变换的长度为3
* 当i=1时，char=A，map.get(A)=3>0，方向多余，不能到达原点;
* 从j=1开始遍历，char=A，map.get(A)-1=3-1=2，res+1=1；
* map中只有A，value=2>0，有方向多余，不能到达原点；
* 向后遍历，j=2，char=A，map.get(A)-1=2-1=1，res+1=2；
* map中只有A，value=1>0，有方向多余，不能到达原点；
* 向后遍历，j=3，char=A，map.get(A)-1=1-1=0，res+1=3；
* map中只有A，value=0==0，没有方向多余，可以到达原点；
* 则变换的长度为3
* 当i=2时，char=A，map.get(A)=3>0，方向多余，不能到达原点;
* 但是后面的A只剩1个，最后map中A的value会剩下1，不能到达原点；
* 所以最终更换的最小长度为3
*/
for (int j = i; j < len; j++) {
char cIndexJ = str.charAt(j);
copyMap.put(cIndexJ, copyMap.get(cIndexJ) - 1); //此方向可以变换成任意方向，个数-1
res++; //需要变换的连续走位的个数
if (isTrue(copyMap)) { //判断是否可以到达原点
break; //如果可以到达原点，则退出循环
}
}
}
if (isTrue(copyMap)) { //如果到达原点则求出其中的最小值
min = Math.min(min, res);
}
}
System.out.println(min);
}
/**
* 没有多余的方向，说明可以到达原点
*/
public static boolean isTrue(Map<Character, Integer> map) {
for (Integer i : map.values()) {
if (i > 0) { //任何方向有多余的都不能回到原点
return false;
}
}
return true; //所有方向多余的个数为0则能回到原点
}
}
代码实现二：
package com.codernav.demo.hwod.exam;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* @title 获得完美走位
* @Description 在第一人称射击游戏中，玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动，从而完成走位。假设玩家每按动一次键盘，游戏人物会向某个方向移动一步，如果玩家在操作一定次数的键盘并且各个方向的步数相同时，此时游戏人物必定会回到原点，则称此次走位为完美走位。
* 现给定玩家的走位（例如：ASDA）,请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位。其中待更换的连续走位可以是相同长度的任何走位。
* 请返回待更换的连续走位的最小可能长度。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/13
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
Zouwei z = new Zouwei(str);
int perfect = str.length() / 4;
Map<Character, Integer> offset = new HashMap<>();
offset.put('W', z.W - perfect);
offset.put('A', z.A - perfect);
offset.put('S', z.S - perfect);
offset.put('D', z.D - perfect);
int min = str.length();
for (int i = 0; i < str.length(); i++) {
HashMap<Character, Integer> copy = new HashMap<>(offset);
int len = 0;
if (copy.get(str.charAt(i)) > 0) {
for (int j = i; j < str.length(); j++) {
char c = str.charAt(j);
copy.put(c, copy.get(c) - 1);
len++;
if (allClear(copy)) {
break;
}
}
}
if (allClear(copy)) {
min = Math.min(min, len);
}
}
System.out.println(min);
}
private static boolean allClear(HashMap<Character, Integer> copy) {
Collection<Integer> values = copy.values();
for (Integer value : values) {
if (value > 0) {
return false;
}
}
return true;
}
static class Zouwei {
Integer W = 0;
Integer A = 0;
Integer S = 0;
Integer D = 0;
String code;
public Zouwei(String code) {
this.code = code;
for (char c : code.toCharArray()) {
switch (c) {
case 'W':
this.W++;
break;
case 'A':
this.A++;
break;
case 'S':
this.S++;
break;
case 'D':
this.D++;
break;
}
}
}
}
}
© 版权声明
文章版权归作者所有，未经允许请勿转载。
相关文章
暂无评论...
1. 本站博客内容及资源，原作者享有著作权，个人可以使用，但请勿用于商业用途。2. 所有文章可以转载、摘编、复制或建立镜像，但请注明原文链接。如有违反，追究法律责任。3. 举报邮箱：codernav@foxmail.com
