本文共 2157 字，大约阅读时间需要 7 分钟。

气球游戏

1 背景

面试腾讯，面试官感觉很忙，一边工作一边面试，一上来自我介绍都省了，直接就是这道题，让半小时写出来，面试的时候思路理出来了，但是平时滑动窗口写的少，自然是没写出来了，假期特地恶补了滑动窗口。发现网上还很少这道题的解法，于是简单整理了一下。题目虽然叫气球游戏，但是本质其实还是“最小覆盖字串”。

2 题目描述

小Q在进行射击气球的游戏，如果小Q在连续T枪中打爆了所有颜色的气球，将得到一只QQ公仔作为奖励。（每种颜色的气球至少被打爆一只）。

• 输入描述：

第一行两个空格间隔的整数数n，m。n<=1000000 m<=2000

第二行一共n个空格间隔的整数，分别表示每一枪打中的气球的颜色,0表示没打中任何颜色的气球。

• 输出描述：

一个整数表示小Q打爆所有颜色气球用的最少枪数。如果小Q无法在这n枪打爆所有颜色的气球，则输出-1

• 示例1

输入：

• 示例2

输入：

3 题解

• 思路：

  滑动窗口算法。先向右不断扩大窗口，满足条件是，再从左边缩小窗口找到最优解。

• 实现：

/** * @author csh * @date 2021/5/1 */public class BalloonGame {    private Integer balloonGame(int n, int m, int[] balloon) {        // 定义窗口和need        HashMap
   
     need = new HashMap<>();        HashMap
    
      window = new HashMap<>();        // m种颜色的气球        for (int i = 1; i <= m; i++)            need.put(i, 1);        // 控制窗口用的指针        int left = 0, right = 0;        // window中满need条件的个数        int valid = 0;        int res = Integer.MAX_VALUE;        while (right < n) {            // 向右扩大窗口            int num = balloon[right];            right++;            if (need.containsKey(num)) {                window.put(num, window.getOrDefault(num, 0) + 1);                if (window.get(num).equals(need.get(num))) valid++;            }            while (valid == m) {                // 记录最小窗口                res = Math.min(res, right - left);                // 缩小窗口                int num2 = balloon[left];                left++;                if (need.containsKey(num2)) {                    if (window.get(num2).equals(need.get(num2))) valid--;                    window.put(num2, window.getOrDefault(num2, 0) - 1);                }            }        }        return res == Integer.MAX_VALUE ? -1 : res;    }    public static void main(String[] args) {        int[] balloon = new int[]{2, 5, 3, 1, 3, 2, 4, 1, 0, 5, 4, 3}; // 答案：6        int[] balloon2 = new int[]{2, 5, 3, 1, 3, 2, 4, 1, 5, 0, 4, 3}; // 答案：5        BalloonGame main = new BalloonGame();        Integer res = main.balloonGame(12, 5, balloon2);        System.out.print("最少需要：" + res);    }}
    
   

转载地址：http://mrgkz.baihongyu.com/