每日leetcode第0083天 0781. Rabbits in Forest

这是一道有趣的数学方面的问题。

今天刚好是中秋节,我们就不管月宫的兔子,来数数森林中的兔子吧。

比如我们遇到了2只兔子说7,那么他们俩可能是颜色一样的,也就是这个颜色兔子得有8只。

比如我们遇到了8只兔子说7,那么这8只可能是颜色一样的,也就是这个颜色兔子得有8只。

比如我们遇到了9只兔子说7,那么不可能是颜色都一样的,也就是这个颜色兔子至少得有16只。

比如我们遇到了17只兔子说7,那么不可能是颜色都一样的,也就是这个颜色兔子至少得有24只。

我们会发现规律,兔子的只数,取决于他们说的数字和多少只说了同样的数字。

1个7,为8只。

2个7,为8只。

3个7,为8只。

4个7,为8只。

5个7,为8只。

6个7,为8只。

7个7,为8只。

8个7,为8只。

9个7,为16只。

也就是拿报号的只数除以8,除完得是向上去整,最后乘以8。

那么向上去整怎么做呢?以8为例,有两种方案:

((报号只数 – 1) / 8) + 1 这样就向上去整了最终结果+1,但也考虑刚好整除,所以预先-1。

(报号只数 + (8 – 1)) / 8 这样也可以向上去整,因为刚好整除的加上7也不够多一位。

 

处理完每一种兔子报的数字和兔子的数量的关联系后,我们就差用什么数据结构来装这些兔子报的号码了。

把数字都存起来,然后再数,时间复杂度会较高。

我们用桶排序来装的话,可以实现,但怕某一只兔子报个很大的数字,这样我们得开很大的数组。空间又是问题。

所以最佳方案应该是哈希表,如果这个数字有,那就这个数字的数量+=1,如果没有,就建立键值对,值开始就是1。

最终根据哈希表的迭代器来加总输出。

 

真是一道有趣的题目,祝大家中秋节快乐。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。