做网站有多难,平面设计学徒要学多久,松江做网站公司,杭州软件开发培训学校1. 题目
给你一个数组 favoriteCompanies #xff0c;其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单#xff08;下标从 0 开始#xff09;。
请找出不是其他任何人收藏的公司清单的子集的收藏清单#xff0c;并返回该清单下标。下标需要按升序排列。
示例 1其中 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 100
1 favoriteCompanies[i].length 500
1 favoriteCompanies[i][j].length 20
favoriteCompanies[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. 解题
std::includes 参考 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:vectorint peopleIndexes(vectorvectorstring favoriteCompanies) {mapint,setvectorstring m;//len,排序后的字符for(auto fc : favoriteCompanies){sort(fc.begin(), fc.end());m[int(fc.size())].insert(fc);}vectorint ans;int len;bool flag;for(int i 0; i favoriteCompanies.size(); i){len favoriteCompanies[i].size();//单词个数只需要在大于它的集合里查找auto it m.lower_bound(len1);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
