【LeetCode】你能在你最喜欢的那天吃到你最喜欢的糖果吗?Java 题解
题目描述
给你一个下标从 0 开始的正整数数组 candiesCount ,其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。同时给你一个二维数组 queries ,其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi] 。
你按照如下规则进行一场游戏:
你从第 0 天开始吃糖果。你在吃完 所有 第 i - 1 类糖果之前,不能 吃任何一颗第 i 类糖果。在吃完所有糖果之前,你必须每天 至少 吃 一颗 糖果。请你构建一个布尔型数组 answer ,满足 answer.length == queries.length 。answer[i] 为 true 的条件是:在每天吃 不超过 dailyCapi 颗糖果的前提下,你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果;否则 answer[i] 为 false 。注意,只要满足上面 3 条规则中的第二条规则,你就可以在同一天吃不同类型的糖果。
请你返回得到的数组 answer 。
思路分析
这个题目题干比较长,需要认真阅读才能理解题意。
分析题意之后,题目核心是分析第 favoriteDay 天能不能吃到 favoriteType 类型糖果。由此,可以得到一个区间范围,最小吃到的糖果数量是 favoriteDay + 1, 最大吃到的糖果数量是 (favoriteDay + 1) * dailyCap。在此区间范围的累计糖果数即可满足条件,返回 true;
AC 代码
总结
上述算法代码的时间复杂度是 O(n), 空间复杂度是 O(1)
在计算糖果数时,采用了前缀和的方法。前缀和是一种重要的预处理,能大大降低查询的时间复杂度。
求前缀和的代码十分经典,熟练掌握可以提升解题效率。
坚持每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/e7437de1432ffaa24ab2e1962】。文章转载请联系作者。
评论