【LeetCode系列】森林中的兔子与子域名访问计数

⭐️前面的话⭐️

本篇文章介绍来自力扣题解，分别为【森林中的兔子】和【子域名访问计数】，展示语言java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆首发时间：🌴2022年12月30日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

781. 森林中的兔子

781. 森林中的兔子

难度中等230

森林中有未知数量的兔子。提问其中若干只兔子 “还有多少只兔子与你（指被提问的兔子）颜色相同?” ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

示例 1：

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

示例 2：

输入：answers = [10,10,10]
输出：11

提示：

• 1 <= answers.length <= 1000
• 0 <= answers[i] < 1000

数学+贪心

class Solution {
    public int numRabbits(int[] answers) {
        //哈希表对回答的答案进行计数 数据范围为1000
        int[] hash = new int[1010];
        for (int x : answers) hash[x]++;
        int n = answers.length;
        int ans = 0;
        for (int i = 0; i < 1001; i++) {
            int cnt = hash[i];
            int pre = i + 1;

            //相同回答不同颜色组数k
            int k = cnt / pre;
            if (k * pre < cnt) k++;
            ans += pre * k;
        }
        return ans;
    }
}

811. 子域名访问计数

811. 子域名访问计数

难度中等148

网站域名 "discuss.leetcode.com" 由多个子域名组成。顶级域名为 "com" ，二级域名为 "leetcode.com" ，最低一级为 "discuss.leetcode.com" 。当访问域名 "discuss.leetcode.com" 时，同时也会隐式访问其父域名 "leetcode.com"以及 "com" 。

计数配对域名 是遵循 "rep d1.d2.d3" 或 "rep d1.d2" 格式的一个域名表示，其中 rep 表示访问域名的次数，d1.d2.d3 为域名本身。

• 例如，"9001 discuss.leetcode.com" 就是一个 计数配对域名 ，表示 discuss.leetcode.com 被访问了 9001 次。

给你一个 计数配对域名 组成的数组 cpdomains ，解析得到输入中每个子域名对应的 计数配对域名 ，并以数组形式返回。可以按 任意顺序 返回答案。

示例 1：

输入：cpdomains = ["9001 discuss.leetcode.com"]
输出：["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
解释：例子中仅包含一个网站域名："discuss.leetcode.com"。
按照前文描述，子域名 "leetcode.com" 和 "com" 都会被访问，所以它们都被访问了 9001 次。

示例 2：

输入：cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
输出：["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
解释：按照前文描述，会访问 "google.mail.com" 900 次，"yahoo.com" 50 次，"intel.mail.com" 1 次，"wiki.org" 5 次。
而对于父域名，会访问 "mail.com" 900 + 1 = 901 次，"com" 900 + 50 + 1 = 951 次，和 "org" 5 次。

提示：

• 1 <= cpdomain.length <= 100
• 1 <= cpdomain[i].length <= 100
• cpdomain[i] 会遵循 "repi d1i.d2i.d3i" 或 "repi d1i.d2i" 格式
• repi 是范围 [1, 104] 内的一个整数
• d1i、d2i 和 d3i 由小写英文字母组成

基本思路： 字符串模拟题

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        int n = cpdomains.length;
        List<String> ans = new ArrayList<>();
        //字符串模拟题
        HashMap<String, Integer> hash = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String str = cpdomains[i];
            String[] ss = str.split(" ");
            String location = ss[1];
            int cnt = Integer.parseInt(ss[0]);
            String[] ls = location.split("\\.");
            int size = ls.length;
            //System.out.println(ls);
            //System.out.println(size);

            String key1 = ss[1];
            String key2 = ls[size - 1];
            String key3 = ls[size - 2] + "." + ls[size - 1];

            hash.put(key1, hash.getOrDefault(key1, 0) + cnt);
            hash.put(key2, hash.getOrDefault(key2, 0) + cnt);
            if (!key1.equals(key3)) hash.put(key3, hash.getOrDefault(key3, 0) +  cnt); 
            
        }

        for (String s : hash.keySet()) {
            String ret = hash.get(s) + " " + s;
            ans.add(ret);
        }
        return ans;
    }
}