55 篇博文 含有标签「哈希表」

1、题干​

给你一个长度为 n 的字符串数组 names 。你将会在文件系统中创建 n 个文件夹：在第 i 分钟，新建名为 names[i] 的文件夹。

由于两个文件 不能 共享相同的文件名，因此如果新建文件夹使用的文件名已经被占用，系统会以 (k) 的形式为新文件夹的文件名添加后缀，其中 k 是能保证文件名唯一的 最小正整数 。

返回长度为 n 的字符串数组，其中 ans[i] 是创建第 i 个文件夹时系统分配给该文件夹的实际名称。

示例 1：

输入：names = ["pes","fifa","gta","pes(2019)"]
输出：["pes","fifa","gta","pes(2019)"]
解释：文件系统将会这样创建文件名：
"pes" --> 之前未分配，仍为 "pes"
"fifa" --> 之前未分配，仍为 "fifa"
"gta" --> 之前未分配，仍为 "gta"
"pes(2019)" --> 之前未分配，仍为 "pes(2019)"

示例 2：

输入：names = ["gta","gta(1)","gta","avalon"]
输出：["gta","gta(1)","gta(2)","avalon"]
解释：文件系统将会这样创建文件名：
"gta" --> 之前未分配，仍为 "gta"
"gta(1)" --> 之前未分配，仍为 "gta(1)"
"gta" --> 文件名被占用，系统为该名称添加后缀 (k)，由于 "gta(1)" 也被占用，所以 k = 2 。实际创建的文件名为 "gta(2)" 。
"avalon" --> 之前未分配，仍为 "avalon"

示例 3：

