C++刷leetcode（5414. 收藏清单）【数据结构】
本帖最后由 糖逗 于 2020-5-17 14:31 编辑给你一个数组 favoriteCompanies ，其中 favoriteCompanies 是第 i 名用户收藏的公司清单（下标从 0 开始）。
请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。
示例 1：
输入：favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
输出：
解释：
favoriteCompanies=["google","facebook"] 是 favoriteCompanies=["leetcode","google","facebook"] 的子集。
favoriteCompanies=["google"] 是 favoriteCompanies=["leetcode","google","facebook"] 和 favoriteCompanies=["google","microsoft"] 的子集。
其余的收藏清单均不是其他任何人收藏的公司清单的子集，因此，答案为 。
示例 2：
输入：favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]
输出：
解释：favoriteCompanies=["facebook","google"] 是 favoriteCompanies=["leetcode","google","facebook"] 的子集，因此，答案为 。
示例 3：
输入：favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
输出：
提示：
1 <= favoriteCompanies.length <= 100
1 <= favoriteCompanies.length <= 500
1 <= favoriteCompanies.length <= 20
favoriteCompanies 中的所有字符串 各不相同 。
用户收藏的公司清单也 各不相同 ，也就是说，即便我们按字母顺序排序每个清单， favoriteCompanies != favoriteCompanies 仍然成立。
所有字符串仅包含小写英文字母。
class Solution {
public:
vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
for (auto& f : favoriteCompanies) {
sort(f.begin(), f.end());
}//先对每个vector中的字符串进行排序
map<int, vector<int>> mapSizeIndex;//存储可能的组的大小和对应的每个数组的序列号
for (int i = 0; i < favoriteCompanies.size(); i++) {
mapSizeIndex.size()].push_back(i);
}
vector<int> ans;
for (auto it = mapSizeIndex.rbegin(); it != mapSizeIndex.rend(); it++) {
for (auto& p : it->second) {
if (it != mapSizeIndex.rbegin() && checkIncludes(favoriteCompanies, ans, p)) continue;
ans.push_back(p);
}
}
sort(ans.begin(), ans.end());
return ans;
}
bool checkIncludes(vector<vector<string>>& fc, vector<int>& ans, int p) {
for (auto i : ans) {
if (includes(fc.begin(), fc.end(), fc.begin(), fc.end())) return true;
}
return false;
}
};
参考链接：https://leetcode-cn.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/solution/favorite-companies-by-ikaruga/#comment
注意事项：
1.map的迭代器能保证键按照排序好的顺序输出。
2.std::includes的使用：https://blog.csdn.net/weixin_44813711/article/details/105135042 学习评论区大佬的代码，暴力算法自己没想出来{:10_324:}
页:
[1]