LeetCode 1452. 收藏清单(std::includes判断子集)
发布日期:2021-07-01 03:25:47
浏览次数:2
分类:技术文章
本文共 2770 字,大约阅读时间需要 9 分钟。
1. 题目
给你一个数组 favoriteCompanies ,其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单(下标从 0 开始)。
请找出不是其他任何人收藏的公司清单的子集的收藏清单,并返回该清单下标。下标需要按升序排列。
示例 1:输入:favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]输出:[0,1,4] 解释:favoriteCompanies[2]=["google","facebook"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集。favoriteCompanies[3]=["google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 和 favoriteCompanies[1]=["google","microsoft"] 的子集。其余的收藏清单均不是其他任何人收藏的公司清单的子集,因此,答案为 [0,1,4] 。示例 2:输入:favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]输出:[0,1] 解释:favoriteCompanies[2]=["facebook","google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集,因此,答案为 [0,1] 。示例 3:输入:favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]输出:[0,1,2,3] 提示:1 <= favoriteCompanies.length <= 1001 <= favoriteCompanies[i].length <= 5001 <= favoriteCompanies[i][j].length <= 20favoriteCompanies[i] 中的所有字符串 各不相同 。用户收藏的公司清单也 各不相同 ,也就是说,即便我们按字母顺序排序每个清单,favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。所有字符串仅包含小写英文字母。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
template <class InputIterator1, class InputIterator2>
bool includes ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2 );
template <class InputIterator1, class InputIterator2, class Compare>
bool includes ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp );
Test whether sorted range includes another sorted range
Returns true if the sorted range [first1,last1) contains all the elements in the sorted range [first2,last2).
- 根据题意,各个集合不相同,那每个集合只需要在比它长的集合里查找,是否为其子集
- map根据长度分组,顺便排序,为使用
includes
准备 - 然后遍历输入数组 fc[i],在map中查找比 fc[i] 长度大的集合,使用
includes
判断
class Solution { public: vector peopleIndexes(vector>& favoriteCompanies) { map >> m;//len,排序后的字符 for(auto& fc : favoriteCompanies) { sort(fc.begin(), fc.end()); m[int(fc.size())].insert(fc); } vector ans; int len; bool flag; for(int i = 0; i < favoriteCompanies.size(); ++i) { len = favoriteCompanies[i].size(); //单词个数,只需要在大于它的集合里查找 auto it = m.lower_bound(len+1); flag = true; for(auto iter = it; iter != m.end(); ++iter) { for(auto sit = iter->second.begin(); sit != iter->second.end(); ++sit) { if(includes(sit->begin(),sit->end(),favoriteCompanies[i].begin(),favoriteCompanies[i].end())) { flag = false; break; } } if(!flag) break; } if(flag) ans.push_back(i); } return ans; }};
464 ms 52.3 MB
转载地址:https://michael.blog.csdn.net/article/details/106174067 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月13日 09时08分06秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
填入空隙(setbkcolor,setbkmode)
2019-05-02
[收藏] FC交换机基础知识详解
2019-05-02
NVMe技术架构深度分析
2019-05-02
技术爆炸时代如何做技术的掌控者?
2019-05-02
机柜服务器如何选择,有哪些学问?
2019-05-02
Ceph存储系统Scrub机制分析
2019-05-02
OpenStack重组,敢问未来路在何方?
2019-05-02
CTO,是怎样炼成的?
2019-05-02
选择GPU服务器的基本原则
2019-05-02
关于数据中台系统,需要了解哪些技术?
2019-05-02
全面分析HDFS基本技术原理
2019-05-02
详解以太网介质技术发展史!
2019-05-02
详解“硬核”虚拟化技术SR-IOV原理
2019-05-02
SAP HANA解决方案设计10问详解
2019-05-02
详解内存运算架构、挑战和趋势
2019-05-02
Lightbits能否让NVMe/TCP新标准旗开得胜?
2019-05-02
数据中台,何为正解?!
2019-05-02
架构师进阶必看!架构师的工作都干些什么?
2019-05-02
详解RDMA架构和技术原理
2019-05-02
Virtio技术架构简明分析
2019-05-02