2022 sf tech solved.

liuyubobobo · liuyubobobo · commit 282cee5616f4 · 2022-06-23T12:49:03.000-07:00
diff --git a/Others/2022-sf-tech/A/CMakeLists.txt b/Others/2022-sf-tech/A/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(A)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(A main.cpp)
diff --git a/Others/2022-sf-tech/A/main.cpp b/Others/2022-sf-tech/A/main.cpp
@@ -0,0 +1,92 @@
+/// Source : https://leetcode.cn/contest/sf-tech/problems/EUpcmh/
+/// Author : liuyubobobo
+/// Time   : 2022-06-23
+
+#include <iostream>
+#include <vector>
+#include <map>
+#include <set>
+#include <cassert>
+
+using namespace std;
+
+
+/// DFS Cycle Finding
+/// Time Complexity: O(|s| + n)
+/// Space Compelxity: O(n)
+class Solution {
+public:
+    bool hasCycle(string graph) {
+
+        vector<string> edges_str = get_edges_str(graph);
+
+        map<int, set<int>> g;
+        for(const string& edge_str: edges_str){
+            int u, v;
+            get_uv_from_edge_str(edge_str, u, v);
+            g[u].insert(v);
+        }
+
+        set<int> visited;
+        bool has_cycle = false;
+        for(const pair<int, set<int>>& p: g){
+            int u = p.first;
+            if(!visited.count(u)){
+                set<int> stack;
+                has_cycle = dfs(g, u, stack, visited);
+                if(has_cycle) break;
+            }
+        }
+        return has_cycle;
+    }
+
+private:
+    bool dfs(const map<int, set<int>>& g, int u, set<int>& stack, set<int>& visited){
+
+        stack.insert(u);
+        if(g.count(u)){
+            for(int v: g.at(u)){
+                if(stack.count(v)) return true;
+                if(!visited.count(v) && dfs(g, v, stack, visited)) return true;
+            }
+        }
+        stack.erase(u);
+        return false;
+    }
+
+    void get_uv_from_edge_str(const string& e, int& u, int& v){
+
+        int arrow_pos = e.find("->");
+        assert(arrow_pos != string::npos);
+
+        u = atoi(e.substr(0, arrow_pos).c_str());
+        v = atoi(e.substr(arrow_pos + 2).c_str());
+    }
+
+    vector<string> get_edges_str(const string& g){
+
+        vector<string> res;
+        for(int start = 0, i = 1; i <= g.size(); i ++)
+            if(i == g.size() || g[i] == ','){
+                res.push_back(g.substr(start, i - start));
+                start = i + 1;
+                i = start + 1;
+            }
+        return res;
+    }
+};
+
+
+int main() {
+
+    cout << Solution().hasCycle("1->2,2->3,3->1") << '\n';
+    // 1
+
+    cout << Solution().hasCycle("1->4,2->5,3->6,3->7,4->8,5->8,5->9,6->9,6->11,7->11,8->12,9->12,9->13,10->13,10->14,11->10,11->14") << '\n';
+    // 0
+
+    cout << Solution().hasCycle("1->4,2->5,3->6,3->7,4->8,5->8,5->9,6->9,6->11,7->11,8->12,9->12,9->13,10->6,10->13,10->14,11->10,11->14") << '\n';
+    // 1
+
+    return 0;
+}
diff --git a/Others/2022-sf-tech/B/CMakeLists.txt b/Others/2022-sf-tech/B/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(B)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(B main.cpp)
diff --git a/Others/2022-sf-tech/B/main.cpp b/Others/2022-sf-tech/B/main.cpp
@@ -0,0 +1,37 @@
+/// Source : https://leetcode.cn/contest/sf-tech/problems/cINqyA/
+/// Author : liuyubobobo
+/// Time   : 2022-06-23
+
+#include <iostream>
+#include <vector>
+#include <cassert>
+
+using namespace std;
+
+
+/// Backpack DP
+/// Time complexity: O(C * n)
+/// Space Complexity: O(C)
+class Solution {
+public:
+    int minRemainingSpace(vector<int>& V, int C) {
+
+        vector<bool> dp(C + 1, false);
+        dp[0] = true;
+        for(int v: V){
+            for(int c = C; c >= v; c --)
+                if(dp[c - v]) dp[c] = true;
+        }
+
+        for(int i = C; i >= 0; i --)
+            if(dp[i]) return C - i;
+        assert(false);
+        return -1;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/Others/2022-sf-tech/B/main2.cpp b/Others/2022-sf-tech/B/main2.cpp
@@ -0,0 +1,52 @@
+/// Source : https://leetcode.cn/contest/sf-tech/problems/cINqyA/
+/// Author : liuyubobobo
+/// Time   : 2022-06-23
+
+#include <iostream>
+#include <vector>
+#include <set>
+
+using namespace std;
+
+
+/// Meet in the middle
+/// Time complexity: O(n * 2^(n / 2))
+/// Space Complexity: O(2^(n/2))
+class Solution {
+public:
+    int minRemainingSpace(vector<int>& V, int C) {
+
+        int n = V.size();
+        if(n == 1) return max(C - V[0], 0);
+
+        int left_n = n / 2, right_n = n - left_n;
+        vector<int> left(1 << left_n, 0), right(1 << right_n, 0);
+        for(int state = 1; state < (1 << left_n); state ++){
+            int p = __builtin_ffs(state) - 1;
+            left[state] = left[state - (1 << p)] + V[p];
+        }
+        for(int state = 1; state < (1 << right_n); state ++){
+            int p = __builtin_ffs(state) - 1;
+            right[state] = right[state - (1 << p)] + V[left_n + p];
+        }
+
+        set<int> left_set(left.begin(), left.end());
+        set<int> right_set(right.begin(), right.end());
+
+        int res = C;
+        for(int e1: left){
+            if(e1 > C) break;
+            auto iter = right_set.upper_bound(C - e1);
+            iter --;
+            res = min(res, C - e1 - *iter);
+        }
+
+        return res;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/Others/2022-sf-tech/C/CMakeLists.txt b/Others/2022-sf-tech/C/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(C)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(C main.cpp)
diff --git a/Others/2022-sf-tech/C/main.cpp b/Others/2022-sf-tech/C/main.cpp
@@ -0,0 +1,34 @@
+/// Source : https://leetcode.cn/contest/sf-tech/problems/8oimK4/
+/// Author : liuyubobobo
+/// Time   : 2022-06-23
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Linear Scan
+/// Time Compelxity: O(n)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    int findMaxCI(vector<int>& nums) {
+
+        int n = nums.size();
+        int res = 0;
+        for(int start = 0, i = 1; i <= n; i ++)
+            if(i == n || nums[i] <= nums[i - 1]){
+                res = max(res, i - start);
+                start = i;
+                i = start;
+            }
+        return res;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/Others/2022-sf-tech/D/CMakeLists.txt b/Others/2022-sf-tech/D/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(D)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(D main.cpp)
diff --git a/Others/2022-sf-tech/D/main.cpp b/Others/2022-sf-tech/D/main.cpp
@@ -0,0 +1,116 @@
+/// Source : https://leetcode.cn/contest/sf-tech/problems/uWWzsv/
+/// Author : liuyubobobo
+/// Time   : 2022-06-23
+
+#include <iostream>
+#include <vector>
+#include <complex>
+
+#define X real()
+#define Y imag()
+
+using namespace std;
+
+
+typedef double C;
+typedef complex<C> P;
+
+const double EPS = 1e-6;
+
+/// Cross Product
+/// Time Complexity: O(t)
+/// Space Complexity: O(1)
+C cross_product(P a, P b){
+    return (conj(a) * b).Y; // a.X * b.Y - b.X * a.Y
+}
+
+bool is_zero(C x){
+    return abs(x) < EPS;
+}
+// 1  : left
+// 0  : touch
+// -1 : right
+int test_point_loc(P p, P s1, P s2){
+    C res = cross_product(p - s1, p - s2);
+    if(is_zero(res)) return 0;
+    return res > 0 ? 1 : -1;
+}
+
+// 0  : on boundary
+// 1  : intersection
+// -1 : no intersection
+int intersect(P p1, P p2, P p3, P p4){
+
+    C x1 = p1.X, y1 = p1.Y, x2 = p2.X, y2 = p2.Y, x3 = p3.X, y3 = p3.Y, x4 = p4.X, y4 = p4.Y;
+
+    int loc1 = test_point_loc(p1, p3, p4), loc2 = test_point_loc(p2, p3, p4);
+    int loc3 = test_point_loc(p3, p1, p2), loc4 = test_point_loc(p4, p1, p2);
+
+    if(loc1 == 0 && min(x3, x4) <= x1 && x1 <= max(x3, x4)
+       && min(y3, y4) <= y1 && y1 <= max(y3, y4)) return 0;
+
+    if(loc2 == 0 && min(x3, x4) <= x2 && x2 <= max(x3, x4)
+       && min(y3, y4) <= y2 && y2 <= max(y3, y4)) return 0;
+
+    if(loc3 == 0 && min(x1, x2) <= x3 && x3 <= max(x1, x2)
+       && min(y1, y2) <= y3 && y3 <= max(y1, y2)) return 0;
+
+    if(loc4 == 0 && min(x1, x2) <= x4 && x4 <= max(x1, x2)
+       && min(y1, y2) <= y4 && y4 <= max(y1, y2)) return 0;
+
+    if(!loc1 || !loc2 || !loc3 || !loc4) return -1;
+
+    if(loc1 * loc2 > 0 || loc3 * loc4 > 0) return -1;
+    return 1;
+}
+
+//long long gcd(long long a, long long b)
+//{
+//    if(a > b) swap(a, b);
+//    if (a == 0) return b;
+//    return gcd(b % a, a);
+//}
+
+int in_polygon(int n, const vector<P>& polygon, P p){
+
+    for(int i = 1; i < n; i ++){
+        int loc = test_point_loc(p, polygon[i], polygon[i - 1]);
+        if(loc == 0 && min(polygon[i].X, polygon[i - 1].X) <= p.X && p.X <= max(polygon[i].X, polygon[i - 1].X)
+           && min(polygon[i].Y, polygon[i - 1].Y) <= p.Y && p.Y <= max(polygon[i].Y, polygon[i - 1].Y))
+            return 0;
+    }
+
+    int loc = test_point_loc(p, polygon[n - 1], polygon[0]);
+    if(loc == 0 && min(polygon[n - 1].X, polygon[0].X) <= p.X && p.X <= max(polygon[n - 1].X, polygon[0].X)
+       && min(polygon[n - 1].Y, polygon[0].Y) <= p.Y && p.Y <= max(polygon[n - 1].Y, polygon[0].Y))
+        return 0;
+
+    // 保证 p2.X - p1.X 和 p2.Y - p1.Y 互质，
+    double INF = 1e9 + 7;
+
+    P p1 = p, p2 = {p.X + INF, p.Y + 1};
+    int cnt = 0;
+    for(int i = 1; i < n; i ++)
+        cnt += intersect(p1, p2, polygon[i], polygon[i - 1]) >= 0;
+    cnt += intersect(p1, p2, polygon[n - 1], polygon[0]) >= 0;
+
+    return (cnt & 1) ? -1 : 1;
+}
+
+class Solution {
+public:
+    bool isPointInPolygon(double x, double y, vector<double>& coords) {
+
+        vector<P> polygon;
+        for(int i = 0; i < coords.size(); i += 2)
+            polygon.push_back({coords[i], coords[i + 1]});
+
+        P p = {x, y};
+        return in_polygon(polygon.size(), polygon, p) < 0;
+    }
+};
+
+int main() {
+
+    return 0;
+}
diff --git a/Others/2022-sf-tech/E/CMakeLists.txt b/Others/2022-sf-tech/E/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(E)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(E main.cpp)
diff --git a/Others/2022-sf-tech/E/main.cpp b/Others/2022-sf-tech/E/main.cpp
diff --git a/readme.md b/readme.md
