又是气死我的一题TAT,我连暴力都写不对。

3. 收藏清单

给你一个数组 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 <= 100
  • 1 <=?favoriteCompanies[i].length <= 500
  • 1 <=?favoriteCompanies[i][j].length <= 20
  • favoriteCompanies[i] 中的所有字符串 各不相同
  • 用户收藏的公司清单也 各不相同 ,也就是说,即便我们按字母顺序排序每个清单, favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。
  • 所有字符串仅包含小写英文字母。

题意

给出一堆集合,求不是任何其他集合子集的集合下标。

思路

暴力就行了,重点是判断子集。把每个集合按照字典序排序(一定要加&啊啊啊),然后用集合 A 去匹配集合 B 上的元素。具体方法是定义一个 A 上的指针 cur ,循环判断 A[cur] == B[j] ,如果等于就 cur++

代码

int vis[105];
class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
        int n = favoriteCompanies.size();
        for(int i=0; i<n; i++) vis[i] = false;
        for(auto &v: favoriteCompanies) sort(v.begin(), v.end());
        
        vector<int> ans;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i == j) continue;
                int cur = 0, leni = favoriteCompanies[i].size(), lenj = favoriteCompanies[j].size();
                for(int k=0; k<lenj; k++) {
                    if(cur >= leni) break;
                    if(favoriteCompanies[i][cur] == favoriteCompanies[j][k]) cur++;
                }
                if(cur == leni) {
                    vis[i] = true;
                    break;
                }
            } 
        }
         
        for(int i=0; i<n; i++) if(!vis[i]) ans.push_back(i);
        return ans;
    }
};
最后修改:2020 年 05 月 17 日 03 : 46 PM
如果觉得我的文章对你有用,请随意赞赏