【Day 52 】2022-12-22 - Shortest-Cycle-Containing-Target-Node

[azl397985856]

Shortest-Cycle-Containing-Target-Node

入选理由

暂无

题目地址

https://binarysearch.com/problems/Shortest-Cycle-Containing-Target-Node

前置知识

• BFS

  题目描述

  You are given a two-dimensional list of integers graph representing a directed graph as an adjacency list. You are also given an integer target.

Return the length of a shortest cycle that contains target. If a solution does not exist, return -1.

Constraints

n, m ≤ 250 where n and m are the number of rows and columns in graph

[bookyue]

code

    public int findShortestCircleContainingTarget(List<List<Integer>> graph, int target) {
        Queue<Integer> queue = new ArrayDeque<>();
        Set<Integer> seen = new HashSet<>();
        queue.offer(target);

        int len = 0;
        while (!queue.isEmpty()) {
            len++;
            for (int size = queue.size(); size > 0; size--) {
                var cur = queue.poll();
                seen.add(cur);

                for (var next : graph.get(cur)) {
                    if (!seen.contains(next))
                        queue.offer(next);
                    else if (next == target)
                        return len;
                }
            }
        }

        return -1;
    }

[buer1121]

class Solution: def solve(self, graph, target): q = collections.deque([target]) visited = set() steps = 0 while q: for i in range(len(q)): cur = q.popleft() visited.add(cur) for neighbor in graph[cur]: if neighbor not in visited: q.append(neighbor) elif neighbor == target: return steps + 1 steps += 1 return -1

[Jetery]

import java.util.*;
class Solution {
    public int solve(int[][] graph, int target) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(target);
        int res = 0;
        while(!queue.isEmpty()){
            res++;
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int cur = queue.poll();
                for(int nxt : graph[cur]){
                    if(nxt == target){
                        return res;
                    }
                    if(visited.contains(nxt)){
                        continue;
                    }
                    visited.add(nxt);
                    queue.offer(nxt);
                }
            }
        }
        return -1;
    }
}

[FlipN9]

/**
    BFS     TC: O(V + E)    SC: O(V)
*/
class Solution {
    public int findShortestCycleContainingTargetNode(List<List<Integer>> graph, int target) {
        int N = graph.size();
        Queue<Integer> q = new ArrayDeque<>();
        boolean[] visited = new boolean[N];

        q.offer(target);
        visited[target] = true; 

        int res = 0, step = 0;
        while (!q.isEmpty()) {
            step++;
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int cur = q.poll();
                for (int next : graph.get(cur)) {
                    if (!visited[next]) {
                        q.offer(visited);
                        visited[next] = true;
                    } else if (next == target) {
                        return step;
                    }
                }
            }
        }
        return -1;
    }
}

[yuxiangdev]

class Solution {
    public int solve(int[][] graph, int target) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(target);
        int step = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int neighbor : graph[target]) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                    }
                    if (neighbor == target) {
                        return neighbor;
                    }
                }
            }
            step++;
        }

        return -1;
    }
}

Time O(V+E) Space O(V)

[zywang0]

class Solution {
    public int findShortestCycleContainingTargetNode(List<List<Integer>> graph, int target) {
        int N = graph.size();
        Queue<Integer> q = new ArrayDeque<>();
        boolean[] visited = new boolean[N];

        q.offer(target);
        visited[target] = true; 

        int res = 0, step = 0;
        while (!q.isEmpty()) {
            step++;
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int cur = q.poll();
                for (int next : graph.get(cur)) {
                    if (!visited[next]) {
                        q.offer(visited);
                        visited[next] = true;
                    } else if (next == target) {
                        return step;
                    }
                }
            }
        }
        return -1;
    }
}

[tiandao043]

思路

没看到样例，根据题意trick在从target开始找圈，维护一个visited观察是否访问过，没访问过加入队列，直到再次遇到target。不必正向做，像前两天的题可以从陆地开始拓展。

代码

class Solution:
    def solve(self, graph, target):
        q = collections.deque([target])
        visited = set()
        steps = 0
        while q:
            for i in range(len(q)):
                cur = q.popleft()
                visited.add(cur)
                for neighbor in graph[cur]:
                    if neighbor not in visited:
                        q.append(neighbor)
                    elif neighbor == target:
                        return steps + 1
            steps += 1
        return -1

