杭州华为od

笔试

2026-06-03 20:00 https://blog.csdn.net/banxia_frontend/article/details/160346662

题目描述

实现一段调度模块功能，将一批资源单元划分到两个隔离资源池中；某些资源单元之间存在互斥关系，例如会竞争同一段频谱、同一类加速卡、同一条转发链路，或者在同一资源池内运行会造成调度冲突；现在有多组资源部署任务，其中第组任务中: 有resourceCount个资源单元，资源编号从1 到resourceCount[i]；例如resourceCount[］为4时，表示有4个资源，分别为资源1.2.3,4;·conflicts[］表示第组任务的互斥资源对，不能放入同一个资源池；例如conflicts[i］为［(1.2).(1.3)］时，表示资源1和资源2互斥，资源1和资源3互斥；请你判断每一组资源部署任务是否可以被划分到两个隔离资源池中，使得每一对互斥资源都位于不同资源池。对于每一组任务：．如果可以完成划分，返回1。．如果无法完成划分，返回0。最终返回一个数组，其中第i个值表示第i组任务是否可以被两个资源池完全隔离。

补充说明（约束条件）

1<= resourceCount.length <= 100
1 <= resourceCount[i] <= 104
0 <= conflicts[i].length <= 2∗104
1 <= conflicts[i][x],conflicts[i][y] <= resourceCount[i]
所有 resourceCount[i] 之和不超过 105
所有 conflicts[i].length 之和不超过 2∗105

第1组任务resourceCount[0]=4，表示有1,2,3,4资源，conflicts[0] = [(1, 2), (1, 3), (2, 4)]，表示第1组资源1和2，1和3，2和4两两互斥，第 1 组任务可以划分，例如：资源池 1: [1, 4] 资源池 2: [2, 3]

第 2 组任务无法划分，因为资源1、2、3两两互斥，只用两个资源池无法完成隔离。

第 3 组任务可以划分，例如：资源池 1: [1, 3, 5] 资源池 2: [2, 4]

输入：[4, 3, 5],[[(1, 2), (1, 3), (2, 4)],[(1, 2), (2, 3), (1, 3)],[(1, 2), (3, 4)]] 结果：[1,0,1]

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 判断资源冲突关系是否可以被两个资源池完全隔离。
 * @param resourceCount int整型一维数组 每组任务的资源单元数量
 * @param conflicts Point类二维数组 每组任务的互斥资源对列表，conflicts[i][j].x 和 conflicts[i][j].y 表示第 i 组任务中的一对互斥资源
 * @return int整型一维数组
 */
function canSeparateResources(resourceCount, conflicts) {
  const result = []

  for (let i = 0; i < resourceCount.length; i++) {
    const n = resourceCount[i]
    const edges = conflicts[i]

    // 构建邻接表，资源编号从1开始
    const adj = Array.from({ length: n + 1 }, () => [])
    for (const edge of edges) {
      const u = edge.x
      const v = edge.y
      adj[u].push(v)
      adj[v].push(u)
    }

    // 0: 未染色, 1: 资源池1, 2: 资源池2
    const color = new Array(n + 1).fill(0)
    let isBipartite = true

    // BFS判断二分图
    for (let start = 1; start <= n && isBipartite; start++) {
      if (color[start] === 0) {
        const queue = [start]
        color[start] = 1

        while (queue.length > 0 && isBipartite) {
          const u = queue.shift()
          for (const v of adj[u]) {
            if (color[v] === color[u]) {
              // 相邻节点同色，不是二分图
              isBipartite = false
              break
            }
            if (color[v] === 0) {
              color[v] = 3 - color[u] // 1变2，2变1
              queue.push(v)
            }
          }
        }
      }
    }

    result.push(isBipartite ? 1 : 0)
  }

  return result
}

杭州 华为od ​

笔试 ​

题目描述 ​

杭州华为od

笔试

题目描述