C++刷leetcode（5414. 收藏清单）【数据结构】

糖逗

1. 
   
2. 给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。
   
3. 
   
4. 请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。
   
5. 
   
6. 
   
7. 
   
8. 示例 1：
   
9. 
   
10. 输入：favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
    
11. 输出：[0,1,4]
    
12. 解释：
    
13. favoriteCompanies[2]=["google","facebook"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集。
    
14. favoriteCompanies[3]=["google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 和 favoriteCompanies[1]=["google","microsoft"] 的子集。
    
15. 其余的收藏清单均不是其他任何人收藏的公司清单的子集，因此，答案为 [0,1,4] 。
    
16. 示例 2：
    
17. 
    
18. 输入：favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]
    
19. 输出：[0,1]
    
20. 解释：favoriteCompanies[2]=["facebook","google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集，因此，答案为 [0,1] 。
    
21. 示例 3：
    
22. 
    
23. 输入：favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
    
24. 输出：[0,1,2,3]
    
25. 
    
26. 
    
27. 提示：
    
28. 
    
29. 1 <= favoriteCompanies.length <= 100
    
30. 1 <= favoriteCompanies[i].length <= 500
    
31. 1 <= favoriteCompanies[i][j].length <= 20
    
32. favoriteCompanies[i] 中的所有字符串 各不相同 。
    
33. 用户收藏的公司清单也 各不相同 ，也就是说，即便我们按字母顺序排序每个清单， favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。
    
34. 所有字符串仅包含小写英文字母。

复制代码

1. class Solution {
   
2. public:
   
3.     vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
   
4.         for (auto& f : favoriteCompanies) {
   
5.             sort(f.begin(), f.end());
   
6.         }//先对每个vector中的字符串进行排序
   
7. 
   
8.         map<int, vector<int>> mapSizeIndex;//存储可能的组的大小和对应的每个数组的序列号
   
9.         for (int i = 0; i < favoriteCompanies.size(); i++) {
   
10.             mapSizeIndex[favoriteCompanies[i].size()].push_back(i);
    
11.         }
    
12. 
    
13.         vector<int> ans;
    
14.         for (auto it = mapSizeIndex.rbegin(); it != mapSizeIndex.rend(); it++) {
    
15.             for (auto& p : it->second) {
    
16.                 if (it != mapSizeIndex.rbegin() && checkIncludes(favoriteCompanies, ans, p)) continue;
    
17.                 ans.push_back(p);
    
18.             }
    
19.         }
    
20. 
    
21.         sort(ans.begin(), ans.end());
    
22.         return ans;
    
23.     }
    
24. 
    
25.     bool checkIncludes(vector<vector<string>>& fc, vector<int>& ans, int p) {
    
26.         for (auto i : ans) {
    
27.             if (includes(fc[i].begin(), fc[i].end(), fc[p].begin(), fc[p].end())) return true;
    
28.         }
    
29.         return false;
    
30.     }
    
31. };

复制代码

参考链接：https://leetcode-cn.com/problems ... by-ikaruga/#comment
注意事项：
1.map的迭代器能保证键按照排序好的顺序输出。
2.std::includes的使用：https://blog.csdn.net/weixin_44813711/article/details/105135042

糖逗

学习评论区大佬的代码，暴力算法自己没想出来