列表

详情

1797. 设计一个验证系统

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

请你实现 AuthenticationManager 类：

如果一个验证码在时刻 t 过期，且另一个操作恰好在时刻 t 发生（renew 或者 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); // 构造 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 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class AuthenticationManager { public: AuthenticationManager(int timeToLive) { } void generate(string tokenId, int currentTime) { } void renew(string tokenId, int currentTime) { } int countUnexpiredTokens(int currentTime) { } }; /** * Your AuthenticationManager object will be instantiated and called as such: * AuthenticationManager* obj = new AuthenticationManager(timeToLive); * obj->generate(tokenId,currentTime); * obj->renew(tokenId,currentTime); * int param_3 = obj->countUnexpiredTokens(currentTime); */

golang 解法, 执行用时: 40 ms, 内存消耗: 7.4 MB, 提交时间: 2022-12-05 18:17:20 

type AuthenticationManager struct {
    Codes []Code
    TimeToLive int
}

type Code struct {
    TokenId string
    CurrentTime int
}

func Constructor(timeToLive int) AuthenticationManager {
    return AuthenticationManager{
        TimeToLive: timeToLive,
    }
}


func (this *AuthenticationManager) Generate(tokenId string, currentTime int)  {
    code := Code{
        TokenId: tokenId,
        CurrentTime: currentTime,
    }
    this.Codes = append(this.Codes, code)
}


func (this *AuthenticationManager) Renew(tokenId string, currentTime int)  {
    for i := 0; i < len(this.Codes); i++ {
        if this.Codes[i].TokenId == tokenId && this.Codes[i].CurrentTime+this.TimeToLive > currentTime{
            this.Codes[i].CurrentTime = currentTime
        }
    }

}


func (this *AuthenticationManager) CountUnexpiredTokens(currentTime int) int {
    res := 0
    for i := 0; i < len(this.Codes); i++ {
        if this.Codes[i].CurrentTime+this.TimeToLive > currentTime {
            res++
        }
    }
    return res
}


/**
 * Your AuthenticationManager object will be instantiated and called as such:
 * obj := Constructor(timeToLive);
 * obj.Generate(tokenId,currentTime);
 * obj.Renew(tokenId,currentTime);
 * param_3 := obj.CountUnexpiredTokens(currentTime);
 */

golang 解法, 执行用时: 40 ms, 内存消耗: 7.2 MB, 提交时间: 2022-12-05 18:16:28 

type AuthenticationManager struct {
	Map  map[string]int
	keys []int
	t    int
}

func Constructor(timeToLive int) AuthenticationManager {
	return AuthenticationManager{t: timeToLive,Map:make(map[string]int,0)}
}

func (au *AuthenticationManager) Generate(tokenId string, currentTime int) {
	au.Map[tokenId] = len(au.keys)
	au.keys = append(au.keys, au.t+currentTime)
}

func (au *AuthenticationManager) Renew(tokenId string, currentTime int) {
	if index, ok := au.Map[tokenId]; ok {
		if au.keys[index] > currentTime {
			au.keys[index] = currentTime + au.t
		}
	}
}

func (au *AuthenticationManager) CountUnexpiredTokens(currentTime int) int {
	l := 0
	for _, key := range au.keys {
		if key > currentTime {
			l++
		}
	}
	return l
}


/**
 * Your AuthenticationManager object will be instantiated and called as such:
 * obj := Constructor(timeToLive);
 * obj.Generate(tokenId,currentTime);
 * obj.Renew(tokenId,currentTime);
 * param_3 := obj.CountUnexpiredTokens(currentTime);
 */


/**
 * Your AuthenticationManager object will be instantiated and called as such:
 * obj := Constructor(timeToLive);
 * obj.Generate(tokenId,currentTime);
 * obj.Renew(tokenId,currentTime);
 * param_3 := obj.CountUnexpiredTokens(currentTime);
 */

golang 解法, 执行用时: 76 ms, 内存消耗: 7.4 MB, 提交时间: 2022-12-05 18:15:54 

type AuthenticationManager struct {
	manager map[string]int
	timetolive int
}


func Constructor(timeToLive int) AuthenticationManager {
	return AuthenticationManager{
		manager: map[string]int{},
		timetolive: timeToLive,
	}
}

// map看一下新增key值，怎么写入的？
func (this *AuthenticationManager) Generate(tokenId string, currentTime int)  {
	this.manager[tokenId] = currentTime
}


func (this *AuthenticationManager) Renew(tokenId string, currentTime int)  {
	if v,ok :=this.manager[tokenId];ok {
		if v + this.timetolive > currentTime{
			this.manager[tokenId] = currentTime
		}
	}
}


func (this *AuthenticationManager) CountUnexpiredTokens(currentTime int) int {
	ans := 0
	for _,v := range this.manager {
		if v + this.timetolive > currentTime{
			ans++
		}
	}
	return ans
}


/**
 * Your AuthenticationManager object will be instantiated and called as such:
 * obj := Constructor(timeToLive);
 * obj.Generate(tokenId,currentTime);
 * obj.Renew(tokenId,currentTime);
 * param_3 := obj.CountUnexpiredTokens(currentTime);
 */


