【设计难题】力扣1797-设计一个验证系统

字数统计: 2.3k字 | 阅读时长: 10分

2021-05-09

摘要: 设计难题，验证系统

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个设计问题，第 48 场双周赛 B 题。本题的设计以哈希表为核心，类似的设计题汇总见文章设计-功能系统。此外还可以用类似于 OrderedDict 的维护更新时间的字典，在文章 OrderedDict：维护插入顺序的有序字典中介绍过原理和代码模板，本题在代码模板的基础上进行一些修改即可，其中用到双向链表和哈希表，代码模板见文章【模板】无重哈希映射和【模板】双向链表。

$1 题目

1797. 设计一个验证系统

你需要设计一个包含验证码的验证系统。每一次验证中，用户会收到一个新的验证码，这个验证码在 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 操作），过期事件优先于其他操作。

提示：

1 <= timeToLive <= 1e8
1 <= currentTime <= 1e8
1 <= tokenId.length <= 5
tokenId 只包含小写英文字母。
所有 generate 函数的调用都会包含独一无二的 tokenId 值。
所有函数调用中，currentTime 的值 严格递增 。
所有函数的调用次数总共不超过 2000 次。

示例 1：
输入：
[“AuthenticationManager”, “renew”, “generate”, “countUnexpiredTokens”, “generate”, “renew”, “renew”, “countUnexpiredTokens”]
[[5], [“aaa”, 1], [“aaa”, 2], [6], [“bbb”, 7], [“aaa”, 8], [“bbb”, 10], [15]]
输出：
[null, null, null, 1, null, null, null, 0]
解释：
AuthenticationManager authenticationManager = new AuthenticationManager(5); // 构造 AuthenticationManager ，设置 timeToLive = 5 秒。
authenticationManager.renew(“aaa”, 1); // 时刻 1 时，没有验证码的 tokenId 为 “aaa” ，没有验证码被更新。
authenticationManager.generate(“aaa”, 2); // 时刻 2 时，生成一个 tokenId 为 “aaa” 的新验证码。
authenticationManager.countUnexpiredTokens(6); // 时刻 6 时，只有 tokenId 为 “aaa” 的验证码未过期，所以返回 1 。
authenticationManager.generate(“bbb”, 7); // 时刻 7 时，生成一个 tokenId 为 “bbb” 的新验证码。
authenticationManager.renew(“aaa”, 8); // tokenId 为 “aaa” 的验证码在时刻 7 过期，且 8 >= 7 ，所以时刻 8 的renew 操作被忽略，没有验证码被更新。
authenticationManager.renew(“bbb”, 10); // tokenId 为 “bbb” 的验证码在时刻 10 没有过期，所以 renew 操作会执行，该 token 将在时刻 15 过期。
authenticationManager.countUnexpiredTokens(15); // tokenId 为 “bbb” 的验证码在时刻 15 过期，tokenId 为 “aaa” 的验证码在时刻 7 过期，所有验证码均已过期，所以返回 0 。

$2 题解

算法1：哈希表

数据结构设计如下：

1 2	set<Token, Cmp, Equal> tokens; unordered_map<string, int> mapping;

其中：

mapping 为哈希映射，保存 tokenId 以及其更新时的时间戳。mapping[tokenID] := tokenID 的更新时间戳，主要用于 renew 操作时 $O(1)$ 地判断该 tokenId 是否存在且没有超时。
tokens 为 TreeSet 保存 tokenId 以及其其更新时的时间戳，用于将所有 token 按时间更新时间从前到后排序。以便查询某时刻有多少未超时的 token。

创建时，就直接往 mapping 和 tokens 里插入即可。

更新时，就更新 mapping[tokenId] 为新的 currentTime，以及删除 tokens 中对应的 token，将 tokenId 和新的 currentTime 组成新的 Token 对象插入 tokens 中。

查询时，将 tokens 中的过期 token 删除掉，剩下的 tokens 的长度就是为过期的 token 数。

代码 (C++)

struct Token
{
    string id;
    int t;
    Token(string id, int t):id(id),t(t){}
};

