[LeetCode] 811. Subdomain Visit Count

jzman 发布于2019-08-19 11:11 / 2851人阅读

Problem

A website domain like "discuss.leetcode.com" consists of various subdomains. At the top level, we have "com", at the next level, we have "leetcode.com", and at the lowest level, "discuss.leetcode.com". When we visit a domain like "discuss.leetcode.com", we will also visit the parent domains "leetcode.com" and "com" implicitly.

Now, call a "count-paired domain" to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be "9001 discuss.leetcode.com".

We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.

Example 1:

Input: 
["9001 discuss.leetcode.com"]
Output: 
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]

Explanation:
We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

Example 2:

Input: 
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output: 
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]

Explanation:
We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.

Notes:

The length of cpdomains will not exceed 100.
The length of each domain name will not exceed 100.
Each address will have either 1 or 2 "." characters.
The input count in any count-paired domain will not exceed 10000.
The answer output can be returned in any order.

Solution

class Solution {
    public List subdomainVisits(String[] cpdomains) {
        Map map = new HashMap<>();
        for (String domain: cpdomains) {
            String[] cp = domain.split(" ");
            Integer value = Integer.valueOf(cp[0]);
            String key = cp[1];
            while (key.length() > 0) {
                if (!map.containsKey(key)) map.put(key, value);
                else map.put(key, map.get(key)+value);
                
                //O(m*n) = O(key.length*1)
                Integer i = key.indexOf(".");
                if (i > 0) key = key.substring(i+1);
                else break;
            }
        }
        List res = new ArrayList<>();
        for (Map.Entry entry: map.entrySet()) {
            String row = Integer.toString(entry.getValue()) + " " + entry.getKey();
            res.add(row);
        }
        return res;
    }
}

Update with String.indexOf(), people saying it"s faster than String.split()

class Solution {
    public List subdomainVisits(String[] cpdomains) {
        Map map = new HashMap<>();
        for (String domain: cpdomains) {
            int i = domain.indexOf(" ");
            Integer value = Integer.valueOf(domain.substring(0, i));
            String key = domain.substring(i+1);
            while (key.length() > 0) {
                map.put(key, map.getOrDefault(key, 0)+value);
                i = key.indexOf(".");   // if "." not exists, i = -1
                if (i > 0) key = key.substring(i+1);
                else break;
            }
        }
        List res = new ArrayList<>();
        for (Map.Entry entry: map.entrySet()) {
            String row = entry.getValue() + " " + entry.getKey();
            res.add(row);
        }
        return res;
    }
}

GPU云服务器云服务器 Subdomain Visit js811 LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77173.html

Leetcode PHP题解--D36 811. Subdomain Visit Count

摘要：题目链接题目分析题目给定一个字符串数组，每个字符串分两部分，以空格分割。第一部分为访问次数，第二部分为域名。要求按同样的格式，分别返回顶级域名二级域名三级域名的访问次数。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 811. Subdomain Visit Count 题目链接 811. Subdomain Visit Count 题目分析题目给定一个字符串数组，每个字符串分两部...

inapt 2019-07-01 12:42 评论0 收藏0
811-子域名访问计数

摘要：作为顶级域名，常用的有，下一级则有，最低的一级为。当我们访问域名时，也同时访问了其父域名以及顶级域名。输入中任意一个域名的访问次数都小于。前言 LeetCode上一道不算难的题目，但是一开始做的时候，执行时间很不理想，通过多次修改代码，总算是改到比较满意的地步。原题目如下：一个网站域名，如discuss.leetcode.com，包含了多个子域名。作为顶级域名，常用的有com，下...

史占广 2019-08-19 11:04 评论0 收藏0
leetcode100 Same Tree 引发的对遍历?算法的思考

摘要：判断两棵树是否是相同题目要求传入两棵树的根节点，判断这两棵树是否相同此题的核心就在于如何遍历树。定义树的一种自然方式是递归的方式。一棵树是一些节点的集合，这个集合可以是空集。这个遍历算法可以用于场景如，计算一个节点的高度。判断两棵树是否是相同题目要求：传入两棵树的根节点，判断这两棵树是否相同此题的核心就在于如何遍历树。一旦我们解决了这个问题，题目也就迎刃而解了。下面就来介绍一下关...

cyrils 2019-08-14 17:52 评论0 收藏0
sqlalchemy使用count时遇到的坑

摘要：在用对一个千万级别表进行操作时，出现了耗时严重内存飙升的情况。在用flask-sqlalchemy对一个千万级别表进行count操作时，出现了耗时严重、内存飙升的情况。要统计出一天内车辆访问次数，原代码如下： car_visit_counts = CarVisit.query.filter( CarVisit.park == car_visit.park, CarVi...

马永翠 2019-07-31 10:31 评论0 收藏0
http cookie解释

摘要：可选项部分只会在浏览器端使用，而不会被发送至服务器端。包括过期时间选项，过期时间选项过期时间，指定了何时不会再被发送至服务器，随后浏览器将删除该。浏览器和Webserver之间的关系，被设计为无状态的，这是一个很重要的设计，可以让客户端无需和服务器保持状态，节省宝贵的端口资源，从而可以为更多的客户链接服务。但是这样带来了问题，简言之，服务器无法知道两个请求是否来自于同一个浏览器。然...

livem 2019-08-22 15:51 评论0 收藏0