RabbitsInForest [source code]
public class RabbitsInForest {
static
/******************************************************************************/
class Solution {
public int numRabbits(int[] answers) {
if (answers.length == 0)
return 0;
int[] counts = new int[1000];
for (int i = 0; i < answers.length; i++) {
counts[answers[i]]++;
}
int res = 0;
res += counts[0];
for (int i = 1; i < 1000; i++) {
int group_max_size = i + 1;
res += ((counts[i] + group_max_size - 1) / group_max_size) * group_max_size;
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
RabbitsInForest.Solution tester = new RabbitsInForest.Solution();
int[][] inputs = {
{1,1,2}, {5},
{}, {0},
{10, 10, 10}, {11},
};
for (int i = 0; i < inputs.length / 2; i++) {
int[] answers = inputs[2 * i];
int ans = inputs[2 * i + 1][0];
System.out.println (Printer.separator ());
int output = tester.numRabbits (answers);
System.out.printf ("[%s] -> %s, expected: %d\n",
Printer.array (answers), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
contest做掉的, 写的时候感觉还是挺有意思的; 速度是8ms (NA);
核心的intuition就是, 每一个兔子反正告诉了你他自己的亲戚有多少, 这个是无法改变的, 那么为了让兔子的总数最少, 就让大家尽可能的共享亲戚; 那么报的亲戚个数相等的, 干脆就是一家人就行了;
当然了, 报数相同的兔子实际上有可能不是亲戚, 但是这个对于题目本身无所谓; 5个红兔子和5个蓝兔子最后贡献的都是10个兔子;
基本就是理解了题目的意思之后, 一点数学计算就行了, 感觉不是特别难; 不过这种数学多的题目, 果然被大量downvote了;
editorial
Approach #1: Count [Accepted]
Intuition
Each rabbit that says a different number must be a different color, and a rabbit only tells us information about rabbits of its color. We can count the number of rabbits of each color separately.
Now, say 13 rabbits answer 5. What does this imply? Say one of the rabbits is red. We could have 5 other red rabbits in this group answering 5, but not more. So, say another rabbit in this group is a different color (blue). We could have 5 other blue rabbits in this group answering 5, but not more. Finally, another rabbit must be a different color (green), and there are 5 other green rabbits (in the forest).
Notice there must be a minimum of 18 rabbits saying 5 (answering or in the forest), since there must be at least 3 unique colors among rabbits that answered or would have answered 5, so it didn't matter that we chose the rabbits to be grouped by color or not when answering.
这个想法是有问题的, 这18只兔子是完全可以是同样的颜色的; 不对, 不可以; 18只红兔子的话, 那么每一个人报数的应该是17; 忘记题目的意思了;
Algorithm
In general, if v = count[k] rabbits answered k, there must be at least a rabbits that answered or would have answered k, where a is the smallest multiple of k+1 such that a >= count[k].
We add all these as together.
class Solution {
public int numRabbits(int[] answers) {
int[] count = new int[1000];
for (int x: answers) count[x]++;
int ans = 0;
for (int k = 0; k < 1000; ++k)
ans += Math.floorMod(-count[k], k+1) + count[k];
return ans;
}
}
跟我的一点差别就是, 不用专门处理0, 第二个就是他这个floorMod, 我不知道用法; 不对啊, 怎么叫不需要考虑0, 我觉得0不单独处理反而比较笨, 本身就是直接一个+= 就结束了;
这些乱七八糟的函数反正我也记不住, 他这里算的时候还要自己用调整参数的小技巧, 算了, 还是自己手动算好了;
round
这个是Pintos里面学来的:
#ifndef __LIB_ROUND_H
#define __LIB_ROUND_H
// Yields X rounded up to the nearest multiple of STEP. For X >= 0, STEP >= 1 only.
#define ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP) * (STEP))
// Yields X divided by STEP, rounded up. For X >= 0, STEP >= 1 only.
#define DIV_ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP))
// Yields X rounded down to the nearest multiple of STEP. For X >= 0, STEP >= 1 only.
#define ROUND_DOWN(X, STEP) ((X) / (STEP) * (STEP))
// There is no DIV_ROUND_DOWN. It would be simply X / STEP.
#endif // lib/round.h
https://leetcode.com/problems/rabbits-in-forest/discuss/114719/My-easy-Java-HashMap-solution
class Solution {
public int numRabbits(int[] answers) {
int res = 0;
Map<Integer,Integer> map = new HashMap<>();
for(int answer : answers){
map.put(answer,map.getOrDefault(answer,0)+1);
}
for(Integer n : map.keySet()){
int group = map.get(n)/(n+1);
res += map.get(n)%(n+1) != 0 ? (group+1)*(n+1) : group*(n+1);
}
return res;
}
}
他们这个处理方法也挺有意思的, 直接判断是否是整数倍;
If x+1 rabbits have same color, then we get x+1 rabbits who all answer x.
now n rabbits answer x.
If n%(x+1)==0, we need n/(x+1) groups of x+1 rabbits.
If n%(x+1)!=0, we need n/(x+1) + 1 groups of x+1 rabbits.the number of groups is math.ceil(n/(x+1)) and it equals to (n+i)/(i+1) , which is more elegant.
public int numRabbits(int[] answers) {
Map<Integer, Integer> m = new HashMap<>();
for (int i : answers) m.put(i, m.getOrDefault(i, 0) + 1);
int res = 0;
for (int i : m.keySet()) res += (m.get(i) + i) / (i + 1) * (i + 1);
return res;
}
https://leetcode.com/problems/rabbits-in-forest/discuss/114714/Java-Simple-Solution
public int numRabbits(int[] answers) {
HashMap<Integer, Double> map = new HashMap();
for (int num : answers) {
map.put(num, map.getOrDefault(num, 0.0) + 1);
}
int res = 0;
for (int key : map.keySet()) {
res += (key + 1) * Math.ceil(map.get(key) / (key + 1));
}
return res;
}
按理说ceil函数应该还是熟悉的; 虽然其实自己写也不麻烦;
https://leetcode.com/problems/rabbits-in-forest/discuss/114710/Java-Solution
class Solution {
public int numRabbits(int[] answers) {
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
int sum = 0;
for(Integer num : answers){
int count = counts.getOrDefault(num+1, 0);
if(count%(num+1)==0) sum+=(num+1);
if(count < num+1)
counts.put(num + 1, count+1);
else
counts.put(num+1,1);
}
return sum;
}
}
看起来是比较不错的1pass, 不过我觉得这个做法最后是否划算还很难说, 因为实际上用于对这个Map的存取的时间也是非常严重的, 而且逻辑也更绕人了;
另外, 他这里的key用的直接就是group size, 这个其实跟普通的用answer做key是没有太大区别的: 自己看他put和get用的都是num + 1, 就理解实际上就是一个offset而已;
public int numRabbits(int[] a) {
Arrays.sort(a);
int total = 0, r = 0;
for(int i = 0; i < a.length; i++) {
if (r-- == 0 || a[i] != a[i-1]) {
r = a[i];
total += a[i]+1;
}
}
return total;
}
画了一个trace之后看懂了; 通过sort把报数相同的放在一起, 然后用类似之前的思路来处理; r是一个group的size, 如果用完了就重新补仓; 比如1 2 2 2 2 3 3这里, 对于2, 就要补仓两次(两个3才能容纳); 这个算法设计的还是可以的, 尤其是对于r的更新: decrement和override(assignment)的结合;
没有submission;
Problem Description
In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.
Return the minimum number of rabbits that could be in the forest.
Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.
Input: answers = [10, 10, 10]
Output: 11
Input: answers = []
Output: 0
``` Note:
- answers will have length at most 1000.
- Each answers[i] will be an integer in the range [0, 999].
Difficulty:Medium
Total Accepted:2K
Total Submissions:4.2K
Contributor:awice