奇安信笔试09.12 题一万圣节讨糖果【滑动窗口】

╰半夏微凉° 2022-12-06 04:30 161阅读 0赞

**2020-09.12 奇安信笔试题一**

### 问题描述 ###

M包糖果，抛M次硬币，使用魔法使硬币连续n次为正面，最多能得到多少颗糖果。（魔法最多能使用一次）

**case**

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * M包糖果，抛M次硬币，硬币连续n次为正面，最多能得到多少颗糖果 * * @param candies int整型一维数组 每包糖果的数量 * @param coin int整型一维数组 抛硬币的结果 * @param n int整型 连续是正面的次数 * @return int整型 * 【测试用例】 * [3,5,7,2,8,8,15,3], [1,0,1,0,1,0,1,0], 3 * 【输出】 * 41 */

### 解题思路 ###

**用滑动窗口，将糖果数组分为三部分**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIzMjk1NQ_size_16_color_FFFFFF_t_70_pic_center]  
**每部分使用三个while循环**

public static int maxCandies(int[] candies, int[] coin, int n) { 
        if (candies.length != coin.length) return 0;
        int total = 0;
        for (int i = 0; i < candies.length; i++) { 
            int ans = 0, j = 0;
            int count = n;
            //窗口左侧的值
            while (j < i) { 
                if (coin[j] == 0) ans += candies[j];
                j++;
            }
            //窗口内的值
            while (j < candies.length && count > 0) { 
                ans += candies[j++];
                count--;
            }
            //剩下的值
            while (j < candies.length) { 
                if (coin[j] == 0) ans += candies[j];
                j++;
            }
            total = Math.max(total, ans);
        }
        return total;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIzMjk1NQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/e2986f73ad9349fb916564b0b6e8f970.png