[SOJ 1377] 字符串统计(时间限制:3秒)

引题:求出现次数最多的数字

假设:给出N个数字, 需要求出现次数最多的数字.
则我们可以使用1个计数器数组来记录每一个数字的出现次数, 然后进行统计即可.
int count[数字] = 出现次数;
int count[数字] += 1;

只需在每次输入时, 利用 数组高效的随机访问 特性, 即可在O(1)时间内完成计数统计. (注意: 这里仅需对输入进行判断即可, 不需要将输入的数字存储下来.)

转化:求出现次数最多的字符串

假设: 给出N个字符串, 需要求 出现次数最多的字符串.

思路1: 我们可以用一个 二维的技术数组 将所有的字符串存储下来, 然后再统计出现次数最多的字符串.

缺点: 1. 该思路会将所有输入的字符串存储下来,占据大量的内存空间
缺点: 2. 如果输入的字符串数量巨大, 如有10万个字符串, 而后续的统计操作是线性操作, 每次统计需要遍历10万个字符串, 需要耗费大量时间.

思路2: 不妨延续我们之前处理“求出现次数最多的数字”的思路, 也适用一个一维的计数数组来解决问题.

因此:
int count[字符串] = 出现次数;
int count[字符串] += 1;

但是!数组的下标要求是一个整数,我们没法用字符串作数组的下标!!
嗯,如果有办法将字符串映射到数字的话,问题就解决了。
我们称完成这种映射的函数为哈希函数

注意:哈希 = 散列, 哈希表(Map/HashTable/HashMap等意思相同) = 散列表. 这2个词语是同一个意思, 有些地方称 哈希表 为 散列表, 也有称为 字典(Dict)的, 但都是同一个东西.

我们现在就来设计一个这样的哈希函数,并保证哈希函数满足这2个要求.
1. 对相同的字符串,每次映射出相同的数字
2. 对不同的字符串,每次映射出不同的独一无二的字符串

