06-模拟

模拟题是思路是相对来说是比较简单的，因为不需要思考思路，题目是会自动给出过程的。

但是在编写之前，一定要画图，不然会忽略一些细节，这就会导致一些问题会无从下手

题目

LC1576.替换所有的问号

这个题目只需要考虑一个细节就可以了：既在最左侧和最右侧的时候，需要考虑下标越界的情况

public String modifyString(String s) {
	char[] arr = s.toCharArray(); // 转换为数组可以比较方便处理
	int n = arr.length;
	for (int i = 0; i < arr.length; i++) {
		char ch = arr[i];
		if (ch == '?') {
			// 给 lCh 和 rCh 一个初始值，这样可以处理当 i 为 0 或 n - 1 的情况：不存在的话，不会保语法错误
			char lCh = 'd', rCh = 'e';
			if (i - 1 >= 0) lCh = arr[i - 1];
			if (i + 1 < arr.length) rCh = arr[i + 1];

			// 只要两次判断就可以了，因为两边最多是两个字符
			if (lCh != 'a' && rCh != 'a') arr[i] = 'a';
			else if (lCh != 'b' && rCh != 'b') arr[i] = 'b';
			else arr[i] = 'c';
		}
	}

	return new String(arr);
}

LC495. 提莫攻击

这个只需要考虑这个细节就可以了：如何计算中间的中毒时间？

把意思转换一下，就是要我们求出这一次攻击的中毒的有效时长。

如果中毒的持续时间过短，那有效的时长就是 duration, 如果两个攻击时间的间隔过短，那么有效时长就是 timeSeries[i + 1] - timeSeries[i]. 因此是有效时长就是算这两个值的较小值

public int findPoisonedDuration(int[] timeSeries, int duration) {
	int result = 0;
	for (int i = 0; i < timeSeries.length - 1; i++) {
		// 获取到第一次攻击和第二次攻击的差值，然后和持续时间比较，获取较小值。
		// 也就是获取 timesSeries[i] 这个攻击后，中毒的有效时长
		result += Math.min(duration, timeSeries[i + 1] - timeSeries[i]);
	}
	return result + duration; // 还少了最后一个
}

LC6. Z 字形变换

这个可以根据题目，一步一步把题目给解出来，但是如果数据量过大的话，那么就需要优化

模拟题优化步骤（重要）：

1. 画图，把题目的情况画出来

   画图的时候可以使用下标来代替，而不是当前参数传入值的内容，因为下标是通用的，而值是会对推出规律起到干扰的作用的

2. 根据图像，反推出一些规律
3. 修改条件，看看这些规律能不能满足新的条件

这个题目就发现了这样的规律：

1. 首行和尾行是相差的公差为 differ = 2 * numRows - 2
2. 把画出来的结果看为一个 V, 计 V 的个数为 count，从 1 开始，那么每个 V 的中间每一行的下标之和就是 (2 * count - 1) * differ

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

public String convert(String s, int numRows) {
	if (numRows == 1) return s;

	int n = s.length(), differ = 2 * numRows - 2;
	char[] result = new char[n];
	int index = 0; // result 的下标
	// 先获取到第一行的内容
	for (int i = 0; i < n; i += differ) {
		result[index++] = s.charAt(i);
	}

	// 获取到中间几行的内容
	for (int i = 1; i < numRows - 1; i++) {
		for (int j = i, count = 1; j < n; j += differ, count++) {
			result[index++] = s.charAt(j);
			if (differ * (2 * count - 1) - j < n) {
				result[index++] = s.charAt(differ * (2 * count - 1) - j);
			}
		}
	}

	// 获取最后一行的内容
	for (int i = numRows - 1; i < n; i += differ) {
		result[index++] = s.charAt(i);
	}

	return new String(result);
}

LC38. 外观数列

这个题目也是一样，根据题目描述来编写算法就可以了

public String countAndSay(int n) {
	StringBuilder result = new StringBuilder("1");
	// 执行 n - 1 次
	for (int i = 1; i < n; i++) {
		result = getResult(result);
	}
	return result.toString();
}

// 根据输入元素，返回下一次的内容
public StringBuilder getResult(StringBuilder input) {
	int left = 0, right = 0, n = input.length();
	StringBuilder result = new StringBuilder();
	while (right < n) {
		// 如果相等，那么就要一直匹配，直到找到第一个不相同的元素位置
		while (right < n && input.charAt(right) == input.charAt(left)) right++;
		// 计算个数
		result.append(right - left).append(input.charAt(left));
		left = right;
	}

	return result;
}

LC1419. 数青蛙

思路：

1. 创建一个 hash 表，key 是 c/r/o/a/k 这几个字符，而 val 是表示当前出现的个数
2. 遍历字符串，获取到下标，将字符对应的 val 加 1
   • 如果是 c(第一个字符），那么就要判断一下 k 对应的值有没有，如果有，那么就要把它 减 1（就是把闲置的青蛙重新取出来，让它再叫，这样可以计算出最小的青蛙数量）
   • 如果不是 c，那么就要判断一下它的前置所对应的 val 是不是为 0, 如果是 0 那么是非法元素，直接返回 -1，如果不是，那么就要把前置内容减 1
3. 在遍历完后，还需要判断一下有没有残留内容，如果有残留的，那么就要返回 -1，如果没有，那么就返回 key 所对应的 hash 值

char[] cryChars = "croak".toCharArray();
public int minNumberOfFrogs(String croakOfFrogs) {
	char[] croaks = croakOfFrogs.toCharArray();
	int n = cryChars.length;
	// 统计当前的字符的个数
	int[] cryCounts = new int[n];

	for (char croak : croaks) {
		int index = getIndex(croak);
		cryCounts[index]++;
		if (index == -1) return -1; // 没有找到字符，非法元素
		if (index == 0) {
			// 蛙叫的开始
			if (cryCounts[n - 1] > 0) cryCounts[n - 1]--; // 如果有多余的叫完的青蛙，那么就可以拿它们来重新叫
		} else {
			if (cryCounts[index - 1] <= 0) return -1; // 非法情况：前面的没有符合满足的条件
			cryCounts[index - 1]--;
		}
	}

	// 判断一下前面还有没有残留
	for (int i = 0; i < n - 1; i++) {
		if (cryCounts[i] != 0) return -1;
	}
	return cryCounts[n - 1]; // 返回最后一个数的值
}

// 获取指定元素的下标
private int getIndex(char ch) {
	for (int i = 0; i < cryChars.length; i++) {
		if (cryChars[i] == ch) return i;
	}
	return -1;
}