struct Cmp
{
    bool operator()(const Token& t1, const Token& t2) const
    {
        if(t1.t == t2. t)
            return t1.id < t2.id;
        return t1.t < t2.t;
    }
};


class AuthenticationManager {
public:
    AuthenticationManager(int timeToLive) {
        this -> timeToLive = timeToLive;
        tokens = set<Token, Cmp>();
        mapping = unordered_map<string, int>();
    }

    void generate(string tokenId, int currentTime) {
        mapping[tokenId] = currentTime;
        tokens.insert(Token(tokenId, currentTime));
    }

    void renew(string tokenId, int currentTime) {
        if(mapping.count(tokenId) == 0 || currentTime - mapping[tokenId] >= timeToLive)
            return;
        tokens.erase(tokens.find(Token(tokenId, mapping[tokenId])));
        tokens.insert(Token(tokenId, currentTime));
        mapping[tokenId] = currentTime;
    }

    int countUnexpiredTokens(int currentTime) {
        auto it = tokens.begin();
        while(it != tokens.end() && currentTime - (*it).t >= timeToLive)
            it = tokens.erase(it);
        return tokens.size();
    }

private:
    set<Token, Cmp> tokens;
    unordered_map<string, int> mapping;
    int timeToLive;
};

算法2: OrderedDict

所有函数调用中，currentTime 的值严格递增。则可以用类似于 OrderedDict 的带更新顺序的字典。具体参考 OrderedDict：维护插入顺序的有序字典，其中有代码模板。

在模板基础上，结合本题需求需要做一些修改，OrderedDict 内部数据结构如下：

1 2	双向链表的节点：(tokenId，过期时间) 哈希表存 tokenId -> 双向链表节点指针

创建时，就直接往 OrderedDict 里插入 tokenID 和 expiredTime 即可。

更新时，双向链表中对应节点更新为新的 expiredTime，并调度到表头。

查询时，将双向链表中的过期 token 删除掉，剩下的 tokens 的长度就是为过期的 token 数。

双向链表节点

双向链表节点在模板基础上修改如下：

struct Token
{
    string id;
    int t; // 过期时间
    Token(string id, int t):id(id),t(t){}
    Token(){}
    bool operator==(const Token& token) const
    {
        return id == token.id && t == token.t;
    }
    bool operator!=(const Token& token) const
    {
        return !(*this == token);
    }
};
ostream& operator<<(ostream& out, const Token& token)
{
    out << "id: " << token.id << "; expiredtime: " << token.t << endl;
    return out;
}

typedef Token DLType;
const DLType DLTypeNULL = Token("", 1e9);
const int MAX_LEN = 1e6;

struct DLNode; // 模板
class DoubleCircleList; // 模板

哈希表节点

哈希表节点在模板的基础上修改如下：

const int INF = INT_MAX;
typedef string HashType;
const HashType HashTypeNULL = "";
struct ValueType
{
    HashType value;
    DLNode *list_node;
    ValueType(HashType v=HashTypeNULL, DLNode *node=nullptr):value(v),list_node(node){}
    bool operator==(const ValueType& v) const
    {
        return value == v.value && list_node == v.list_node;
    }
    bool operator!=(const ValueType& v) const
    {
        return !(*this == v);
    }
};
const ValueType VALUENULL(HashTypeNULL, nullptr);

字符串哈希函数

字符串的哈希函数有很多，在文章字符串哈希有用到最简单的两种。下面用到的是另外一种：

int SDBMHash(char *str)
{
    int hash = 0;

    while (*str)
    {
        // equivalent to: hash = 65599 * hash + (*str++);
        hash = (*str++) + (hash << 6) + (hash << 16) - hash;
    }
    return (hash & 0x7FFFFFFF);
}

int f(const string& str)
{
    return SDBMHash((char*)str.c_str());
}

class CloseHashTable; // 模板

OrderedDict 实现

class OrderedDict
{
public:
    OrderedDict()
    {
        linkedlist = DoubleCircleList();
        CloseHashTable mapping(hashtable_capacity, f);
    }

    ~OrderedDict(){}