换句话说,如果我们第一次将字符串“abc”映射到数字233的话,那么第二次映射字符串“abc”的话,结果应该也是数字233.
而且,我们要保证字符串“abcd”不能映射到数字233,因为这个数字已经被字符串“abc”给占据掉了!(若无法保证映射结果的独一无二的话,便会发生哈希冲突

注意:尽管哈希冲突是无法避免的, 但是我们应当尽可能降低发生的概率.

1个简单的哈希函数 (将字符串映射到数字):

该哈希函数的映射方式: 逐个累加字符的ASCII码值 并同时乘上 该字符所在的位置.

注意: 最后计算出的哈希值需要%MAXN(即哈希表数组的长度)来保证所求出的哈希值(即哈希表数组的下标是合法下标,也就是避免数组越界)

#define MAXN 1000
/* 哈希函数 */
int Hash(const char * str) {
    int index = 0;
    int at = -1;
    while (str[at++]) {
        index += ((at + 1) * (str[at] % 'a')) % MAXN;
    }
    return index;
}

动手实现自己的哈希表!

注意:我们将上文所提到的计数数组称为哈希表,而我们自己写的将字符串映射到数字的函数称为哈希函数

结合上面的知识, 我们可以来解决问题了。

SOJ1377 字符串统计(时间限制:3秒)
需include: stdlib.h, stdio.h, string.h
#pragma warning (disable:4996)

// 单词长度
#define MAX_LEN 105

/* 哈希表 */
#define MAXN 1000
int map[MAXN];

/* 哈希函数 */
int Hash(const char * str) {
    int index = 0;
    int at = -1;
    while (str[++at]) {
        index += ((at + 1) * (str[at] % 'a')) % MAXN;
    }
    return index;
}

int main() {
    int N; scanf("%d", &N);

    char ans_str[MAX_LEN];
    int ans_count = 0;

    while (N--) {
        // WARNING: 输入使用gets()会Wrong Answer.
        char tempStr[MAX_LEN]; scanf("%s", &tempStr);
        int curCount = map[Hash(tempStr)] += 1;

        // Update Ans.
        if (curCount > ans_count) {
            ans_count = curCount;
            strcpy(ans_str, tempStr);
        }
    }

    puts(ans_str);
}
SOJ1003 第三届程序设计大赛 让气球飞起来
代码与SOJ1377完全相同.

不妨直接使用C++ STL提供的map结构

延续上面的思路,我们也可以不必自己动手实现map.

注意: 使用C++ STL的map时, 若key为字符串, 则需要使用C++的string类.
但是, C的scanf()gets()并不支持输入 string类, 所以只能使用cin来输入string.

注意: cin的输入效率比scanf()差很多, 如果字符串的输入量非常大, 需要重新设置cin的一些属性, 以加速cin的输入速度.

在使用cin输入string时, 请加上下面2句代码, 否则将会面临Time Limit Exceed的问题.

ios::sync_with_stdio(0);
cin.tie(0);

来做题目叭

SOJ1003 第三届程序设计大赛 让气球飞起来
SOJ1377 字符串统计(时间限制:3秒)

通解代码

15 Responses

  1. 头像 antankdem说道:

    cialis order online[/url]

  2. Yes! Finally something about best delta 8 carts.

    Feel free to visit my web blog … buy delta 8 thc carts

  3. 头像 best delta 8说道:

    Asking questions are really pleasant thing if you are not understanding something completely, except this post presents
    pleasant understanding even.

    Look at my blog … best delta 8

  4. 头像 delta 8 carts说道:

    I know this if off topic but I’m looking into starting my own weblog and was curious what all is required
    to get set up? I’m assuming having a blog like yours would cost
    a pretty penny? I’m not very internet smart
    so I’m not 100% certain. Any tips or advice would be greatly appreciated.

    Appreciate it

    Here is my webpage … delta 8 carts

  5. 头像 best delta 8说道:

    I really like your blog.. very nice colors & theme. Did you design this website yourself or did
    you hire someone to do it for you? Plz respond as I’m looking to create my own blog and
    would like to find out where u got this from. appreciate it

    Also visit my page … best delta 8

  6. Excellent blog here! Also your web site loads up very fast!
    What web host are you using? Can I get your affiliate link to your
    host? I wish my site loaded up as quickly as yours lol

    my web-site … Area 52 Delta 8 THC

  7. 头像 best CBD说道:

    Hi I am so excited I found your webpage, I
    really found you by accident, while I was browsing on Aol for something
    else, Nonetheless I am here now and would just like to say cheers for
    a incredible post and a all round interesting blog (I also love the theme/design), I don’t have time to browse
    it all at the minute but I have book-marked it and also included your RSS feeds, so when I
    have time I will be back to read more, Please do keep up the awesome work.

    Also visit my website – best CBD

  8. 头像 cbd gummies说道:

    Incredible quest there. What occurred after? Thanks!

    Take a look at my website :: cbd gummies

  9. 头像 buy cbd gummies说道:

    Everything is very open with a really clear description of the
    issues. It was truly informative. Your website is useful.

    Many thanks for sharing!

    Here is my blog buy cbd gummies

  10. 头像 delta 8说道:

    I’ve been browsing online more than 4 hours today, yet I never found any interesting article like yours.
    It’s pretty worth enough for me. In my opinion, if all site owners and bloggers made good content as you did, the net will be much more useful than ever before.

    Also visit my web page delta 8

  11. I do not even know how I ended up here, but I thought this post was great.

    I do not know who you are but definitely you’re going to
    a famous blogger if you are not already 😉 Cheers!

    Also visit my website – delta 8 thc near me

  12. 头像 buy delta 8 thc说道:

    May I just say what a comfort to uncover somebody that
    truly understands what they are discussing on the web. You certainly realize how to bring a problem to light and make it important.
    A lot more people should check this out and understand this side of the story.
    It’s surprising you’re not more popular because you certainly possess the
    gift.

    Feel free to visit my blog post – buy delta 8 thc

  13. 头像 elderjiang说道:

    It’s very good. I learned so mush from that.

  14. 头像 buy cbd gummies说道:

    I’d like to find out more? I’d want to find out some additional information.

    My blog :: buy cbd gummies

  15. 头像 CBD oil for sale说道:

    I am sure this post has touched all the internet people,
    its really really nice paragraph on building up new web site.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

> 表情包