LeetCode 811. Subdomain Visit Count

题目描述 LeetCode 811

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.

中文描述

见例子就好

解题思路

这道题考察的特别扎实，看代码吧

C语言代码

这道题目很有挑战力，所以为了更好地写好这道题目，更好地反思回顾，我会讲的很细，简而言之分模块。听说集齐七颗龙珠（模块）就能召唤神龙（最终程序），现在就来随我集龙珠吧！！！

  • 1，连接数字和字符串的 C 语言代码，也就是说，把数字和字符串拼接起来，再放到字符串中。
# include <stdio.h>
# include <string.h>

void xx(char temp[], int x)
{
    int i = 0;
    int length = 0;
    char tmp;

    while(x != 0)
    {
        temp[length ++ ] = x%10 + '0';
        x = x/10;
    }

    // 反转 ，当执行while之后，temp数组中存放，1009，反转之后存放 9001
    for (i = 0; i < length/2; i ++)
    {
        tmp = temp[i];
        temp[i] = temp[length - i - 1];
        temp[length -i - 1] = tmp;
    }
    temp[length ++] = ' ';
    temp[length] = '\0';
}

main()
{
    int a = 9001;
    char b[100] = "discuss.leetcode.com"; 
    char temp[100];

    xx(temp, a);      // 将数字 a = 9001 转化为单个字符，存放到 temp 字符串数组中

    strcat(temp, b);  // 拼接数字字符串 和 字符串
    printf("%s\n\n", temp);

    printf("%c   ", 8 + '0');   // 将数字转化为字符
    printf("%d   ", '8' - '0'); // 将字符转化为数字
    printf("\n\n");
}
  • 2，实现 Example 1 之不完全版
# include <stdio.h>
# include <string.h>

int dd(int size)
{
    int i = 0;
    int sum = 1;

    for ( i = 0; i < size; i ++)
    {
        sum *= 10;
    }

    return sum;
}

int charinverseint(char number[])
{
    int size = strlen(number);
    int i;
    int sum = 0;

    for (i = 0; i < size; i ++)
    {
        sum += (number[i] - '0') * dd(size - i - 1);
    }

    return sum;
}

void subdomainVisits(char** cpdomains, int cpdomainsSize, int* returnSize) 
{
    int i, j;
    int len = 0;
    int flag = 0;
    char domains[100][100];
    int domains_i = 0 , domains_j = 0;
    char str_int[20];

    len = strlen( * ( cpdomains ) );
    for ( i = 0; i < len; i ++ )
    {
        domains_j = 0;
        if( * ( * (cpdomains ) + i) == ' ' || * ( * (cpdomains ) + i ) == '.')
        {
            flag ++;
            for (j = i + 1; j < len; j ++)
            {
                domains[domains_i][domains_j ++ ] = * ( * (cpdomains ) + j) ;
            }
            domains[domains_i][domains_j] = '\0';
            domains_i ++;
        }

        if (flag == 0)
        {
            str_int[i] = * ( * (cpdomains ) + i);
        }

        if (flag == 1)
        {
            str_int[i] = '\0';
        }
    }

    for (i = 0; i < domains_i; i++)
    {
        printf("%d %s\n", charinverseint(str_int), domains[i]);
    }
}

main()
{
    char *words[4] = {"9001 discuss.leetcode.com"};
    int cpdomainsSize = 1;
    int returnSize = 1;

    subdomainVisits(words, cpdomainsSize, &returnSize);
}
  • 3，二重指针的返回
# include <stdio.h>

char** vv()
{
    static char *word[4];
    char** p;
    char temp[100][100] = {"abc", "fff", "hhh"};

    p = word;

    *(p) = temp[0];
    *(p + 1) = temp[1];
    *(p + 2) = temp[2];

    return p;
}

main()
{
    char** y;
    int i;

    y = vv();

    for (i = 0; i < 3; i ++)
    {
        printf("%s\n", *(y + i));
    }
}
  • 4，完整实现 Example 1
# include <stdio.h>
# include <string.h>

void numberversechar(char temp[], int x)
{
    int i = 0;
    int length = 0;
    char tmp;

    while(x != 0)
    {
        temp[length ++ ] = x%10 + '0';
        x = x/10;
    }

    // 反转
    for (i = 0; i < length/2; i ++)
    {
        tmp = temp[i];
        temp[i] = temp[length - i - 1];
        temp[length -i - 1] = tmp;
    }

    temp[length ++] = ' ';
    temp[length] = '\0';
}

int dd(int size)
{
    int i = 0;
    int sum = 1;

    for ( i = 0; i < size; i ++)
    {
        sum *= 10;
    }

    return sum;
}

int charinverseint(char number[])
{
    int size = strlen(number);
    int i;
    int sum = 0;

    for (i = 0; i < size; i ++)
    {
        sum += (number[i] - '0') * dd(size - i - 1);
    }

    return sum;
}

char** subdomainVisits(char** cpdomains, int cpdomainsSize, int* returnSize) 
{
    int i, j;
    int len = 0;
    int flag = 0;
    char domains[100][100];
    int domains_i = 0 , domains_j = 0;
    char str_int[20];
    
    char temp[100][100];
    static char *word[100];
    char** ddomains;
    ddomains = word;
    
    len = strlen( * ( cpdomains ) );
    for ( i = 0; i < len; i ++ )
    {
        domains_j = 0;
        if( * ( * (cpdomains ) + i) == ' ' || * ( * (cpdomains ) + i ) == '.')
        {
            flag ++;
            for (j = i + 1; j < len; j ++)
            {
                domains[domains_i][domains_j ++ ] = * ( * (cpdomains ) + j) ;
            }
            domains[domains_i][domains_j] = '\0';
            domains_i ++;
        }

        if (flag == 0)
        {
            str_int[i] = * ( * (cpdomains ) + i);
        }

        if (flag == 1)
        {
            str_int[i] = '\0';
        }
    }

/*  for (i = 0; i < domains_i; i++)
    {
        printf("%d %s\n", charinverseint(str_int), domains[i]);
    }*/

    for (i = 0; i < domains_i; i ++)
    {
        numberversechar(temp[i], charinverseint(str_int));
        strcat(temp[i], domains[i]);
        
        * ( ddomains + i ) = temp[i];
        
        //printf("1  %s\n", temp[i]);
        //printf("%s\n", *(ddomains + i));
    }

    *returnSize = domains_i;

    return ddomains;
}

