每日一题（哈希表篇）

发布于: 2024-11-16 更新于: 2024-12-5 收录于: 编程 , 算法

文章字数: 17530 阅读时间: 35 分钟

简单题

202. 快乐数

力扣原题链接 (简单题)

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入： n = 19
输出： true
解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

示例 2：

输入： n = 2
输出： false

提示：

1 <= n <= 2³¹ - 1

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
    bool isHappy(int n)
    {
        int sum = 0, digit = 0;                  // 初始化 sum 为 0，digit 为 0
        unordered_map<int, bool> map{{n, true}}; // 创建一个哈希表，记录已出现的和
        while (true) // 无限循环，直到找到结果
        {
            digit = n % 10;       // 取出当前数字的最后一位
            n /= 10;              // 去掉最后一位数字
            sum += digit * digit; // 计算当前数字的平方并累加到 sum
            if (n == 0) // 如果 n 变为 0，说明已经处理完所有位
            {
                if (sum == 1) // 如果当前和为 1，n 是快乐数
                    break;
                if (map[sum] == true) // 如果当前和已经出现过，n 不是快乐数
                    return false;
                map[sum] = true; // 将当前和加入哈希表
                n = sum;         // 将和作为新的 n 继续处理
                sum = 0;         // 重置 sum 为 0，准备下一轮计算
            }
        }
        return true; // 如果循环结束，说明 n 是快乐数
    }

算法步骤

初始化：
- 创建一个变量 sum 用于保存每次计算的平方和，初始为 0。
- 创建一个变量 digit 用于保存提取的每位数字，初始为 0。
- 使用哈希表 map 来记录已经出现过的平方和，初始化时将输入 n 加入。
循环处理：
- 使用 while (true) 无限循环，直到找到结果（快乐数或确定不是快乐数）。
- 在循环内，提取 n 的最后一位数字，并更新 n 去掉最后一位。
- 计算当前数字的平方并累加到 sum。
条件判断：
- 如果 n 变为 0，表示已经处理完所有位：
  - 检查 sum 是否为 1，是则退出循环，返回 true。
  - 如果当前的 sum 已经在哈希表中出现过，说明进入循环，返回 false。
  - 否则，将当前 sum 记录进哈希表，并将 sum 作为新的 n 继续处理，同时重置 sum。
结束条件：
- 如果循环结束，说明 n 到达 1，返回 true。

注意点

循环检测：使用哈希表来记录已经出现过的平方和，有效避免无限循环。
重置和更新：在每次计算平方和后，将其作为新的 n 处理，并重置 sum，确保每轮计算的独立性。

205. 同构字符串

力扣原题链接 (简单题)

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入： s = “egg”, t = “add”
输出： true

示例 2：

输入： s = “foo”, t = “bar”
输出： false

示例 3：

输入： s = “paper”, t = “title”
输出： true

提示：

1 <= s.length <= 5 * 10⁴
t.length == s.length
s 和 t 由任意有效的 ASCII 字符组成

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
    bool isIsomorphic(string s, string t)
    {
        // 定义一个映射关系，用于存储字符从 s 到 t 的映射
        unordered_map<char, char> map;
        // 遍历字符串 s
        for (int i = 0; i < s.length(); ++i)
        {
            // 如果 s[i] 尚未在 map 中，添加映射关系
            if (map.find(s[i]) == map.end())
                map[s[i]] = t[i];
            else
            {
                // 如果已经存在映射，检查映射是否一致
                if (map[s[i]] != t[i])
                    return false; // 如果不一致，则字符串不构
            }
        }
        // 定义一个反向映射关系，用于检查 t 到 s 的唯一性
        unordered_map<char, char> reversedMap;
        // 遍历前面的映射关系
        for (const auto &p : map)
        {
            // 如果 p.second 尚未在 reversedMap 中，添加反向映射关系
            if (reversedMap.find(p.second) == reversedMap.end())
                reversedMap[p.second] = p.first;
            else
            {
                // 如果已经存在反向映射，检查反向映射是否一致
                if (reversedMap[p.second] != p.first)
                    return false; // 如果不一致，则字符串不构
            }
        }
        return true; // 如果所有检查通过，则字符串同构
    }

主要步骤

建立映射关系：使用一个哈希表 map 来存储从字符串 s 到 t 的映射关系。
遍历字符串：使用循环逐个检查 s 中的字符：
- 如果字符还没有在映射中，添加字符 s[i] 的映射关系到 t[i]。
- 如果已经存在映射关系，检查当前字符的映射是否一致。
反向映射检查：为了确保不同的字符不会映射到相同的字符，使用另一个哈希表 reversedMap 检查从 t 到 s 的反向映射关系。
返回结果：如果所有的映射关系都通过了检查，则返回 true；否则返回 false。

注意点

唯一性：同构的要求包括相同字符必须映射为相同字符，不同字符不能映射为相同字符。这两个条件的检查都必须通过，才能判定两个字符串是同构的。

290. 单词规律

力扣原题链接 (简单题)

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = “abba”, s = “dog cat cat dog”
输出: true

示例 2:

输入: pattern = “abba”, s = “dog cat cat fish”
输出: false

示例 3:

输入: pattern = “aaaa”, s = “dog cat cat dog”
输出: false

提示:

1 <= pattern.length <= 300
pattern 只包含小写英文字母
1 <= s.length <= 3000
s 只包含小写英文字母和 ' '
s 不包含 任何前导或尾随对空格
s 中每个单词都被 单个空格 分隔

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
    bool wordPattern(string pattern, string s)
    {
        istringstream is(s);             // 使用字符串流分隔字符串 s 中的单词
        string word;                     // 存储当前读取的单词
        int i = 0;                       // pattern 的索引，同时统计单词数量
        unordered_map<string, char> map; // 用于存放单词到字母的映射
        // 逐个读取单词并与 pattern 进行比对
        while (is >> word)
        {
            if (map.find(word) == map.end()) // 如果单词不在映射中
                map[word] = pattern[i++];    // 将单词与对应的字母建立映射
            else
            {
                if (map[word] != pattern[i++]) // 如果单词已经存在映射但与当前输出的字母不同
                    return false;              // 返回 false，表示不符合规律
            }
        }
        // 如果读取的单词数与 pattern 中的字母数不一致，返回 false
        if (i != pattern.length())
            return false;
        unordered_map<char, string> reversedMap; // 用于存放字母到单词的反向映射
        // 检查反向映射是否符合规律
        for (const auto &p : map)
        {
            if (reversedMap.find(p.second) == reversedMap.end()) // 如果字母不在反向映射中
                reversedMap[p.second] = p.first;                 // 将字母与对应的单词建立反向映射
            else
            {
                if (reversedMap[p.second] != p.first) // 如果字母已经存在反向映射但与当前单词不同
                    return false;                     // 返回 false，表示不符合规律
            }
        }
        return true; // 如果所有映射都符合规律，返回 true
    }

