每日算法-250522

每日算法学习记录 - 2025-05-25

今天主要解决了两道 LeetCode 题目，记录一下解题思路和代码。

1010. 总持续时间可被 60 整除的歌曲

题目概览

思路

核心思想： 计数与模运算。
利用一个辅助数组（或哈希表）记录歌曲时长对 60 取模后的余数的出现次数。对于每首新歌，我们查找能与之配对（两者时长之和能被 60 整除）的已有歌曲数量，然后更新当前歌曲余数的计数。

解题过程

1. 初始化结果 ret = 0 和一个长度为 60 的数组 map（用于存储余数 0-59 出现的次数），所有元素初始为 0。
2. 遍历输入的歌曲时长数组 time 中的每一首歌曲时长 x：
   a. 计算当前歌曲时长 x 对 60 取模后的余数 currentRemainder = x % 60。
   b. 我们需要找到另一首歌曲，其时长对 60 取模的余数为 targetRemainder，使得 (currentRemainder + targetRemainder) % 60 == 0。
   * 特别地，如果 currentRemainder 是 0（即 x 是 60 的倍数），我们则需要找余数也是 0 的歌曲。此时 (60 - 0) % 60 = 0。这个额外的 % 60 操作确保了当 currentRemainder 为 0 时，targetRemainder 也为 0，从而正确访问 map[0] 而不是 map[60]（会越界）。
   d. 在更新计数之前，将 map[targetRemainder] 的值累加到 ret 上。这表示当前歌曲 x 与之前已统计过的、余数为 targetRemainder 的歌曲形成了有效的配对。
   e. 然后，将当前歌曲的余数 currentRemainder 在 map 中的计数加 1 (map[currentRemainder]++)，供后续歌曲配对使用。
3. 遍历结束后，ret 即为所求的数对总数。

复杂度

• 时间复杂度: $O(n)$，其中 $n$ 是歌曲的数量。我们只需要遍历一次歌曲数组。
• 空间复杂度: $O(1)$，因为我们使用了一个固定大小（60）的数组 map。

Code

class Solution {public int numPairsDivisibleBy60(int[] time) {int ret = 0;int[] map = new int[60]; // map[i] 存储时长 % 60 == i 的歌曲数量for (int x : time) {int currentRemainder = x % 60;int targetRemainder = (60 - currentRemainder) % 60;ret += map[targetRemainder];map[currentRemainder]++;}return ret;}
}

---

2506. 统计相似字符串对的数目

题目概览

思路

核心思想： 位掩码 (Bitmask) 与哈希表。
用一个整数的位来表示一个字符串中出现过的字符集合（例如，第 0 位代表 ‘a’，第 1 位代表 ‘b’，以此类推）。如果字符出现，则对应位为 1，否则为 0。这样，每个字符串的字符集都可以唯一地表示为一个整数。然后使用哈希表统计具有相同字符集（即相同位掩码）的字符串数量。

解题过程

1. 初始化结果 ret = 0 和一个哈希表 map（用于存储 Integer 类型的位掩码到其出现次数 Integer 的映射）。
2. 遍历输入的字符串数组 words 中的每个字符串 word：
   a. 生成位掩码 (Mask): 为当前 word 创建一个整数 mask。初始化 mask = 0。
   b. 遍历 word 中的每个字符 c：
   * 计算该字符对应的位索引：bitIndex = c - 'a'。
   * 通过位或操作 mask |= (1 << bitIndex)，将 mask 中对应的位置为 1。这表示字符 c 在 word 中存在。
   c. 查找与计数:
   * 在哈希表 map 中查找键为当前 mask 的值。这个值代表之前已经遇到过多少个与当前 word 具有相同字符集的字符串。使用 map.getOrDefault(mask, 0) 获取这个数量，设为 count。
   * 将 count 累加到结果 ret。这表示当前字符串 word 与之前 count 个具有相同字符集的字符串均可形成一个相似对。
   d. 更新哈希表: 将当前 mask 在 map 中的计数值加 1。即 map.put(mask, count + 1)。
3. 遍历结束后，ret 即为所求的相似字符串对的数目。

复杂度

• 时间复杂度: $O(N\cdot L)$，其中 $N$ 是字符串数组 words 的长度， $L$ 是字符串的平均长度。对于每个字符串，我们需要遍历其所有字符来构建位掩码。
• 空间复杂度: $O(K)$，其中 $K$ 是不同字符集（即不同位掩码）的数量。在最坏情况下，$K$ 可以达到 $N$（所有字符串的字符集都不同）。由于字符集最多有 $2^{26}$ 种，所以空间复杂度也可以看作是 $O(\min (N,2^{26}))$。如果仅考虑小写字母，则 $K$ 最多为 $2^{26}$，是一个常数，此时空间复杂度可视为 $O(1)$。但通常情况下，我们会说 $O(N)$ 作为上限，因为map中最多存储N个不同的mask。

Code

class Solution {public int similarPairs(String[] words) {int ret = 0;Map<Integer, Integer> map = new HashMap<>(); // 存储 mask -> countfor (String word : words) {int mask = 0;for (char c : word.toCharArray()) {mask |= (1 << (c - 'a')); // 设置对应字符的位为1}// 当前mask已出现的次数，即有多少个之前的字符串可以和当前字符串配对int countOfThisMask = map.getOrDefault(mask, 0);ret += countOfThisMask;// 更新当前mask的计数map.put(mask, countOfThisMask + 1);}return ret;}
}