每日算法-250514

每日算法学习记录 (2024-05-14)

今天记录三道 LeetCode 算法题的解题思路和代码。

---

1. 两数之和

题目截图:

解题思路

这道题要求我们从一个整数数组中找出两个数，使它们的和等于一个给定的目标值 target，并返回这两个数的下标。

核心思路是使用 哈希表 来优化查找过程：

1. 我们遍历数组 nums。对于当前遍历到的元素 num (设其下标为 i)，我们期望找到另一个数 complement = target - num。
2. 在遍历过程中，我们检查哈希表中是否已经存在 complement。
   • 如果哈希表中包含 complement，说明我们找到了这两个数。哈希表中存储了 complement 及其对应的下标。此时，直接返回 [哈希表中complement的下标, 当前下标 i]。
   • 如果哈希表中不包含 complement，则将当前的 num 及其下标 i 存入哈希表，供后续的元素查找配对。

这样，每个元素只需要被访问一次，哈希表的查找和插入操作平均时间复杂度为 $O(1)$。

复杂度

• 时间复杂度: $O(n)$, 其中 $n$ 是数组 nums 的长度。我们只需要遍历一次数组。
• 空间复杂度: $O(n)$, 最坏情况下，哈希表需要存储 $n$ 个元素（例如，没有找到配对或者所有元素都不同且需要到最后才找到配对）。

Code

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> hashTable = new HashMap<>();for (int i = 0; i < nums.length; i++) {int num = nums[i];int complement = target - num;if (hashTable.containsKey(complement)) {return new int[] {hashTable.get(complement), i};}hashTable.put(num, i);}return new int[]{-1, -1}; }
}

---

1512. 好数对的数目

题目截图:

解题思路

题目要求计算数组中 “好数对” (i, j) 的数量，其中 nums[i] == nums[j] 且 i < j。

我们可以遍历数组，对于每个元素 nums[x]：

1. 我们需要知道在它之前（即下标小于 x 的位置）有多少个与 nums[x] 相等的元素。
2. 这些先前出现的相等元素都可以与当前的 nums[x] 组成一个好数对。

为了高效地统计先前出现元素的数量，我们可以使用一个计数数组（或哈希表）。由于题目说明 1 <= nums[i] <= 100，一个大小为 101 的数组 counts 即可胜任，其中 counts[k] 用来记录数字 k 到目前为止出现的次数。

遍历 nums 数组中的每个数字 num：

1. 在遇到当前的 num 时，counts[num] 的值即为之前已经出现过的 num 的数量。这些都可以与当前的 num 配对，所以将 counts[num] 加到总结果 ret 中。
2. 然后，将 counts[num] 的值加 1，表示当前的 num 也被统计进去了，供后续元素配对使用。

这个过程 ret += counts[num]++; 巧妙地实现了先加旧值再更新的逻辑。

复杂度

• 时间复杂度: $O(n)$, 其中 $n$ 是数组 nums 的长度。我们只需要遍历一次数组。
• 空间复杂度: $O(C)$, 其中 $C$ 是数字的取值范围（本题中为 100）。由于 $C$ 是常数，可以认为是 $O(1)$。

Code

class Solution {public int numIdenticalPairs(int[] nums) {int ret = 0;int[] counts = new int[101]; for (int num : nums) {ret += counts[num];counts[num]++;}return ret;}
}

---

1128. 等价多米诺骨牌对的数量

题目截图:

解题思路

题目定义了多米诺骨牌的等价关系：[a, b] 与 [c, d] 等价，当且仅当 (a == c && b == d) 或者 (a == d && b == c)。我们需要计算等价多米诺骨牌对的数目。

这个问题的核心在于如何识别等价的骨牌。我们可以为每一张骨牌 [a, b] 定义一个 规范表示。由于 1 <= dominoes[i][j] <= 9，一个常用的方法是将骨牌表示为一个两位数。为了保证 [a, b] 和 [b, a] 有相同的规范表示，我们可以约定将较小的数字放在十位，较大的数字放在个位（或者反之，只要统一即可）。
例如，如果约定将较大的数字编码在前面，则对于骨牌 [x, y]，其规范键可以表示为 max(x, y) * 10 + min(x, y)。这样，[1, 2] 和 [2, 1] 都会被映射到 2 * 10 + 1 = 21。

代码中的实现是：
int key = (x[0] > x[1]) ? (x[0] * 10 + x[1]) : (x[1] * 10 + x[0]);
这等价于 max(x[0], x[1]) * 10 + min(x[0], x[1])。

一旦我们有了规范的键，问题就转化为了统计具有相同键的骨牌数量，这与上一题 “好数对的数目” 的逻辑类似：

1. 使用一个计数数组 counts（由于键的范围是 11 到 99，数组大小为 100 即可，counts[key] 记录键 key 出现的次数）。
2. 遍历所有多米诺骨牌 domino：
   a. 计算其规范键 key。
   b. 当前骨牌 domino 可以与之前出现过的 counts[key] 个具有相同规范键的骨牌组成等价对。将 counts[key] 加到总结果 ret 中。
   c. 然后，将 counts[key] 的值加 1。

复杂度

• 时间复杂度: $O(n)$, 其中 $n$ 是 dominoes 数组的长度。我们只需要遍历一次数组。
• 空间复杂度: $O(C)$, 其中 $C$ 是规范键的可能数量（最大为 99）。由于 $C$ 是常数，可以认为是 $O(1)$。

Code

class Solution {public int numEquivDominoPairs(int[][] dominoes) {int ret = 0;int[] counts = new int[100]; for (int[] domino : dominoes) {int key = (domino[0] > domino[1]) ? (domino[0] * 10 + domino[1]) : (domino[1] * 10 + domino[0]);ret += counts[key];counts[key]++;}return ret;}
}