1452 added.

liuyubobobo · liuyubobobo · commit 75af3cbcebb1 · 2020-05-16T23:10:52.000-07:00
diff --git a/1452-People-Whose-List-of-Favorite-Companies-Is-Not-a-Subset-of-Another-List/cpp-1452/CMakeLists.txt b/1452-People-Whose-List-of-Favorite-Companies-Is-Not-a-Subset-of-Another-List/cpp-1452/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.16)
+project(C)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(C main3.cpp)
diff --git a/1452-People-Whose-List-of-Favorite-Companies-Is-Not-a-Subset-of-Another-List/cpp-1452/main.cpp b/1452-People-Whose-List-of-Favorite-Companies-Is-Not-a-Subset-of-Another-List/cpp-1452/main.cpp
@@ -0,0 +1,53 @@
+/// Source : https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/
+/// Author : liuyubobobo
+/// Time   : 2020-05-16
+
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+
+using namespace std;
+
+
+/// Brute Force + HashSet to check subset
+/// Time Complexity: O(n^2 * m * |s|)
+/// Space Complexity: O(n * m)
+class Solution {
+public:
+    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
+
+        int n = favoriteCompanies.size();
+
+        vector<unordered_set<string>> setv;
+        for(const vector<string>& v: favoriteCompanies)
+            setv.push_back(unordered_set<string>(v.begin(), v.end()));
+
+        vector<int> res;
+        for(int i = 0; i < n; i ++){
+            bool is_sub = false;
+            for(int j = 0; j < n; j ++)
+                if(j != i && setv[i].size() < setv[j].size() && isSub(setv[i], setv[j])){
+                    is_sub = true;
+                    break;
+                }
+
+            if(!is_sub) res.push_back(i);
+        }
+        return res;
+    }
+
+private:
+    // see if a is subset of b
+    bool isSub(const unordered_set<string>& a, const unordered_set<string>& b){
+
+        for(string e: a)
+            if(!b.count(e)) return false;
+        return true;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/1452-People-Whose-List-of-Favorite-Companies-Is-Not-a-Subset-of-Another-List/cpp-1452/main2.cpp b/1452-People-Whose-List-of-Favorite-Companies-Is-Not-a-Subset-of-Another-List/cpp-1452/main2.cpp
@@ -0,0 +1,54 @@
+/// Source : https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/
+/// Author : liuyubobobo
+/// Time   : 2020-05-16
+
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+
+using namespace std;
+
+
+/// Brute Force + Binary Search to check subset
+/// Time Complexity: O(n^2 * m * logm * |s|)
+/// Space Complexity: O(n * m)
+class Solution {
+public:
+    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
+
+        int n = favoriteCompanies.size();
+        for(int i = 0; i < n; i ++)
+            sort(favoriteCompanies[i].begin(), favoriteCompanies[i].end());
+
+        vector<int> res;
+        for(int i = 0; i < n; i ++){
+            bool is_sub = false;
+            for(int j = 0; j < n; j ++)
+                if(j != i && favoriteCompanies[i].size() < favoriteCompanies[j].size() &&
+                   isSub(favoriteCompanies[i], favoriteCompanies[j])){
+                    is_sub = true;
+                    break;
+                }
+
+            if(!is_sub) res.push_back(i);
+        }
+        return res;
+    }
+
+private:
+    // see if a is subset of b
+    bool isSub(const vector<string>& a, const vector<string>& b){
+
+        for(string e: a){
+            vector<string>::const_iterator iter = lower_bound(b.begin(), b.end(), e);
+            if(iter == b.end() || *iter != e) return false;
+        }
+        return true;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/1452-People-Whose-List-of-Favorite-Companies-Is-Not-a-Subset-of-Another-List/cpp-1452/main3.cpp b/1452-People-Whose-List-of-Favorite-Companies-Is-Not-a-Subset-of-Another-List/cpp-1452/main3.cpp
@@ -0,0 +1,63 @@
+/// Source : https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/
+/// Author : liuyubobobo
+/// Time   : 2020-05-16
+
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+#include <unordered_map>
+
+using namespace std;
+
+
+/// Brute Force + Using String to Int Set to check subset
+/// Time Complexity: O(n * m * |s| + n^2 * m)
+/// Space Complexity: O(n * m)
+class Solution {
+public:
+    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
+
+        int n = favoriteCompanies.size();
+
+        unordered_map<string, int> map;
+        int index = 0;
+
+        vector<unordered_set<int>> mapv;
+        for(const vector<string>& v: favoriteCompanies){
+            unordered_set<int> tv;
+            for(const string& s: v){
+                if(!map.count(s)) map[s] = index ++;
+                tv.insert(map[s]);
+            }
+            mapv.push_back(tv);
+        }
+
+        vector<int> res;
+        for(int i = 0; i < n; i ++){
+            bool is_sub = false;
+            for(int j = 0; j < n; j ++)
+                if(j != i && mapv[i].size() <= mapv[j].size() && isSub(mapv[i], mapv[j])){
+                    is_sub = true;
+                    break;
+                }
+
+            if(!is_sub) res.push_back(i);
+        }
+        return res;
+    }
+
+private:
+    // see if a is subset of b
+    bool isSub(const unordered_set<int>& a, const unordered_set<int>& b){
+
+        for(int e: a)
+            if(!b.count(e)) return false;
+        return true;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -1052,7 +1052,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 1449 | [Form Largest Integer With Digits That Add up to Target](https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/) | [无] | [C++](1449-Form-Largest-Integer-With-Digits-That-Add-up-to-Target/cpp-1449/) | | |
 | 1450 | [Number of Students Doing Homework at a Given Time](https://leetcode.com/problems/number-of-students-doing-homework-at-a-given-time/) | [无] | [C++](1450-Number-of-Students-Doing-Homework-at-a-Given-Time/cpp-1450/) | | |
 | 1451 | [Rearrange Words in a Sentence](https://leetcode.com/problems/rearrange-words-in-a-sentence/) | [无] | [C++](1451-Rearrange-Words-in-a-Sentence/cpp-1451/) | | |
-| | | | | | |
+| 1452 | [People Whose List of Favorite Companies Is Not a Subset of Another List](https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/) | [无] | [C++](1452-People-Whose-List-of-Favorite-Companies-Is-Not-a-Subset-of-Another-List/cpp-1452/) | | |
 
 ## 力扣中文站比赛
 
