【python】Leetcode每日一题-森林中的兔子
2024-10-10 10:12:12
【python】Leetcode每日一题-森林中的兔子
【题目描述】
森林中,每个兔子都有颜色。其中一些兔子(可能是全部)告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。
返回森林中兔子的最少数量。
示例1:
示例:
输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 "1" 的兔子可能有相同的颜色,设为红色。
之后回答了 "2" 的兔子不会是红色,否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外,森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。
输入: answers = [10, 10, 10]
输出: 11
输入: answers = []
输出: 0
说明:
1. answers 的长度最大为1000。
2. answers[i] 是在 [0, 999] 范围内的整数。
【分析】
思路
解决办法就是 对于
[n,n,n,···,n]
,记num=len([···])
,则存在关系\[least(num)=\begin{cases}
n+1, & num\leq n+1\\
ceil(num/(n+1))*(n+1), & num = n+1
\end{cases}
\]即对于报相同数目的兔子序列,其具有相同颜色的兔子的最大数量为
n+1
。由此,思路就是将原数组进行排序,然后扫一遍,对报相同数目兔子求
least
,最后求总和。AC代码
class Solution:
def numRabbits(self, answers) -> int:
if answers == []:
return 0
least = 0
answers.sort()
i = 0
while i < len(answers):
p = answers[i]
if p == 0:
least += 1
i += 1
continue
num = 1
for j in range(i+1, len(answers)):
if answers[j] == p:
num += 1
else:
i = j
break
else:
i = len(answers)
least += (math.ceil(num / (p+1))) * (p+1)
return least
看过题解之后,自己的思路的核心思想是
贪心
,同时不需要排序再遍历,可以利用哈希表
统计各元素出现次数。
最新文章
- ES6之块级作用域
- [转]win 10 开始菜单(Win 7风格)增强工具 StartIsBack++ v1.3.4 简体中文特别版
- 第四十三章 微服务CICD(5)- gitlab + jenkins + docker + dockerregsitry
- 记STM32F030多通道ADC DMA读取乱序问题
- JavaScript学习笔记-商品管理新增/删除/修改功能
- Codeforces #Round 376 F 题解
- iOS验证码倒计时(GCD实现)
- [译]GotW #89 Smart Pointers
- Unity插件之NGUI学习(8)—— Table和NGUI尺寸转换为世界坐标系尺寸
- 第三题 有如下Student&#160;对象, &#160;private&#160;String&#160;name;&#160;&#160; &#160;&#160;&#160;&#160;private&#160;int&#160;age;&#160;&#160; &#160;&#160;&#160;&#160;private&#160;int&#160;score;&#160;&#160; private&#160;String&#160;classNum;&#160; 其中,classNum&
- Python 内置方法
- xcode更换启动图显示空白launchImg
- Python基础-元组、列表、字典
- leetcode1011
- python基础学习10----集合
- 联想一体机u盘启动设置
- 光速 React
- angular指令中的scope绑定策略
- 老曹眼中的Linux基础
- 【转】巫师3:狂猎(The Witcher 3: Wild Hunt )的游戏事件工作流
热门文章
- WPF 应用 - 图表 LiveCharts
- kali Linux树莓派的完整配置,以及python环境的配置
- Flask面试问题
- 海岸线、科赫曲线、turtle、递归
- P1579_哥德巴赫猜想(JAVA语言)
- RabbitMQ 入门 (Go) - 1. 简介和安装
- SDK音频测试流程
- MarkDown-简单学习
- 基于ZXing.Net生成一维二维码
- react项目运行安装依赖报错:Error: pngquant failed to build, make sure that libpng-dev is installed