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

1、题干​

给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下：

1. 使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
2. 将替换表与普通英文字母表对齐，形成对照表。
3. 按照对照表 替换 message 中的每个字母。
4. 空格 ' ' 保持不变。

• 例如，key = "happy boy"（实际的加密密钥会包含字母表中每个字母 至少一次），据此，可以得到部分对照表（'h' -> 'a'、'a' -> 'b'、'p' -> 'c'、'y' -> 'd'、'b' -> 'e'、'o' -> 'f'）。

返回解密后的消息。

示例 1：

输入：key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
输出："this is a secret"
解释：对照表如上图所示。
提取 "the quick brown fox jumps over the lazy dog" 中每个字母的首次出现可以得到替换表。

示例 2：

输入：key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"
输出："the five boxing wizards jump quickly"
解释：对照表如上图所示。
提取 "eljuxhpwnyrdgtqkviszcfmabo" 中每个字母的首次出现可以得到替换表。

提示：

• 26 <= key.length <= 2000
• key 由小写英文字母及 ' ' 组成
• key 包含英文字母表中每个字符（'a' 到 'z'）至少一次
• 1 <= message.length <= 2000
• message 由小写英文字母和 ' ' 组成

2、思路​

借助哈希集合做字母关系映射

3、代码​

function decodeMessage(key: string, message: string): string {
    const B = ' ', chars = [...new Set(key)].filter(c => c !== B);
    return [].map.call(message, (c) => c === B ? B : String.fromCharCode(97 + chars.indexOf(c))).join('');
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个由英文字母组成的字符串 s ，请你找出并返回 s 中的 最好 英文字母。返回的字母必须为大写形式。如果不存在满足条件的字母，则返回一个空字符串。

最好 英文字母的大写和小写形式必须 都 在 s 中出现。

英文字母 b 比另一个英文字母 a 更好 的前提是：英文字母表中，b 在 a 之 后 出现。

示例 1：

输入：s = "lEeTcOdE"
输出："E"
解释：
字母 'E' 是唯一一个大写和小写形式都出现的字母。

示例 2：

输入：s = "arRAzFif"
输出："R"
解释：
字母 'R' 是大写和小写形式都出现的最好英文字母。
注意 'A' 和 'F' 的大写和小写形式也都出现了，但是 'R' 比 'F' 和 'A' 更好。

示例 3：

输入：s = "AbCdEfGhIjK"
输出：""
解释：
不存在大写和小写形式都出现的字母。

提示：

• 1 <= s.length <= 1000
• s 由小写和大写英文字母组成

2、思路1​

哈希表模拟

3、代码​

function greatestLetter(s: string): string {
    const dict = new Set();
    let ans = '';

    for (const c of s) {
        dict.add(c);
        const l = c.toLowerCase(), L = c.toUpperCase();
        if (L > ans && dict.has(l) && dict.has(L)) ans = L;
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

6、思路2​

倒序枚举字母表

7、代码​

function greatestLetter(s: string): string {
    for (let i = 90; i >= 65; i--) {
        const C = String.fromCharCode(i), c = C.toLowerCase();
        if (s.includes(C) && s.includes(c)) return C;
    }

    return '';
};

8、复杂度​

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

9、执行结果​

1、题干​

给你用户在 LeetCode 的操作日志，和一个整数 k 。日志用一个二维整数数组 logs 表示，其中每个 logs[i] = [IDi, timei] 表示 ID 为 IDi 的用户在 timei 分钟时执行了某个操作。

多个用户 可以同时执行操作，单个用户可以在同一分钟内执行 多个操作 。

指定用户的 用户活跃分钟数（user active minutes，UAM） 定义为用户对 LeetCode 执行操作的 唯一分钟数 。 即使一分钟内执行多个操作，也只能按一分钟计数。

请你统计用户活跃分钟数的分布情况，统计结果是一个长度为 k 且 下标从 1 开始计数 的数组 answer ，对于每个 j（1 <= j <= k），answer[j] 表示 用户活跃分钟数 等于 j 的用户数。

返回上面描述的答案数组 answer 。

示例 1：

输入：logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5
输出：[0,2,0,0,0]
解释：
ID=0 的用户执行操作的分钟分别是：5 、2 和 5 。因此，该用户的用户活跃分钟数为 2（分钟 5 只计数一次）
ID=1 的用户执行操作的分钟分别是：2 和 3 。因此，该用户的用户活跃分钟数为 2
2 个用户的用户活跃分钟数都是 2 ，answer[2] 为 2 ，其余 answer[j] 的值都是 0

示例 2：

输入：logs = [[1,1],[2,2],[2,3]], k = 4
输出：[1,1,0,0]
解释：
ID=1 的用户仅在分钟 1 执行单个操作。因此，该用户的用户活跃分钟数为 1
ID=2 的用户执行操作的分钟分别是：2 和 3 。因此，该用户的用户活跃分钟数为 2
1 个用户的用户活跃分钟数是 1 ，1 个用户的用户活跃分钟数是 2 
因此，answer[1] = 1 ，answer[2] = 1 ，其余的值都是 0

提示：

• 1 <= logs.length <= 104
• 0 <= IDi <= 109
• 1 <= timei <= 105
• k 的取值范围是 [用户的最大用户活跃分钟数, 105]

2、思路1​

使用哈希表模拟

3、代码​

function findingUsersActiveMinutes(logs: number[][], k: number): number[] {
    const map = new Map<number, Set<number>>();
    for (const [id, m] of logs) {
        map.set(id, (map.get(id) ?? new Set()).add(m));
    }

    const ans = new Array(k).fill(0);
    for (const [id, set] of map) {
        if (set.size <= k) ans[set.size - 1] += 1;
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

6、思路2​

使用排序模拟，可以排序+set，也可以排序+过滤

7、代码​

排序+set

function findingUsersActiveMinutes(logs: number[][], k: number): number[] {
    logs.sort((a, b) => a[0] - b[0]);

    const ans = new Array(k).fill(0);
    for (let i = 0, set = new Set(); i < logs.length; i++) {
        set.add(logs[i][1]);
        
        if (logs[i][0] !== logs[i + 1]?.at(0)) {
            if (set.size <= k) ans[set.size - 1] += 1;
            set = new Set();
        }
    }

    return ans;
};

排序+过滤

function findingUsersActiveMinutes(logs: number[][], k: number): number[] {
    logs.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
    logs = logs.filter((l, i) => l[0] !== logs[i + 1]?.at(0) || l[1] !== logs[i + 1]?.at(1));

    const ans = new Array(k).fill(0);
    for (let i = 0, c = 0; i < logs.length; i++) {
        c++;
        if (logs[i][0] !== logs[i + 1]?.at(0)) {
            if (c <= k) ans[c - 1] += 1;
            c = 0;
        }
    }

    return ans;
};

8、复杂度​

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

9、执行结果​

1、题干​

给你一个数组 nums ，数组中只包含非负整数。定义 rev(x) 的值为将整数 x 各个数字位反转得到的结果。比方说 rev(123) = 321 ， rev(120) = 21 。我们称满足下面条件的下标对 (i, j) 是 好的 ：

• 0 <= i < j < nums.length
• nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

请你返回好下标对的数目。由于结果可能会很大，请将结果对 109 + 7 取余 后返回。

示例 1：

输入：nums = [42,11,1,97]
输出：2
解释：两个坐标对为：
 - (0,3)：42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。
 - (1,2)：11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12 。

示例 2：

输入：nums = [13,10,35,24,76]
输出：4

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

2、思路​

题中的条件转换为 nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])，转换后简单很多，遍历所有数字计算 nums[i] - rev(nums[i]) 并使用哈希表计数

3、代码​

function countNicePairs(nums: number[]): number {
    const M = 1e9 + 7, map = new Map();

    let ans = 0;
    for (const n of nums) {
        let cn = n, rn = 0;
        while (cn) {
            rn = 10 * rn + (cn % 10);
            cn = (cn / 10) >> 0;
        }

        const c = map.get(n - rn) || 0;
        ans = (ans + c) % M;
        map.set(n - rn, c + 1);
    }

    return ans;
};

可以使用字符串反转数字，代码更简短，但消耗的时间和内存偏多（时间：204 ms，内存：63.5 MB）。

function countNicePairs(nums: number[]): number {
    const M = 1e9 + 7, map = new Map();

    for (const n of nums) {
        const rn = +[...`${n}`].reverse().join('');
        map.set(n - rn, (map.get(n - rn) || 0) + 1);
    }

    return [...map.values()].reduce((a, c) => (a + (c * c - c) / 2) % M, 0);
};

4、复杂度​

• 时间复杂度：$O(n*logm)$，其中 $n$ 为数组长度，$m$ 为数字值
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。

从 s 中取出字符并重新排列，返回可以形成 target 的 最大 副本数。

示例 1：

输入：s = "ilovecodingonleetcode", target = "code"
输出：2
解释：
对于 "code" 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。
对于 "code" 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。
形成的字符串分别是 "ecod" 和 "code" ，都可以重排为 "code" 。
可以形成最多 2 个 "code" 的副本，所以返回 2 。

示例 2：

输入：s = "abcba", target = "abc"
输出：1
解释：
选取下标为 0 、1 和 2 的字符，可以形成 "abc" 的 1 个副本。 
可以形成最多 1 个 "abc" 的副本，所以返回 1 。
注意，尽管下标 3 和 4 分别有额外的 'a' 和 'b' ，但不能重用下标 2 处的 'c' ，所以无法形成 "abc" 的第 2 个副本。

示例 3：

输入：s = "abbaccaddaeea", target = "aaaaa"
输出：1
解释：
选取下标为 0 、3 、6 、9 和 12 的字符，可以形成 "aaaaa" 的 1 个副本。
可以形成最多 1 个 "aaaaa" 的副本，所以返回 1 。

提示：

• 1 <= s.length <= 100
• 1 <= target.length <= 10
• s 和 target 由小写英文字母组成

2、思路1​

枚举计数

3、代码​

function rearrangeCharacters(s: string, target: string): number {
    let ans = Infinity;

    for (const t of target) {
        const c1 = [...s].filter(c => c === t).length;
        const c2 = [...target].filter(c => c === t).length;
        ans = Math.min(ans, c1 / c2 >> 0);
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

6、思路2​

哈希计数

7、代码​

function rearrangeCharacters(s: string, target: string): number {
    const dict1 = {};
    for (const c of target) dict1[c] = (dict1[c] || 0) + 1;

    const dict2 = {};
    for (const c of s) dict2[c] = (dict2[c] || 0) + 1;

    let ans = Infinity;
    for (const k of Object.keys(dict1)) {
        ans = Math.min(ans, (dict2[k] || 0) / dict1[k] >> 0);
    }

    return ans;
};

8、复杂度​

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

9、执行结果​

1、题干​

给你一个字符串 s ，它包含一些括号对，每个括号中包含一个 非空 的键。

• 比方说，字符串 "(name)is(age)yearsold" 中，有 两个 括号对，分别包含键 "name" 和 "age" 。

你知道许多键对应的值，这些关系由二维字符串数组 knowledge 表示，其中 knowledge[i] = [keyi, valuei] ，表示键 keyi 对应的值为 valuei 。

你需要替换 所有 的括号对。当你替换一个括号对，且它包含的键为 keyi 时，你需要：

• 将 keyi 和括号用对应的值 valuei 替换。
• 如果从 knowledge 中无法得知某个键对应的值，你需要将 keyi 和括号用问号 "?" 替换（不需要引号）。

knowledge 中每个键最多只会出现一次。s 中不会有嵌套的括号。

请你返回替换 所有 括号对后的结果字符串。

示例 1：

输入：s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
输出："bobistwoyearsold"
解释：
键 "name" 对应的值为 "bob" ，所以将 "(name)" 替换为 "bob" 。
键 "age" 对应的值为 "two" ，所以将 "(age)" 替换为 "two" 。

示例 2：

输入：s = "hi(name)", knowledge = [["a","b"]]
输出："hi?"
解释：由于不知道键 "name" 对应的值，所以用 "?" 替换 "(name)" 。

示例 3：

输入：s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
输出："yesyesyesaaa"
解释：相同的键在 s 中可能会出现多次。
键 "a" 对应的值为 "yes" ，所以将所有的 "(a)" 替换为 "yes" 。
注意，不在括号里的 "a" 不需要被替换。

提示：

• 1 <= s.length <= 105
• 0 <= knowledge.length <= 105
• knowledge[i].length == 2
• 1 <= keyi.length, valuei.length <= 10
• s 只包含小写英文字母和圆括号 '(' 和 ')' 。
• s 中每一个左圆括号 '(' 都有对应的右圆括号 ')' 。
• s 中每对括号内的键都不会为空。
• s 中不会有嵌套括号对。
• keyi 和 valuei 只包含小写英文字母。
• knowledge 中的 keyi 不会重复。

2、思路1​

正则

3、代码​

function evaluate(s: string, knowledge: string[][]): string {
    const map = new Map(knowledge as Array<[string, string]>);
    return s.replace(/\(([^)]*)\)/g, (m, s1) => map.get(s1) ?? '?');
};

4、执行结果​

5、思路2​

模拟

6、代码​

function evaluate(s: string, knowledge: string[][]): string {
    const map = new Map(knowledge as Array<[string, string]>);

    let ans = '';
    for (let i = 0, l = 0, r = 0; i < s.length; i = r + 1) {
        l = s.indexOf('(', i);
        if (l < 0) {
            ans += i ? s.slice(i) : s;
            break;
        }

        r = s.indexOf(')', l);

        const w = s.slice(l + 1, r);
        ans += s.slice(i, l) + (map.get(w) ?? '?');
    }

    return ans;
};

7、复杂度​

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

8、执行结果​

1、题干​

给你一个下标从 0 开始长度为 n 的字符串 num ，它只包含数字。

如果对于 每个 0 <= i < n 的下标 i ，都满足数位 i 在 num 中出现了 num[i]次，那么请你返回 true ，否则返回 false 。

示例 1：

输入：num = "1210"
输出：true
解释：
num[0] = '1' 。数字 0 在 num 中出现了一次。
num[1] = '2' 。数字 1 在 num 中出现了两次。
num[2] = '1' 。数字 2 在 num 中出现了一次。
num[3] = '0' 。数字 3 在 num 中出现了零次。
"1210" 满足题目要求条件，所以返回 true 。

示例 2：

输入：num = "030"
输出：false
解释：
num[0] = '0' 。数字 0 应该出现 0 次，但是在 num 中出现了两次。
num[1] = '3' 。数字 1 应该出现 3 次，但是在 num 中出现了零次。
num[2] = '0' 。数字 2 在 num 中出现了 0 次。
下标 0 和 1 都违反了题目要求，所以返回 false 。

提示：

• n == num.length
• 1 <= n <= 10
• num 只包含数字。

2、思路​

模拟

3、代码​

function digitCount(num: string): boolean {
    for (let i = 0; i < 10; i++) {
        let c = +num[i] || 0;
        for (const n of num) {
            if (+n === i) c--;
        }
        if (c) return false;
    }

    return true;
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104
• 1 <= x <= 109

2、思路​

• 数组总和 sum 必须大于 x
• 找 x 转换为找 sum-x，会简单些
• 滑动窗口找总和为 sum-x 的区间 $(l, r]$，区间求和使用前缀和减少时间复杂度

3、代码​

function minOperations(nums: number[], x: number): number {
    let sum = 0, preSums = [];
    for (const n of nums) {
        sum += n;
        preSums.push(sum);
    }

    if (sum <= x) return sum < x ? -1 : nums.length;

    x = sum - x;
    let ans = Infinity, l = -1, r = 0;
    while (l <= r) {
        const y = preSums[r] - (preSums[l] ?? 0);
        if (y === x) ans = Math.min(nums.length - r + l, ans);
        y <= x ? r++ : l++;
    }

    return ans < Infinity ? ans : -1;
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个由小写英文字母组成的字符串 s ，请你找出并返回第一个出现 两次 的字母。

注意：

• 如果 a 的 第二次 出现比 b 的 第二次 出现在字符串中的位置更靠前，则认为字母 a 在字母 b 之前出现两次。
• s 包含至少一个出现两次的字母。

示例 1：

输入：s = "abccbaacz"
输出："c"
解释：
字母 'a' 在下标 0 、5 和 6 处出现。
字母 'b' 在下标 1 和 4 处出现。
字母 'c' 在下标 2 、3 和 7 处出现。
字母 'z' 在下标 8 处出现。
字母 'c' 是第一个出现两次的字母，因为在所有字母中，'c' 第二次出现的下标是最小的。

示例 2：

输入：s = "abcdd"
输出："d"
解释：
只有字母 'd' 出现两次，所以返回 'd' 。

提示：

• 2 <= s.length <= 100
• s 由小写英文字母组成
• s 包含至少一个重复字母

2、思路​

记录字符出现次数，首次重复出现则返回

3、代码​

function repeatedCharacter(s: string): string {
    const dict = {};
    for (const c of s) {
        if (dict[c]) return c;
        dict[c] = 1;
    }
};

4、复杂度​

• 时间复杂度：$O(C)$，其中 $C<=26$
• 空间复杂度：$O(C)$，其中 $C<=26$

1、题干​

给你三个整数数组 nums1、nums2 和 nums3 ，请你构造并返回一个 元素各不相同的 数组，且由 至少 在 两个 数组中出现的所有值组成。数组中的元素可以按 任意 顺序排列。

示例 1：

输入：nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]
输出：[3,2]
解释：至少在两个数组中出现的所有值为：
- 3 ，在全部三个数组中都出现过。
- 2 ，在数组 nums1 和 nums2 中出现过。

示例 2：

输入：nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]
输出：[2,3,1]
解释：至少在两个数组中出现的所有值为：
- 2 ，在数组 nums2 和 nums3 中出现过。
- 3 ，在数组 nums1 和 nums2 中出现过。
- 1 ，在数组 nums1 和 nums3 中出现过。

示例 3：

输入：nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]
输出：[]
解释：不存在至少在两个数组中出现的值。

提示：

• 1 <= nums1.length, nums2.length, nums3.length <= 100
• 1 <= nums1[i], nums2[j], nums3[k] <= 100

2、思路1​

借助位运算、二进制，计算和存储数字出现次数，以消除重复数字产生的影响

3、代码​

function twoOutOfThree(nums1: number[], nums2: number[], nums3: number[]): number[] {
    const bucket = new Array(101).fill(0);
    const matrix = [nums1, nums2, nums3];

    for (let i = 0; i < matrix.length; i++) {
        for (const n of matrix[i]) bucket[n] = bucket[n] | (1 << i);
    }

    return bucket.map((c, n) => (c > 2 && c !== 4) ? n : 0).filter(Boolean);
};

4、复杂度​

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

5、执行结果​

6、思路2​

哈希集合过滤数组中重复出现的数字

7、代码​

function twoOutOfThree(nums1: number[], nums2: number[], nums3: number[]): number[] {
    const s1 = new Set(nums1);
    const s2 = new Set(nums2);
    const s3 = new Set(nums3);
    const s4 = new Set([...nums1, ...nums2, ...nums3]);

    const ans = [];
    for (const n of s4) {
        const c = +s1.has(n) + +s2.has(n) + +s3.has(n);
        if (c > 1) ans.push(n);
    }

    return ans;
};

8、复杂度​

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

9、执行结果​