主要思路

分词: 利用 istringstream 从字符串 s 中逐个提取单词。
正向映射: 使用一个哈希表 map 来存储单词与模式字符之间的映射关系。
反向映射: 使用另一个哈希表 reversedMap 来确定模式字符与单词的反向映射。
一致性检查: 在映射建立过程中，检查每个单词和字符之间的对应关系是否一致。

注意点

边界条件: 必须确保读取的单词数量与模式的长度一致，如果不一致则直接返回 false。
双向映射: 在建立映射时要同时考虑单向与反向映射，以确保没有冲突。例如，如果同一个字符可以对应多个不同的单词，则返回 false。
性能考虑: 使用哈希表进行查找，可以有效提高查找的效率。

387. 字符串中的第一个唯一字符

力扣原题链接 (简单题)

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例 1：

输入: s = “leetcode”
输出: 0

示例 2:

输入: s = “loveleetcode”
输出: 2

示例 3:

输入: s = “aabb”
输出: -1

提示:

1 <= s.length <= 10⁵
s 只包含小写字母

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    int firstUniqChar(string s)
    {
        unordered_map<char, int> map;
        // 统计每个字符出现的次数
        for (const auto &c : s)
        {
            ++map[c];
        }
        // 查找第一个不重复的字符并返回其索引
        for (int i = 0; i < s.length(); ++i)
        {
            if (map[s[i]] == 1)
                return i;
        }
        // 如果不存在不重复字符，返回 -1
        return -1;
    }

关键步骤

统计字符出现次数：
- 使用 unordered_map 记录每个字符在字符串中出现的次数。
- 遍历字符串，对于每个字符 c，将其出现次数加一。
查找第一个不重复字符：
- 再次遍历字符串，检查每个字符的出现次数。
- 如果某个字符只出现一次，返回该字符的索引。
返回结果：
- 如果遍历结束后没有找到不重复的字符，返回 -1。

594. 最长和谐子序列

力扣原题链接 (简单题)

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

给你一个整数数组 nums ，请你在所有可能的

子序列

中找到最长的和谐子序列的长度。

数组的 子序列 是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：

输入： nums = [1,3,2,2,5,2,3,7]
输出： 5
解释： 最长和谐子序列是 [3,2,2,2,3]。

示例 2：

输入： nums = [1,2,3,4]
输出： 2
解释： 最长和谐子序列是 [1,2]，[2,3] 和 [3,4]，长度都为 2。

示例 3：

输入： nums = [1,1,1,1]
输出： 0
解释： 不存在和谐子序列。

提示：

1 <= nums.length <= 2 * 10⁴
-10⁹ <= nums[i] <= 10⁹

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
    int findLHS(vector<int> &nums)
    {
        // 声明一个映射，用于记录每个元素及其出现的次数
        map<int, int> mapN;
        // 遍历数组，统计每个数字出现的次数
        for (const auto &num : nums)
        {
            ++mapN[num]; // 对当前数字的计数加 1
        }
        // 如果映射只包含一个数字，则不可能构成和谐子序列，返回 0
        if (mapN.size() == 1)
            return 0;
        // 声明当前和以前的迭代器
        map<int, int>::iterator previous = mapN.begin(), current;
        int maxLen = 0;  // 最长和谐子序列长度
        int tempLen = 0; // 临时长度变量
        // 遍历映射，从第二个元素开始
        for (auto it = next(mapN.begin()); it != mapN.end(); ++it)
        {
            current = it; // 当前元素
            // 检查前一个元素与当前元素的差值是否为 1
            if (previous->first + 1 == current->first)
            {
                // 计算当前和前一个元素的出现次数之和，并与maxLen比较更新最大长度
                maxLen = (current->second + previous->second) > tempLen ? current->second + previous->second : tempLen;
                // 更新临时长度
                tempLen = maxLen;
            }
            // 更新前一个元素为当前元素
            previous = current;
        }
        // 返回找到的最长的和谐子序列的长度
        return maxLen;
    }

代码思路

统计元素出现次数：
- 使用 map<int, int> 来存储每个元素及其出现的次数。遍历 nums 数组，将每个数字的出现次数记录在映射中。
检查映射中的元素个数：
- 如果映射中只有一个数字，则没有和谐子序列，直接返回 0。
遍历映射：
- 使用迭代器遍历映射，从第二个元素开始，检查前一个元素与当前元素的差值是否为 1。
  - 如果差值为 1，计算这两个元素的出现次数之和，并更新 maxLen。
返回结果：
- 最后返回找到的最长和谐子序列的长度 maxLen。

注意点

边界情况：在处理边界情况时，注意如果只有一个元素，和谐子序列的长度应直接返回 0。
迭代器的使用：使用 next(mapN.begin()) 从第二个元素开始遍历，对应前一个元素和当前元素的比较逻辑。
注意变量的初始化：特别是 maxLen 和 tempLen 的初始值应该设置为 0，以确保在后续逻辑中能够正确比较和更新。

599. 两个列表的最小索引总和

力扣原题链接 (简单题)

假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。

你需要帮助他们找到索引和最小的共同喜爱的餐厅。如果答案不止一个，则输出所有答案并且不考虑顺序。你可以假设答案总是存在。

示例 1:

输入: list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]，list2 = [“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]
输出: [“Shogun”]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:

输入: list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]，list2 = [“KFC”, “Shogun”, “Burger King”]
输出: [“Shogun”]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

提示:

1 <= list1.length, list2.length <= 1000
1 <= list1[i].length, list2[i].length <= 30
list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。
list1 的所有字符串都是唯一的。
list2 中的所有字符串都是唯一的。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
    vector<string> findRestaurant(vector<string> &list1, vector<string> &list2)
    {
        // 创建一个哈希表，用于存储 Andy 最喜欢的餐厅及其索引
        unordered_map<string, int> rest1
        // 将 list1 中的餐厅及其索引存入哈希表
        for (int i = 0; i < list1.size(); ++i)
        {
            rest1[list1[i]] = i;
        }
        // 存储结果的向量
        vector<string> res;
        // 初始化最小索引和
        int indexSum = INT_MAX, tempIndexSum = 0;
        // 遍历 Doris 的餐厅列表
        for (int j = 0; j < list2.size() && j <= indexSum; ++j)
        {
            // 如果 Doris 的餐厅不在 Andy 的列表中，跳过
            if (rest1.find(list2[j]) == rest1.end())
                continue;
            // 计算当前共同餐厅的索引和
            tempIndexSum = j + rest1[list2[j]];
            // 如果当前索引和小于已知的最小索引和，更新结果
            if (tempIndexSum < indexSum)
            {
                indexSum = tempIndexSum;
                res.clear();             // 清空之前的结果
                res.push_back(list2[j]); // 添加当前餐厅
            }
            // 如果相等，则将当前餐厅添加到结果中
            else if (tempIndexSum == indexSum)
                res.push_back(list2[j]);
        }
        // 返回找到的共同最爱餐厅
        return res;
    }

