博客
关于我
781. 森林中的兔子 Java
阅读量:351 次
发布时间:2019-03-04

本文共 1881 字,大约阅读时间需要 6 分钟。

  1. 森林中的兔子
    森林中,每个兔子都有颜色。其中一些兔子(可能是全部)告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。

返回森林中兔子的最少数量。

示例:

输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 “1” 的兔子可能有相同的颜色,设为红色。
之后回答了 “2” 的兔子不会是红色,否则他们的回答会相互矛盾。
设回答了 “2” 的兔子为蓝色。
此外,森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。

输入: answers = [10, 10, 10]

输出: 11

输入: answers = []

输出: 0
说明:

answers 的长度最大为1000。

answers[i] 是在 [0, 999] 范围内的整数。

两种情况:

1、同种颜色的兔子所回应的数量一定是相同的
2、有可能有不同颜色的兔子回应了同样的数量
思路:
先对数组进行排序,利用哈希表保存回应相同数量的兔子的数量。
1、若 value(回应的兔子数量)等于 key(回应的数量)+ 1 ,意味着这个颜色的兔子全部都回应了;
2、若 value 大于 key + 1,则意味着有不同颜色的兔子回应了相同的数量;
3、若 value 小于 key + 1,则意味着该颜色的兔子并没有全部回应
具体代码如下

import java.util.Map.Entry;class Solution {   	public static int numRabbits(int[] answers) {   		if( answers.length == 0 ) return 0;  // 如果没有任何回应,则返回0        Arrays.sort(answers);		int count = 0;        Map
map = new HashMap
(); int loc = 0; // 保存该回应数量的开始位置 for( int i = 1; i < answers.length; i++) { if( answers[i] != answers[i-1] ) { // 此时的 i 指向的是下一回应数量的位置 map.put(answers[i-1], i - loc); loc = i; } } map.put(answers[answers.length-1], answers.length - loc); Set
> set = map.entrySet(); for( @SuppressWarnings("rawtypes") Entry entry : set ){ // 注:key + 1 代表该颜色的兔子总共拥有的数量 int key = (int)entry.getKey(); int value = (int)entry.getValue(); if( value == key + 1 ) { // 如果该颜色的兔子全部都回应了 count += (int)entry.getValue(); // 直接相加 } else { if( value < key + 1 ) { // 如果该颜色的兔子没有全部回应 count += key + 1; } else if( value > key + 1 ) { // 如果有其他颜色的兔子也回应相同的数量 while( value > key + 1 ) { count += key + 1; value -= key + 1; } count += key + 1; } } } return count; }}

转载地址:http://ploe.baihongyu.com/

你可能感兴趣的文章
mysql 敲错命令 想取消怎么办?
查看>>
Mysql 整形列的字节与存储范围
查看>>
mysql 断电数据损坏,无法启动
查看>>
MySQL 日期时间类型的选择
查看>>
Mysql 时间操作(当天,昨天,7天,30天,半年,全年,季度)
查看>>
MySQL 是如何加锁的?
查看>>
MySQL 是怎样运行的 - InnoDB数据页结构
查看>>
mysql 更新子表_mysql 在update中实现子查询的方式
查看>>
MySQL 有什么优点?
查看>>
mysql 权限整理记录
查看>>
mysql 权限登录问题:ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: YES)
查看>>
MYSQL 查看最大连接数和修改最大连接数
查看>>
MySQL 查看有哪些表
查看>>
mysql 查看锁_阿里/美团/字节面试官必问的Mysql锁机制,你真的明白吗
查看>>
MySql 查询以逗号分隔的字符串的方法(正则)
查看>>
MySQL 查询优化:提速查询效率的13大秘籍(避免使用SELECT 、分页查询的优化、合理使用连接、子查询的优化)(上)
查看>>
mysql 查询数据库所有表的字段信息
查看>>
【Java基础】什么是面向对象?
查看>>
mysql 查询,正数降序排序,负数升序排序
查看>>
MySQL 树形结构 根据指定节点 获取其下属的所有子节点(包含路径上的枝干节点和叶子节点)...
查看>>