[LeetCode] 811. Subdomain Visit Count

jzman 發布于2019-08-19 11:11 / 2886人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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