主要步骤

哈希表存储：
- 通过 unordered_map 创建一个哈希表 rest1，用于存储 Andy 的餐厅及对应的索引，使得查找更加高效。
填充哈希表：
- 遍历 list1（Andy的餐厅列表），将餐厅名称作为键，索引作为值存入 rest1。
遍历 Doris 的列表：
- 通过循环遍历 list2（Doris的餐厅列表），检查每个餐厅是否在 rest1 中存在。
- 如果存在，计算该餐厅的索引和（即 Andy 和 Doris 的索引和）。
更新结果：
- 维护最小索引和的变量 indexSum，并在找到更小的索引和时更新结果。
- 如果当前的索引和等于最小索引和，则将该餐厅添加到结果中。
返回结果：
- 函数返回一个包含共同最爱餐厅的向量。

注意点

哈希表的使用：哈希表的使用使得餐厅的查找变得高效，避免了重复的遍历。
清空结果向量：在找到更小的索引和时，需要清空结果向量并添加新的餐厅。
使用INT_MAX：初始化最小索引和为 INT_MAX 是一种常见的做法，用于确保可以找到最小值。

645. 错误的集合

力扣原题链接 (简单题)

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1：

输入： nums = [1,2,2,4]
输出： [2,3]

示例 2：

输入： nums = [1,1]
输出： [1,2]

提示：

2 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁴

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
    vector<int> findErrorNums(vector<int> &nums)
    {
        // 创建一个大小为 10001 的数组 vec 初始化为 0，用于计数
        vector<int> vec(10001, 0);
        // 遍历输入的数组 nums，统计每个数字出现的次数
        for (const auto &num : nums)
        {
            ++vec[num];
        }
        int lost = -1, repeat = -1; // 初始化丢失的数字和重复的数字
        // 遍历 vec 数组，从 1 到 10000 找出丢失和重复的数字
        for (int i = 1; i < vec.size() && (lost == -1 || repeat == -1); ++i)
        {
            if (vec[i] == 2) // 如果数字出现了两次，记录为重复的数字
                repeat = i;
            else if (vec[i] == 0) // 如果数字没有出现，记录为丢失的数字
                lost = i;
        }
        // 如果没有找到丢失和重复的数字，返回空数组；否则返回重复和丢失的数字
        return (lost == -1 && repeat == -1) ? vector<int>{} : vector<int>{repeat, lost};
    }

函数解析

输入和输出
- 输入：一个整数数组 nums，表示错误的集合。
- 输出：一个包含重复整数和丢失整数的数组。
数据结构
- 使用一个大小为 10001 的 vector，以 0 初始化，用于计数出现的数字。因为我们要检查的数字范围是 1 到 n，所以 10001 是合适的大小（vec[0] 未使用）。
统计出现次数
- 遍历输入数组 nums，使用计数数组 vec 统计每个数字出现的次数。
查找丢失和重复的数字
- 再次遍历计数数组 vec，检查每个数字的出现次数：
  - 如果一个数字的计数为 2，则该数字是重复的。
  - 如果一个数字的计数为 0，则该数字是丢失的。

注意点

遍历优化：遍历计数数组时，使用条件 lost == -1 || repeat == -1 进行优化，一旦找到需要的数字即可停止，提升效率。
返回值处理：使用三元运算符简化返回值的处理，确保函数在找不到丢失或重复数字时返回空数组。

884. 两句话中的不常见单词

力扣原题链接 (简单题)

句子是一串由空格分隔的单词。每个单词仅由小写字母组成。

如果某个单词在其中一个句子中恰好出现一次，在另一个句子中却 没有出现 ，那么这个单词就是 不常见的 。

给你两个句子 s1 和 s2 ，返回所有 不常用单词 的列表。返回列表中单词可以按 任意顺序 组织。

示例 1：

输入： s1 = “this apple is sweet”, s2 = “this apple is sour”
输出： [“sweet”,“sour”]

示例 2：

输入： s1 = “apple apple”, s2 = “banana”
输出： [“banana”]

提示：

1 <= s1.length, s2.length <= 200
s1 和 s2 由小写英文字母和空格组成
s1 和 s2 都不含前导或尾随空格
s1 和 s2 中的所有单词间均由单个空格分隔

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    vector<string> uncommonFromSentences(string s1, string s2)
    {
        istringstream is1(s1), is2(s2); // 使用字符串流来处理句子
        string word;                    // 存储每个单词
        unordered_map<string, int> uMap; // 创建一个哈希表用于记录每个单词的出现次数
        // 遍历两个句子，将所有单词出现的次数记录到 uMap 中
        while (is1 >> word || is2 >> word)
        {
            ++uMap[word]; // 每遇到一个单词，次数加1
        }
        vector<string> res; // 用于存储不常见单词的结果
        // 遍历哈希表，找出出现次数为1的单词
        for (const auto &p : uMap)
        {
            if (p.second == 1) // 如果单词出现次数为1，加入结果列表
                res.push_back(p.first);
        }
        return res; // 返回不常见单词的列表
    }

主要步骤

使用字符串流：
- 通过 istringstream 分别将两个句子 s1 和 s2 处理成单词流，便于逐个读取单词。
哈希表记录单词出现次数：
- 使用 unordered_map 来存储每个单词及其在两个句子中出现的次数。哈希表的键是单词，值是该单词出现的次数。
统计单词出现次数：
- 通过 while 循环读取单词，并对出现的单词在哈希表中进行计数。
查找不常见单词：
- 遍历哈希表，找出出现次数为1的单词，并将其添加到结果列表中。
返回结果：
- 最后返回包含不常见单词的向量。

注意点

字符串流的用法：使用 istringstream 是处理字符串的一个很好的选择，它能够方便地将整个句子拆分为单个单词。
哈希表的选择：使用 unordered_map 可以实现快速的查找和插入操作，适合用于存储单词及其计数。
单词读取方式：在读取单词时，使用 || 可以在两个句子流中同时读取，但要注意边界条件，以避免读取到未知的状态。

1207. 独一无二的出现次数

力扣原题链接 (简单题)

给你一个整数数组 arr，如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

