LeetCode算法题-Subdomain Visit Count（Java实现）

佚名 5年前 (2019-04-29) 算法 1768人围观抢沙发百度已收录

这是悦乐书的第320次更新，第341篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第189题（顺位题号是811）。像“discuss.leetcode.com”这样的网站域名由各种子域组成。在顶级，我们有“com”，在下一级，我们有“leetcode.com”，在最低级别，“discuss.leetcode.com”。当我们访问像“discuss.leetcode.com”这样的域名时，我们也会隐含地访问父名“leetcode.com”和“com”。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

现在，将“计数配对域名”称为计数（表示此域收到的访问次数），后跟空格，后跟地址。计数配对域名的示例可以是“9001 discuss.leetcode.com”。

给出了计数配对域名的cpdomains数组，以相同的格式，返回所有域名和访问次数组成的字符串数组。例如：

输入：[“9001 discuss.leetcode.com”]

输出：[“9001 discuss.leetcode.com”，“9001 leetcode.com”，“9001 com”]

说明：我们只有一个网站域名：“discuss.leetcode.com”。如上所述，还将访问子域“leetcode.com”和“com”。所以他们将被访问9001次。

输入：[“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”访问一次，“wiki.org”访问5次。对于子域名，我们将访问“mail.com”900 + 1 = 901次，“com”900 + 50 + 1 = 951次，以及“org”5次。

注意：

cpdomains的长度不会超过100。
每个域名的长度不超过100。
每个地址都有1或2个“.”字符。
任何计数配对域名中的访问次数不会超过10000。
答案输出可以按任何顺序返回。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 解题

每个域名加访问次数组成的字符串，根据域名中的点号，可以分为两种情况：

（1）域名中只有一个点号时，可以拆分成两个新的字符串，一是访问次数加最后面的顶级域名，二是访问次数加域名本身。

（2）域名中有两个点号时，可以拆分成三个新的字符串，一是访问次数加最后面的顶级域名，二是访问次数加第二级域名加顶级域名，三是访问次数加域名本身。

而顶级域名或者二级域名加顶级域名可能会重复出现，但是点击次数要进行累加，所以借助HashMap来存储数组，key为域名，value为访问次数。

整体思路是遍历cpdomains数组，拆分每一组计数配对域名，存入HashMap中，遍历HashMap存入List中，返回List。

public List<String> subdomainVisits(String[] cpdomains) {
    List<String> list = new ArrayList<String>();
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    for (String str : cpdomains) {
        // 根据空格进行第一次拆分
        String[] arr = str.split(" ");
        // 对第一次拆分的结果以点号进行二次拆分
        String[] arr2 = arr[1].split("\\.");
        // 第一次拆分中，域名的访问次数
        int count = Integer.valueOf(arr[0]);
        String current = "";
        int n = arr2.length-1;
        // 从后往前遍历第二次拆分的结果，存入HashMap
        for (int i=n; i >= 0; i--) {
            current = arr2[i] + (i<n ? "." : "") + current;
            map.put(current, map.getOrDefault(current, 0)+count);
        }
    }
    for (String key : map.keySet()) {
        list.add(map.get(key)+" "+key);
    }
    return list;
}