题目：AI处理器组合
知识点：数组
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
某公司研发了一款高性能AI处理器。每台物理设备具备8颗AI处理器，编号分别为0、1、2、3、4、5、6、7。编号0-3的处理器处于同一个链路中，编号4-7的处理器处于另外一个链路中，不通链路中的处理器不能通信，如下图所示。现给定服务器可用的处理器编号数组array，以及任务申请的处理器数量num，找出符合下列亲和性调度原则的芯片组合。如果不存在符合要求的组合，则返回空列表。
亲和性调度原则：
如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。
如果申请处理器个数为2，则选择同一链路剩余可用的处理器数量2个的为最佳，其次是剩余4个，最后是剩余3个。
如果申请处理器个数为4，则必须选择同一链路剩余可用的处理器数量为4个。
如果申请处理器个数为8，则申请节点所有8个处理器。
提示：
1. 任务申请的处理器数量只能是1、2、4、8
2. 编号0-3的处理器处于一个链路，编号4-7的处理器处于另外一个链路。
3. 处理器编号唯一，且不存在相同编号处理器
输入描述：
输入包含可用的处理器编号数组array，以及任务申请的处理器数量num两个部分。
第一行为array，第二行为num。例如：
[0, 1, 4, 5, 6, 7]
1
表示当前编号为0、1、4、5、6、7的处理器可用。任务申请1个处理器。
0<= array.length <= 8
0<= array[i] <= 7
num in [1, 2, 4, 8]
输出描述：
输出为组合列表，当array=[0, 1, 4, 5, 6, 7] ，num=1时，输出为[[0], [1]]
示例1
输入：
[0, 1, 4, 5, 6, 7]
1
输出：
[[0], [1]]
说明：
根据第一条亲和性调度原则，在剩余两个处理器的链路（0,1,2,3）中选择处理器。由于只有0和1可用，则返回任意一颗处理器即可
示例2
输入：
[0, 1, 4, 5, 6, 7]
4
输出：
[[4, 5, 6, 7]]
说明：
根据第三条亲和性调度原则，必须选择同一链路剩余可用的处理器数量为4个的环。
解题思路：
这题主要还是逻辑题。
主要难点是：
需要考虑可用处理器数量的优先级；
需要求出申请处理器的所有可能性。
代码实现：
package com.codernav.demo.hwod.exam;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
/**
* @title AI处理器组合
* @Description 某公司研发了一款高性能AI处理器。
* 每台物理设备具备8颗AI处理器，编号分别为0、1、2、3、4、5、6、7。编号0-3的处理器处于同一个链路中，
* 编号4-7的处理器处于另外一个链路中，不通链路中的处理器不能通信，如下图所示。
* 现给定服务器可用的处理器编号数组array，以及任务申请的处理器数量num，找出符合下列亲和性调度原则的芯片组合。
* 如果不存在符合要求的组合，则返回空列表。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/14
*/
public class Main {
public static List<Integer> first; //第一个链路
public static List<Integer> second; //第二个链路
public static int remainFirst; //第一个链路的可用处理器个数
public static int remainSecond; //第二个链路的可用处理器个数
public static List<List<Integer>> tempLists = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] strings = sc.nextLine().replace("[", "")
.replace("]", "")
.split(",");
int num = sc.nextInt(); //申请处理器的数量
first = new ArrayList<>();
second = new ArrayList<>();
for (String s : strings) {
int i = Integer.parseInt(s.trim());
if (i < 4) {
first.add(i);
} else {
second.add(i);
}
}
remainFirst = first.size();
remainSecond = second.size();
if (num == 1) {
oneCpu();
} else if (num == 2) {
twoCpu();
}
if (num == 4) {
if (remainFirst == 4) {
tempLists.add(Arrays.asList(0, 1, 2, 3));
}
if (remainSecond == 4) {
tempLists.add(Arrays.asList(4, 5, 6, 7));
}
}
if (num == 8) {
if (remainSecond == 4) {
tempLists.add(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7));
}
}
System.out.println(tempLists.size() == 0 ? "[]" : tempLists);
}
/**
* 申请处理器个数为1
* 则选择同一链路，剩余可用的处理器数量为1个的最佳
* 其次是剩余3个的为次佳
* 然后是剩余2个
* 最后是剩余4个
*/
public static void oneCpu() {
List<List<Integer>> lists = new ArrayList<>();
int[] ints = new int[]{1, 3, 2, 4}; //可用处理器数量的优先级
boolean isFit = false; //是否有了满足的链路
for (int i : ints) {
if (i == remainFirst) {
lists.add(first);
isFit = true;
}
if (i == remainSecond) {
lists.add(second);
isFit = true;
}
if (isFit) {
break;
}
}
for (List<Integer> list : lists) {
handle(list, new ArrayList<>(), 0, 1);
}
}
/**
* 申请处理器个数为2
* 则选择同一链路,剩余可用的处理器数量2个的为最佳
* 其次是剩余4个
* 最后是剩余3个
*/
public static void twoCpu() {
List<List<Integer>> lists = new ArrayList<>();
int[] ints = new int[]{2, 4, 3}; //可用处理器数量的优先级
boolean isFit = false; //是否有了满足的链路
for (int i : ints) {
if (i == remainFirst) {
lists.add(first);
isFit = true;
}
if (i == remainSecond) {
lists.add(second);
isFit = true;
}
if (isFit) {
break;
}
}
for (List<Integer> list : lists) {
handle(list, new ArrayList<>(), 0, 2);
}
}
/**
* 申请n个处理器的所有可能性
*
* @param firstOrSecond 选中的链路
* @param list 申请的处理器
* @param index 处理器的索引
* @param n 申请处理器的个数
*/
public static void handle(List<Integer> firstOrSecond, List<Integer> list, int index, int n) {
if (list.size() == n) {
List<Integer> tempList = new ArrayList<>(list);
tempLists.add(tempList);
} else {
for (int i = index; i < firstOrSecond.size(); i++) {
list.add(firstOrSecond.get(i));
handle(firstOrSecond, list, i + 1, n);
list.remove(list.size() - 1);
}
}
}
}
相关文章