输入： arr = [1,2,2,1,1,3]
输出： true
解释： 在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：

输入： arr = [1,2]
输出： false

示例 3：

输入： arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出： true

提示：

1 <= arr.length <= 1000
-1000 <= arr[i] <= 1000

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    bool uniqueOccurrences(vector<int> &arr)
    {
        unordered_map<int, int> numCount; // 存储每个数字出现的次数
        for (const auto &num : arr)
        {
            ++numCount[num]; // 统计每个数字的出现次数
        }
        unordered_set<int> unique; // 存储唯一出现次数
        for (const auto &p : numCount)
        {
            unique.insert(p.second); // 插入出现次数到集合中
        }
        return unique.size() == numCount.size(); // 比较唯一出现次数的数量与数字种类数量
    }

代码解析

数据结构：
- unordered_map<int, int> numCount：用于存储每个数字及其出现次数。
- unordered_set<int> unique：用于存储唯一的出现次数。
统计出现次数：

- 遍历整数数组 arr，通过 ++numCount[num] 统计每个数字的出现次数。

记录唯一出现次数：
- 遍历 numCount，将每个数字的出现次数插入 unique 集合中。由于集合的特性，重复的出现次数会被自动忽略。
比较大小：
- 最后，比较 unique 集合的大小与 numCount 的大小是否相等。如果相等，则说明出现次数都是独一无二的，返回 true；否则返回 false。

注意点

使用 unordered_map 和 unordered_set：
- unordered_map 提供平均 O(1) 的时间复杂度用于插入和查找，适合快速统计频率。
- unordered_set 也具有平均 O(1) 的时间复杂度，用于存储唯一值，避免重复。

中等题

3. 无重复字符的最长子串

力扣原题链接 (中等题)

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是子串的长度，"pwke" 是一个_子序列，_不是子串。

提示：

0 <= s.length <= 5 * 10⁴
s 由英文字母、数字、符号和空格组成

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    int lengthOfLongestSubstring(string s)
    {
        if (s.length() <= 1)
            return s.length();
        unordered_map<char, int> unique;   // 用于存储字符及其索引
        int len = 0, maxLen = 0, temp = 0; // len 列表当前无重复字符的长度，maxLen 最大长度
        for (size_t i = 0; i < s.length(); ++i)
        {
            if (unique.count(s[i])) // 检查字符是否已存在
            {
                maxLen = len > maxLen ? len : maxLen; // 更新最大长度
                len = 0;                              // 重置当前长度
                i = unique[s[i]];                     // 跳转到重复字符索引
                unique.clear();                       // 清空唯一字符存储
            }
            else
            {
                ++len;            // 增加当前无重复字符的长度
                unique[s[i]] = i; // 记录当前字符及其索引
            }
        }
        return len > maxLen ? len : maxLen; // 返回最大长度
    }

关键步骤

初始化：
- 使用 unordered_map<char, int> unique 来存储字符及其索引。
- 初始化 len 用于当前无重复字符的长度，maxLen 用于记录最大的长度。
遍历字符串：
- 使用 for 循环遍历字符串的每个字符。
- 检查当前字符是否已经存在于哈希表中：
  - 如果存在，更新 maxLen 如果当前长度 len 大于 maxLen，并重置 len 为 0。
  - 将索引 i 更新为当前重复字符的索引，并清空哈希表。
- 如果不存在，增加当前无重复字符的长度 len，并将当前字符及其索引存入哈希表。
返回结果：
- 最后返回 maxLen 和 len 中的较大值，以确保得到最长的无重复字符子串长度。

注意点

索引跳转：当发现重复字符时，需要将索引 i 跳转到该字符上一次出现的位置，这一操作确保了不会错过字符串中的任何潜在最长子串。
哈希表的清空：在发现重复字符后，需要清空 unique，这样才能从当前索引重新开始统计下一段无重复字符的长度。
边界条件：需要处理字符串长度小于或等于 1 的情况，直接返回字符串的长度。

204. 计数质数

力扣原题链接 (中等题)

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入： n = 10
输出： 4
解释： 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入： n = 0
输出： 0

示例 3：

输入： n = 1
输出： 0

提示：

0 <= n <= 5 * 10⁶

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
    int countPrimes(int n)
    {
        // 如果 n 为 0 或 1，直接返回 0
        if (n == 0 || n == 1)
            return 0;
        // 初始化一个布尔类型的向量，用于标记质数
        vector<bool> nums(n, true);
        int times = 1, temp = 0;
        // 使用埃拉托斯特尼筛法标记非质数
        for (int i = 2; i <= nums.size() / 2; ++i)
        {
            if (nums[i] == true)
            {
                times = 2;
                temp = i * times;
                while (temp <= n - 1)
                {
                    nums[temp] = false;
                    temp = i * ++times;
                }
            }
        }
        // 统计质数的数量
        int count = 0;
        for (const auto &num : nums)
        {
            if (num == true)
                ++count;
        }
        // 返回质数的数量，减去 0 和 1 这两个非质数
        return count - 2;
    }

主要步骤

边界条件处理：
- 如果 n 为 0 或 1，直接返回 0，因为 0 和 1 都不是质数。
初始化布尔向量：
- 使用 vector<bool> nums(n, true) 初始化一个布尔类型的向量，长度为 n，所有元素初始值为 true，表示默认所有数都是质数。
埃拉托斯特尼筛法：
- 从 2 开始，遍历到 n/2，对于每个质数 i，将其倍数标记为非质数（即 false）。
- 具体实现是通过一个 while 循环，不断将 i 的倍数标记为 false，直到倍数超过 n-1。
统计质数数量：
- 遍历布尔向量 nums，统计值为 true 的元素数量。
- 由于 0 和 1 不是质数，最终结果需要减去 2。
返回结果：
- 返回统计的质数数量。

注意点

边界条件：函数一开始就处理了 n 为 0 或 1 的情况，避免了后续不必要的计算。
布尔向量的初始化：使用 vector<bool> 来标记质数和非质数，初始值为 true，表示默认所有数都是质数。
埃拉托斯特尼筛法的实现：遍历范围是从 2 到 n/2，因为大于 n/2 的数不可能再有倍数小于 n。使用 while 循环来标记非质数，确保所有倍数都被正确标记。
统计质数数量：在统计质数数量时，需要减去 0 和 1 这两个非质数。

215. 数组中的第K个最大元素

力扣原题链接 (中等题)

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    int findKthLargest(vector<int> &nums, int k)
    {
        // 使用一个最小堆来存储前 k 个最大的元素
        priority_queue<int, vector<int>, greater<int>> mHeap;
        // 遍历数组中的每个数字
        for (const auto &num : nums)
        {
            // 将当前数字加入堆中
            mHeap.push(num);
            // 如果堆的大小超过 k，移除堆顶元素
            if (mHeap.size() > k)
                mHeap.pop();
        }
        // 堆顶元素即为第 k 个最大的元素
        return mHeap.top();
    }

