碎碎念
这是我在2024年12月21日的算法练习，加油！
题目一：不常见单词查找
884. 两句话中的不常见单词
题目描述
给定两个句子 s1 和 s2，找出仅在其中一个句子中出现一次的单词。也就是说，这些单词在两个句子中只出现过一次，并且只出现在其中一个句子中。
示例
示例 1:
输入: s1 = "this apple is sweet", s2 = "this apple is sour"
输出: ["sweet","sour"]
示例 2:
输入: s1 = "apple apple", s2 = "banana"
输出: ["banana"]
解题思路
-
字符串分割
- 使用 C++ 的
istringstream进行字符串分割，根据 C++ Reference 文档，这是处理空格分隔字符串的标准方法。 istringstream会自动跳过空格，逐个读取单词。- 通过将两个句子分开处理，可以准确统计每个单词的总出现次数。
- 使用 C++ 的
-
词频统计
- 使用
unordered_map记录每个单词的出现次数。 - 遍历两个句子中的所有单词，并在哈希表中更新对应单词的计数。
- 时间复杂度为 O(n)，其中 n 为总单词数。
- 空间复杂度为 O(m)，其中 m 为不重复单词数。
- 使用
-
结果筛选
- 遍历哈希表，筛选出出现次数为 1 的单词，这些单词即为仅在一个句子中出现过的单词。
完整代码实现
#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>using namespace std;class Solution {
public:vector<string> uncommonFromSentences(string s1, string s2) {unordered_map<string, int> wordsCount; // 哈希表用于记录单词频率string word;vector<string> result;// Lambda 函数用于处理字符串分割和词频统计auto helper = [&](const string& s) {istringstream iss(s);while (iss >> word) {wordsCount[word]++;}};helper(s1); // 处理第一个句子helper(s2); // 处理第二个句子// 筛选出只出现一次的单词for (const auto& [key, value] : wordsCount) {if (value == 1) {result.emplace_back(key);}}return result;}
};
代码解析
unordered_map<string, int> wordsCount: 用于存储每个单词及其出现次数。helperLambda 函数: 负责将输入的句子进行分割，并更新哈希表中的单词计数。- 遍历哈希表: 通过遍历哈希表中的键值对，筛选出出现次数为 1 的单词，并将其添加到结果向量中。
时间复杂度分析
- 字符串分割: 每个句子都需要 O(n) 的时间进行分割。
- 词频统计: 由于使用了哈希表，插入和查找操作的平均时间复杂度为 O(1)，总的词频统计时间复杂度为 O(n)。
- 结果筛选: 遍历哈希表，时间复杂度为 O(m)。
总体时间复杂度为 O(n)，其中 n 是两个句子中单词的总数。
题目二：字符串压缩
面试题 01.06. 字符串压缩
题目描述
实现一个方法，将连续重复的字符进行压缩。对于每一组连续重复的字符，替换成字符后跟其出现的次数。如果压缩后的字符串没有变短，则返回原始字符串。
示例
示例 1:
输入："aabcccccaaa"
输出："a2b1c5a3"
示例 2:
输入："abc"
输出："abc"
解题思路
使用双指针技巧解决该问题：
-
指针设计
i指针：标记当前处理字符的起始位置。j指针：向后搜索相同字符的结束位置。- 区间
[i, j)表示连续相同字符段。
-
压缩规则
- 记录每段相同字符的首字符和出现次数。
- 当压缩后字符串更短时返回压缩后的字符串，否则返回原字符串。
- 时间复杂度为 O(n)，其中 n 是字符串的长度。
- 空间复杂度为 O(n)，用于存储压缩后的字符串。
-
优化点
- 预先计算压缩后的字符串长度，可以避免在不必要的情况下进行字符串拼接。
- 使用
ostringstream或者直接构造字符串以提升效率。
完整实现
#include <string>using namespace std;class Solution {
public:string compressString(string S) {int i = 0, j = 0;string result;while (i < S.size()) {// 移动 j 指针，找到当前字符段的结束位置while (j < S.size() && S[i] == S[j]) {j++;}// 记录当前字符及其出现次数result += S[i];result += to_string(j - i);i = j; // 更新 i 指针，开始处理下一个字符段}// 比较压缩后的字符串长度与原字符串的长度return result.size() < S.size() ? result : S;}
};
代码解析
- 指针
i和j: 用于标记当前正在处理的字符段的起始和结束位置。 - 字符串拼接: 将当前字符和其出现次数拼接到结果字符串中。
- 条件判断: 最后比较压缩后的字符串长度与原字符串长度，决定返回哪一个。
时间复杂度分析
- 主循环: 每个字符最多被遍历两次（一次由 i 指针，一次由 j 指针），时间复杂度为 O(n)。
- 字符串拼接: 在最坏情况下，每个字符都需要被拼接到结果字符串中，依然保持 O(n) 的时间复杂度。
总体时间复杂度为 O(n)，空间复杂度为 O(n)。
进一步优化
- 如果需要提高性能，可以考虑预分配足够的空间给
result字符串，避免多次内存分配。 - 在处理大量重复字符时，可以提前返回结果，减少不必要的计算。
总结
今天的两题也是非常简单的两题，主要考察了字符串处理的基本技巧。加油喔！
附加资源
- C++
istringstream使用指南 - LeetCode 884. 两句话中的不常见单词 题解
- LeetCode 面试题 01.06. 字符串压缩 解题思路
- 双指针算法详解