main()
{
    char *words[4] = {"9001 discuss.leetcode.com"};
    int cpdomainsSize = 1;
    int returnSize = 1;
    char** doo;
    int i;
        
    doo = subdomainVisits(words, cpdomainsSize, &returnSize);
    
    printf("returnSize = %d\n", returnSize);
    for (i = 0; i < returnSize; i ++)
    {
        printf("%s\n", *(doo + i));
    }
}
  • 5，完整实现
# include<stdio.h>
# include<string.h>

void numberversechar(char temp[], int x)
{
    int i = 0;
    int length = 0;
    char tmp;

    while(x != 0)
    {
        temp[length ++ ] = x%10 + '0';
        x = x/10;
    }

    // 反转
    for (i = 0; i < length/2; i ++)
    {
        tmp = temp[i];
        temp[i] = temp[length - i - 1];
        temp[length -i - 1] = tmp;
    }

    temp[length ++] = ' ';
    temp[length] = '\0';
}

int dd(int size)
{
    int i = 0;
    int sum = 1;

    for ( i = 0; i < size; i ++)
    {
        sum *= 10;
    }

    return sum;
}

int charinverseint(char number[])
{
    int size = strlen(number);
    int i;
    int sum = 0;

    for (i = 0; i < size; i ++)
    {
        sum += (number[i] - '0') * dd(size - i - 1);
    }

    return sum;
}

char** subdomainVisits(char** cpdomains, int cpdomainsSize, int* returnSize) 
{
    int i, j , k;
    
    /* yanzhengchuanguolaide word
    for(i = 0; i < cpdomainsSize; i ++)
    {
        printf("%s\n", *(cpdomains + i));
    }*/
    int len;
    int flag = 0;
    int oo = 0;
    char domains[10000][100];
    int domains_i = 0, domains_j = 0;
    int number[10000];

    char str[100] = "";

    char str_domains[10000][100];
    static char *word[10000];
    char **ddomains;
    ddomains = word;

    for (i = 0; i < cpdomainsSize; i ++)
    {
        len = strlen(* ( cpdomains + i ));
        flag = 0;
        for(j = 0; j < len; j ++)
        {
            domains_j = 0;
            if( * ( * (cpdomains + i) + j) == ' ' || * ( * (cpdomains + i) + j) == '.')
            {
                flag ++;
                for(k = j + 1; k < len; k ++)
                {
                    domains[domains_i][domains_j ++ ] = * ( * (cpdomains + i) + k) ;
                }
                domains[domains_i][domains_j] = '\0';
                domains_i ++;
                
                if (flag == 1)
                {
                    str[j] = '\0';
                    //printf("%s\n", str);
                }

                if(* ( * (cpdomains + i) + j) == '.')
                {
                    number[oo ++ ] = charinverseint(str);
                    //printf("%d, %d, %s\n", oo - 1, number[oo - 1], str);
                }
            }

            if (flag == 0)
            {
                str[j] = * ( * (cpdomains + i) + j);
            }

        }

        number[oo ++] = charinverseint(str);
        //printf("%d, %d, %s\n", oo - 1, number[oo - 1], str);

    }
    
    // 验证一下
/*  for (i = 0; i < domains_i; i ++)
    {
        printf("%d, %s\n", number[i], domains[i]);
    }*/

    for (i = 0; i < domains_i - 1; i ++)
    {
        if(number[i] != 0)
        {
            for (j = i + 1; j < domains_i; j ++)
            {
                if(strcmp(domains[i], domains[j]) == 0)
                {
                    number[i] += number[j];
                    number[j] = 0;
                }
            }
        }
    }
    
    j = 0;
    for (i = 0; i < domains_i; i ++)
    {
        if(number[i] != 0)
        {
            numberversechar(str_domains[i], number[i]);
            strcat(str_domains[i], domains[i]);
            * ( ddomains + j ) = str_domains[i];
            j ++;
        }
    }
    
    *returnSize = j;
    return ddomains;

}

main()
{
    char *words[100] = {"900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
    int cpdomainsSize = 4;
    int returnSize = 0;
    char** doo;
    int i;

    doo = subdomainVisits(words, cpdomainsSize, &returnSize);
    
    printf("returnSize = %d\n", returnSize);
    for (i = 0; i < returnSize; i ++)
    {
        printf("%s\n", *(doo + i));
    }
}
运行结果

思考

  • 这道题目难吗？ 貌似不难，简单的字符串处理一下，考察数字转化字符串，字符串转化数字，二重指针，字符串拼接，不难但是折磨人，断断续续做了一周，好烦。
  • 建议特别有兴趣就做，没有就放弃这个吧
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,125评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,293评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,054评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,077评论 1赞 291
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,096评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,062评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,988评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,817评论 0赞 273
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,266评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,486评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,646评论 1赞 347
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,375评论 5赞 342
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,974评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,621评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,796评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,642评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,538评论 2赞 352

推荐阅读更多精彩内容