leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1452.cpp (1472B)

      1 class Solution {
      2   public:
      3     vector<int> peopleIndexes(const vector<vector<string>> &favoriteCompanies) const {
      4         const int n = size(favoriteCompanies);
      5         vector<unordered_set<int>> companies(n);
      6         unordered_map<string, int> um;
      7 
      8         for (int i = 0; i < n; i++) {
      9             for (const auto &company : favoriteCompanies[i]) {
     10                 const auto it = um.find(company);
     11                 const int key = it == um.end() ? um.size() : it->second;
     12                 if (it == um.end()) um.emplace(company, key);
     13                 companies[i].insert(key);
     14             }
     15         }
     16 
     17         static int candidates[101];
     18         vector<int> res;
     19         for (int i = 0; i < n; i++) {
     20             int elems = 0;
     21             for (int j = 0; j < n; j++) {
     22                 if (i == j) continue;
     23                 if (size(companies[i]) >= size(companies[j])) continue;
     24                 candidates[elems++] = j;
     25             }
     26 
     27             for (const auto &company : companies[i]) {
     28                 int t = 0;
     29                 for (int j = 0; j < elems; j++) {
     30                     const int candidate = candidates[j];
     31                     if (companies[candidate].count(company)) {
     32                         candidates[t++] = candidate;
     33                     }
     34                 }
     35 
     36                 if (!t) {
     37                     res.push_back(i);
     38                     break;
     39                 }
     40                 elems = t;
     41             }
     42         }
     43         return res;
     44     }
     45 };