写点什么

【LeetCode】森林中的兔子 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 04 月 04 日

题目

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


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


示例:


输入: answers = [1, 1, 2]


输出: 5


来源:力扣(LeetCode)


链接:https://leetcode-cn.com/problems/rabbits-in-forest

解题代码

public class DayCode {    public static void main(String[] args) {        int[] answers = new int[]{1, 1, 2};        int ans = new DayCode().numRabbits(answers);        System.out.println("ans is " + ans);    }
/** * 时间复杂度 O(n log n) * 空间复杂度 O(1) * @param answers * @return */ public int numRabbits(int[] answers) { int result = 0; Arrays.sort(answers); int n = answers.length; for (int i = 0; i < n; i++) { int cnt = answers[i]; result += cnt + 1; int k = cnt; while (k-- > 0 && i + 1 < n && answers[i] == answers[i + 1]) { i++; } } return result; }
}
复制代码

总结

  • 这个题目题意容易理解,重点是思维的培养。

  • 这个题目应用了贪心的思想解决。贪心算法是用计算机来模拟一个“贪心”的人做出决策的过程。这个人十分贪婪,每一步行动总是按某种指标选取最优的操作。而且他目光短浅,总是只看眼前,并不考虑以后可能造成的影响。

  • 坚持每日一题,加油!

发布于: 2021 年 04 月 04 日阅读数: 11
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】森林中的兔子Java题解