输入：names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
输出：["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
解释：当创建最后一个文件夹时，最小的正有效 k 为 4 ，文件名变为 "onepiece(4)"。

示例 4：

输入：names = ["wano","wano","wano","wano"]
输出：["wano","wano(1)","wano(2)","wano(3)"]
解释：每次创建文件夹 "wano" 时，只需增加后缀中 k 的值即可。

示例 5：

输入：names = ["kaido","kaido(1)","kaido","kaido(1)"]
输出：["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
解释：注意，如果含后缀文件名被占用，那么系统也会按规则在名称后添加新的后缀 (k) 。

提示：

• 1 <= names.length <= 5 * 10^4
• 1 <= names[i].length <= 20
• names[i] 由小写英文字母、数字和/或圆括号组成。

2、思路1-暴力哈希​

遍历文件名数组 names，遇到不存在的文件名就将它存入哈希表与结果数组；遇到已存在的文件名就从 1 开始尝试给它加后缀，直到找到不存在的文件名，新的文件名同样需要存入哈希表与结果数组

3、代码​

function getFolderNames(names: string[]): string[] {
    const set = new Set();

    return names.map(name => {
        if (!set.has(name)) return set.add(name), name;

        for (let k = 1; k; k++) {
            const newName = name + `(${k})`;
            if (!set.has(newName)) {
                return set.add(newName), newName;
            }
        }
    });
};

4、执行结果​

5、思路2-优化哈希​

上面的解法可以对内层循环进行优化，记录文件名是否存在的同时也记录它出现的次数，这样可以使得内层循环不用每次都从 1 开始

6、代码​

function getFolderNames(names: string[]): string[] {
    const map = new Map<string, number>();

    return names.map(name => {
        if (!map.has(name)) return map.set(name, 1), name;

        for (let k = map.get(name); k; k++) {
            const newName = name + `(${k})`;
            if (map.has(newName)) continue;

            map.set(name, k + 1);
            map.set(newName, 1);

            return newName;
        }
    });
};

7、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

8、执行结果​

1、题干​

给你一个整数数组 nums ，返回其中 按位与三元组 的数目。

按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：

• 0 <= i < nums.length
• 0 <= j < nums.length
• 0 <= k < nums.length
• nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。

示例 1：

输入：nums = [2,1,3]
输出：12
解释：可以选出如下 i, j, k 三元组：
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

示例 2：

输入：nums = [0,0,0]
输出：27

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] < 216

先暴力打个卡睡觉

2、思路​

本题可以用三数之和的思路暴力解题。先用哈希表 map 存储所有二元组按位与的结果与出现次数，再枚举数组 nums 与 map 所有的键，如果二者位与结果为 0 就累计其次数

这种暴力思路会超时吗？可以稍微分析下时间复杂度：

• 第一个嵌套循环的时间复杂度为 $O(n^2)$，其中 $n$ 为数组 nums 长度，由于 $n <= 1000$，整体量级最多为 $10^6$，基本不会超时；
• 第二个嵌套循环的时间复杂度为 $O(nm)$，其中 $m$ 为哈希表键的个数，由于 nums[i] 小于 $2^{16}$，所以二元组按位与的结果个数不会超过 $2^{16}$，即哈希表的键数 $m<=65536$，整体量级最多为 $6*10^7$，大概率能过

3、代码​

function countTriplets(nums: number[]): number {
    const map = new Map();
    for (const x of nums) {
        for (const y of nums) {
            const z = x & y;
            map.set(z, (map.get(z) || 0) + 1);
        }
    }

    let ans = 0;
    for (const x of nums) {
        for (const [y, c] of map) {
            if (!(x & y)) ans += c;
        }
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(nm)$
• 空间复杂度：$O(m)$

5、执行结果​

1、题干​

给你两个二维整数数组 items1 和 items2 ，表示两个物品集合。每个数组 items 有以下特质：

• items[i] = [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 ，weighti 表示第 i 件物品的 重量 。
• items 中每件物品的价值都是 唯一的 。

请你返回一个二维数组 ret，其中 ret[i] = [valuei, weighti]， weighti 是所有价值为 valuei 物品的 重量之和 。

注意：ret 应该按价值 升序 排序后返回。

示例 1：

输入：items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]
输出：[[1,6],[3,9],[4,5]]
解释：
value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 5 ，总重量为 1 + 5 = 6 。
value = 3 的物品再 items1 中 weight = 8 ，在 items2 中 weight = 1 ，总重量为 8 + 1 = 9 。
value = 4 的物品在 items1 中 weight = 5 ，总重量为 5 。
所以，我们返回 [[1,6],[3,9],[4,5]] 。

示例 2：

输入：items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]]
输出：[[1,4],[2,4],[3,4]]
解释：
value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 3 ，总重量为 1 + 3 = 4 。
value = 2 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 1 ，总重量为 3 + 1 = 4 。
value = 3 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。
所以，我们返回 [[1,4],[2,4],[3,4]] 。

示例 3：

输入：items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]]
输出：[[1,7],[2,4],[7,1]]
解释：
value = 1 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 4 ，总重量为 3 + 4 = 7 。
value = 2 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。
value = 7 的物品在 items2 中 weight = 1 ，总重量为 1 。
所以，我们返回 [[1,7],[2,4],[7,1]] 。

提示：

• 1 <= items1.length, items2.length <= 1000
• items1[i].length == items2[i].length == 2
• 1 <= valuei, weighti <= 1000
• items1 中每个 valuei 都是 唯一的 。
• items2 中每个 valuei 都是 唯一的 。

2、思路1-整合+排序​

整合两个数组再统一升序排序，接着遍历所有物品得到结果

3、代码​

function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
    items1.push(...items2);
    items1.sort((a, b) => a[0] - b[0]);

    const ans = [];
    for (let i = 0; i < items1.length; i++) {
        if (items1[i][0] === items1[i + 1]?.at(0)) items1[i + 1][1] += items1[i][1];
        else ans.push(items1[i]);
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$

5、执行结果​

6、思路2-桶排序​

以价值作为桶序号，累加物品重量，最后返回重量大于0的桶序号及其重量

桶内不需要再排序，而是累加数值，跟常见的桶排序有点不同

7、代码​

function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
    const bucket = new Array(1001).fill(0);
    for (let i = 0; i < items1.length || i < items2.length; i++) {
        if (items1[i]) bucket[items1[i][0]] += items1[i][1];
        if (items2[i]) bucket[items2[i][0]] += items2[i][1];
    }

    return bucket.map((w, i) => [i, w]).filter(b => b[1]);
};

