算法day_6 算法练习

碎碎念

这是我在2024年12月23日的算法练习，加油！

题目一：第 K 个独一无二的字符串

数组中第 K 个独一无二的字符串

定义：在数组中只出现过 一次 的字符串称为 独一无二的字符串。

题目描述

给定一个字符串数组 arr 和一个整数 k，返回 arr 中第 k 个 独一无二的字符串。如果 少于 k 个独一无二的字符串，则返回空字符串 ""。

要求：按照字符串在原数组中的 顺序 找到第 k 个独一无二的字符串。

示例

示例 1

输入：arr = ["d","b","c","b","c","a"], k = 2
输出："a"
解释：
数组中的独一无二的字符串包括 "d" 和 "a"。
"d" 最先出现，是第 1 个独一无二的字符串。
"a" 是第 2 个独一无二的字符串。
因此，返回 "a" 。

示例 2

输入：arr = ["aaa","aa","a"], k = 1
输出："aaa"
解释：
数组中的所有字符串都是独一无二的，返回第 1 个字符串 "aaa"。

示例 3

输入：arr = ["a","b","a"], k = 3
输出：""
解释：
唯一的独一无二的字符串是 "b"。因为少于 3 个独一无二的字符串，返回空字符串 ""。

题目难度

简单

知识点

• 哈希表（Hash Table）
• 字符串处理
• 数组遍历

解题思路

1. 使用 unordered_map 统计每个字符串的出现次数。
2. 遍历数组，依次查找出现次数为 1 的字符串，找到第 k 个返回。
3. 如果遍历结束仍未找到，返回空字符串。

代码实现

#include <unordered_map>
#include <vector>
#include <string>using namespace std;class Solution {
public:string kthDistinct(vector<string>& arr, int k) {// 统计每个字符串的出现次数unordered_map<string, int> count;for (const auto& str : arr) {count[str]++;}// 按顺序查找第k个独一无二的字符串for (const auto& str : arr) {if (count[str] == 1) {if (--k == 0) {return str;}}}return ""; // 不存在第k个独一无二的字符串}
};

---

题目二：查找共用字符

查找共用字符

题目描述

给定一个字符串数组 words，找出所有在 words 的每个字符串中都出现的共用字符（包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

示例

示例 1

输入：words = ["bella","label","roller"]
输出：["e","l","l"]

示例 2

输入：words = ["cool","lock","cook"]
输出：["c","o"]

提示

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] 由小写英文字母组成

题目难度

简单（实际上具有中等难度）

知识点

• 数组处理
• 哈希表（Hash Table）
• 字符频率统计

解题思路

1. 初始化一个长度为26的数组 minFre，记录每个字母在所有单词中出现的最小频率。
2. 遍历每个单词，统计每个字母的频率，并更新 minFre。
3. 根据 minFre 构建结果数组。

代码实现

#include <vector>
#include <string>
#include <algorithm>
#include <climits>using namespace std;class Solution {
public:vector<string> commonChars(vector<string>& words) {// 初始化最小频率数组vector<int> minFre(26, INT_MAX);for(const string& word: words){// 记录当前单词中每个字母的频率vector<int> fre(26, 0);for(char ch : word){fre[ch - 'a']++;}// 更新全局最小频率for(int i = 0; i < 26; ++i ){minFre[i] = min(fre[i], minFre[i]);}}// 根据minFre构建结果vector<string> result;for(int i = 0; i < 26; ++i){while(minFre[i]-- > 0){result.emplace_back(1, 'a' + i);}}return result;}
};
``}# 参考资料- [LeetCode 第 2053 题：第 K 个独一无二的字符串](https://leetcode.cn/problems/kth-distinct-string-in-an-array/)
- [LeetCode 第 1002 题：查找共用字符](https://leetcode.cn/problems/find-common-characters/)
- [C++ `unordered_map` 使用详解](https://www.cplusplus.com/reference/unordered_map/unordered_map/)
- [字符串处理方法](https://www.geeksforgeeks.org/string-handling-in-cpp/)
- [频率统计与应用](https://www.geeksforgeeks.org/frequency-count-occurrences-array/)