代码分析

最小堆的使用：
- 在 C++ 中，使用 priority_queue<int, vector<int>, greater<int>> 来实现最小堆。greater<int> 表示我们希望实现一个最小堆的行为。
遍历数组：
- 对数组中的每个元素 num 进行遍历。
- 将 num 加入最小堆。
- 如果堆的大小超过了 k，则弹出堆顶元素（即当前堆中最小的元素），以确保堆中始终保存的是最大的 k 个元素。
返回结果：
- 最后，堆顶元素 mHeap.top() 即为第 k 个最大的元素。

注意点

排序与元素的关系：注意这里返回的是排序后的第 k 个最大元素，不要混淆为第 k 个不同的最大元素。
堆的特性：熟悉堆的基本操作（插入、删除、获取堆顶元素）是实现该算法的基础。
最小堆模板参数说明：
- priority_queue<int, vector<int>, greater<int>> 中，int 是存储的元素类型，vector<int> 是底层容器的类型（用来存储堆中的元素），greater<int> 则用于指定堆的比较方式，确保堆顶始终是最小的元素，从而实现最小堆的特性。

347. 前 K 个高频元素

力扣原题链接 (中等题)

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 10⁵
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶： 你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
    vector<int> topKFrequent(vector<int> &nums, int k)
    {
        unordered_map<int, int> frequency; // 用于存储每个元素及其出现的频率
        for (const auto &num : nums) // 遍历数组
        {
            ++frequency[num]; // 统计每个元素的频率
        }
        // 自定义比较函数，用于优先队列，按频率从高到低排序
        auto compare = [](const pair<int, int> &a, const pair<int, int> &b)
        {
            return a.second > b.second; // 返回频率较高的元素优先
        };//注意这里要加分号——“;”
        // 创建一个优先队列，存储元素和频率，使用自定义比较函数
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compare)> mHeap(compare);
        for (const auto &p : frequency) // 遍历频率映射
        {
            mHeap.push(p); // 将元素及其频率压入优先队列
            if (mHeap.size() > k) // 如果队列大小超过要求的 k
                mHeap.pop();      // 移除频率最低的元素
        }
        vector<int> res; // 用于存储结果
        while (!mHeap.empty()) // 将优先队列中的元素弹出并存入结果中
        {
            res.push_back(mHeap.top().first); // 获取频率最高的元素
            mHeap.pop();                      // 移除该元素
        }
        return res; // 返回高频元素的数组
    }

函数步骤

频率统计：
- 使用 unordered_map<int, int> 类型的 frequency 来存储每个元素及其出现的频率。
- 遍历数组 nums，对每个元素进行频率统计。
优先队列：
- 使用 priority_queue 来维护频率最高的元素。
- 自定义比较函数，使得优先队列能够按照频率从高到低进行排序。
维护队列大小：
- 遍历频率映射，将每个元素及其对应的频率压入优先队列。
- 如果队列的大小超过 k，则移除频率最低的元素（即队头元素）。
提取结果：
- 最后，通过弹出优先队列中的元素，将频率最高的元素保存到结果数组中，并返回该数组。

注意点

使用 unordered_map：
- 频率统计使用了 unordered_map，其查找和插入时间复杂度为 O(1)，适合大量数据处理。
自定义比较函数：
- 自定义的比较函数在优先队列中起到关键作用，确保频率高的元素优先出队。
优先队列的容量管理：
- 在维护优先队列大小时，通过条件判断实现了只保留前 k 高频元素，可以有效提高空间利用率。

380. O(1) 时间插入、删除和获取随机元素

力扣原题链接 (中等题)

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的平均时间复杂度为 O(1) 。

示例：

输入：
[“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”]
[ [], [1], [2], [2], [], [1], [2], [] ]
输出：[null, true, false, true, 2, true, false, 2]
解释：
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

提示：

-2³¹ <= val <= 2³¹ - 1
最多调用 insert、remove 和 getRandom 函数 2 * 10⁵ 次
在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class RandomizedSet
{
private:
    unordered_map<int, int> vai; // 用于存储元素值和其在向量中位置的映射
    vector<int> v; // 用于存储集合中的元素
public:
    // 构造函数，初始化 RandomizedSet 对象
    RandomizedSet()
    {
        srand(time(NULL)); // 用当前时间设置随机数种子
    }
    // 插入元素 val，若成功插入返回 true，否则返回 false
    bool insert(int val)
    {
        if (vai.count(val)) // 检查元素是否已存在
            return false; // 元素已存在，返回 false
        v.push_back(val); // 将元素插入向量
        vai[val] = v.size() - 1; // 更新映射，记录元素在向量中的位置
        return true; // 插入成功，返回 true
    }
    // 移除元素 val，若成功移除返回 true，否则返回 false
    bool remove(int val)
    {
        if (vai.count(val) == 0) // 检查元素是否存在
            return false; // 元素不存在，返回 false
        int lastVal = v.back(); // 获取向量最后一个元素
        int removedIndex = vai[val]; // 获取要删除元素的位置
        // 用最后一个元素替换要删除的元素
        v[removedIndex] = lastVal;
        vai[lastVal] = removedIndex; // 更新最后一个元素的位置
        vai.erase(val); // 从映射中删除要移除的元素
        v.pop_back(); // 从向量中移除最后一个元素
        return true; // 移除成功，返回 true
    }
    // 随机返回现有集合中的一项
    int getRandom()
    {
        return v[rand() % v.size()]; // 返回随机索引处的元素
    }
};

1. 类的功能

RandomizedSet 类实现了一个数据结构，可以进行插入、删除和随机获取集合中的元素。
所有操作的平均时间复杂度为 O(1)。

2. 成员变量

unordered_map<int, int> vai：用于存储元素值与其在集合向量中的索引的映射，方便快速查找。
vector<int> v：用于存储集合中的元素，支持随机访问。

3. 构造函数

在构造函数中使用 srand(time(NULL)) 设置随机数种子，以确保每次运行时随机数生成的不同。

4. 插入方法 insert(int val)

首先检查元素是否已经存在于集合中，若存在则返回 false。
若不存在，将元素添加到 vector 中，并更新哈希表，记录该元素的位置。
返回 true 表示插入成功。

5. 移除方法 remove(int val)

首先检查要移除的元素是否存在，若不存在则返回 false。
获取集合中最后一个元素，用它的值替代要删除的元素，以保持操作的 O(1) 时间复杂度。
更新哈希表中最后一个元素对应的索引，并删除要移除元素的映射关系。
从 vector 中移除最后一个元素。
返回 true 表示移除成功。

