魔咒词典(hash表)- HDU 1880

公众号现在输入题号可以直接查看题目啦~比如输入1000,会显示HDU1000的题目内容

哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

数组的特点是:寻址容易,插入和删除困难;

而链表的特点是:寻址困难,插入和删除容易。

那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法——拉链法,我们可以理解为“链表的数组”,如图:

优缺点

优点:不论哈希表中有多少数据,查找、插入、删除(有时包括删除)只需要接近常量的时间即0(1)的时间级。实际上,这只需要几条机器指令。

哈希表运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器)哈希表的速度明显比树快,树的操作通常需要O(N)的时间级。哈希表不仅速度快,编程实现也相对容易。

如果不需要有序遍历数据,并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

缺点:它是基于数组的,数组创建后难于扩展,某些哈希表被基本填满时,性能下降得非常严重,所以程序员必须要清楚表中将要存储多少数据(或者准备好定期地把数据转移到更大的哈希表中,这是个费时的过程)。

在实际应用中,hash表可能需要进行重hash操作来进行性能提升。如Redis源码中的hash表。

题目:

Problem Description

哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒,哈利很难全部记住,但是为了对抗强敌,他必须在危急时刻能够调用任何一个需要的魔咒,所以他需要你的帮助。

给你一部魔咒词典。当哈利听到一个魔咒时,你的程序必须告诉他那个魔咒的功能;当哈利需要某个功能但不知道该用什么魔咒时,你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中,就输出“what?”

Input

首先列出词典中不超过100000条不同的魔咒词条,每条格式为:

[魔咒] 对应功能

其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串,字符串中保证不包含字符“[”和“]”,且“]”和后面的字符串之间有且仅有一个空格。词典最后一行以“@END@”结束,这一行不属于词典中的词条。

词典之后的一行包含正整数N(<=1000),随后是N个测试用例。每个测试用例占一行,或者给出“[魔咒]”,或者给出“对应功能”。

Output

每个测试用例的输出占一行,输出魔咒对应的功能,或者功能对应的魔咒。如果魔咒不在词典中,就输出“what?”

Sample Input

[expelliarmus] the disarming charm

[rictusempra] send a jet of silver light to hit the enemy

[tarantallegra] control the movement of one's legs

[serpensortia] shoot a snake out of the end of one's wand

[lumos] light the wand

[obliviate] the memory charm

[expecto patronum] send a Patronus to the dementors

[accio] the summoning charm

@END@

4

[lumos]

the summoning charm

[arha]

take me to the sky

Sample Output

light the wand

accio

what?

what?

解题思路:

通过key-value查找即可,本题性能关键地方在于使用数组索引进行链表的指向操作。

源代码:G++ 171ms

#include <stdio.h>
#include <string.h>

#define N 100010 
#define H 100007 

//链表节点
typedef struct node_s {
    //魔法指令
    char charm[25];
    //魔法功能
    char function[85];
    //索引指向
    int next;
}node_t;

//hash表,采用数组方式存储
static node_t hash_a[N], hash_b[N];

static int index_a, index_b;

static int hash_index_a[N], hash_index_b[N];

void init_hash() {
    //初始值为-1
    for (int i = 0; i < H; i++) {
        hash_index_a[i] = -1;
        hash_index_b[i] = -1;
    }
    //指向为0
    index_a = 0;
    index_b = 0;
}

//BKDR字符串hash算法
//是Kernighan和Dennis在《The C programming language》中提出的
unsigned int hashcode(char * s) {
    unsigned int seed = 131;
    unsigned int hash = 0;
    while (*s) {
        hash = hash * seed + *s++;
    }
    return (hash & 0x7fffffff) % H;
}

//插入hash
void insert_hash(char* charm, char * function) {
    unsigned int h;
    //计算hash值
    h = hashcode(charm);
    //存入数据
    strcpy(hash_a[index_a].charm, charm);
    strcpy(hash_a[index_a].function, function);
    //注意这里的指向
    //对于重复的元素,采用索引指向的方式进行链接
    //虽然同样是链表,但是数组及索引指向在性能上要好很多
    //不需要malloc分配节点,也不需要销毁节点
    hash_a[index_a].next = hash_index_a[h];
    //第一次进来保存的是0
    hash_index_a[h] = index_a;
    ++index_a;

    //同上
    h = hashcode(function);
    strcpy(hash_b[index_b].charm, charm);
    strcpy(hash_b[index_b].function, function);
    hash_b[index_b].next = hash_index_b[h];
    hash_index_b[h] = index_b;
    ++index_b;
}

