网站建设的意义_建设银行app忘记登录密码_杭州百度人工优化_产品推销

问题描述

我们需要设计一个推荐系统，它接受一个产品数组和一个搜索词。每当用户输入一个字母时，系统应该返回与当前输入前缀匹配的最多三个产品。如果匹配的产品超过三个，则按字典序返回最小的三个。

1268. 搜索推荐系统 - 力扣（LeetCode）

问题拆解

在设计这个推荐系统时，我们的任务是实现一个产品推荐功能：在用户输入每个字母时，根据当前的输入词前缀找出符合条件的前三个产品，并按字典序排列。这个问题可以拆解为几个小步骤，分别处理：

对产品进行排序，使它们在字典序排列。
构建搜索前缀：当用户每次输入一个字母时，逐步构成当前的前缀。
查找匹配产品：根据当前前缀，找到符合要求的最多三个产品。
存储并输出结果：将每次匹配的推荐产品存储在结果列表中。

详细解决方案和实现步骤

1. 对产品进行排序

我们使用 sort() 函数对产品数组进行排序。这样，在后续查找时可以确保找到的结果是按字典序排列的。C++ 中的 sort() 函数是基于快排实现的，平均时间复杂度为 (O(N \log N))，可以有效地对产品进行排序。

sort(products.begin(), products.end());

2. 构建搜索前缀

在处理搜索词时，我们希望每次用户输入一个字母后更新当前前缀，并基于这个前缀寻找匹配的产品。例如，如果搜索词是 “mouse”，那么当用户输入第一个字母 “m” 时，前缀是 “m”；当输入第二个字母 “o” 时，前缀更新为 “mo”。

for (char c : searchWord) {prefix += c; // 每次添加一个字母到前缀中

每次循环中，我们根据新的 prefix 来进行产品查找。

3. 查找匹配产品

有了前缀后，我们接下来要做的是找出所有以该前缀开头的产品。由于之前已经排序过产品，所以在循环遍历产品时，一旦找到不匹配的产品，可以立即停止循环。我们使用 find(prefix) == 0 来判断一个产品是否以当前前缀开头。

代码解析

判断前缀匹配：product.find(prefix) == 0 表示当前产品 product 的开头是前缀 prefix。
存储前三个产品：在匹配产品的循环中，一旦找到的匹配产品达到 3 个，即 suggestions.size() == 3，就可以跳出循环，以避免不必要的计算。

for (const string& product : products) {if (product.find(prefix) == 0) { // 找到前缀匹配的产品suggestions.push_back(product); // 加入到推荐列表if (suggestions.size() == 3) // 只保留最多3个break;}
}

4. 存储并输出结果

每次找到符合条件的推荐产品后，我们将其添加到最终的结果列表 result 中：

result.push_back(suggestions);

完整代码实现

下面是完整的 C++ 实现，包括了以上所有步骤：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>using namespace std;vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {// 对产品列表按字典序排序sort(products.begin(), products.end());vector<vector<string>> result; // 最终结果存储string prefix; // 当前前缀// 遍历每个字符，构建前缀并查找匹配的产品for (char c : searchWord) {prefix += c; // 构建当前前缀vector<string> suggestions; // 当前前缀的推荐产品列表// 遍历所有产品，找出匹配前缀的产品for (const string& product : products) {if (product.find(prefix) == 0) { // 如果产品以前缀开头suggestions.push_back(product);if (suggestions.size() == 3) // 只保留最多三个推荐break;}}// 将当前前缀的推荐列表加入到结果中result.push_back(suggestions);}return result;
}// 测试示例
int main() {vector<string> products = {"mobile", "mouse", "moneypot", "monitor", "mousepad"};string searchWord = "mouse";vector<vector<string>> results = suggestedProducts(products, searchWord);// 输出结果for (const auto& res : results) {cout << "[ ";for (const auto& str : res) {cout << str << " ";}cout << "]" << endl;}return 0;
}

运行结果示例

假设输入的 products 为 {"mobile", "mouse", "moneypot", "monitor", "mousepad"}，searchWord 为 "mouse"。代码输出如下：

[ mobile moneypot monitor ]
[ mobile moneypot monitor ]
[ mouse mousepad ]
[ mouse mousepad ]
[ mouse mousepad ]

复杂度分析

时间复杂度： $O(N \log N + M \cdot N)$ ，其中 $N$ 是产品的数量， $M$ 是搜索词的长度。
- 排序复杂度为 $\log N)$ 。
- 查找前缀的复杂度为 $\cdot N)$ 。
空间复杂度：O(M * 3)，其中 (M) 是搜索词的长度，最大推荐产品数为 3。

总结

通过以上步骤，我们实现了一个动态推荐系统，它能在用户逐字输入时提供实时的产品推荐。我们利用字符串的 find() 方法有效地检查前缀匹配，同时通过逐步构建前缀确保推荐的准确性。这种算法设计思路不仅清晰而且高效，适合处理实际应用中的类似问题。希望本博客能帮助读者更好地理解此算法的实现过程和细节。