大连建设主管部门官方网站,贡井区建设局网站,微信如何制作网页,电商网官方网站完美走位
题目描述 在第一人称射击游戏中#xff0c;玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动#xff0c;从而完成走位。 假设玩家每按动一次键盘#xff0c;游戏任务会向某个方向移动一步#xff0c;如果玩家在操作一定次数的键…完美走位
题目描述 在第一人称射击游戏中玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动从而完成走位。 假设玩家每按动一次键盘游戏任务会向某个方向移动一步如果玩家在操作一定次数的键盘并且各个方向的步数相同时此时游戏任务必定会回到原点则称此次走位为完美走位。 现给定玩家的走位例如ASDA请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位。其中待更换的连续走位可以是相同长度的任何走位。 请返回待更换的连续走位的最小可能长度。 如果原走位本身是一个完美走位则返回0。 输入描述 输入为由键盘字母表示的走位s例如ASDA 输出描述 输出为待更换的连续走位的最小可能长度。 用例
输入WASDAASD输出1说明将第二个A替换为W即可得到完美走位
输入AAAA输出3说明将其中三个连续的A替换为WSD即可得到完美走位
源码和解析 解析 先匹配出多的字符及个数 那个字符次数-平均值为多余的。即需要在原字符串中找出一个子串该子串满足多余出来的字符和出现的字数。 如A多了2次 S多了一次 那么查找的子串可以为ASA AAS SSAA等。最后返回的结果是那个最短子串的长度。 使用双指针来解决这个问题。不断地判断两个指针之间的字符串是否满足条件。若满足条件左指针右移到右指针那个位置继续寻找下一个子串。最后再将字符串反向来查找一次。就基本能满足大多数测试用例了。 示例代码
import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class T26 {public static void main(String[] args) {String input WASDAASDSDAS;char[] chArr input.toCharArray();char C[] { W, A, S, D };MapCharacter, Integer chCountMap new HashMapCharacter, Integer();for (char c : C) {chCountMap.put(c, 0);}// 统计每个字符出现的次数for (char c : chArr) {chCountMap.put(c, chCountMap.get(c) 1);}int avgLen input.length() / 4;// 计算每个字符的差值for (char c : C) {chCountMap.put(c, chCountMap.get(c) - avgLen);}// 计算每个字符正和负的情况 其实就是统计正出现的个数即可for (char c : C) {int count chCountMap.get(c);if (count 0)chCountMap.remove(c); // 移除负数次数的}int min count(input, chCountMap);int reverseMin count(new StringBuilder(input).reverse().toString(),chCountMap);if (min reverseMin) {System.out.println(min);} else {System.out.println(reverseMin);}}// 统计双指针找满足条件的最小子串长度public static int count(String input, MapCharacter, Integer chCountMap) {int start 0; // 开始索引int end 1;// 结束索引int min Integer.MAX_VALUE;String word;while (end input.length()) {word input.substring(start, end);if (!chCountMap.containsKey(word.charAt(0))) {// 首字母不是 干掉start;end;continue;}if (check(word, chCountMap)) {start end;if (word.length() min) {min word.length();}end;} else {end;}}return min;}// 统计 字符串中是否有满足map中字符出现个数的public static boolean check(String word, MapCharacter, Integer wordMap) {char[] chArr word.toCharArray();MapCharacter, Integer cMap new HashMap();for (char c : chArr) {if (cMap.containsKey(c)) {cMap.put(c, cMap.get(c) 1);} else {cMap.put(c, 1);}}SetCharacter keySet wordMap.keySet();boolean flag true;for (Character key : keySet) {if (!cMap.containsKey(key))return false;if (wordMap.get(key) cMap.get(key))return false;}if (flag)return true;return false;}
}
代码测试结果 输入WASDAASDSDAS 输入AAAA
