殊途同归

2077. 殊途同归

迷宫由 n 个从 1 到 n 的房间组成，有些房间由走廊连接。给定一个二维整数数组 corridors，其中 corridors[i] = [room1_i, room2_i] 表示有一条走廊连接 room1_i 和room2_i，允许迷宫中的一个人从 room1_i 到 room1_i ，反之亦然。

迷宫的设计者想知道迷宫有多让人困惑。迷宫的 混乱分数 是 长度为 3 的不同的环的数量。

例如, 1 → 2 → 3 → 1 是长度为 3 的环, 但 1 → 2 → 3 → 4 和 1 → 2 → 3 → 2 → 1 不是。

如果在第一个环中访问的一个或多个房间不在第二个环中，则认为两个环是不同的。

返回迷宫的混乱分数。

示例 1:

输入: n = 5, corridors = [[1,2],[5,2],[4,1],[2,4],[3,1],[3,4]]
输出: 2
解释:
一个长度为 3 的环为 4→1→3→4，用红色表示。
注意，这是与 3→4→1→3 或 1→3→4→1 相同的环，因为房间是相同的。
另一个长度为 3 的环为 1→2→4→1，用蓝色表示。
因此，有两个长度为 3 的不同的环。

示例 2:

输入: n = 4, corridors = [[1,2],[3,4]]
输出: 0
解释:
没有长度为 3 的环。

提示:

2 <= n <= 1000
1 <= corridors.length <= 5 * 10⁴
corridors[i].length == 2
1 <= room1_i, room2_i <= n
room1_i != room2_i
没有重复的走廊。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int numberOfPaths(int n, vector<vector<int>>& corridors) { } };

cpp 解法, 执行用时: 96 ms, 内存消耗: 36.2 MB, 提交时间: 2023-10-22 08:33:05

class Solution {
public:
    int numberOfPaths(int n, vector<vector<int>>& corridors) {
        vector<bitset<1010>> e(n);
        for(auto &co:corridors){
            co[0]--,co[1]--;
            e[co[0]][co[1]]=1;
            e[co[1]][co[0]]=1;
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(e[i][j]&&e[j][i]){
                    ans+=(e[i]&e[j]).count();
                }
            }
        }
        return ans/3;
    }
};

python3 解法, 执行用时: 80 ms, 内存消耗: 26.5 MB, 提交时间: 2023-10-22 08:32:47

class Solution:
    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:
        bits = [0] * (n + 1)
        for a, b in corridors:
            if a > b: a, b = b, a
            bits[a] += 1 << b
        return sum((bits[a] & bits[b]).bit_count() for a, b in corridors)

java 解法, 执行用时: 117 ms, 内存消耗: 64.9 MB, 提交时间: 2023-10-22 08:32:28

class Solution {
    public int numberOfPaths(int n, int[][] corridors) {
        boolean[][] arr = new boolean[n][n];
        for(int[] corridor:corridors){
            arr[corridor[0]-1][corridor[1]-1] = true;
            arr[corridor[1]-1][corridor[0]-1] = true;
        }
        int ans = 0;
        for(int[] corridor:corridors){
            //只遍历比边上两点序号都小的第三点以便去重
            for(int i=0;i<Math.min(corridor[0], corridor[1])-1;i++){
                if(arr[corridor[0]-1][i]&&arr[corridor[1]-1][i]){
                    ans++;
                }
            }
        }
        return ans;
    }
}

golang 解法, 执行用时: 232 ms, 内存消耗: 10 MB, 提交时间: 2023-10-22 08:32:10

func numberOfPaths(n int, corridors [][]int) int {
	path := make([]map[int]struct{}, n)
	for _, corridor := range corridors {

		if corridor[0] < corridor[1] {
            if path[corridor[0]-1]==nil{
                path[corridor[0]-1] = map[int]struct{}{}
            }
			path[corridor[0]-1][corridor[1]-1] = struct{}{}
		} else {
            if path[corridor[1]-1]==nil{
                path[corridor[1]-1] = map[int]struct{}{}
            }
			path[corridor[1]-1][corridor[0]-1] = struct{}{}
		}
	}
	ans := 0
	for i := 0; i < n; i++ {
		for j := range path[i] {
			for k := range path[j] {
				if _, ok := path[i][k]; ok {
					ans++
				}
			}
		}
	}
	return ans
}

上一题

下一题

详情