2729-2732 solved.

liuyubobobo · liuyubobobo · commit ca3de8db18fa · 2023-06-19T14:40:14.000-07:00
diff --git a/2501-3000/2729-Check-if-The-Number-is-Fascinating/cpp-2729/CMakeLists.txt b/2501-3000/2729-Check-if-The-Number-is-Fascinating/cpp-2729/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.25)
+project(cpp_2729)
+
+set(CMAKE_CXX_STANDARD 17)
+
+add_executable(cpp_2729 main.cpp)
diff --git a/2501-3000/2729-Check-if-The-Number-is-Fascinating/cpp-2729/main.cpp b/2501-3000/2729-Check-if-The-Number-is-Fascinating/cpp-2729/main.cpp
@@ -0,0 +1,33 @@
+/// Source : https://leetcode.com/problems/check-if-the-number-is-fascinating/description/
+/// Author : liuyubobobo
+/// Time   : 2023-06-13
+
+#include <iostream>
+#include <vector>
+#include <numeric>
+#include <algorithm>
+
+using namespace std;
+
+
+/// Simulation
+/// Time Complexity: O(logn)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    bool isFascinating(int n) {
+
+        int a = n, b = 2 * n, c = 3 * n;
+        string s = to_string(a) + to_string(b) + to_string(c);
+
+        vector<int> f(10, 0);
+        for(char c: s) f[c - '0'] ++;
+        return count_if(f.begin() + 1, f.end(), [](int e){return e == 1;}) == 9;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/2501-3000/2730-Find-the-Longest-Semi-Repetitive-Substring/cpp-2730/CMakeLists.txt b/2501-3000/2730-Find-the-Longest-Semi-Repetitive-Substring/cpp-2730/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.25)
+project(cpp_2730)
+
+set(CMAKE_CXX_STANDARD 17)
+
+add_executable(cpp_2730 main.cpp)
diff --git a/2501-3000/2730-Find-the-Longest-Semi-Repetitive-Substring/cpp-2730/main.cpp b/2501-3000/2730-Find-the-Longest-Semi-Repetitive-Substring/cpp-2730/main.cpp
@@ -0,0 +1,37 @@
+/// Source : https://leetcode.com/problems/find-the-longest-semi-repetitive-substring/description/
+/// Author : liuyubobobo
+/// Time   : 2023-06-13
+
+#include <iostream>
+#include <algorithm>
+
+using namespace std;
+
+
+/// Brute Force
+/// Time Complexity: O(n^2)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    int longestSemiRepetitiveSubstring(string s) {
+
+        int res = 1;
+        for(int i = 0; i + 1 < s.size(); i ++)
+            res = max(res, solve(s, i, i + 1));
+        return res;
+    }
+
+private:
+    int solve(const string& s, int a, int b){
+        int res = 2;
+        for(int i = a - 1; i >= 0 && s[i] != s[i + 1]; i --) res ++;
+        for(int i = b + 1; i < s.size() && s[i] != s[i - 1]; i ++) res ++;
+        return res;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/2501-3000/2731-Movement-of-Robots/cpp-2731/CMakeLists.txt b/2501-3000/2731-Movement-of-Robots/cpp-2731/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.25)
+project(cpp_2731)
+
+set(CMAKE_CXX_STANDARD 17)
+
+add_executable(cpp_2731 main.cpp)
diff --git a/2501-3000/2731-Movement-of-Robots/cpp-2731/main.cpp b/2501-3000/2731-Movement-of-Robots/cpp-2731/main.cpp
@@ -0,0 +1,49 @@
+/// Source : https://leetcode.com/problems/movement-of-robots/description/
+/// Author : liuyubobobo
+/// Time   : 2023-06-13
+
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+using namespace std;
+
+
+/// Ad-Hoc
+/// Time Complexity: O(nlogn)
+/// Space Complexity: O(1)
+class Solution {
+
+private:
+    const long long MOD = 1e9 + 7;
+
+public:
+    int sumDistance(vector<int>& nums, string s, int d) {
+
+        int n = nums.size();
+        for(int i = 0; i < n; i ++)
+            if(s[i] == 'R') nums[i] += d; else nums[i] -= d;
+        sort(nums.begin(), nums.end());
+
+        long long right_dis = 0, right_cnt = n - 1;
+        for(int i = 1; i < n; i ++) right_dis += 0ll + nums[i] - nums[0];
+
+        long long res = right_dis % MOD;
+        for(int i = 1; i < n; i ++){
+            long long cur = 0ll + nums[i] - nums[i - 1];
+
+            right_dis = (right_dis - right_cnt * cur % MOD + MOD) % MOD;
+            right_cnt --;
+
+            res = (res + right_dis) % MOD;
+            res %= MOD;
+        }
+        return res;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/2501-3000/2732-Find-a-Good-Subset-of-the-Matrix/cpp-2732/CMakeLists.txt b/2501-3000/2732-Find-a-Good-Subset-of-the-Matrix/cpp-2732/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.25)
+project(cpp_2732)
+
+set(CMAKE_CXX_STANDARD 17)
+
+add_executable(cpp_2732 main.cpp)
diff --git a/2501-3000/2732-Find-a-Good-Subset-of-the-Matrix/cpp-2732/main.cpp b/2501-3000/2732-Find-a-Good-Subset-of-the-Matrix/cpp-2732/main.cpp
@@ -0,0 +1,44 @@
+/// Source : https://leetcode.com/problems/find-a-good-subset-of-the-matrix/description/
+/// Author : liuyubobobo
+/// Time   : 2023-06-19
+
+#include <iostream>
+#include <vector>
+#include <map>
+
+using namespace std;
+
+
+/// Ad-Hoc
+/// Time Complexity: O(n * 2^b)
+/// Space Complexity: O(2^b)
+class Solution {
+public:
+    vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
+
+        int n = grid.size(), b = grid[0].size();
+
+        map<int, int> pattern2index;
+        for(int i = 0; i < n; i ++){
+
+            int value = 0;
+            for(int j = 0; j < b; j ++)
+                if(grid[i][j]) value += (1 << j);
+
+            if(value == 0) return {{i}};
+
+            auto iter = pattern2index.find(value);
+            if(iter != pattern2index.end()) return {iter->second, i};
+
+            for(int s = 0; s < (1 << b); s ++)
+                if((s & value) == 0) pattern2index[s] = i;
+        }
+        return {};
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -2629,6 +2629,10 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 2726 | JavaScript Problem | - | - | - | - |
 | 2727 | JavaScript Problem | - | - | - | - |
 | 2728 | [Count Houses in a Circular Street](https://leetcode.com/problems/count-houses-in-a-circular-street/description/) | [无] | [C++](2001-2500/2728-Count-Houses-in-a-Circular-Street/cpp-2728/) | | |
+| 2729 | [Check if The Number is Fascinating](https://leetcode.com/problems/check-if-the-number-is-fascinating/) | [无] | [C++](2001-2500/2729-Check-if-The-Number-is-Fascinating/cpp-2729/) | | |
+| 2730 | [Find the Longest Semi-Repetitive Substring](https://leetcode.com/problems/find-the-longest-semi-repetitive-substring/) | [无] | [C++](2001-2500/2730-Find-the-Longest-Semi-Repetitive-Substring/cpp-2730/) | | |
+| 2731 | [Movement of Robots](https://leetcode.com/problems/movement-of-robots/) | [无] | [C++](2001-2500/2731-Movement-of-Robots/cpp-2731/) | | |
+| 2732 | [Find a Good Subset of the Matrix](https://leetcode.com/problems/find-a-good-subset-of-the-matrix/) | [无] | [C++](2001-2500/2732-Find-a-Good-Subset-of-the-Matrix/cpp-2732/) | | |
 | | | | | | |
 | 2737 | [Find the Closest Marked Node](https://leetcode.com/problems/find-the-closest-marked-node/) | [无] | [C++](2001-2500/2737-Find-the-Closest-Marked-Node/cpp-2737/) | | |
 | 2738 | Database Problem: [Link](https://github.com/liuyubobobo/Play-Leetcode-Database/) | - | - | - | - |
