单词频率

2021-01-03

设计一个方法，找出任意指定单词在一本书中的出现频率。

你的实现应该支持如下操作：

WordsFrequency(book)构造函数，参数为字符串数组构成的一本书
get(word)查询指定单词在书中出现的频率
示例：

WordsFrequency wordsFrequency = new WordsFrequency({"i", "have", "an", "apple", "he", "have", "a", "pen"});
wordsFrequency.get("you"); //返回0，"you"没有出现过
wordsFrequency.get("have"); //返回2，"have"出现2次
wordsFrequency.get("an"); //返回1
wordsFrequency.get("apple"); //返回1
wordsFrequency.get("pen"); //返回1
提示：

book[i]中只包含小写字母
1 <= book.length <= 100000
1 <= book[i].length <= 10
get函数的调用次数不会超过100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/words-frequency-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class WordsFrequency {

    Map<String, Integer> map = null;

    public WordsFrequency(String[] book) {
        map = new HashMap<>();
        for (String bk : book) {
            map.put(bk, map.getOrDefault(bk, 0) + 1);
        }
    }

    public int get(String word) {
        return map.getOrDefault(word, 0);
    }
}

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * WordsFrequency obj = new WordsFrequency(book);
 * int param_1 = obj.get(word);
 */

c++实现哈希表

/* 单词最大长度 */
#define MAX_WORD_LEN 11

/* 每个元素所带的数据 */
typedef struct {
    char word[MAX_WORD_LEN];
    int cnt;
} hash_set_elem_t;

/* 哈希表容量，一定要大于元素最大个数 */
#define HASH_SET_CAPACITY 100001
/* 哈希表取模的质数，也即哈希桶的个数，小于HASH_SET_CAPACITY */
#define PRIME 99997

/* 元素的哈希函数 */
int elem_hash(const hash_set_elem_t *elem)
{
    const char *str = elem->word;
    unsigned int r = 0;
    int len = strlen(str);

    int i;
    for (i = 0; i < len; i++) {
        r = (r * 31 + str[i]) % PRIME;
    }

    return r % PRIME;
}

/* 元素的比较函数 */
bool cmp(const char *elem1, const char *elem2)
{
    return strcmp(elem1, elem2) == 0;
}

/* 哈希集合 */
typedef struct {
    int head[PRIME]; /* 首节点下标 */

    struct {
        hash_set_elem_t elem;
        int next;
    } node[HASH_SET_CAPACITY]; /* 静态链表 */

    int size; /* 实际元素个数 */
    int (*hash)(const hash_set_elem_t *elem); /* 元素的哈希函数 */
    bool (*cmp)(const char *elem1, const char *elem2); /* 元素的比较函数 */
} WordsFrequency;

/* 创建一个哈希集合 */
WordsFrequency *hash_set_create(int (*hash)(const hash_set_elem_t *elem),
                            bool (*cmp)(const char *elem1, const char *elem2))
{
    WordsFrequency *result = (WordsFrequency *)malloc(sizeof(WordsFrequency));
    memset(result->head, -1, sizeof(result->head));
    memset(result->node, -1, sizeof(result->node));
    for (int i = 0; i < HASH_SET_CAPACITY; i++) {
        (result->node)[i].elem.cnt = 0;
    }
    result->size = 0;
    result->hash = hash;
    result->cmp = cmp;
    return result;
}

/* 添加一个元素，如果已存在则添加失败 */
bool hash_set_add(WordsFrequency *set, const hash_set_elem_t *elem)
{
    int i;
    int hash = set->hash(elem);

    /* 已经存在,出现次数+1 */
    for (i = set->head[hash]; i != -1; i = set->node[i].next) {
        if (set->cmp(elem->word, set->node[i].elem.word)) {
            (set->node[i].elem.cnt)++;
            return false;
        }
    }

    /* 不存在，则插入在首节点之前*/
    set->node[set->size].next = set->head[hash];
    strcpy(set->node[set->size].elem.word, elem->word);
    (set->node[set->size].elem.cnt)++;
    set->head[hash] = set->size++;

    return true;
}

WordsFrequency *wordsFrequencyCreate(char **book, int bookSize)
{
    WordsFrequency *set = hash_set_create(elem_hash, cmp);
    hash_set_elem_t e;

    for (int i = 0; i < bookSize; i++) {
        strcpy(e.word, book[i]);
        e.cnt = 0;
        hash_set_add(set, &e);
    }

    return set;
}

int wordsFrequencyGet(WordsFrequency *set, char *word)
{
    int i;

    if (word == NULL || strlen(word) == 0) {
        return 0;
    }

    int hash = set->hash(word);
    for (i = set->head[hash]; i != -1; i = set->node[i].next) {
        if (set->cmp(word, set->node[i].elem.word)) {
            return set->node[i].elem.cnt;
        }
    }
    return 0;
}

/* 销毁哈希集合 */
void wordsFrequencyFree(WordsFrequency *obj)
{
    free(obj);
    obj = NULL;
}

/**
 * Your WordsFrequency struct will be instantiated and called as such:
 * WordsFrequency* obj = wordsFrequencyCreate(book, bookSize);
 * int param_1 = wordsFrequencyGet(obj, word);
 * wordsFrequencyFree(obj);
*/

作者：yuxiaochen99
链接：https://leetcode-cn.com/problems/words-frequency-lcci/solution/chun-czi-ji-shi-xian-ha-xi-huo-zhe-shi-yong-uthash/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：yuxiaochen99来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。