//查找表A
int search_hash_a(char* charm) {
    //获取hash值
    unsigned int h = hashcode(charm);
    //计算指向
    int next = hash_index_a[h];

    while (next != -1) {
        //查看是否是这个字符串
        if (strcmp(charm, hash_a[next].charm) == 0)
            return next;
        //下一个指向
        next = hash_a[next].next;
    }
    return -1;
}

//同上
int search_hash_b(char *ans) {
    unsigned int h = hashcode(ans);
    int next = hash_index_b[h];
    while (next != -1) {
        if (strcmp(ans, hash_b[next].function) == 0) 
            return next;
        next = hash_b[next].next;
    }
    return -1;
}

int main() {
    char line[120], charm[25], function[85];
    int count, res;
    //初始化hash
    init_hash();
    //
    while (gets(line)) {
        //如果发现是@END@,跳出循环,这部分是key->value
        if (line[0] == '@')
            break;

        //获取key值:魔法命令
        int len = 0;
        char * p = line;

        for (; *(p-1) != ']'; ) {
            charm[len++] = *p++;
        }

        charm[len] = 0;

        //获取value的值:魔法功能
        len = 0;

        for (p++; *p;) {
            function[len++] = *p++;
        }

        function[len] = 0;
        //插入到hash表中
        insert_hash(charm, function);
    }

    scanf("%d", &count);
    getchar();

    while (count--) {
        gets(line);
        //[表示是魔法命令,从hash表A中查询值
        if (line[0] == '[') {
            int index = search_hash_a(line);

            if (index == -1)
                printf("what?\n");
            else
                printf("%s\n", hash_a[index].function);
        }
        else {
            //从hash表B中查询魔法命令
            int index = search_hash_b(line);

            if (index == -1)
                printf("what?\n");
            else {
                int len = strlen(hash_b[index].charm);
                char * p = hash_b[index].charm;
                for (int i = 1; i < len - 1; ++i) {
                    printf("%c", p[i]);
                }
                printf("\n");
            }

        }
    }

    return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-03-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端黑板报

采用Symbol和process.nextTick实现Promise

作者简介:slashhuang 研究型程序员 现就职于爱屋吉屋 Promise已经成为处理Node.js异步流程的标配技术。 V8的async/await语法构...

2468
来自专栏生信宝典

为啥我的Python这么慢 (一)

在Python系列教程中,我们提到一个概念字符串是不可修改的。这一点可以通过id函数来判断确实是对的。但是这个概念会对我们写作程序有什么影响一直没有特别深的理解...

2116
来自专栏瓜大三哥

HLS Lesson8-基本操作

1.算术操作 ? 如果是定点数处理时候,需要遵循的原则是:大数据不溢出,小数据不损失 2.算数赋值 ? ? #include<iostream> #includ...

2497
来自专栏撸码那些事

【封装那些事】 未利用封装

1624
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day14 Java对象的克隆

  今天要介绍一个概念,对象的克隆。本篇有一定难度,请先做好心理准备。看不懂的话可以多看两遍,还是不懂的话,可以在下方留言,我会看情况进行修改和补充。   克隆...

2106
来自专栏风口上的猪的文章

.NET面试题系列[15] - LINQ:性能

当你使用LINQ to SQL时,请使用工具(比如LINQPad)查看系统生成的SQL语句,这会帮你发现问题可能发生在何处。

3234
来自专栏偏前端工程师的驿站

Design Pattern: Not Just Mixin Pattern

Brief                                 从Mix-In模式到Mixin模式,中文常用翻译为“混入/织入模式”。单纯从名字上看...

2006
来自专栏斑斓

Scala的面向对象与函数编程

很难说FP和OO孰优孰劣,应该依场景合理选择使用。倘若从这个角度出发,Scala就体现出好处了,毕竟它同时支持了OO和FP两种设计范式。 从设计角度看,我认为O...

3155
来自专栏cmazxiaoma的架构师之路

一个Java小白的面试之旅总结

1923
来自专栏小蠢驴iOS专题

实际开发中-Block导致循环引用的问题

2024

扫码关注云+社区

领取腾讯云代金券