[RestlessBreeze]

今天leetcode的每日一题

code

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int m = nums.size();
        vector<int> dp(1 << m, 0);
        vector<vector<int>> gcd_tmp(m, vector<int>(m, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                gcd_tmp[i][j] = gcd(nums[i], nums[j]);
            }
        }
        int all = 1 << m;
        for (int s = 1; s < all; ++s) {
            int t = __builtin_popcount(s);
            if (t & 1) {
                continue;
            }
            for (int i = 0; i < m; ++i) {
                if ((s >> i) & 1) {
                    for (int j = i + 1; j < m; ++j) {
                        if ((s >> j) & 1) {
                            dp[s] = max(dp[s], dp[s ^ (1 << i) ^ (1 << j)] + t / 2 * gcd_tmp[i][j]);
                        }
                    }
                }
            }
        }
        return dp[all - 1];
    }
};

[klspta]

class Solution {
    public int maxScore(int[] nums) {
        int n = nums.length;
        int[][] g = new int[n][n];
        // 预计算gcd
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                g[i][j] = gcd(nums[i], nums[j]);
            }
        }

        int[] pos = new int[n];
        int[] DP = new int[1 << n];
        for (int s = 3; s < DP.length; s++) {
            int d = 0;
            for (int i = 0; i < n; i++) {
                if ((s & (1 << i)) != 0) pos[d++] = i;
            }
            if ((d & 1) != 0) continue;

            for (int i = 0; i < d; i++) {
                for (int j = i + 1; j < d ; j++) {
                    int t = (s &~(1<<pos[i])) &~(1<<pos[j]);
                    DP[s] = Math.max(DP[s], (d >> 1) * g[pos[i]][pos[j]] + DP[t]);
                }
            }
        }
        return DP[DP.length - 1];
    }

    private int gcd(int x, int y) {
        if (x == 0) return y;
        if (y == 0) return x;
        return x < y ? gcd(y % x, x) : gcd(x % y, y);
    }
}

[BruceZhang-utf-8]

public int findCircle(List<List> graph, int target) { Queue queue = new ArrayDeque<>(); Set set = new HashSet<>(); queue.offer(target); int length = 0; while (!queue.isEmpty()) { length++; for (int size = queue.size(); size > 0; size--) { var curr = queue.poll(); set.add(curr);

            for (var next : graph.get(curr)) {
                if (!set.contains(next)){
                queue.offer(next);
                }else if (next == target){
                    return length;
                    }
            }
        }
    }

    return -1;
}

[Moin-Jer]

public int findShortestCircleContainingTarget(List<List<Integer>> graph, int target) {
    Queue<Integer> queue = new ArrayDeque<>();
    Set<Integer> seen = new HashSet<>();
    queue.offer(target);

    int len = 0;
    while (!queue.isEmpty()) {
        len++;
        for (int size = queue.size(); size > 0; size--) {
            var cur = queue.poll();
            seen.add(cur);

            for (var next : graph.get(cur)) {
                if (!seen.contains(next))
                    queue.offer(next);
                else if (next == target)
                    return len;
            }
        }
    }

    return -1;
}

[A-pricity]

class Solution:
    def solve(self, graph, target):
        q = collections.deque([target])
        visited = set()
        steps = 0
        while q:
            for i in range(len(q)):
                cur = q.popleft()
                visited.add(cur)
                for neighbor in graph[cur]:
                    if neighbor not in visited:
                        q.append(neighbor)
                    elif neighbor == target:
                        return steps + 1
            steps += 1
        return -1

[paopaohua]

class Solution:
    def solve(self, graph, target):
        q = collections.deque([target])
        visited = set()
        steps = 0
        while q:
            for i in range(len(q)):
                cur = q.popleft()
                visited.add(cur)
                for neighbor in graph[cur]:
                    if neighbor not in visited:
                        q.append(neighbor)
                    elif neighbor == target:
                        return steps + 1
            steps += 1
        return -1

[mayloveless]

参考官方解答

代码