    void generate(string key, int value, int timeToLive)
    {
        ValueType v = mapping.findx(key);
        if(v != VALUENULL)
        {
            DLNode *node = v.list_node;
            linkedlist.remove(node);
            mapping.removex(key);
        }
        DLNode *node = linkedlist.insertHead(DLType(key, value + timeToLive));
        mapping.insertx(key, ValueType(key, node));
    }

    void renew(string key, int value, int timeToLive)
    {
        ValueType v = mapping.findx(key);
        if(v == VALUENULL || (v.list_node -> val).t <= value)
            return;
        if(v != VALUENULL)
        {
            DLNode *node = v.list_node;
            linkedlist.remove(node);
            mapping.removex(key);
        }
        DLNode *node = linkedlist.insertHead(DLType(key, value + timeToLive));
        mapping.insertx(key, ValueType(key, node));
    }

    int query(int value)
    {
        while(true)
        {
            DLType token = linkedlist.getTail();
            if(token == DLTypeNULL)
                break;
            if(token.t > value)
                break;
            ValueType v = mapping.findx(token.id);
            DLNode *node = v.list_node;
            linkedlist.remove(node);
            mapping.removex(token.id);
        }
        return size();
    }

    int size() const
    {
        return linkedlist.size();
    }

    void traverse() const
    {
        if(linkedlist.isEmpty())
        {
            cout << "Empty" << endl;
            return;
        }
        DLNode *head = linkedlist.get_head();
        DLNode *iter = head;
        do{
            cout << (iter -> val).id << " " << (iter -> val).t << "; ";
            iter = linkedlist.get_next(iter);
        }
        while(iter != head);
        cout << endl;
    }

private:
    const int hashtable_capacity = 99991;
    DoubleCircleList linkedlist;
    CloseHashTable mapping;
};

代码 (C++)

// 双向链表
struct Token
{
    string id;
    int t; // 过期时间
    Token(string id, int t):id(id),t(t){}
    Token(){}
    bool operator==(const Token& token) const
    {
        return id == token.id && t == token.t;
    }
    bool operator!=(const Token& token) const
    {
        return !(*this == token);
    }
};
ostream& operator<<(ostream& out, const Token& token)
{
    out << "id: " << token.id << "; expiredtime: " << token.t << endl;
    return out;
}

typedef Token DLType;
const DLType DLTypeNULL = Token("", 1e9);
const int MAX_LEN = 1e6;

struct DLNode; // 模板
class DoubleCircleList; // 模板

// 哈希映射
const int INF = INT_MAX;
typedef string HashType;
const HashType HashTypeNULL = "";
struct ValueType
{
    HashType value;
    DLNode *list_node;
    ValueType(HashType v=HashTypeNULL, DLNode *node=nullptr):value(v),list_node(node){}
    bool operator==(const ValueType& v) const
    {
        return value == v.value && list_node == v.list_node;
    }
    bool operator!=(const ValueType& v) const
    {
        return !(*this == v);
    }
};
const ValueType VALUENULL(HashTypeNULL, nullptr);

int SDBMHash(char *str)
{
    int hash = 0;

    while (*str)
    {
        // equivalent to: hash = 65599 * hash + (*str++);
        hash = (*str++) + (hash << 6) + (hash << 16) - hash;
    }
    return (hash & 0x7FFFFFFF);
}

int f(const string& str)
{
    return SDBMHash((char*)str.c_str());
}

class CloseHashTable; // 模板

// 有序字典
class OrderedDict;

class AuthenticationManager {
public:
    AuthenticationManager(int timeToLive) {
        this -> timeToLive = timeToLive;
    }

    void generate(string tokenId, int currentTime) {
        ordereddict.generate(tokenId, currentTime, timeToLive);
    }

    void renew(string tokenId, int currentTime) {
        ordereddict.renew(tokenId, currentTime, timeToLive);
    }

    int countUnexpiredTokens(int currentTime) {
        int ans = ordereddict.query(currentTime);
        return ans;
    }

private:
    OrderedDict ordereddict;
    int timeToLive;
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法leetcode

【设计难题】力扣1797-设计一个验证系统

$1 题目

$2 题解

算法1：哈希表

代码 (C++)

算法2: OrderedDict

双向链表节点

哈希表节点

字符串哈希函数

OrderedDict 实现

代码 (C++)