8、复杂度​

• 时间复杂度：$O(max(C,n))$
• 空间复杂度：$O(C)$

9、执行结果​

10、思路3-哈希+排序​

以价值作为哈希表的键，累加物品重量，最后返回按键升序排序的键值对

11、代码​

function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
    const map = new Map();
    for (let i = 0; i < items1.length || i < items2.length; i++) {
        if (items1[i]) map.set(items1[i][0], (map.get(items1[i][0]) || 0) + items1[i][1]);
        if (items2[i]) map.set(items2[i][0], (map.get(items2[i][0]) || 0) + items2[i][1]);
    }

    return [...map].sort((a, b) => a[0] - b[0]);
};

12、复杂度​

• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$

13、执行结果​

14、思路4-双指针+排序​

先对两个数组分别排序，再使用双指针按价值从小到大遍历所有物品

15、代码​

function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
    items1.sort((a, b) => a[0] - b[0]);
    items2.sort((a, b) => a[0] - b[0]);

    const ans = [];
    for (let i = 0, j = 0; i < items1.length || j < items2.length;) {
        while (i < items1.length && (!items2[j] || items1[i][0] < items2[j][0])) {
            ans.push(items1[i]);
            i++;
        }

        while (j < items2.length && (!items1[i] || items1[i][0] > items2[j][0])) {
            ans.push(items2[j]);
            j++;
        }

        if (i < items1.length && j < items2.length && items1[i][0] === items2[j][0]) {
            items1[i][1] += items2[j][1];
            ans.push(items1[i]);
            i++, j++;
        }
    }

    return ans;
};

16、复杂度​

• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(\log n)$

17、执行结果​

1、题干​

给你一个非负整数数组 nums 。在一步操作中，你必须：

• 选出一个正整数 x ，x 需要小于或等于 nums 中 最小 的 非零 元素。
• nums 中的每个正整数都减去 x。

返回使 nums 中所有元素都等于 0 需要的 最少 操作数。

示例 1：

输入：nums = [1,5,0,3,5]
输出：3
解释：
第一步操作：选出 x = 1 ，之后 nums = [0,4,0,2,4] 。
第二步操作：选出 x = 2 ，之后 nums = [0,2,0,0,2] 。
第三步操作：选出 x = 2 ，之后 nums = [0,0,0,0,0] 。

示例 2：

输入：nums = [0]
输出：0
解释：nums 中的每个元素都已经是 0 ，所以不需要执行任何操作。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

2、思路1​

根据题目描述，每一步都消除了所有最小的正整数，因此最少步数就是数组 nums 去重后正整数的个数。

第一个思路是：排序后统计去重正整数个数

3、代码​

function minimumOperations(nums: number[]): number {
    nums.sort((a, b) => a - b);

    let step = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] && nums[i] !== nums[i - 1]) step++;
    }

    return step;
};

4、复杂度​

• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(\log n)$

5、执行结果​

6、思路2​

哈希去重统计正整数的个数

7、代码​

function minimumOperations(nums: number[]): number {
    const set = new Set(nums);
    return set.size - (set.has(0) ? 1 : 0);
};

或者这样

function minimumOperations(nums: number[]): number {
    return new Set(nums.filter(Boolean)).size;
};

8、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

9、执行结果​

1、题干​

给你一个整数数组 ranks 和一个字符数组 suit 。你有 5 张扑克牌，第 i 张牌大小为 ranks[i] ，花色为 suits[i] 。

下述是从好到坏你可能持有的 手牌类型 ：

1. "Flush"：同花，五张相同花色的扑克牌。
2. "Three of a Kind"：三条，有 3 张大小相同的扑克牌。
3. "Pair"：对子，两张大小一样的扑克牌。
4. "High Card"：高牌，五张大小互不相同的扑克牌。

请你返回一个字符串，表示给定的 5 张牌中，你能组成的 最好手牌类型 。