/**
 * Your AuthenticationManager object will be instantiated and called as such:
 * obj := Constructor(timeToLive);
 * obj.Generate(tokenId,currentTime);
 * obj.Renew(tokenId,currentTime);
 * param_3 := obj.CountUnexpiredTokens(currentTime);
 */

java 解法, 执行用时: 56 ms, 内存消耗: 42.8 MB, 提交时间: 2022-12-05 18:14:20 

class AuthenticationManager {
    private int timeToLive;
    private Map<String, Integer> tokens;

    public AuthenticationManager(int timeToLive) {
        tokens = new HashMap<>();
        this.timeToLive = timeToLive;
    }

    /**
     * 根据题意，不需要考虑是否之前已经存在了，只需要把 tokenId-currentTime 更新/添加到哈希表中就好
     */
    public void generate(String tokenId, int currentTime) {
        tokens.put(tokenId, currentTime);
    }

    public void renew(String tokenId, int currentTime) {
        // 首先看看缓存（哈希表）中里面有没有对应的 tokenId，如果没有就什么都不用做了
        if (tokens.containsKey(tokenId)) {
            // 如果有的话，先记录下来它的上次生成时间
            int time = tokens.get(tokenId);
            // currentTime - time 就是上次生成时间和当前时间的差值
            // 如果差值严格小于生存时间 timeToLive ，那么就可以更新了，否则什么都不做
            if (currentTime - time < timeToLive) tokens.put(tokenId, currentTime);
        }
    }

    public int countUnexpiredTokens(int currentTime) {
        int ans = 0;
        // 对缓存（哈希表）中的每一个对象进行遍历，检查他们的生成时间和当前时间的差值是否满足要求
        for (Map.Entry<String, Integer> entry : tokens.entrySet()) {
            if (currentTime - entry.getValue() < timeToLive) ++ans;
        }
        return ans;
    }
}

/**
 * Your AuthenticationManager object will be instantiated and called as such:
 * AuthenticationManager obj = new AuthenticationManager(timeToLive);
 * obj.generate(tokenId,currentTime);
 * obj.renew(tokenId,currentTime);
 * int param_3 = obj.countUnexpiredTokens(currentTime);
 */

python3 解法, 执行用时: 220 ms, 内存消耗: 16.4 MB, 提交时间: 2022-12-05 18:13:26 

class AuthenticationManager:

    def __init__(self, timeToLive: int):
        self.ttl = timeToLive
        self.map = {}

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

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

    def countUnexpiredTokens(self, currentTime: int) -> int:
        return len([a for a in self.map if self.map[a] > currentTime])


# Your AuthenticationManager object will be instantiated and called as such:
# obj = AuthenticationManager(timeToLive)
# obj.generate(tokenId,currentTime)
# obj.renew(tokenId,currentTime)
# param_3 = obj.countUnexpiredTokens(currentTime)

python3 解法, 执行用时: 100 ms, 内存消耗: 16.8 MB, 提交时间: 2022-12-05 18:13:07 

class Node:
    def __init__(self, val=0, key=None, prev=None, nxt=None):
        self.expire = val
        self.key = key
        self.prev = prev
        self.next = nxt

class AuthenticationManager:

    def __init__(self, timeToLive: int):
        self.ttl = timeToLive
        self.head = Node(-1)
        self.tail = Node(-1)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.map = {}
    
    # 新建一个节点，塞到链表最后面，添加到哈希表里
    def generate(self, tokenId: str, currentTime: int) -> None:
        node = Node(currentTime + self.ttl, tokenId)
        self.map[tokenId] = node

        #塞到最后
        last = self.tail.prev
        last.next = node
        node.prev = last
        self.tail.prev = node
        node.next = self.tail

    # 如果这个节点存在且没有过期，那么把这个节点找出来，更新过期时间，塞到最后
    def renew(self, tokenId: str, currentTime: int) -> None:
        if tokenId in self.map and self.map[tokenId].expire > currentTime:

            #从原来的地方取出来
            node = self.map[tokenId]
            prev = node.prev
            nxt = node.next
            prev.next = nxt
            nxt.prev = prev
            #更新过期时间
            node.expire = currentTime + self.ttl
            #塞到最后
            last = self.tail.prev
            last.next = node
            node.prev = last
            self.tail.prev = node
            node.next = self.tail           
        
    # 在双向链表里把所有过期的节点删了，在哈希表里也删掉，返回长度
    def countUnexpiredTokens(self, currentTime: int) -> int:
        while self.head.next.expire != -1 and self.head.next.expire <= currentTime:
            node = self.head.next
            self.map.pop(node.key)
            self.head.next = node.next
            node.next.prev = self.head
        return len(self.map)


# Your AuthenticationManager object will be instantiated and called as such:
# obj = AuthenticationManager(timeToLive)
# obj.generate(tokenId,currentTime)
# obj.renew(tokenId,currentTime)
# param_3 = obj.countUnexpiredTokens(currentTime)

上一题

© 2024 leetcode.cn