- 标签：哈希表、字符串、排序

- 难度：中等

- [1657. 确定两个字符串是否接近 - 力扣](https://leetcode.cn/problems/determine-if-two-strings-are-close/)

**描述**：如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：

- 操作 1：交换任意两个现有字符。

- 例如，`abcde` -> `aecdb`。

- 操作 2：将一个 现有 字符的每次出现转换为另一个现有字符，并对另一个字符执行相同的操作。

- 例如，`aacabb` -> `bbcbaa`（所有 `a` 转化为 `b`，而所有的 `b` 转换为 `a` ）。

给定两个字符串，$word1$ 和 $word2$。

**要求**：如果 $word1$ 和 $word2$ 接近 ，就返回 $True$；否则，返回 $False$。

**说明**：

- $1 \le word1.length, word2.length \le 10^5$。

- $word1$ 和 $word2$ 仅包含小写英文字母。

**示例**：

- 示例 1：

输入：word1 = "abc", word2 = "bca"

输出：True

解释：2 次操作从 word1 获得 word2 。

执行操作 1："abc" -> "acb"

执行操作 1："acb" -> "bca"

- 示例 2：

输入：word1 = "a", word2 = "aa"

输出：False

解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。

无论是操作 1，还是操作 2，只是对字符位置进行交换，而不会产生或者删除字符。

则我们只需要检查两个字符串的字符种类以及每种字符的个数是否相同即可。

具体步骤如下：

1. 分别使用哈希表 $cnts1$、$cnts2$ 统计每个字符串中的字符种类，每种字符的个数。

2. 判断两者的字符种类是否相等，并且判断每种字符的个数是否相同。

3. 如果字符种类相同，且每种字符的个数完全相同，则返回 $True$，否则，返回 $False$。

class Solution:

def closeStrings(self, word1: str, word2: str) -> bool:

cnts1 = Counter(word1)

cnts2 = Counter(word2)

return cnts1.keys() == cnts2.keys() and sorted(cnts1.values()) == sorted(cnts2.values())

- **时间复杂度**：$O(max(n1, n2) + |\sum| \times \log | \sum |)$，其中 $n1$、$n2$ 分别为字符串 $word1$、$word2$ 的长度，$\sum$ 为字符集，本题中 $| \sum | = 26$。

- **空间复杂度**：$O(| \sum |)$。

- 标签：数组、哈希表

- 难度：中等

- [1726. 同积元组 - 力扣](https://leetcode.cn/problems/tuple-with-same-product/)

**描述**：给定一个由不同正整数组成的数组 $nums$。

**要求**：返回满足 $a \times b = c \times d$ 的元组 $(a, b, c, d)$ 的数量。其中 $a$、$b$、$c$ 和 $d$ 都是 $nums$ 中的元素，且 $a \ne b \ne c \ne d$。

**说明**：

- $1 \le nums.length \le 1000$。

- $1 \le nums[i] \le 10^4$。

- $nums$ 中的所有元素互不相同。

**示例**：

- 示例 1：

输入：nums = [2,3,4,6]

输出：8

解释：存在 8 个满足题意的元组：

(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)

(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

- 示例 2：

输入：nums = [1,2,4,5,10]

输出：16

解释：存在 16 个满足题意的元组：

(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)

(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)

(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)

(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

1. 二重循环遍历数组 $nums$，使用哈希表 $cnts$ 记录下所有不同 $nums[i] \times nums[j]$ 的结果。

2. 因为满足 $a \times b = c \times d$ 的元组 $(a, b, c, d)$ 可以按照不同顺序进行组和，所以对于 $x$ 个 $nums[i] \times nums[j]$，就有 $C_x^2$ 种组和方法。

3. 遍历哈希表 $cnts$ 中所有值 $value$，将不同组和的方法数累积到答案 $ans$ 中。

4. 遍历完返回答案 $ans$。

class Solution:

def tupleSameProduct(self, nums: List[int]) -> int:

cnts = Counter()

size = len(nums)

for i in range(size):

for j in range(i + 1, size):

product = nums[i] * nums[j]

cnts[product] += 1

ans = 0

for key, value in cnts.items():

ans += value * (value - 1) * 4

return ans

- **时间复杂度**：$O(n^2)$，其中 $n$ 表示数组 $nums$ 的长度。

- **空间复杂度**：$O(n^2)$。

- 标签：贪心、数组、排序

- 难度：中等

- [1921. 消灭怪物的最大数量 - 力扣](https://leetcode.cn/problems/eliminate-maximum-number-of-monsters/)

**描述**：你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭。给定一个下标从 $0$ 开始且大小为 $n$ 的整数数组 $dist$，其中 $dist[i]$ 是第 $i$ 个怪物与城市的初始距离（单位：米）。

怪物以恒定的速度走向城市。每个怪物的速度都以一个长度为 $n$ 的整数数组 $speed$ 表示，其中 $speed[i]$ 是第 $i$ 个怪物的速度（单位：千米/分）。

你有一种武器，一旦充满电，就可以消灭 一个 怪物。但是，武器需要 一分钟 才能充电。武器在游戏开始时是充满电的状态，怪物从 第 $0$ 分钟时开始移动。

一旦任一怪物到达城市，你就输掉了这场游戏。如果某个怪物 恰好 在某一分钟开始时到达城市（距离表示为 $0$），这也会被视为输掉 游戏，在你可以使用武器之前，游戏就会结束。

**要求**：返回在你输掉游戏前可以消灭的怪物的最大数量。如果你可以在所有怪物到达城市前将它们全部消灭，返回 $n$。

**说明**：

**示例**：

- 示例 1：

输入：dist = [1,3,4], speed = [1,1,1]

输出：3

解释：

第 0 分钟开始时，怪物的距离是 [1,3,4]，你消灭了第一个怪物。

第 1 分钟开始时，怪物的距离是 [X,2,3]，你消灭了第二个怪物。

第 3 分钟开始时，怪物的距离是 [X,X,2]，你消灭了第三个怪物。

所有 3 个怪物都可以被消灭。

- 示例 2：

输入：dist = [1,1,2,3], speed = [1,1,1,1]

输出：1

解释：

第 0 分钟开始时，怪物的距离是 [1,1,2,3]，你消灭了第一个怪物。

第 1 分钟开始时，怪物的距离是 [X,0,1,2]，所以你输掉了游戏。

你只能消灭 1 个怪物。

对于第 $i$ 个怪物，最晚可被消灭的时间为 $times[i] = \lfloor \frac{dist[i] - 1}{speed[i]} \rfloor$。我们可以根据以上公式，将所有怪物最晚可被消灭时间存入数组 $times$ 中，然后对 $times$ 进行升序排序。

然后遍历数组 $times$，对于第 $i$ 个怪物：

1. 如果 $times[i] < i$，则说明第 $i$ 个怪物无法被消灭，直接返回 $i$ 即可。

2. 如果 $times[i] \ge i$，则说明第 $i$ 个怪物可以被消灭，继续向下遍历。

如果遍历完数组 $times$，则说明所有怪物都可以被消灭，则返回 $n$。

class Solution:

def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:

times = []

for d, s in zip(dist, speed):

time = (d - 1) // s

times.append(time)

times.sort()

size = len(times)

for i in range(size):

if times[i] < i:

return i

return size

- **时间复杂度**：$O(n \times \log n)$，其中 $n$ 为数组 $dist$ 的长度。

- **空间复杂度**：$O(n)$。