注意：返回的字符串 大小写 需与题目描述相同。

示例 1：

输入：ranks = [13,2,3,1,9], suits = ["a","a","a","a","a"]
输出："Flush"
解释：5 张扑克牌的花色相同，所以返回 "Flush" 。

示例 2：

输入：ranks = [4,4,2,4,4], suits = ["d","a","a","b","c"]
输出："Three of a Kind"
解释：第一、二和四张牌组成三张相同大小的扑克牌，所以得到 "Three of a Kind" 。
注意我们也可以得到 "Pair" ，但是 "Three of a Kind" 是更好的手牌类型。
有其他的 3 张牌也可以组成 "Three of a Kind" 手牌类型。

示例 3：

输入：ranks = [10,10,2,12,9], suits = ["a","b","c","a","d"]
输出："Pair"
解释：第一和第二张牌大小相同，所以得到 "Pair" 。
我们无法得到 "Flush" 或者 "Three of a Kind" 。

提示：

• ranks.length == suits.length == 5
• 1 <= ranks[i] <= 13
• 'a' <= suits[i] <= 'd'
• 任意两张扑克牌不会同时有相同的大小和花色。

2、思路​

结果总共4种情况，可以分类讨论：

• 首先判断花色，全部相同则为同花 Flush
• 对 ranks 排序，遍历检查 ranks 属于其他哪种情况
• 若大小全不同，则为高牌 High Card
• 若有3张相同，则为三条 Three of a Kind
• 最后只剩对子 Pair 这一种可能

3、代码​

function bestHand(ranks: number[], suits: string[]): string {
    if (suits.every(s => s === suits[0])) return 'Flush';

    ranks.sort((a, b) => a - b);
    if (ranks.every((r, i) => r !== ranks[i - 1])) return 'High Card';

    if (ranks.some((r, i) => r === ranks[i - 1] && r === ranks[i + 1])) return 'Three of a Kind';

    return 'Pair';
};

4、复杂度​

• 时间复杂度：$O(C)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤：

• 从 nums 选出 两个 相等的 整数
• 从 nums 中移除这两个整数，形成一个 数对

请你在 nums 上多次执行此操作直到无法继续执行。

返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，其中 answer[0] 是形成的数对数目，answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。

示例 1：

输入：nums = [1,3,2,1,3,2,2]
输出：[3,1]
解释：
nums[0] 和 nums[3] 形成一个数对，并从 nums 中移除，nums = [3,2,3,2,2] 。
nums[0] 和 nums[2] 形成一个数对，并从 nums 中移除，nums = [2,2,2] 。
nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [2] 。
无法形成更多数对。总共形成 3 个数对，nums 中剩下 1 个数字。

示例 2：

输入：nums = [1,1]
输出：[1,0]
解释：nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [] 。
无法形成更多数对。总共形成 1 个数对，nums 中剩下 0 个数字。

示例 3：

输入：nums = [0]
输出：[0,1]
解释：无法形成数对，nums 中剩下 1 个数字。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

2、思路​

假设所求结果为数组 ans，ans[0] 表示数对数目，ans[1] 表示剩下的整数数目。

遍历 nums 数组并对每个整数计数，当某个整数个数为奇数时 ans[1]+=1，反之 ans[1]-=1 且 ans[0]+=1。

3、代码​

function numberOfPairs(nums: number[]): number[] {
    const ans = [0, 0], bucket = new Array(101).fill(0);

    for (let i = 0; i < nums.length; i++) {
        bucket[nums[i]] += 1;
        ans[0] += bucket[nums[i]] % 2 ? 0 : 1;
        ans[1] += bucket[nums[i]] % 2 ? 1 : -1;
    }

    return ans;
};

4、复杂度​

• 时间复杂：$O(n)$
• 空间复杂：$O(C)$

5、执行结果​

1、题干​

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

示例 1：

输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

示例 2：

输入：hours = [6,6,6]
输出：0

提示：

• 1 <= hours.length <= 104
• 0 <= hours[i] <= 16

2、思路-前缀和+哈希表​