function solve(graph, target){
    const arr = [target];
    const visited = new Set();
    let steps = 0;
    while (arr.length) {
        const value = arr.pop()
        visited.add(value)
        for(let neighbor in graph[value]){
            if (!visited.has(neighbor)) {
                arr.push(neighbor)
            } else if(neighbor === target) {
                return steps + 1 
            }
        }
        steps += 1
    }
    return -1;
}

[luhaoling]

public int findShortestCircleContainingTarget(List<List> graph, int target) { Queue queue = new ArrayDeque<>(); Set seen = new HashSet<>(); queue.offer(target);

int len = 0;
while (!queue.isEmpty()) {
    len++;
    for (int size = queue.size(); size > 0; size--) {
        var cur = queue.poll();
        seen.add(cur);

        for (var next : graph.get(cur)) {
            if (!seen.contains(next))
                queue.offer(next);
            else if (next == target)
                return len;
        }
    }
}

return -1;

}

[chenming-cao]

参考官方解答，BFS

public int findShortestCircleContainingTarget(List<List<Integer>> graph, int target) {
    Queue<Integer> queue = new ArrayDeque<>();
    Set<Integer> seen = new HashSet<>();
    queue.offer(target);

    int len = 0;
    while (!queue.isEmpty()) {
        len++;
        for (int size = queue.size(); size > 0; size--) {
            var cur = queue.poll();
            seen.add(cur);

            for (var next : graph.get(cur)) {
                if (!seen.contains(next))
                    queue.offer(next);
                else if (next == target)
                    return len;
            }
        }
    }

    return -1;
}

[zjsuper]

import collections class Solution(object): def verticalTraversal(self, root): self.seen = defaultdict(lambda :defaultdict(list)) self.dfs(root,0,0) ans = [] print(sorted(self.seen)) print(self.seen) for x in sorted(self.seen): temp = [] for y in sorted(self.seen[x]): temp += sorted(v for v in self.seen[x][y]) ans.append(temp) return ans def dfs(self,root,row,col): if not root: return

    self.seen[col][row].append(root.val)

    self.dfs(root.left,row+1,col-1)
    self.dfs(root.right,row+1,col+1)

[mayloveless]

思路

1298. 你能从盒子里获得的最大糖果数 维护一个box 数组，满足进队列，访问过出队列，暂时无法访问可甩到队尾，如果只有一个也打不开则退出。其余条件翻译题意

代码

var maxCandies = function(status, candies, keys, containedBoxes, initialBoxes) {
    const boxes = initialBoxes;
    let candy = 0;
    const opened = {};
    while (boxes.length) {
        const box = boxes.shift();
        if (!status[box]) {
            if (!boxes.length) break;
            boxes.push(box);
            continue;
        }

        opened[box] = true;
        candy += candies[box];
        if (keys[box].length) {
            keys[box].forEach(key => {
                status[key] = 1;
            })
        }

        const contained = containedBoxes[box];
        contained.forEach(b => {
            if (!opened[b]) {
                boxes.push(b);
            }
        });
    }

    return candy;
};

复杂度

时间：O(n) 空间：O(n)

[snmyj]

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        int sum=0;
        vector<bool> candysigns(candies.size(),1);
        vector<bool> boxsigns(candies.size(),1);
        vector<int> getbox;
        for(int i=0;i<initialBoxes.size();i++){
            int m=initialBoxes[i];
            boxsigns[m]=0;
            if(status[m]==1) {
                sum+=candies[m];
                candysigns[m]=0;
            }
            if(keys[m].size()!=0){
                for(int j=0;j<keys[m].size();m++){
                    if(candysigns[j]!=0) {
                         sum+=candies[j];
                         candysigns[j]=0;
                    }
                }
            }
            if(containedBoxes[m].size()!=0){
                for(int k=0;k<containedBoxes[m].size();k++){
                getbox.push_back(containedBoxes[m][k]);
                if(boxsigns[k]!=0) boxsigns[containedBoxes[m][k]]=1;
            }
        }
        for(int i=0;i<boxsigns.size();i++){
            if(boxsigns[i]==1){
                if(candysigns[i]!=0) sum+=candies[i];
            }
        }
        return sum;
    }
};