2022.09.23.-秋招-第一题-最佳检测顺序

TaZi SU @ 8 months ago

题目思路

这道题目要求对云存储系统中的服务节点进行排序，以便在检测服务状态时，能够优先检测对业务影响较大的节点。具体来说，影响力大的节点是指当该节点发生故障时，会影响更多依赖它的其他节点。为了实现这一目标，我们需要计算每个节点的影响力，即该节点及其所有后继节点的数量。然后，根据影响力对节点进行排序，影响力大的节点排在前面；如果影响力相同，则按节点编号的升序排列。

1. 依赖关系的表示 首先，我们需要理解服务节点之间的依赖关系。题目中指出，每个节点最多只依赖一个其他节点，并且依赖关系不成环。因此，整个系统的依赖关系可以表示为一组树结构或森林结构，每棵树的根节点是没有依赖的节点（f[i] = -1）。

2. 计算每个节点的影响力 影响力大的节点意味着该节点所在的子树规模大，即该节点及其所有后继节点的数量较多。因此，我们可以通过**深度优先搜索（DFS）**遍历每棵树，计算每个节点的子树大小。

具体步骤：

1.构建树结构： 使用一个数组fa[]表示每个节点的父节点。使用邻接表e[]来存储每个节点的子节点。

2.深度优先搜索（DFS）： 从每棵树的根节点开始，递归计算每个节点的子树大小cnt[]。 cnt[i]表示节点i及其所有后继节点的总数量。

3. 排序节点 计算完每个节点的影响力后，我们需要根据以下规则对节点进行排序：

按影响力降序排列：影响力大的节点排在前面。按节点编号升序排列：如果两个节点的影响力相同，则编号小的节点排在前面。

4. 输出排序结果 根据排序后的节点顺序输出节点编号，即为检测节点的优先顺序。

5. 时间复杂度分析 构建树结构：遍历所有节点，时间复杂度为O(n)。 DFS计算子树大小：每个节点只被访问一次，时间复杂度为O(n)。排序：使用快速排序或其他高效排序算法，时间复杂度为O(n log n)。总体时间复杂度：O(n log n)，适用于n最多为100,000的情况。

类似题目推荐

本质就是考察了一下dfs和自定义排序。较为经典。

LeetCode

CodeFun2000

1.P1224 携程 2023.04.15-春招-第三题-魔法之树

2.P1196 华为实习 2023-04-19-第二题-塔子哥出城

3.P1159. 2022年清华大学(深圳)保研夏令营机试题-第一题-树上计数

4.P1190 华为实习 2023.04.12-第二题-获取最多食物

5.P1044. 拼多多内推笔试-2023.2.22.投喂珍珠

更多请见:知识点分类-训练-深度优先搜索专栏

代码

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int fa[N];				//节点i的父节点
vector<int> e[N];		//节点i的子节点
int cnt[N];				//节点i的子树中的节点个数
int dfs(int s)		//计算s的 子树中的节点个数
{
	cnt[s] = 1;		//s本身
	for(int g: e[s])	//遍历s的每个子节点
	{
		cnt[s] += dfs(g);	//递归计算每个子节点的子树的节点个数，然后加到s上
	}
	return cnt[s];		//返回s的子树的节点个数
}
int ans[N];
bool cmp(int &x, int &y) {		//重写排序函数，按照子树中节点个数排序，相等时按大小排序
	if(cnt[x] == cnt[y]) return x < y;
	return cnt[x] > cnt[y];
}
int main()
{
	cin >> n;
	for(int i = 0 ; i < n ; i++) {
		cin >> fa[i];		//输入i的父节点
		if(fa[i] != -1) {		//-1代表i没有父节点，此时i为一棵树的根节点
			e[fa[i]].push_back(i);	//添加到父节点的子节点集合中
		}
	}
	for(int i = 0 ; i < n ; i++) {
		ans[i] = i;		//顺便初始化一下排序的值
		if(fa[i] == -1)	//i为一棵树的根节点，从这个点开始遍历
            dfs(i);
	}
	sort(ans, ans+n, cmp);	//排序
	for(int i = 0 ; i < n ; i ++) {
		cout << ans[i] << " \n"[i+1==n];	//输出，" \n"[i+1==n]代表最后一次输出回车，前面输出空格分割
	}
}

python

from collections import defaultdict
n = int(input())
e = defaultdict(list)
a = list(map(int,input().split()))
# 读入 + 存图
for i in range(n):
	if a[i] != -1:
		e[a[i]].append(i)
# cnt 子树大小
cnt = [0] * n
# dfs 求子树大小
def dfs(u):
	cnt[u] = 1
	for v in e[u]:
		dfs(v)
		cnt[u] += cnt[v]
# 按题目要求排序
res = []
for i in range(n):
	if cnt[i] == 0:
		dfs(i)
	res.append([i , cnt[i]])
res.sort(key = lambda x : (-x[1] , x[0]))
print(" ".join(map(str,[x[0] for x in res])))

Java

