LeetCode358用C语言实现的代码

以下是 LeetCode 358 题的 C 语言代码实现，使用了哈希表和双向链表：

#include <stdio.h>
#include <stdlib.h>

#define MAX_TIME 1000000

// 双向链表节点
typedef struct ListNode {
    int key;        // 键
    int value;      // 值
    int time;       // 时间戳
    struct ListNode *prev;  // 前指针
    struct ListNode *next;  // 后指针
} ListNode;

// 双向链表
typedef struct List {
    ListNode *head;     // 头节点
    ListNode *tail;     // 尾节点
} List;

// 哈希表
typedef struct {
    List *lists;    // 双向链表数组
    int size;       // 哈希表大小
} MyHashMap;

// 创建一个新节点
ListNode* createNode(int key, int value, int time) {
    ListNode *node = (ListNode*)malloc(sizeof(ListNode));
    node->key = key;
    node->value = value;
    node->time = time;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 初始化双向链表
void initList(List *list) {
    list->head = createNode(-1, -1, 0);
    list->tail = createNode(-1, -1, 0);
    list->head->next = list->tail;
    list->tail->prev = list->head;
}

// 在双向链表头部插入一个节点
void insertNode(List *list, ListNode *node) {
    node->next = list->head->next;
    node->prev = list->head;
    list->head->next->prev = node;
    list->head->next = node;
}

// 移除双向链表中的一个节点
void removeNode(List *list, ListNode *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node);
}

// 初始化哈希表
MyHashMap* myHashMapCreate() {
    MyHashMap *hashMap = (MyHashMap*)malloc(sizeof(MyHashMap));
    hashMap->lists = (List*)malloc(sizeof(List) * MAX_TIME);
    hashMap->size = MAX_TIME;
    for (int i = 0; i < MAX_TIME; i++) {
        initList(&hashMap->lists[i]);
    }
    return hashMap;
}

// 插入一个键值对
void myHashMapPut(MyHashMap* obj, int key, int value, int timestamp) {
    // 查找该键是否已经存在
    ListNode *node = NULL;
    List *list = &obj->lists[key % obj->size];
    ListNode *cur = list->head->next;
    while (cur != list->tail) {
        if (cur->key == key) {
            node = cur;
            break;
        }
        cur = cur->next;
    }

    // 如果不存在，则创建一个新节点
    if (node == NULL) {
        node = createNode(key, value, timestamp);
        insertNode(list, node);
    }
    // 如果已经存在，则更新该节点的值和时间戳，并将其移动到双向链表头部
    else {
        node->value = value;
        node->time = timestamp;
        removeNode(list, node);
        insertNode(list, node);
    }
}

// 获取一个键值对
int myHashMapGet(MyHashMap* obj, int key, int timestamp) {
    // 查找该键是否存在
    List *list = &obj->lists[key % obj->size];
    ListNode *cur = list->head->next;
    while (cur != list->tail) {
        if (cur->key == key) {
            // 如果时间戳不在有效期内，则返回空值
            if (timestamp - cur->time >= MAX_TIME) {
                return -1;
            }
            // 否则将该节点移动到双向链表头部，并返回其值
            removeNode(list, cur);
            insertNode(list, cur);
            return cur->value;
        }
        cur = cur->next;
    }
    return -1;
}

// 释放哈希表的内存
void myHashMapFree(MyHashMap* obj) {
    for (int i = 0; i < MAX_TIME; i++) {
        ListNode *cur = obj->lists[i].head;
        while (cur != NULL) {
            ListNode *node = cur;
            cur = cur->next;
            free(node);
        }
    }
    free(obj->lists);
    free(obj);
}

int main() {
    MyHashMap *hashMap = myHashMapCreate();
    myHashMapPut(hashMap, 1, 1, 0);
    myHashMapPut(hashMap, 2, 2, 0);
    printf("%d\n", myHashMapGet(hashMap, 1, 1)); // 输出 1
    printf("%d\n", myHashMapGet(hashMap, 2, 2)); // 输出 2
    printf("%d\n", myHashMapGet(hashMap, 1, 3)); // 输出 -1
    printf("%d\n", myHashMapGet(hashMap, 2, 3)); // 输出 2
    myHashMapFree(hashMap);
    return 0;
}

需要注意的是，LeetCode 358 题的时间戳范围比较大，因此我们需要使用一个足够大的数组来存储双向链表，这里我们使用了 MAX_TIME = 1000000。另外，为了方便起见，在哈希表中使用双向链表数组来存储键值对，而不是使用单独的链表。