Medium

题目描述

有一个身份验证系统，它使用身份验证令牌。对于每个会话，用户将收到一个新的身份验证令牌，该令牌将在 currentTime 之后的 timeToLive 秒过期。如果令牌被续期，过期时间将延长到（可能不同的）currentTime 之后的 timeToLive 秒过期。

实现 AuthenticationManager 类：

  • AuthenticationManager(int timeToLive) 构造 AuthenticationManager 并设置 timeToLive。
  • generate(string tokenId, int currentTime) 在给定的 currentTime 时间（以秒为单位）生成一个具有给定 tokenId 的新令牌。
  • renew(string tokenId, int currentTime) 在给定的 currentTime 时间（以秒为单位）续期具有给定 tokenId 的未过期令牌。如果没有具有给定 tokenId 的未过期令牌，则忽略请求，什么也不会发生。
  • countUnexpiredTokens(int currentTime) 返回在给定 currentTime 时间未过期的令牌数量。

请注意，如果令牌在时间 t 过期，而另一个操作恰好发生在时间 t（续期或 countUnexpiredTokens），则过期会在其他操作之前发生。

示例 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); // 构造 timeToLive = 5 秒的 AuthenticationManager。
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 的续期请求被忽略，什么也不发生。
authenticationManager.renew("bbb", 10); // tokenId 为 "bbb" 的令牌在时间 10 未过期，所以续期请求得到满足，现在令牌将在时间 15 过期。
authenticationManager.countUnexpiredTokens(15); // tokenId 为 "bbb" 的令牌在时间 15 过期，tokenId 为 "aaa" 的令牌在时间 7 过期，所以目前没有令牌未过期，返回 0。

约束条件：

  • 1 <= timeToLive <= 10^8
  • 1 <= currentTime <= 10^8
  • 1 <= tokenId.length <= 5
  • tokenId 仅包含小写字母
  • 所有对 generate 的调用都将包含唯一的 tokenId 值
  • 所有函数调用中的 currentTime 值严格递增
  • 最多进行 2000 次函数调用

解题思路

这是一道设计类问题，需要我们实现一个身份验证管理器来管理令牌的生命周期。

核心思路： 使用哈希表来存储每个令牌的过期时间。对于每个令牌ID，我们记录其过期时间（生成时间 + timeToLive）。

操作分析：

  1. generate：创建新令牌，记录其过期时间为 currentTime + timeToLive
  2. renew：检查令牌是否存在且未过期，如果满足条件则更新过期时间
  3. countUnexpiredTokens：遍历所有令牌，统计未过期的数量

优化策略：

  • 在 countUnexpiredTokens 中可以顺便清理已过期的令牌，减少内存占用
  • 由于题目保证 currentTime 严格递增，我们可以利用这个特性进行优化

时间复杂度分析：

  • generate 和 renew 操作都是 O(1)
  • countUnexpiredTokens 需要遍历所有令牌，最坏情况为 O(n)

这种实现方式简洁高效，满足题目的所有要求。

代码实现

class AuthenticationManager {
private:
    int timeToLive;
    unordered_map<string, int> tokens; // tokenId -> expiry time
    
public:
    AuthenticationManager(int timeToLive) : timeToLive(timeToLive) {
        
    }
    
    void generate(string tokenId, int currentTime) {
        tokens[tokenId] = currentTime + timeToLive;
    }
    
    void renew(string tokenId, int currentTime) {
        if (tokens.find(tokenId) != tokens.end() && tokens[tokenId] > currentTime) {
            tokens[tokenId] = currentTime + timeToLive;
        }
    }
    
    int countUnexpiredTokens(int currentTime) {
        int count = 0;
        auto it = tokens.begin();
        while (it != tokens.end()) {
            if (it->second > currentTime) {
                count++;
                ++it;
            } else {
                it = tokens.erase(it); // Clean up expired tokens
            }
        }
        return count;
    }
};

class AuthenticationManager:

    def __init__(self, timeToLive: int):
        self.timeToLive = timeToLive
        self.tokens = {}  # tokenId -> expiry time

    def generate(self, tokenId: str, currentTime: int) -> None:
        self.tokens[tokenId] = currentTime + self.timeToLive

    def renew(self, tokenId: str, currentTime: int) -> None:
        if tokenId in self.tokens and self.tokens[tokenId] > currentTime:
            self.tokens[tokenId] = currentTime + self.timeToLive

    def countUnexpiredTokens(self, currentTime: int) -> int:
        # Clean up expired tokens while counting
        expired_tokens = []
        count = 0
        
        for tokenId, expiryTime in self.tokens.items():
            if expiryTime > currentTime:
                count += 1
            else:
                expired_tokens.append(tokenId)
        
        # Remove expired tokens
        for tokenId in expired_tokens:
            del self.tokens[tokenId]
            
        return count

public class AuthenticationManager {
    private int timeToLive;
    private Dictionary<string, int> tokens; // tokenId -> expiry time

    public AuthenticationManager(int timeToLive) {
        this.timeToLive = timeToLive;
        this.tokens = new Dictionary<string, int>();
    }
    
    public void Generate(string tokenId, int currentTime) {
        tokens[tokenId] = currentTime + timeToLive;
    }
    
    public void Renew(string tokenId, int currentTime) {
        if (tokens.ContainsKey(tokenId) && tokens[tokenId] > currentTime) {
            tokens[tokenId] = currentTime + timeToLive;
        }
    }
    
    public int CountUnexpiredTokens(int currentTime) {
        var expiredTokens = new List<string>();
        int count = 0;
        
        foreach (var kvp in tokens) {
            if (kvp.Value > currentTime) {
                count++;
            } else {
                expiredTokens.Add(kvp.Key);
            }
        }
        
        // Clean up expired tokens
        foreach (string tokenId in expiredTokens) {
            tokens.Remove(tokenId);
        }
        
        return count;
    }
}

var AuthenticationManager = function(timeToLive) {
    this.timeToLive = timeToLive;
    this.tokens = new Map(); // tokenId -> expiry time
};

AuthenticationManager.prototype.generate = function(tokenId, currentTime) {
    this.tokens.set(tokenId, currentTime + this.timeToLive);
};

AuthenticationManager.prototype.renew = function(tokenId, currentTime) {
    if (this.tokens.has(tokenId) && this.tokens.get(tokenId) > currentTime) {
        this.tokens.set(tokenId, currentTime + this.timeToLive);
    }
};

AuthenticationManager.prototype.countUnexpiredTokens = function(currentTime) {
    let count = 0;
    const expiredTokens = [];
    
    for (const [tokenId, expiryTime] of this.tokens) {
        if (expiryTime > currentTime) {
            count++;
        } else {
            expiredTokens.push(tokenId);
        }
    }
    
    // Clean up expired tokens
    for (const tokenId of expiredTokens) {
        this.tokens.delete(tokenId);
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
AuthenticationManager()O(1)O(1)
generate()O(1)O(1)
renew()O(1)O(1)
countUnexpiredTokens()O(n)O(1)
总体空间复杂度-O(n)

其中 n 为当前存储的令牌数量。由于题目限制最多 2000 次调用，实际的 n 值相对较小。