华为OD机试之完美走位（Java源码）

完美走位

题目描述

在第一人称射击游戏中，玩家通过键盘的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' };
		Map<Character, Integer> chCountMap = new HashMap<Character, 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, Map<Character, 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, Map<Character, Integer> wordMap) {
		char[] chArr = word.toCharArray();
		Map<Character, Integer> cMap = new HashMap<>();
		for (char c : chArr) {
			if (cMap.containsKey(c)) {
				cMap.put(c, cMap.get(c) + 1);
			} else {
				cMap.put(c, 1);
			}
		}
		Set<Character> 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;
	}
}