6. 随机获取方法 getRandom()

通过生成一个随机索引，返回 vector 中对应的元素。
使用 rand() 方法产生随机数并对集合大小取余，确保返回的索引有效。

注意点

复杂度要求：所有操作必须满足平均时间复杂度为 O(1)，这个要求使得实现的设计尤为重要。
数据结构选择：
- 使用 unordered_map 来实现快速查找（O(1)），对元素的插入和删除操作提供支持。
- 使用 vector 以支持随机访问元素，确保能有效实现 getRandom() 方法。
随机数种子：在构造函数中使用 srand() 设置随机种子，能够确保每次运行时随机数生成的不同。
元素替换：在删除元素时，通过用集合中的最后一个元素替换被删除元素，避免了需要在中间位置进行元素移动的开销，从而保持时间复杂度为 O(1)。

451. 根据字符出现频率排序

力扣原题链接 (中等题)

给定一个字符串 s ，根据字符出现的频率对其进行 降序排序 。一个字符出现的频率是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

示例 1:

输入: s = “tree”
输出: “eert”
解释: ’e’出现两次，‘r’和’t’都只出现一次。因此’e’必须出现在’r’和’t’之前。此外，“eetr"也是一个有效的答案。

示例 2:

输入: s = “cccaaa”
输出: “cccaaa”
解释: ‘c’和’a’都出现三次。此外，“aaaccc"也是有效的答案。注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:

输入: s = “Aabb”
输出: “bbAa”
解释: 此外，“bbaA"也是一个有效的答案，但"Aabb"是不正确的。注意’A’和’a’被认为是两种不同的字符。

提示:

1 <= s.length <= 5 * 10⁵
s 由大小写英文字母和数字组成

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
    string frequencySort(string s)
    {
        // 如果字符串长度为1，直接返回该字符串
        if (s.length() == 1)
            return s;
        // 创建一个哈希表，用于存储每个字符出现的频率
        unordered_map<char, int> frequency;
        // 遍历字符串，统计每个字符的频率
        for (const auto &c : s)
        {
            ++frequency[c]; // 频率加一
        }
        // 定义比较函数，用于优先队列排序
        auto compare = [](const pair<char, int> &a, const pair<char, int> &b)
        {
            return a.second < b.second; // 根据频率降序排序
        }; //注意这里要加分号——“;”
        // 创建优先队列，存储字符及其频率
        priority_queue<pair<char, int>, vector<pair<char, int>>, decltype(compare)> que(frequency.begin(), frequency.end(), compare);
        string str; // 用于保存排序后的字符串
        // 处理优先队列，构建排序后的字符串
        while (!que.empty())
        {
            int repeat = que.top().second; // 获取当前字符的频率
            char insert = que.top().first; // 获取当前字符
            while (repeat)                 // 根据频率，将字符添加到字符串中
            {
                --repeat;              // 频率减一
                str.push_back(insert); // 将字符插入字符串
            }
            que.pop(); // 移除优先队列中的字符
        }
        return str; // 返回排序后的字符串
    }

主要步骤

特殊情况处理：当输入字符串长度为1时，直接返回该字符串。
频率统计：
- 使用 unordered_map<char, int> 来记录每个字符及其频率。
- 遍历字符串，统计每个字符出现的次数。
优先队列排序：
- 定义一个比较函数，按照频率进行排序（降序）。
- 使用 priority_queue 存储字符及其频率，以便能够快速获取频率最高的字符。
构建结果字符串：
- 从优先队列中取出字符，并根据其频率附加到结果字符串中。
- 重复直到优先队列为空。

注意点

哈希表的使用：unordered_map 提供了常数时间复杂度的插入和查找操作，适合频率统计。
优先队列的性质：优先队列自动保持元素的排序状态，因此可以高效地处理和获取频率最高的字符。
字符频率的处理：在处理字符频率时，采用两次 top() 操作获取字符及其频率，并使用循环将其添加至结果字符串，这是确保结果字符串正确构造的关键。

648. 单词替换

力扣原题链接 (中等题)

在英语中，我们有一个叫做词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 衍生词 (derivative)。例如，词根 help，跟随着继承词 "ful"，可以形成新的单词 "helpful"。

现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有 衍生词 用词根替换掉。如果 衍生词 有许多可以形成它的词根，则用最短的词根替换它。

你需要输出替换之后的句子。

示例 1：

输入： dictionary = [“cat”,“bat”,“rat”], sentence = “the cattle was rattled by the battery”
输出： “the cat was rat by the bat”

示例 2：

输入： dictionary = [“a”,“b”,“c”], sentence = “aadsfasf absbs bbab cadsfafs”
输出： “a a b c”

提示：

1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i] 仅由小写字母组成。
1 <= sentence.length <= 10⁶
sentence 仅由小写字母和空格组成。
sentence 中单词的总量在范围 [1, 1000] 内。
sentence 中每个单词的长度在范围 [1, 1000] 内。
sentence 中单词之间由一个空格隔开。
sentence 没有前导或尾随空格。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    string replaceWords(vector<string> &dictionary, string &sentence)
    {
        unordered_map<string, int> roots; // 用于存储词根及其长度的哈希表
        // 将字典中的词根存入哈希表
        for (const auto &root : dictionary)
        {
            roots[root] = root.length(); // 词根及其长度
        }
        std::istringstream iss(sentence); // 使用字符串流处理句子
        string word, comparedWord, res;   // 定义所需的字符串变量
        // 按照空格分割句子中的每个单词
        while (iss >> word)
        {
            // 遍历所有词根
            for (const auto &p : roots)
            {
                comparedWord = word.substr(0, p.second); // 获取单词的前缀
                // 如果前缀与词根匹配，则用词根替换该单词
                if (p.first == comparedWord)
                    word = p.first; // 替换为词根
            }
            res += word + " "; // 将替换后的单词添加到结果字符串中
        }
        return res.substr(0, res.length() - 1); // 去掉最后一个空格并返回结果
    }

主要功能和步骤

词根字典的构建：
- 使用 unordered_map 存储词根及其长度，方便后续查找。
句子处理：
- 通过 std::istringstream 对句子进行分词，逐个处理每个单词。
前缀匹配：
- 对于每个单词，遍历字典中的每个词根，检查单词的前缀是否与词根匹配。
- 如果匹配，则用该词根替换原单词。
结果拼接：
- 将替换后的单词添加到结果字符串中，并在最后去掉多余的空格。

注意点