import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int N = 100010;
    static int n;
    static Map<Integer, List<Integer>> graph = new HashMap<>();
    static boolean[] visited = new boolean[N];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for(int i = 0; i < N; i++){
            graph.put(i, new ArrayList<>());
        }
        // 读入,存图
        for(int i = 0; i < n; i++){
            int temp = in.nextInt();
            if(temp != -1){
                add(temp, i);
            }
        }
        // dfs 求后继结点个数 , 以二元组形式存储，以便之后的自定义排序
        List<int[]> res = new ArrayList<>();
        for(int i = 0; i < n; i++){
            res.add(new int[]{dfs(i), i});
        }
        // 自定义排序
        Collections.sort(res, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                // 根据题解,优先按后继结点个数降序排序
                if (a[0] != b[0]) {
                    return b[0] - a[0];
                } else { // 相同情况下 按节点编号升序排序
                    return Integer.compare(a[1], b[1]);
                }
            }
        });
        // 输出答案
        for(int[] pair : res){
            System.out.print(pair[1] + " ");
        }
    }
    // 计算后继节点个数
    private static int dfs(int i){
        int count = 0;
        for(int j : graph.get(i)){
            count += dfs(j);
        }
        return count+1;
    }
    private static void add(int a, int b){
        graph.get(a).add(b);
    }
}
// bt  guanam

Go

package main

import (
	"fmt"
	"sort"
)

const N int = 1e5 + 10

var f []int = make([]int, N)
var n int

type node struct {
	id     int
	sonCnt int
}

func dfs(edges [][]int, x int) int {
	if len(edges[x]) == 0 {
		return 1
	}
	res := 1
	for _, v := range edges[x] {
		res += dfs(edges, v)
	}
	return res
}

func main() {
	//构建有向图 计算每个节点的子节点个数 排序
	fmt.Scan(&n)
	//有向图的邻接边
	edges := make([][]int, n)
	for i := range edges {
		edges[i] = make([]int, 0)
	}
	outDegree := make([]int, n) //每个节点的出度
	for i := 0; i < n; i++ {
		fmt.Scan(&f[i])
		if f[i] != -1 {
			edges[f[i]] = append(edges[f[i]], i)
			outDegree[f[i]]++
		}
	}
	cnt := make([]int, n)
	for i := 0; i < n; i++ {
		if outDegree[i] == 0 { //如果出度为0 子节点就只算它自己
			cnt[i] = 1
		} else { //出度不为0 dfs它的所有直接子节点 更新它的总子节点个数
			cnt[i] = dfs(edges, i)
		}
	}
	nodes := make([]node, n)
	for i := 0; i < n; i++ {
		nodes[i].id = i
		nodes[i].sonCnt = cnt[i]
	}
	sort.Slice(nodes, func(i, j int) bool {
		if nodes[i].sonCnt != nodes[j].sonCnt { //子节点数量不同时 按照子节点数量降序排列
			return nodes[i].sonCnt > nodes[j].sonCnt
		}
		return nodes[i].id < nodes[j].id //相同时 按照编号升序排列
	})
	for i := 0; i < n; i++ {
		fmt.Printf("%d", nodes[i].id)
		if i != n-1 {
			fmt.Printf(" ")
		}
	}
}
// by xchen

Js

// 创建 readline interface 实例
const rl = require('readline').createInterface({input: process.stdin});

// 获取 readline 迭代器
const iter = rl[Symbol.asyncIterator]();

// 定义异步函数，并使用 IIFE 函数立即执行
void async function () {
    // 读取第一行输入，n 代表节点个数
    const n = parseInt(await readline());

    // 读取第二行输入，F 代表以空格分隔的每个节点的父节点编号
    const F = (await readline()).split(' ').map(item => parseInt(item));

    // 创建 Map，存放每个节点的父节点后继位置的数组
    const map = new Map();

    // 定义数组存放每个节点所对应的后继结点个数
    const count = [];

    // 遍历每个节点，判断其父节点是否存在，如果存在，则将该节点下标加入其对应的数组中，否则跳过
    for (let i = 0; i < n; i++) {
        if (F[i] !== -1) {
            if (map.has(F[i])) {
                map.set(F[i], [...map.get(F[i]), i]);   // 将该节点下标 push 进去其父节点后继位置的数组中
            }
            else {
                map.set(F[i], [i]);    // 新建一个数组，存放当前节点下标，指定其为其父节点的后继位置
            }
        }
    }

    // 定义深度优先遍历函数，参数分别为 map 和 currV，返回值为当前节点的后继结点个数
    const dfs = (map, currV) => {
        if (!map.has(currV) || map.get(currV) === 0) {   // 当前节点不存在或其没有后继结点，返回 1

            return 1;
        }
        let res = 1;   // res 表示当前节点及其后继结点的总个数
        const edge = map.get(currV);   // 获取当前节点的后继位置数组
        for (let V of edge) {
            res += dfs(map, V);   // 递归计算每个后继结点的后继结点总个数，并将结果加到 res 上
        }
        return res;   // 返回当前节点及其后继结点的总个数
    }

    // 定义二维数组 comp 存放每个节点的下标和其所对应的后继结点个数
    const comp = new Array(n).fill(0).map(item => new Array(2).fill(0));
    const res = [];

    // 遍历每个节点，计算其所对应的后继结点总数并存入 comp 中
    for (let i = 0; i < n; i++) {
        comp[i][0] = i;   // 第一列存放节点下标
        comp[i][1] = dfs(map, i);   // 第二列存放节点的后继结点总个数
    }

    // 对二维数组 comp 进行排序，先按第二列倒序排序，之后按第一列顺序排序
    comp.sort((a, b) => {
        if (a[1] === b[1]) {
            return a[0] - b[0];
        }
        else {
            return b[1] - a[1];
        }
    })

    // 将排序后的节点下标存入 res 数组中
    for (let pair of comp) {
        res.push(pair[0])
    }

    // 输出 res 数组中的元素，以空格分隔
    console.log(res.join(' '))
}()

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

# Submissions

220

Accepted

Uploaded By

TaZi

1 solutions

题目思路

类似题目推荐

LeetCode

CodeFun2000

代码

CPP

python

Java

Go

Js

Information

Status

Development

Support