这是悦乐书的第320次更新，第341篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第189题（顺位题号是811）。像“discuss.leetcode.com”这样的网站域名由各种子域组成。在顶级，我们有“com”，在下一级，我们有“leetcode.com”，在最低级别，“discuss.leetcode.com”。当我们访问像“discuss.leetcode.com”这样的域名时，我们也会隐含地访问父名“leetcode.com”和“com”。
现在，将“计数配对域名”称为计数（表示此域收到的访问次数），后跟空格，后跟地址。计数配对域名的示例可以是“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;
}
03 小结
算法专题目前已日更超过五个月，算法题文章189+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论