字符串处理：
- std::istringstream 是处理字符串的一个便捷工具，可以方便地进行分词。
前缀替换逻辑：
- 注意判断条件的顺序，如果一个单词的多个词根都可以匹配，应根据长度优先选择最短的词根替换。
结果字符串处理：
- 最后返回结果时，需要去掉最后一个多余的空格，避免格式问题。

692. 前K个高频单词

力扣原题链接 (中等题)

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。注意，按字母顺序 “i” 在 “love” 之前。

示例 2：

输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
输出: [“the”, “is”, “sunny”, “day”]
解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，出现次数依次为 4, 3, 2 和 1 次。

注意：

1 <= words.length <= 500
1 <= words[i] <= 10
words[i] 由小写英文字母组成。
k 的取值范围是 [1, 不同 words[i] 的数量]

进阶： 尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    vector<string> topKFrequent(vector<string> &words, int k)
    {
        // 创建一个哈希表记录每个单词的出现频率
        unordered_map<string, int> frequency;
        // 遍历单词列表，统计每个单词的出现次数
        for (const auto &word : words)
        {
            ++frequency[word];
        }
        // 自定义比较函数，用于优先队列的排序
        auto compare = [](const pair<string, int> &a, const pair<string, int> &b)
        {
            // 如果出现频率不同，则按频率排序
            if (a.second != b.second)
                return a.second > b.second;
            // 如果出现频率相同，则按字典顺序排序
            return a.first < b.first;
        };
        // 创建一个优先队列，保存出现频率最高的单词
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(compare)>
            que(compare);
        // 将每个单词及其频率推入优先队列
        for (const auto &p : frequency)
        {
            que.push(p);
            // 保持队列的大小不超过 k
            if (que.size() > k)
                que.pop();
        }
        // 创建一个向量用于存储结果
        vector<string> res;
        // 从优先队列中弹出元素并存入结果向量
        while (!que.empty())
        {
            res.push_back(que.top().first);
            que.pop();
        }
        // 反转结果向量，以保证返回的顺序是从高频到低频
        return vector<string>(res.rbegin(), res.rend());
    }

主要步骤

统计单词频率：使用 unordered_map 来记录每个单词的出现次数。
自定义排序规则：通过 lambda 表达式定义一个比较函数，用于在优先队列中排序。
使用优先队列：通过 priority_queue 来维护出现频率最高的 k 个单词。
构建结果：将优先队列中的元素弹出并存入结果向量，最后反转结果以确保频率从高到低。

注意点

哈希表的使用：unordered_map 高效地存储和查找单词频率，时间复杂度为 O(n)，其中 n 是单词列表的长度。
优先队列的自定义排序：比较函数确保了正确的排序逻辑，优先考虑频率，其次考虑字典序。
保持优先队列大小：在加入新元素时，始终保持队列的大小不超过 k，避免内存浪费。
结果反转：在从优先队列中取出元素时，需要反转结果，否则将以低频优先的顺序输出。

718. 最长重复子数组

力扣原题链接 (中等题)

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

输入： nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出： 3
解释： 长度最长的公共子数组是 [3,2,1] 。

示例 2：

输入： nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出： 5

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
    int findLength(vector<int> &nums1, vector<int> &nums2)
    {
        // 创建一个哈希表，将 nums1 中的元素及其索引存储在 deque 中
        unordered_map<int, deque<int>> umMap1;
        // 遍历 nums1，填充哈希表
        for (int i = 0; i < nums1.size(); ++i)
        {
            umMap1[nums1[i]].push_back(i); // 将 nums1 中的元素的索引存入 deque
        }
        int currentLen = 0; // 当前正在比较的公共子数组的长度
        int maxLen = 0;     // 记录找到的最大长度
        int nums1Index = 0; // nums1 的索引
        int nums2Index = 0; // nums2 的索引
        deque<int> temp;    // 用于存储 nums1 中和 nums2[j] 相同的元素的索引
        // 遍历 nums2
        for (int j = 0; j < nums2.size(); ++j)
        {
            // 如果 nums2 剩余的元素个数小于等于当前最大长度，提前结束
            if(nums2.size() - j <= maxLen)
                break;
            // 如果 nums2[j] 在 nums1 中没有出现，继续下一个元素
            if (umMap1.count(nums2[j]) == 0)
                continue;
            // 获取与 nums2[j] 相同的 nums1 中的索引
            temp = umMap1[nums2[j]];
            // 遍历这些索引
            while (!temp.empty())
            {
                currentLen = 0; // 重置当前长度
                nums2Index = j; // nums2 当前索引
                nums1Index = temp.front(); // 从 deque 中获取 nums1 当前索引
                temp.pop_front(); // 移除 deque 中的前一个索引
                // 比较两个数组从当前索引开始的元素是否相同
                while (nums1Index < nums1.size() && nums2Index < nums2.size() && nums1[nums1Index] == nums2[nums2Index])
                {
                    ++currentLen; // 计数
                    ++nums1Index; // 移动 nums1 索引
                    ++nums2Index; // 移动 nums2 索引
                }
                // 更新最大长度
                maxLen = currentLen > maxLen ? currentLen : maxLen;
            }
        }
        return maxLen; // 返回最大公共子数组长度
    }

主要步骤

哈希表初始化：
- 使用 unordered_map<int, deque<int>> umMap1 来存储 nums1 中每个元素及其对应的索引。每个元素的索引存储在双端队列中，以便可以高效地遍历。
遍历 nums2：
- 对于 nums2 中的每个元素，先检查该元素是否在 nums1 中存在。如果不存在，跳过当前元素。
- 如果存在，通过哈希表获取所有对应的 nums1 中的索引。
比较子数组：
- 对于 nums2[j] 在 nums1 中的每个索引，初始化 currentLen 为零，然后从这个索引开始，逐个比较 nums1 和 nums2 中的元素。只要两个数组的元素相同，就增加当前长度计数。
- 移动 nums1 和 nums2 的索引，直到遇到不同的元素或到达数组结尾。
更新最大长度：
- 每次找到一个公共子数组时，检查并更新记录的 maxLen。
提前结束条件：
- 为了节省时间，如果 nums2 剩余的元素个数小于等于当前已找到的最大长度，则可以提前结束循环。

注意点

哈希表的使用： 利用哈希表快速查找和访问索引，可以显著提高算法效率。
双端队列的应用： 使用双端队列方便了索引的管理和遍历，确保每次我们可以快速访问到当前正在比较的索引。

720. 词典中最长的单词

力扣原题链接 (中等题)

给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。

若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

请注意，单词应该从左到右构建，每个额外的字符都添加到前一个单词的结尾。

示例 1：

输入： words = [“w”,“wo”,“wor”,“world”, “world”]
输出： “world”
解释： 单词"world"可由"w”, “wo”, “wor”, 和 “world"逐步添加一个字母组成。