• 计算 hours 的前缀和数组 sums，当 hours[i] 大于 8 时前缀和 +1 否则 -1
• 将 sums[i] 与 i 分别作为键值存入哈希表 map；为保证结果时段最大，仅当哈希表中不存在 sums[i] 时才存入该键值对
• 如果 sums[i] 大于 0，则区间 [0,i] 可能是最长时段
• 如果 sums[i] 小于等于 0，则区间 [map.get(sums[i] - 1),i) 也可能是最长时段
• 所有备选时段长度的最大值即所求的最长时段

这题的前缀和在整数范围上具有连续性，所以能用哈希表

3、代码​

function longestWPI(hours: number[]): number {
    const sums = hours.map(() => 0);
    const map = new Map();

    let ans = 0;
    for (let i = 0; i < hours.length; i++) {
        sums[i] = (sums[i - 1] || 0) + (hours[i] > 8 ? 1 : -1);
        if (sums[i] > 0) ans = Math.max(ans, i + 1);
        else {
            if (map.has(sums[i] - 1)) ans = Math.max(ans, i - map.get(sums[i] - 1));
        }

        if (!map.has(sums[i])) map.set(sums[i], i);
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

6、前缀和+栈​

这个思路是我能写出来的吗

function longestWPI(hours: number[]): number {
    const sums = hours.map(() => 0);
    const minStack = [0];

    let ans = 0;
    for (let i = 0; i < hours.length; i++) {
        sums[i] = (sums[i - 1] || 0) + (hours[i] > 8 ? 1 : -1);
        if (sums[i] > 0) ans = Math.max(ans, i + 1);
        if (sums[i] < sums[minStack.at(-1)]) minStack.push(i);
    }

    for (let i = hours.length - 1; i > -1; i--) {
        while (sums[minStack.at(-1)] < sums[i]) {
            const l = minStack.pop();
            ans = Math.max(ans, i - l);
        }
    }

    return ans;
};

1、题干​

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。

在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。

我们可以按下面的指令规则行动：

• 如果方格存在，'U' 意味着将我们的位置上移一行；
• 如果方格存在，'D' 意味着将我们的位置下移一行；
• 如果方格存在，'L' 意味着将我们的位置左移一列；
• 如果方格存在，'R' 意味着将我们的位置右移一列；
• '!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。

（注意，字母板上只存在有字母的位置。）

返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

示例 1：

输入：target = "leet"
输出："DDR!UURRR!!DDD!"

示例 2：

输入：target = "code"
输出："RR!DDRR!UUL!R!"

提示：

• 1 <= target.length <= 100
• target 仅含有小写英文字母。

2、思路​

根据题意模拟，关键注意 z 的路线否则会越界；任意字母到 z 的路线优先在水平方向移动，其他情况则优先在垂直方向移动

3、代码​

function alphabetBoardPath(target: string): string {
    let ans = '', p1 = [0, 0], p2 = [0, 0];

    for (let i = 0; i < target.length; i++) {
        p1 = p2;
        const code = target.charCodeAt(i) - 97;
        p2 = [code / 5 >> 0, code % 5];

        const dx = p2[1] - p1[1], dy = p2[0] - p1[0];
        const my = (dy >= 0 ? 'D'.repeat(dy) : 'U'.repeat(-dy));
        const mx = (dx >= 0 ? 'R'.repeat(dx) : 'L'.repeat(-dx));

        ans += (target[i] === 'z' ? mx + my : my + mx) + '!';
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

你需要设计一个包含验证码的验证系统。每一次验证中，用户会收到一个新的验证码，这个验证码在 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：

输入：
["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 。

提示：

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

2、思路​

根据题意模拟，token 存储在哈希表中；generate 与 renew 直接读写哈希表，时间复杂度 $O(1)$；countUnexpiredTokens 需要遍历哈希表中所有值，时间复杂度为 $O(n)$

由于所有函数调用次数最多为 $2000$，所以时间复杂度的最大量级为 $1000*1000$，基本不会出现超时

3、代码​

class AuthenticationManager {
    timeToLive: number;
    tokenMap: Map<string, number>;

    constructor(timeToLive: number) {
        this.timeToLive = timeToLive;
        this.tokenMap = new Map();
    }

    generate(tokenId: string, currentTime: number): void {
        this.tokenMap.set(tokenId, currentTime + this.timeToLive);
    }

    renew(tokenId: string, currentTime: number): void {
        if (this.tokenMap.get(tokenId) > currentTime) this.generate(tokenId, currentTime);
    }

    countUnexpiredTokens(currentTime: number): number {
        let ans = 0;
        for (const t of this.tokenMap.values()) {
            if (t > currentTime) ans++;
        }
        return ans;
    }
}

4、复杂度​

• 时间复杂度：generate $O(1)$，renew $O(1)$，countUnexpiredTokens $O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡，安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工卡的次数大于等于三次，这个系统会自动发布一个 警告 。

给你字符串数组 keyName 和 keyTime ，其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在 某一天 内使用员工卡的时间。

使用时间的格式是 24小时制 ，形如 "HH:MM" ，比方说 "23:51" 和 "09:49" 。

请你返回去重后的收到系统警告的员工名字，将它们按 字典序升序 排序后返回。

请注意 "10:00" - "11:00" 视为一个小时时间范围内，而 "22:51" - "23:52" 不被视为一小时时间范围内。

示例 1：

输入：keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
输出：["daniel"]
解释："daniel" 在一小时内使用了 3 次员工卡（"10:00"，"10:40"，"11:00"）。

示例 2：

输入：keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
输出：["bob"]
解释："bob" 在一小时内使用了 3 次员工卡（"21:00"，"21:20"，"21:30"）。

提示：

• 1 <= keyName.length, keyTime.length <= 105
• keyName.length == keyTime.length
• keyTime 格式为 "HH:MM" 。
• 保证 [keyName[i], keyTime[i]] 形成的二元对 互不相同 。
• 1 <= keyName[i].length <= 10
• keyName[i] 只包含小写英文字母。

2、思路1​

哈希表存储员工姓名（键）和开门时间数组（值），时间转为分钟数并排序，最后检查每个员工的开门时间是否违规

3、代码​

function alertNames(names: string[], times: string[]): string[] {
    const map = new Map<string, number[]>();
    for (let i = 0; i < names.length; i++) {
        if (!map.has(names[i])) map.set(names[i], []);
        map.get(names[i]).push(60 * (+times[i].slice(0, 2)) + +(times[i].slice(3)));
    }

    const ans = [];
    for (const [name, minutes] of map) {
        if (minutes.length < 3) continue;

        minutes.sort((a, b) => a - b);
        for (let i = 0; i < minutes.length - 2 && ans.at(-1) !== name; i++) {
            if (minutes[i + 2] - minutes[i] <= 60) ans.push(name);
        }
    }

    return ans.sort();
};

4、复杂度​

• 时间复杂度：$O(n*logn)$
• 空间复杂度：$O(n)$

5、执行结果​

6、思路2​

二维数组存储员工姓名和开门时间，时间转为分钟数，对二维数组按姓名和分钟数升序排序，最后检查每个员工的开门时间是否违规

7、代码​

function alertNames(names: string[], times: string[]): string[] {
    const matrix: [string, number][] = names.map((n, i) => [n, 60 * (+times[i].slice(0, 2)) + +(times[i].slice(3))]);
    matrix.sort((a, b) => {
        if (a[0] === b[0]) return a[1] - b[1];
        return a[0] > b[0] ? 1 : -1;
    });

    const ans = [];

    for (let i = 0; i < matrix.length - 2; i++) {
        if (matrix[i + 2][0] !== matrix[i][0] || matrix[i][0] === ans.at(-1)) continue;
        if (matrix[i + 2][1] - matrix[i][1] <= 60) ans.push(matrix[i][0]);
    }

    return ans;
};

8、复杂度​

• 时间复杂度：$O(n*logn)$
• 空间复杂度：$O(n)$

9、执行结果​