Leet Code Weekly Contest 284

1. Find All K-Distant Indices in an Array

$O(n^2)$ brute-force is enough.

c++

class Solution
{
public:

    vector<int> findKDistantIndices(vector<int>& nums, int key, int k)
    {
        int n = nums.size();
        vector<int> ans;
        
        for (int i = 0; i < n; i++)
        {
            bool found = false;
            
            for (int j = 0; j < n; j++)
            {
                if (nums[j] == key && abs(i - j) <= k)
                {
                    found = true;
                }
            }
            
            if (found)
            {
                ans.push_back(i);
            }
        }
        
        return ans;
    }
};

2. Count Artifacts That Can Be Extracted

Take a hash-map for excavating positions.
And brute-force for each artifact.

c++

class Solution
{
public:
    
    int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig)
    {
        set<pair<int, int>> D;
        
        for (auto &d : dig)
        {
            D.insert(make_pair(d[0], d[1]));
        }
        
        int ans = 0;
        
        for (auto &a : artifacts)
        {
            bool found = true;
            
            for (int r = a[0]; r <= a[2]; r++)
            {
                for (int c = a[1]; c <= a[3]; c++)
                {
                    if (D.find(make_pair(r, c)) == D.end())
                    {
                        found = false;
                    }
                }
            }
            
            if (found)
            {
                ans++;
            }
        }
        
        return ans;
    }
};

3. Maximize the Topmost Element After K Moves

Consider how you can make the i-th element the top-most after exactly $k$ $k$ moves:
- Assume there are $a = i$ elements before and $b = n - i - 1$ elements after the current one.
- Remove the first $a$ elements and repeat removing and putting back the current one ( $k = a + 2p$ , $p \geq 0$ ).
- Remove the first $a + 1$ elements and randomly do any operations and then put the current one back ( $k = a + 2$ ).

c++

class Solution
{
public:

    int maximumTop(vector<int>& nums, int k)
    {
        int ans = INT_MIN, n = nums.size();
        
        for (int i = 0; i < n; i++)
        {
            int a = i, b = n - i - 1;
            
            bool valid = false;
            
            if (k == a)
            {
                valid = true;
            }
            
            if ((k > a) && (k - a) % 2 == 0)
            {
                valid = true;
            }
            
            if ((a + b) > 0 && (k >= a + 2))
            {
                valid = true;
            }
            
            if (valid)
            {
                ans = max(ans, nums[i]);
            }
        }
        
        return ans == INT_MIN ? -1 : ans;
    }
};

4. Minimum Weighted Subgraph With the Required Paths

Then two paths may share some edges.
Assume the last node of the shared path is $x$ .
The answer should be $dis(src1, x) + dis(src2, x) + dis(x, dest)$ .
Build graph and mirror-graph.
SPFA.

c++

typedef long long ll;

const ll INF = 10000000001;

struct Edge
{
    ll src, tgt, dis;
    
    Edge(ll _src, ll _tgt, ll _dis)
    {
        src = _src;
        tgt = _tgt;
        dis = _dis;
    }
};

class SPFA
{
    private:
        ll n;
        vector<vector<Edge>> edges;
    
    public:
        SPFA(ll _n)
        {
            n = _n;
            edges = vector<vector<Edge>>(_n);
        }
    
        void add(int s, int t, int dis)
        {
            edges[s].push_back(Edge(s, t, dis));
        }
    
        vector<ll> solve(ll s)
        {
            vector<ll> dis(n, INF);
            vector<bool> vis(n, false);
            
            queue<ll> que;
            que.push(s);
            
            dis[s] = 0;
            vis[s] = true;
            
            while (!que.empty())
            {
                ll x = que.front(); que.pop();
                vis[x] = false;
                
                for (auto &e : edges[x])
                {
                    int y = e.tgt;
                    
                    if (dis[x] + e.dis < dis[y])
                    {
                        dis[y] = dis[x] + e.dis;
                        
                        if (!vis[y])
                        {
                            que.push(y);
                            vis[y] = true;
                        }
                    }
                }
            }
            
            return dis;
        }
};

class Solution
{
public:
    
    long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest)
    {
        SPFA F(n), R(n);
        
        for (auto &e : edges)
        {
            F.add(e[0], e[1], e[2]);
            R.add(e[1], e[0], e[2]);
        }
        
        vector<ll> a = F.solve(src1);
        vector<ll> b = F.solve(src2);
        vector<ll> c = R.solve(dest);
        
        ll ans = INF;
        
        for (int i = 0; i < n; i++)
        {
            ans = min(ans, a[i] + b[i] + c[i]);
        }
        
        return ans == INF ? -1 : ans;
    }
};

Leet Code Weekly Contest 284

1. Find All K-Distant Indices in an Array

2. Count Artifacts That Can Be Extracted

3. Maximize the Topmost Element After K Moves

4. Minimum Weighted Subgraph With the Required Paths

COMMAND INTERFACE

:help aguang.xyz