示例 2：

输入： words = [“a”, “banana”, “app”, “appl”, “ap”, “apply”, “apple”]
输出： “apple”
解释： “apply” 和 “apple” 都能由词典中的单词组成。但是 “apple” 的字典序小于 “apply”

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 30
所有输入的字符串 words[i] 都只包含小写字母。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
    string longestWord(vector<string> &words)
    {
        // 如果输入的单词数组只有一个单词，则返回空字符串
        if (words.size() == 1)
            return "";
        // 对单词数组按字典序排序
        sort(words.begin(), words.end());
        // 创建一个长度为 31 的双端队列数组，用于存放不同长度的单词
        vector<deque<string>> vec(31);
        // 将单词按照长度分类存入 vec
        for (const auto &str : words)
        {
            vec[str.length()].push_back(str);
        }
        int count = 0;           // 计数器
        string comparedStr = ""; // 用于比较的字符串
        deque<string> temp;      // 临时队列
        // 从后向前遍历所有长度，从最长的单词开始
        for (int i = vec.size() - 1; i > 0; --i)
        {
            // 当长度为 i 的单词队列不为空时
            while (!vec[i].empty())
            {
                count = i; // 重置计数器为当前长度 i
                // 遍历每个长度为 j 的单词，查找与当前最长单词的前 j 个字符匹配的单词
                for (int j = i - 1; j >= 1; --j)
                {
                    temp = vec[j]; // 将长度为 j 的单词队列赋值给 temp
                    while (!temp.empty())
                    {
                        // 获取当前长度为 i 的单词的前 j 个字符
                        comparedStr = vec[i].front().substr(0, j);
                        // 如果匹配的字符等于 temp 队列的前面一个单词
                        if (comparedStr == temp.front())
                        {
                            --count;          // 匹配成功，计数器减一
                            temp.pop_front(); // 移除已经匹配的单词
                            break;            // 退出当前循环
                        }
                        temp.pop_front(); // 移除 temp 队列的前一个单词
                    }
                }
                // 如果计数器等于 1，返回当前单词
                if (count == 1)
                    return vec[i].front();
                // 移除已处理的长度为 i 的单词
                vec[i].pop_front();
            }
        }
        // 如果没有找到符合条件的单词，返回空字符串
        return "";
    }

主要步骤

输入参数：
- vector<string>& words: 输入的字符串数组，代表一个英语词典。
特殊情况处理：
- 如果输入的单词数组只有一个单词，则直接返回空字符串。
排序：
- 对单词数组按照字典序进行排序，这样可以确保返回的单词是字典序最小的。
分类存储：
- 创建一个长度为 31 的双端队列数组 vec，用来存储不同长度的单词，方便后续处理。
单词构建检查：
- 从最长的单词开始向前检查，寻找可以由更短的单词逐步构建的最长单词。
- 使用嵌套循环遍历每个长度的单词，并比较其前缀是否能在短单词列表中找到匹配。
返回结果：
- 当找到符合条件的单词时，立即返回；如果遍历完成后没有找到，则返回空字符串。

注意点

字典序：排序操作非常重要，因为它保证了在存在多个答案时，可以优先返回字典序最小的单词。
双端队列：使用双端队列 (deque) 以提高从两端插入和删除的效率，适合这个场景下的需求。
计数器的使用：count 变量用来记录当前匹配的状态，只有在完全匹配时才返回结果。
前缀匹配逻辑：在进行前缀比较时，确保正确处理每个长度的单词，并适时更新临时队列，避免重复匹配。

970. 强整数

力扣原题链接 (中等题)

给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。

如果某一整数可以表示为 xⁱ + y^j ，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个 强整数 。

你可以按 任何顺序 返回答案。在你的回答中，每个值最多出现一次。

示例 1：

输入： x = 2, y = 3, bound = 10
输出： [2,3,4,5,7,9,10]
解释：
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

示例 2：

输入： x = 3, y = 5, bound = 15
输出： [2,4,6,8,10,14]

提示：

1 <= x, y <= 100
0 <= bound <= 10⁶

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
    vector<int> powerfulIntegers(int x, int y, int bound)
    {
        // 如果上限值小于等于 1，返回空列表
        if (bound <= 1)
            return {};
        // 如果上限值小于等于 x 和 y 中的最小值
        if (bound <= min(x, y))
        {
            // 如果上限值为 2，返回包含上限值的列表
            if (bound == 2)
                return {bound};
            return {};
        }
        unordered_map<int, int> uMap; // 存储每个基数的次幂上限
        // 计算 x 的最大幂次
        int temp = (x == 1) ? 0 : bound / x; // 当 x 为 1 时，处理特殊情况
        // 计算 x 的各个幂次，同时更新 uMap
        while (temp > 0)
        {
            ++uMap[x];
            temp /= x;
        }
        // 计算 y 的最大幂次
        temp = (y == 1) ? 0 : bound / y; // 当 y 为 1 时，处理特殊情况
        // 计算 y 的各个幂次，同时更新 uMap
        while (temp > 0)
        {
            ++uMap[y];
            temp /= y;
        }
        unordered_set<int> tempRes;  // 存储强整数的集合
        int xn = 0, yn = 0, sum = 0; // 变量初始化
        // 遍历 x 的次幂
        for (int i = 0; i <= uMap[x] && pow(x, i) <= bound; ++i)
        {
            xn = pow(x, i); // 计算当前 x 的幂
            // 遍历 y 的次幂
            for (int j = 0; j <= uMap[y] && pow(y, j) <= bound; ++j)
            {
                yn = pow(y, j); // 计算当前 y 的幂
                sum = xn + yn;  // 计算强整数
                // 如果和小于等于上限，则添加到集合
                if (sum <= bound)
                    tempRes.insert(sum);
            }
        }
        // 返回强整数的向量形式
        return vector<int>(tempRes.begin(), tempRes.end());
    }

代码实现思路

边界条件处理：
- 如果 bound 小于或等于 1，直接返回空向量。
- 如果 bound 小于 x 和 y 中的最小值，进一步处理:
  - 如果 bound 等于 2，返回包含 bound 的列表。
  - 否则返回空列表。
计算基数的次幂上限：
- 使用 unordered_map<int, int> uMap 存储每个基数的最大幂次。
- 对于每个基数 x 和 y，计算其各个次幂，直到大于 bound。
计算强整数：
- 使用嵌套循环遍历 x 和 y 的次幂。如果 xn + yn（强整数的值）小于等于 bound，则将该值插入到 unordered_set<int> tempRes 中以确保唯一性。
返回结果：
- 最后将集合中的强整数转为向量 vector<int> 并返回。