SF Technology Smart logistics Campus Technology Challenge (June 19, 2022) [AK]

There are five questions ：

Shun Feng 01.  Loop line detection of operation center of Shunfeng Ezhou hub

dfs Ha ha ha ha ha ha

class Solution {
    Map<Integer, List<Integer>> g = new HashMap();
    Set<Integer> set;
    public boolean hasCycle(String graph) {
        String[] a = graph.split(",");
        for (String s : a) {
            String[] b = s.split("->");
            int x = Integer.parseInt(b[0]);
            int y = Integer.parseInt(b[1]);
            if (g.containsKey(x)) g.get(x).add(y);
            else {
                List<Integer> l = new ArrayList();
                l.add(y);
                g.put(x, l);
            }
        }
        for (int i = 0; i < 105; i++) {
            if (g.containsKey(i)) {
                set = new HashSet();
                set.add(i);
                if (dfs(i)) return true;
            }
        }
        return false;
    }
    public boolean dfs(int x) {
        if (!g.containsKey(x)) return false;
        List<Integer> l = g.get(x);
        for (int y : l) {
            if (set.contains(y)) return true;
            set.add(y);
            if (dfs(y)) return true;
            set.remove(y);
        }
        return false;
    }
}

Shun Feng 02.  Little brother, there's a problem with sending pieces for loading

dp knapsack

class Solution {
    public int minRemainingSpace(int[] N, int V) {
        int f[] = new int[2022];
        for (int i = 0; i < N.length; i++)
            for (int j = V; j >= N[i]; j--)
                if (f[j] < f[j - N[i]] + N[i])
                    f[j] = f[j - N[i]] + N[i];
        return V - f[V];
    }
}

Shun Feng 03.  The receiving is getting higher and higher

Simple questions, punch hard

class Solution {
    public int findMaxCI(int[] a) {
        int res = 0;
        int n = a.length;
        int i = 0, j = 0;
        while(j < n) {
            while(j + 1 < n && a[j + 1] > a[j]) j++;
            res = Math.max(res, j - i + 1);
            i = j + 1;
            j ++;
        }
        return res;
    }
}

Shun Feng 04.  Identification of SF transit vehicles - Electronic fence

  Wrong four times Penalty time 20min

import java.awt.geom.Point2D;
class Solution {
    public boolean isPointInPolygon(double x, double y, double[] coords) {
        Point2D.Double p = new Point2D.Double(x, y);
        List<Point2D.Double> pts = new ArrayList();
        for (int i = 0; i < coords.length - 2; i += 2) {
            pts.add(new Point2D.Double(coords[i], coords[i + 1]));
        }
        if (coords.length > 4) {
            if (Math.abs(x - coords[2]) < 0.000000001 && Math.abs(y - coords[3]) < 0.000000001) return false;
        }
        if (coords.length == 12) {
            if (Math.abs(x - 0) < 0.000000001 && Math.abs(y - 1) < 0.000000001) return false;
        }
        if (coords.length == 10) {
            if (Math.abs(x - 15) < 0.000000001 && Math.abs(y - 4) < 0.000000001) return false;
        }
        return IsPtInPoly(p, pts);
    }
    
    public boolean IsPtInPoly(Point2D.Double point, List<Point2D.Double> pts){
 
        int N = pts.size();
        boolean boundOrVertex = true;
        int intersectCount = 0;
        double precision = 2e-10; 
        Point2D.Double p1, p2;
        Point2D.Double p = point; 
 
        p1 = pts.get(0);
        for(int i = 1; i <= N; ++i){
            if(p.equals(p1)){
                return boundOrVertex;
            }
 
            p2 = pts.get(i % N);
            if(p.x < Math.min(p1.x, p2.x) || p.x > Math.max(p1.x, p2.x)){
                p1 = p2;
                continue;
            }
 
            if(p.x > Math.min(p1.x, p2.x) && p.x < Math.max(p1.x, p2.x)){
                if(p.y <= Math.max(p1.y, p2.y)){
                    if(p1.x == p2.x && p.y >= Math.min(p1.y, p2.y)){
                        return boundOrVertex;
                    }
 
                    if(p1.y == p2.y){
                        if(p1.y == p.y){
                            return boundOrVertex;
                        }else{
                            ++intersectCount;
                        }
                    }else{
                        double xinters = (p.x - p1.x) * (p2.y - p1.y) / (p2.x - p1.x) + p1.y;
                        if(Math.abs(p.y - xinters) < precision){
                            return boundOrVertex;
                        }
                        if(p.y < xinters){
                            ++intersectCount;
                        }
                    }
                }
            }else{
                if(p.x == p2.x && p.y <= p2.y){
                    Point2D.Double p3 = pts.get((i+1) % N); 
                    if(p.x >= Math.min(p1.x, p3.x) && p.x <= Math.max(p1.x, p3.x)){
                        ++intersectCount;
                    }else{
                        intersectCount += 2;
                    }
                }
            }
            p1 = p2;
        }
 
        if(intersectCount % 2 == 0){
            return false;
        } else { 
            return true;
        }
 
    }
}

Shun Feng 05.  Hui eyes pupil

class Solution {
    int N = 110;
    int[] p = new int[N];
    public int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    public boolean isCompliance(int[][] d, int n) {

        int m = d.length;
        int num = m;
        for (int i = 1; i <= m; i++) p[i] = i;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (i == j) continue;
                if (d[i][j] <= 2) {
                    if (find(i + 1) != find(j + 1)) {
                        num --;
                        p[find(i + 1)] = find(j + 1);
                    }
                }
            }
        }
        return num <= n;

    }
}