一道算法题:对哈希表Python、C++标准库的一些思索

举报
irrational 发表于 2022/03/09 22:37:26 2022/03/09
【摘要】 leetcode374. 子域名访问计数 难度:中等 收藏 网站域名 "discuss.leetcode.com" 由多个子域名组成。顶级域名为 "com" ,二级域名为 "leetcode.com...

leetcode374. 子域名访问计数

难度:中等

收藏

网站域名 "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 次。

  
 
  • 1
  • 2
  • 3
  • 4

示例 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
  • 2
  • 3
  • 4

提示:

  • 1 <= cpdomain.length <= 100
  • 1 <= cpdomain[i].length <= 100
  • cpdomain[i] 会遵循 "repi d1i.d2i.d3i""repi d1i.d2i" 格式
  • repi 是范围 [1, 104] 内的一个整数
  • d1id2id3i 由小写英文字母组成
class Solution:
    def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
        cnt={}
        for str1 in cpdomains:
            k=str1.find(' ')
            a,b=str1.split(' ')
            a=int(a)
            str1=str1[k+1:]
            while True:
                try:
                    cnt[str1] +=a
                except:
                    cnt[str1] = a
                k=str1.find('.')
                
                if k==-1:
                    break
                str1=str1[k+1:]
        res=[]
        for item in cnt:
            res.append(str(cnt[item])+' '+item)
        return res
            

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

C++:由调通答案代码简单改编,供理解

#include<bits/stdc++.h>
#include<vector>
using namespace std;
vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> cnt;
        for (auto& str: cpdomains) {
            cout<<str<<endl;
            int k = str.find(' ');//返回空格位置的下标
            printf("k=%d\n",k);
            cout<<str.substr(0, k)<<endl;//substr左闭右开,也就是找到了空格为k,那么就是左边的子串
            int c = stoi(str.substr(0, k));//string to int "900"->900
            printf("c=%d\n",c);
            str = str.substr(k + 1);//空格往后的子串
            cout<<str<<endl;
            while (true) {
                cnt[str] += c;//从左往右,对各个域名+访问次数
                k = str.find('.');//从左往右,找到第一个'.'的下标
                printf("now k=%d\n",k);
                if (k == -1) break;
                str = str.substr(k + 1);
            }
        }
        vector<string> res;
        for (auto& [k, v]: cnt)
            res.push_back(to_string(v) + ' ' + k);
        for (int k=0;k<res.size();k++)
        cout<<res[k]<<endl;
        return res;
    }
int main(){
    string str[]={"900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
    vector<string> strArray(str, str+4);
    subdomainVisits(strArray);
   	return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

文章来源: blog.csdn.net,作者:irrationality,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/weixin_54227557/article/details/123353736

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。