手机验证码问题

一、题目

Leetcode：https://leetcode.cn/problems/design-authentication-manager/description/

你需要设计一个包含验证码的验证系统。每一次验证中，用户会收到一个新的验证码，这个验证码在 currentTime 时刻之后 timeToLive 秒过期。如果验证码被更新了，那么它会在 currentTime （可能与之前的 currentTime 不同）时刻延长 timeToLive 秒。

请你实现 AuthenticationManager 类：

• AuthenticationManager(int timeToLive) 构造 AuthenticationManager 并设置 timeToLive 参数。
• generate(string tokenId, int currentTime) 给定 tokenId ，在当前时间 currentTime 生成一个新的验证码。
• renew(string tokenId, int currentTime) 将给定 tokenId 且 未过期 的验证码在 currentTime 时刻更新。如果给定 tokenId 对应的验证码不存在或已过期，请你忽略该操作，不会有任何更新操作发生。
• countUnexpiredTokens(int currentTime) 请返回在给定 currentTime 时刻，未过期 的验证码数目。

如果一个验证码在时刻 t 过期，且另一个操作恰好在时刻 t 发生（renew 或者 countUnexpiredTokens 操作），过期事件 优先于 其他操作。

二、分析

此题目本身比较简单，难点在于理解题意。直接看代码比较方便

// 哈希表的思路
// 这个实现并没有删除过期节点的功能
class AuthenticationManager {
public:
    explicit AuthenticationManager(int timeToLive) {
        time_to_live_ = timeToLive;
    }

    void generate(std::string tokenId, int currentTime) {
        mp_[tokenId] = currentTime + time_to_live_;
    }

    void renew(std::string tokenId, int currentTime) {
        auto iter = mp_.find(tokenId);
        if (iter != mp_.end() && iter->second > currentTime) {
            iter->second = currentTime + time_to_live_;
        }
    }

    int countUnexpiredTokens(int currentTime) {
        int res = 0;
        for (const auto& x : mp_) {
            if (x.second > currentTime) {
                res++;
            }
        }
        return res;
    }

private:
    int time_to_live_;
    std::unordered_map<std::string, int> mp_;
};


// 哈希表+双向链表的思路
// 可以删除过期节点
struct Node {
public:
    int expire_;
    std::string key_;
    Node* prev_;
    Node* next_;

    explicit Node(int expire) : expire_(expire), prev_(nullptr), next_(nullptr) {}
    Node(int expire, std::string key) : expire_(expire), key_(key), prev_(nullptr), next_(nullptr) {}
    Node(int expire, std::string key, Node* prev, Node* next)
        : expire_(expire), key_(key), prev_(prev), next_(next) {}
};

class AuthenticationManager {
public:
    explicit AuthenticationManager(int timeToLive) {
        time_to_live_ = timeToLive;
        head_ = new Node(-1);
        tail_ = new Node(-1);
        head_->next_ = tail_;
        tail_->prev_ = head_;
    }

    void generate(std::string tokenId, int currentTime) {
        Node* node = new Node(currentTime + time_to_live_, tokenId);
        mp_[tokenId] = node;
        Node* last = tail_->prev_;
        last->next_ = node;
        node->prev_ = last;
        tail_->prev_ = node;
        node->next_ = tail_;
    }

    void renew(std::string tokenId, int currentTime) {
        auto iter = mp_.find(tokenId);
        if (iter != mp_.end() && iter->second->expire_ > currentTime) {
            Node* node = mp_[tokenId];
            Node* prev = node->prev_;
            Node* next = node->next_;
            prev->next_ = next;
            next->prev_ = prev;
            node->expire_ = currentTime + time_to_live_;
            Node* last = tail_->prev_;
            last->next_ = node;
            node->prev_ = last;
            tail_->prev_ = node;
            node->next_ = tail_;
        }
    }

    int countUnexpiredTokens(int currentTime) {
        while (head_->next_->expire_ > 0 && head_->expire_ <= currentTime) {
            Node* node = head_->next_;
            mp_.erase(node->key_);
            head_->next_ = node->next_;
            node->next_->prev_ = head_;
            delete node;
        }
        return mp_.size();
    }

private:
    int time_to_live_{0};
    Node* head_{nullptr};
    Node* tail_{nullptr};
    std::unordered_map<std::string, Node*> mp_;
};