SF smart logistics Campus Technology Challenge (no T4)

SF smart logistics campus technology challenge （ nothing t4）

Loop line detection of operation center of Shunfeng Ezhou hub - Power button (LeetCode) competition

【 background 】

Ezhou Huahu airport is the first in Asia 、 The world's fourth professional freight hub airport .2016 year 4 It was officially approved by the Civil Aviation Administration of China ,2017 year 12 month 20 The Japanese hub project officially started ,2022 year 3 month 19 Boeing is used by SF airlines in Japan B757-200F The test flight of the F-type all cargo aircraft was successful , It is the first time that China has completed the test flight of the new airport with an all cargo aircraft .
Shunfeng Ezhou hub transfer center covers an area of about one million square meters , Realize the unloading of express from （ unloading / Unloader ） To sorting and then loading / Fully automatic punching . The total length of automatic equipment transportation line is more than tens of kilometers . How to ensure the express to arrive at the loading or punching port most efficiently is the core problem to be solved .
The automatic equipment in the transfer center is connected through the transportation line , Form a three-dimensional connected network , When the express arrives at the diversion intersection, it needs to make a decision on the branch road , On the premise of ensuring the best route in the whole journey , At the same time, it is necessary to avoid congestion caused by a large number of express mails rushing to the shortest line , It is also necessary to avoid the faulty equipment on the faulty line in time , Until the fault is repaired .
The simplified diagram of automatic transportation line is as follows ：

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-cGS5Wk2t-1655727366330)(https://pic.leetcode-cn.com/1652078050-dkDCol- Probe customers - Directed graph (6)].png)

The unloading port represents the starting node of Express Travel , The loading port represents the final destination node after the express travels through the route , The node represents the diversion or confluence point of the route from the unloading port to the loading port , Unloading port and loading port are also special nodes .
The edge represents the automatic equipment transportation line between two adjacent nodes , The line represents from the starting node to the destination node （ Loading port ） Through all sides .
There should be no ring circuit on the whole connected network , The circular route may cause the express to be transported on the transportation line for a long time , So that I miss the flight or vehicle , Cause delay . Therefore, ring should be avoided when establishing the line data model .

【 problem 】

Please help detect whether there is a circular path on the line .

Example 1：

Input ：
"1->2,2->3,3->1"

Output ：
true

Tips :

• 0 < Number of nodes < 100

Problem analysis

The amount of data is pitifully small .

After recording all the paths , Start at each point dfs, If at one time dfs If you can reach a point twice, it means that there is a path .

AC Code

class Solution {
public:
    unordered_map<int,vector<int>>mymap;
    unordered_map<int,int>cnt;
    bool dfs(int x)
    {
        if(cnt[x]==1)return true;
        cnt[x]=1;
        for(auto i:mymap[x])
        {
            if(dfs(i))return true;
        }
        cnt[x]=0;
        return false;
    }
    bool hasCycle(string graph) {
        int n=graph.size();
        
        for(int i=0;i<n;i++)
        {
            int a=0,b=0;
            while(i<n&&graph[i]>='0'&&graph[i]<='9')
            {
                a*=10;
                a+=(graph[i]-'0');
                i++;
            }
            i+=2;
            while(i<n&&graph[i]>='0'&&graph[i]<='9')
            {
                b*=10;
                b+=(graph[i]-'0');
                i++;
            }
            mymap[a].push_back(b);
        }
        bool flag=false;
        for(int i=1;i<=100;i++)
        {
            if(dfs(i))return true;
        }
        return false;
    }
};

Little brother, there's a problem with sending pieces for loading - Power button (LeetCode) competition

problem

The express boy needs to pick up pieces every day and send express by battery car , Suppose the capacity of the battery car express box is V, I need to deliver n A courier , Each express has a certain size .
It is required to be delivered in the n Express delivery , Pick up any number of express packages and put them into the express box , Do not overflow , Minimize the remaining space of the express box .

Input ：

• n An express volume array :N[],
• Battery car express box capacity :V

return ：

• Try to fill up the express , The minimum remaining capacity of the express box

Example 1

Input ：N = [8, 1, 12, 7, 9, 7], V = 11
Output ：1
explain ： Capacity of express box V by 11, Item volume array N by [8, 1, 12, 7, 9, 7], The optimal solution is to take the volume as
1 The express delivery and volume of 9 Express delivery of , That is, the minimum remaining space of the express box is 11-(1+9)=1

Tips

• 0 < N.length ≤ 30
• 0 < N[i] < 2000
• V Integers ：0 ≤ V ≤ 2000

Problem analysis

01 Knapsack template questions , First find the volume V The most cargo you can take , Finally, return to the backpack volume V The difference with the goods taken is ok .

AC Code

class Solution {
public:
    int minRemainingSpace(vector<int>& N, int V) {
        int n=N.size();
        vector<int>f(V+1);
        for(int i=0;i<n;i++)
        {
            for(int j=V;j>=N[i];j--)
            {
                f[j]=max(f[j],f[j-N[i]]+N[i]);
            }
        }
        return V-f[V];
    }
};

The receiving is getting higher and higher - Power button (LeetCode) competition

background
Summer is coming , It's getting hotter and hotter , It's very hard for SF to receive and send express . To encourage you , We have set up various prize contests . Among them, there is a competition called "getting higher and higher" , The competition compares the number of days that the number of pieces received by the younger brother increases continuously , The larger the number of consecutive days, the higher the ranking .

problem
There are many young brothers , Please help design an algorithm that can quickly calculate the maximum number of consecutive days for my brother's daily receipt .
Input : One dimensional array nums[n]
Output : Continuously increasing the length of days

Example ：

 Input ：[54,42,62,75,82,86,86]
 Output ：5
 explain :
 The little elder brother A The number of receipts in the last week is ：54,42,62,75,82,86,86, So little brother A The maximum number of consecutive days of daily receipts in this week is 5
-  The little elder brother A At the end of the week 2 From day to day 6 The number of daily receipts is increasing 
-  The first 7 Day and day 6 The number of pieces received per day is the same , Not counting growth 

Tips ：

• 0 <= nums.length < 200000

Problem analysis

use dp[i] To i Days of continuous growth , Judge whether the current element is larger than the previous element , If it is greater than :dp[i]=dp[i-1]+1, If not equal to :dp[i]=1; Maintain the maximum value in this process .

AC Code

class Solution {
public:
    int findMaxCI(vector<int>& nums) {
        int n=nums.size();
        vector<int>f(n,1);
        int res=1;
        for(int i=1;i<n;i++)
        {
            if(nums[i]>nums[i-1])f[i]+=f[i-1];
            res=max(f[i],res);
        }
        return res;
    }
};

Identification of SF transit vehicles - Electronic fence - Power button (LeetCode) competition

Is to judge whether a point is in a polygon , A lot of searches on the Internet

Hui eyes pupil - Power button (LeetCode) competition

【 background 】

" Hui eyes pupil " The platform can monitor the image by analyzing the camera , Automatically identify whether the site image meets the standards 、 Whether the tool is fixed and positioned 、 Fire warning 、 Burglar alarm 、 Intrusion warning of abnormal personnel .
For the sake of operation and maintenance , The site is required to manage the cameras in groups , Each group has a special leader responsible for management .

【 problem 】

Suppose the platform deploys a set of distance cameras distance, Arrange for the site n Person in charge , among :
distance[i][j] Indicates that the camera i And cameras j Distance between , If distance[i][j]<=2 M means they belong to the same group .

Please design an algorithm to determine whether the site can be managed by at least one person in charge of each group of cameras .
Input : Collection of distances between camera deployments m*m Two dimensional array of distance[m][m], Number of people n
Output ： Whether the required results are met :true/false

Example 1：
Suppose there are three cameras 1,2,3

 Input ：distance=[[0,1,3], [1,0,3], [3,3,0]], n = 2
 Output ：true
 explain ：
distance： Collection of distances between camera deployments , camera id= Indexes i+1;
distance=[
 [0,1,3], =>  camera id1(i=0) Go to the camera id1、2、3（j=0,1,2） Distance of ：id1->id1: 0 rice ;id1->id2: 1 rice ;id1->id3: 3 rice 
 [1,0,3], =>  camera id2(i=1) Go to the camera id1、2、3（j=0,1,2） Distance of ：id2->id1: 1 rice ;id2->id2: 0 rice ;id2->id3: 3 rice 
 [3,3,0]] =>  camera id3(i=2) Go to the camera id1、2、3（j=0,1,2） Distance of ：id3->id1: 3 rice ;id3->id2: 1 rice ;id3->id3: 3 rice 
n： Number of persons in charge 
 camera 1 And 2 The distance to 1, camera 1 And 3 The distance to 3, camera 2 And 3 The distance to 3, So the camera 1 and 2 For a group , camera 3 Work in your own group , Altogether 2 Group Cameras ,2<=n, Therefore, it can meet the requirement that at least one person in charge of each group is responsible for management .

Problem analysis

dfs Or directly go up and look up the set , Make all paths less than or equal to 2 All of them are regarded as a connected block , Just see how many connecting blocks there are .

I use dfs, Start at each point dfs, The path distance traversed each time is less than or equal to 2 All points are marked , Start at one point each time dfs Then the counter ++, If this starting point is before dfs If you encounter it, don't do it dfs. Finally, return to the counter .

AC Code

class Solution {
public:
    unordered_map<int,int>mymap;
    void dfs(int x,vector<vector<int>>& distance)
    {
        if(mymap[x]==1)return ;
        mymap[x]=1;
        int n=distance[x-1].size();
        for(int i=0;i<n;i++)
        {
            if(distance[x-1][i]<=2)
                dfs(i+1,distance);
        }
    }
    bool isCompliance(vector<vector<int>>& distance, int n) {
        int len=distance.size(),res=0;
        for(int i=0;i<len;i++)
        {
            if(mymap[i+1]==0)
            {
                res++;
                dfs(i+1,distance);
            }
        }
        return res<=n;
    }
};