【华为OD-E卷-AI处理器组合100分（python、java、c++、js、c）】
【华为OD-E卷-AI处理器组合100分（python、java、c++、js、c）】
题目
某公司研发了一款高性能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、2、4、8。 编号0-3的处理器处于一个链路，编号4-7的处理器处于另外一个链路。 处理器编号唯一，且不存在相同编号处理器。
输入描述
- 输入包含可用的处理器编号数组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]]。
用例
用例一：
输入：
[0, 1, 4, 5, 6, 7]
1
输出：
[[0], [1]]
用例二：
输入：
[0, 1, 4, 5, 6, 7]
4
输出：
[[4, 5, 6, 7]]
说明
根据第三条亲和性调度原则，必须选择同一链路剩余可用的处理器数量为4个的环
python解法
- 解题思路：
- 这个问题是关于处理一个数组 arr，并根据给定的数字 num 对该数组进行不同方式的调度。调度的方式依赖于以下几个步骤：
初始化与分组：首先将输入数组 arr 排序，然后将数组中的元素分成两个子列表 link1 和 link2，其中 link1 包含所有小于4的元素，link2 包含所有大于等于4的元素。
调度规则：根据输入的 num 值，决定如何处理这两个子列表：
num = 1：选择长度为 1、2、3 或 4 的组合进行调度。
num = 2：选择长度为 2、3 或 4 的组合进行调度。
num = 4：只调度长度为 4 的子列表。
num = 8：如果 link1 和 link2 都有长度为 4 的元素，将它们合并并进行调度。
深度优先搜索（DFS）：使用递归的 DFS 方法来枚举 link1 和 link2 中所有可能的子集组合，根据 num 的值来决定每次深度遍历的层数。每次递归都会生成不同长度的组合，并最终返回所有可能的调度结果。
class ProcessorScheduler:
def __init__(self, arr, num):
# 初始化，arr是输入的数组，num是调度的规则
self.arr = sorted(arr) # 排序输入数组
self.num = num # 设定调度规则
self.link1 = [] # 小于4的元素
self.link2 = [] # 大于等于4的元素
self.result = [] # 存储调度结果
def split_links(self):
# 根据元素大小将arr分成两个子列表
for e in self.arr:
if e < 4:
self.link1.append(e)
else:
self.link2.append(e)
def schedule(self):
# 根据num值来选择调度方式
self.split_links() # 先分组
len1 = len(self.link1)
len2 = len(self.link2)
if self.num == 1:
self._schedule_one(len1, len2)
elif self.num == 2:
self._schedule_two(len1, len2)
elif self.num == 4:
self._schedule_four(len1, len2)
elif self.num == 8:
self._schedule_eight(len1, len2)
return self.result
def _schedule_one(self, len1, len2):
# 处理num为1的情况，根据长度分别递归调度
if len1 == 1 or len2 == 1:
if len1 == 1:
self._dfs(self.link1, 1)
if len2 == 1:
self._dfs(self.link2, 1)
elif len1 == 3 or len2 == 3:
if len1 == 3:
self._dfs(self.link1, 1)
if len2 == 3:
self._dfs(self.link2, 1)
elif len1 == 2 or len2 == 2:
if len1 == 2:
self._dfs(self.link1, 1)
if len2 == 2:
self._dfs(self.link2, 1)
elif len1 == 4 or len2 == 4:
if len1 == 4:
self._dfs(self.link1, 1)
if len2 == 4:
self._dfs(self.link2, 1)
def _schedule_two(self, len1, len2):
# 处理num为2的情况，根据长度分别递归调度
if len1 == 2 or len2 == 2:
if len1 == 2:
self._dfs(self.link1, 2)
if len2 == 2:
self._dfs(self.link2, 2)
elif len1 == 4 or len2 == 4:
if len1 == 4:
self._dfs(self.link1, 2)
if len2 == 4:
self._dfs(self.link2, 2)
elif len1 == 3 or len2 == 3:
if len1 == 3:
self._dfs(self.link1, 2)
if len2 == 3:
self._dfs(self.link2, 2)
def _schedule_four(self, len1, len2):
# 处理num为4的情况，只调度长度为4的子列表
if len1 == 4:
self.result.append(self.link1)
if len2 == 4:
self.result.append(self.link2)
def _schedule_eight(self, len1, len2):
# 处理num为8的情况，如果link1和link2都有长度为4的元素，合并调度
if len1 == 4 and len2 == 4:
self.result.append(self.link1 + self.link2)
def _dfs(self, arr, level):
# 通过深度优先搜索枚举所有可能的组合
path = []
self._dfs_helper(arr, 0, level, path)
def _dfs_helper(self, arr, index, level, path):
# 递归函数，生成长度为level的子集
if len(path) == level:
self.result.append(path[:]) # 如果路径长度符合条件，保存该组合
return
for i in range(index, len(arr)):
path.append(arr[i]) # 选择当前元素
self._dfs_helper(arr, i + 1, level, path) # 递归选择下一个元素
path.pop() # 回溯，移除当前元素
if __name__ == "__main__":
arr = eval(input()) # 输入数组
num = int(input()) # 输入调度规则
scheduler = ProcessorScheduler(arr, num)
print(scheduler.schedule()) # 输出调度结果
java解法
- 解题思路
- 该题目要求根据给定的数组和一个调度级别 num，从数组中生成符合条件的组合。具体而言，数组中的元素根据大小被分为两组：link1（包含小于 4 的元素）和 link2（包含大于等于 4 的元素）。根据不同的调度级别 num，选择合适的组合方式：
调度级别为 1 或 2：
从 link1 和 link2 中分别生成大小为 num 的所有组合。
调度级别为 4：
如果 link1 或 link2 中有正好 4 个元素，将其加入结果。
调度级别为 8：
如果 link1 和 link2 都有 4 个元素，则将两者合并，并将合并后的结果加入到结果中。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入数组并将其转换为 Integer 数组
Integer[] arr = Arrays.stream(sc.nextLine().split("[\\[\\]\\,\\s]"))
.filter(str -> !"".equals(str)) // 去除空字符串
.map(Integer::parseInt) // 转换为整数
.toArray(Integer[]::new); // 转换为 Integer 数组
// 读取调度级别 num
int num = sc.nextInt();
// 调用 findProcessorCombinations 方法计算并打印结果
System.out.println(findProcessorCombinations(arr, num));
}
// 主计算方法：根据调度级别生成符合条件的组合
public static List<List<Integer>> findProcessorCombinations(Integer[] arr, int num) {
List<List<Integer>> result = new ArrayList<>(); // 存储最终结果
List<Integer> link1 = new ArrayList<>(); // 存储小于4的元素
List<Integer> link2 = new ArrayList<>(); // 存储大于等于4的元素
// 遍历数组，将元素根据大小分配到 link1 或 link2 中
for (int p : arr) {
if (p < 4) {
link1.add(p); // 小于4的元素加入 link1
} else {
link2.add(p); // 大于等于4的元素加入 link2
}
}
// 根据调度级别调用不同的生成组合的方法
if (num == 1 || num == 2) {
findCombinations(link1, num, result); // 从 link1 中找大小为 num 的组合
findCombinations(link2, num, result); // 从 link2 中找大小为 num 的组合
} else if (num == 4) {
// 如果 link1 或 link2 有正好 4 个元素，将其加入结果
if (link1.size() == 4) result.add(new ArrayList<>(link1));
if (link2.size() == 4) result.add(new ArrayList<>(link2));
} else if (num == 8 && link1.size() == 4 && link2.size() == 4) {
// 如果 link1 和 link2 都有 4 个元素，合并它们
List<Integer> combined = new ArrayList<>(link1);
combined.addAll(link2);
result.add(combined);
}
return result; // 返回最终的组合结果
}
// 找到从 link 中选取 num 个元素的所有组合
private static void findCombinations(List<Integer> link, int num, List<List<Integer>> result) {
if (link.size() >= num) {
// 如果 link 中的元素数量大于或等于 num，调用回溯算法生成所有组合
backtrack(link, new ArrayList<>(), 0, num, result);
}
}
// 回溯算法：生成所有符合条件的组合
private static void backtrack(List<Integer> link, List<Integer> current, int start, int num, List<List<Integer>> result) {
if (current.size() == num) {
// 如果当前组合的大小等于 num，将其加入结果
result.add(new ArrayList<>(current));
return;
}
// 遍历 link 中的元素，生成组合
for (int i = start; i < link.size(); i++) {
current.add(link.get(i)); // 将当前元素加入组合
backtrack(link, current, i + 1, num, result); // 递归生成剩余的组合
current.remove(current.size() - 1); // 回溯，移除最后一个元素
}
}
}
C++解法
- 解题思路
更新中
C解法
更新中
JS解法
更新中
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
题目整理、思路解题不易，如对您有帮助，欢迎点赞/收藏 O(∩_∩)O