腾讯一面之气球游戏

腾讯一面之气球游戏"/>

腾讯一面之气球游戏

题目原文

小Q在进行射击气球的游戏，如果小Q在连续T枪中打爆了所有颜色的气球，将得到一只QQ公仔作为奖励。（每种颜色的球至少被打爆一只）。
这个游戏中有m种不同颜色的气球，编号1到m。
小Q一共有n发子弹，然后连续开了n枪。
小Q想知道在这n枪中，打爆所有颜色的气球最少用了连续几枪？

原始连接

思路与解答

这个题目一开始是琢磨题目了半天，后面自己整理了一下，基本就是不断开枪，开枪之后数字就代表颜色编号，因为颜色可以重复的，题目是问里面连续中枪的时候可以覆盖全部的颜色。

直观上来说其实就是需要连续的一段数字里面可以保证包含所有的颜色，图中两个箭头都满足，但是我们需要的是最短的射击次数，所以后面的才是要的答案。
这种两边夹住一部分结果进行判断的操作其实都是窗口的思想。
我们可以定义两个指针，左边和右边，两个指针都是递增的，
1、当我们移动右边边的指针的时候保证窗口内可以包含所有元素，当满足条件的时候停止
2、我们移动左边指针，意味着窗口内元素会减少，当我们减少元素的时候，不断判断是否窗口内还是满足全部的元素
3、窗口内的元素个数我们计数，在窗口里面则每出现一次就+1，移除的时候则减一，当窗口里面每次移除的时候我们更新路径

代码示例

 public static int search(int[] nums, int colorCount) {int left = 0;int right = 0;int[] colorCnts = new int[colorCount + 1]; //记录窗口内颜色的个数，因为颜色不会从0开始，所以数组个数+1int curColor = colorCount;Arrays.fill(colorCnts, 1);colorCnts[0] = 0;int window = Integer.MAX_VALUE;while (right < nums.length) {int rightNumber = nums[right];right++;if (colorCnts[rightNumber]-- > 0) {curColor--;}while (curColor == 0) {if (right - left < window) {window = right - left;}int leftNumber = nums[left];left++;if (colorCnts[leftNumber]++ == 0) {curColor++;}}}return window == Integer.MAX_VALUE ? -1 : window;}

代码说明，我们提前把窗口内颜色对应的数字都做标记，里面有1的就是存在的标记
当right往右边移动时，颜色进入窗口，我们把颜色数量往下减，直到数量是0的时候，说明全部颜色都覆盖了，此时移动左边指针，颜色出窗口的时候颜色标记+1