当前位置： 首页 > article >正文

【2024年华为OD机试】(A卷,100分)- 处理器问题（Java JS PythonC/C++）

article 2025/1/13 20:23:11

在这里插入图片描述

一、问题描述

题目描述

某公司研发了一款高性能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, 2, 3）中选择处理器。

由于只有0和1可用，则返回任意一颗处理器即可。

输入

[0, 1, 4, 5, 6, 7]
4

输出

[[4, 5, 6, 7]]

说明

根据第三条亲和性调度原则，必须选择同一链路剩余可用的处理器数量为4个的环

题目解析

用例中，链路link1=[0,1]，链路link2=[4,5,6,7]

现在要选1个处理器，则需要按照亲和性调度原则

如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。

最佳的是，找剩余可用1个处理器的链路，发现没有，link1剩余可用2，link2剩余可用4

其次的是，找剩余可用3个处理器的链路，发现没有

再次的是，找剩余可用2个处理器的链路，link1符合要求，即从0和1处理器中任选一个，有两种选择，可以使用dfs找对应组合。

二、JavaScript算法源码

以下是 JavaScript 代码的中文详细注释和逻辑讲解：

代码逻辑

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

// 创建 readline 接口，用于从控制台读取输入
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

// 存储输入的行数据
const lines = [];

// 监听输入事件
rl.on("line", (line) => {
  lines.push(line); // 将输入的行数据存入 lines 数组

  // 当输入的行数达到 2 行时，开始处理数据
  if (lines.length === 2) {
    const arr = JSON.parse(lines[0]); // 解析第一行输入为数组
    const num = lines[1]; // 获取第二行输入的数字

    // 调用算法函数并输出结果
    console.log(getResult(arr, num));

    // 清空 lines 数组，准备接收下一组输入
    lines.length = 0;
  }
});

// 算法入口
function getResult(arr, num) {
  const link1 = []; // 存储小于 4 的元素
  const link2 = []; // 存储大于等于 4 的元素

  // 将数组排序并分为两组
  arr
    .sort((a, b) => a - b) // 升序排序
    .forEach((e) => {
      e < 4 ? link1.push(e) : link2.push(e); // 根据元素大小分组
    });

  const ans = []; // 存储最终结果
  const len1 = link1.length; // link1 的长度
  const len2 = link2.length; // link2 的长度

  // 根据输入的数字 num 执行不同的逻辑
  switch (num) {
    case "1":
      // 如果 link1 或 link2 的长度为 1，调用 dfs 函数
      if (len1 === 1 || len2 === 1) {
        if (len1 === 1) dfs(link1, 0, 1, [], ans);
        if (len2 === 1) dfs(link2, 0, 1, [], ans);
      }
      // 如果 link1 或 link2 的长度为 3，调用 dfs 函数
      else if (len1 === 3 || len2 === 3) {
        if (len1 === 3) dfs(link1, 0, 1, [], ans);
        if (len2 === 3) dfs(link2, 0, 1, [], ans);
      }
      // 如果 link1 或 link2 的长度为 2，调用 dfs 函数
      else if (len1 === 2 || len2 === 2) {
        if (len1 === 2) dfs(link1, 0, 1, [], ans);
        if (len2 === 2) dfs(link2, 0, 1, [], ans);
      }
      // 如果 link1 或 link2 的长度为 4，调用 dfs 函数
      else if (len1 === 4 || len2 === 4) {
        if (len1 === 4) dfs(link1, 0, 1, [], ans);
        if (len2 === 4) dfs(link2, 0, 1, [], ans);
      }
      break;

    case "2":
      // 如果 link1 或 link2 的长度为 2，调用 dfs 函数
      if (len1 === 2 || len2 === 2) {
        if (len1 === 2) dfs(link1, 0, 2, [], ans);
        if (len2 === 2) dfs(link2, 0, 2, [], ans);
      }
      // 如果 link1 或 link2 的长度为 4，调用 dfs 函数
      else if (len1 === 4 || len2 === 4) {
        if (len1 === 4) dfs(link1, 0, 2, [], ans);
        if (len2 === 4) dfs(link2, 0, 2, [], ans);
      }
      // 如果 link1 或 link2 的长度为 3，调用 dfs 函数
      else if (len1 === 3 || len2 === 3) {
        if (len1 === 3) dfs(link1, 0, 2, [], ans);
        if (len2 === 3) dfs(link2, 0, 2, [], ans);
      }
      break;

    case "4":
      // 如果 link1 或 link2 的长度为 4，直接将整个数组加入结果
      if (len1 === 4 || len2 === 4) {
        if (len1 === 4) ans.push(link1);
        if (len2 === 4) ans.push(link2);
      }
      break;

    case "8":
      // 如果 link1 和 link2 的长度都为 4，将两个数组合并后加入结果
      if (len1 === 4 && len2 === 4) {
        ans.push([...link1, ...link2]);
      }
      break;
  }

  // 将结果数组转换为字符串，并用逗号分隔
  return JSON.stringify(ans).split(",").join(", ");
}

// 深度优先搜索（DFS）函数
function dfs(arr, index, level, path, res) {
  // 如果当前路径的长度等于目标长度，将路径加入结果
  if (path.length === level) {
    return res.push([...path]);
  }

  // 遍历数组，递归生成组合
  for (let i = index; i < arr.length; i++) {
    path.push(arr[i]); // 将当前元素加入路径
    dfs(arr, i + 1, level, path, res); // 递归调用
    path.pop(); // 回溯，移除当前元素
  }
}

代码讲解

  1. 输入处理：

    • 使用 readline 模块从控制台读取输入。
    • 将输入的行数据存入 lines 数组。
    • 当输入的行数达到 2 行时，解析第一行为数组 arr，第二行为字符串 num。

  2. 数据分组：

    • 将数组 arr 排序并分为两组：
      • link1：存储小于 4 的元素。
      • link2：存储大于等于 4 的元素。

  3. 逻辑分支：

    • 根据输入的数字 num，执行不同的逻辑：
      • num === "1"：处理长度为 1、2、3、4 的情况，调用 dfs 函数生成组合。
      • num === "2"：处理长度为 2、3、4 的情况，调用 dfs 函数生成组合。
      • num === "4"：处理长度为 4 的情况，直接将整个数组加入结果。
      • num === "8"：处理 link1 和 link2 长度都为 4 的情况，将两个数组合并后加入结果。

  4. 深度优先搜索（DFS）：

    • dfs 函数用于生成指定长度的组合。
    • 通过递归和回溯，生成所有可能的组合，并将结果存入 res 数组。

  5. 结果输出：

    • 将结果数组 ans 转换为字符串，并用逗号分隔后返回。

示例解析

输入
[1, 2, 3, 4, 5, 6, 7, 8]
"2"
运行结果
[[1, 2], [1, 3], [2, 3], [4, 5], [4, 6], [5, 6]]
  • 解析：
    • 输入数组 [1, 2, 3, 4, 5, 6, 7, 8] 被分为 link1 = [1, 2, 3] 和 link2 = [4, 5, 6, 7, 8]。
    • 输入 num = "2"，表示需要生成长度为 2 的组合。
    • 最终结果为 link1 和 link2 中长度为 2 的所有组合。

总结

  • 该代码通过分组和深度优先搜索（DFS），实现了根据输入条件生成指定长度的组合。
  • 适用于需要处理分组和组合问题的场景，尤其是需要根据条件动态生成结果的场景。

如果有其他问题，欢迎随时提问！

三、Java算法源码

以下是 Java 代码的中文详细注释和逻辑讲解：

代码逻辑

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Main {
  public static void main(String[] args) {
    // 创建 Scanner 对象，用于从控制台读取输入
    Scanner sc = new Scanner(System.in);

    // 读取输入的第一行，解析为整数数组
    Integer[] arr =
        Arrays.stream(sc.nextLine().split("[\\[\\]\\,\\s]")) // 使用正则表达式分割输入
            .filter(str -> !"".equals(str)) // 过滤空字符串
            .map(Integer::parseInt) // 将字符串转换为整数
            .toArray(Integer[]::new); // 转换为 Integer 数组

    // 读取输入的第二行，作为条件参数
    String num = sc.next();

    // 调用算法函数并输出结果
    System.out.println(getResult(arr, num));
  }

  // 算法入口
  public static String getResult(Integer[] arr, String num) {
    // 定义两个列表，分别存储小于 4 和大于等于 4 的元素
    ArrayList<Integer> link1 = new ArrayList<>();
    ArrayList<Integer> link2 = new ArrayList<>();

    // 对数组进行排序
    Arrays.sort(arr, (a, b) -> a - b);

    // 遍历数组，将元素分为两组
    for (Integer e : arr) {
      if (e < 4) {
        link1.add(e); // 小于 4 的元素加入 link1
      } else {
        link2.add(e); // 大于等于 4 的元素加入 link2
      }
    }

    // 存储最终结果的列表
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();

    // 获取 link1 和 link2 的长度
    int len1 = link1.size();
    int len2 = link2.size();

    // 根据输入的条件 num 执行不同的逻辑
    switch (num) {
      case "1":
        // 如果 link1 或 link2 的长度为 1，调用 dfs 函数
        if (len1 == 1 || len2 == 1) {
          if (len1 == 1) dfs(link1, 0, 1, new ArrayList<>(), ans);
          if (len2 == 1) dfs(link2, 0, 1, new ArrayList<>(), ans);
        }
        // 如果 link1 或 link2 的长度为 3，调用 dfs 函数
        else if (len1 == 3 || len2 == 3) {
          if (len1 == 3) dfs(link1, 0, 1, new ArrayList<>(), ans);
          if (len2 == 3) dfs(link2, 0, 1, new ArrayList<>(), ans);
        }
        // 如果 link1 或 link2 的长度为 2，调用 dfs 函数
        else if (len1 == 2 || len2 == 2) {
          if (len1 == 2) dfs(link1, 0, 1, new ArrayList<>(), ans);
          if (len2 == 2) dfs(link2, 0, 1, new ArrayList<>(), ans);
        }
        // 如果 link1 或 link2 的长度为 4，调用 dfs 函数
        else if (len1 == 4 || len2 == 4) {
          if (len1 == 4) dfs(link1, 0, 1, new ArrayList<>(), ans);
          if (len2 == 4) dfs(link2, 0, 1, new ArrayList<>(), ans);
        }
        break;

      case "2":
        // 如果 link1 或 link2 的长度为 2，调用 dfs 函数
        if (len1 == 2 || len2 == 2) {
          if (len1 == 2) dfs(link1, 0, 2, new ArrayList<>(), ans);
          if (len2 == 2) dfs(link2, 0, 2, new ArrayList<>(), ans);
        }
        // 如果 link1 或 link2 的长度为 4，调用 dfs 函数
        else if (len1 == 4 || len2 == 4) {
          if (len1 == 4) dfs(link1, 0, 2, new ArrayList<>(), ans);
          if (len2 == 4) dfs(link2, 0, 2, new ArrayList<>(), ans);
        }
        // 如果 link1 或 link2 的长度为 3，调用 dfs 函数
        else if (len1 == 3 || len2 == 3) {
          if (len1 == 3) dfs(link1, 0, 2, new ArrayList<>(), ans);
          if (len2 == 3) dfs(link2, 0, 2, new ArrayList<>(), ans);
        }
        break;

      case "4":
        // 如果 link1 或 link2 的长度为 4，直接将整个列表加入结果
        if (len1 == 4 || len2 == 4) {
          if (len1 == 4) ans.add(link1);
          if (len2 == 4) ans.add(link2);
        }
        break;

      case "8":
        // 如果 link1 和 link2 的长度都为 4，将两个列表合并后加入结果
        if (len1 == 4 && len2 == 4) {
          ans.add(
              Stream.concat(link1.stream(), link2.stream())
                  .collect(Collectors.toCollection(ArrayList<Integer>::new)));
        }
        break;
    }

    // 将结果列表转换为字符串并返回
    return ans.toString();
  }

  // 深度优先搜索（DFS）函数
  public static void dfs(
      ArrayList<Integer> arr, // 当前处理的列表
      int index, // 当前处理的起始索引
      int level, // 目标组合的长度
      ArrayList<Integer> path, // 当前路径
      ArrayList<ArrayList<Integer>> res // 结果列表
      ) {
    // 如果当前路径的长度等于目标长度，将路径加入结果
    if (path.size() == level) {
      res.add(new ArrayList<>(path));
      return;
    }

    // 遍历数组，递归生成组合
    for (int i = index; i < arr.size(); i++) {
      path.add(arr.get(i)); // 将当前元素加入路径
      dfs(arr, i + 1, level, path, res); // 递归调用
      path.remove(path.size() - 1); // 回溯，移除当前元素
    }
  }
}

代码讲解

  1. 输入处理：

    • 使用 Scanner 从控制台读取输入。
    • 第一行输入解析为整数数组 arr，使用正则表达式 [\\[\\]\\,\\s] 分割输入字符串，并过滤空字符串。
    • 第二行输入作为条件参数 num。

  2. 数据分组：

    • 将数组 arr 排序并分为两组：
      • link1：存储小于 4 的元素。
      • link2：存储大于等于 4 的元素。

  3. 逻辑分支：

    • 根据输入的条件 num，执行不同的逻辑：
      • num == "1"：处理长度为 1、2、3、4 的情况，调用 dfs 函数生成组合。
      • num == "2"：处理长度为 2、3、4 的情况，调用 dfs 函数生成组合。
      • num == "4"：处理长度为 4 的情况，直接将整个列表加入结果。
      • num == "8"：处理 link1 和 link2 长度都为 4 的情况，将两个列表合并后加入结果。

  4. 深度优先搜索（DFS）：

    • dfs 函数用于生成指定长度的组合。
    • 通过递归和回溯，生成所有可能的组合，并将结果存入 res 列表。

  5. 结果输出：

    • 将结果列表 ans 转换为字符串并返回。

示例解析

输入
[1, 2, 3, 4, 5, 6, 7, 8]
"2"
运行结果
[[1, 2], [1, 3], [2, 3], [4, 5], [4, 6], [5, 6]]
  • 解析：
    • 输入数组 [1, 2, 3, 4, 5, 6, 7, 8] 被分为 link1 = [1, 2, 3] 和 link2 = [4, 5, 6, 7, 8]。
    • 输入 num = "2"，表示需要生成长度为 2 的组合。
    • 最终结果为 link1 和 link2 中长度为 2 的所有组合。

总结

  • 该代码通过分组和深度优先搜索（DFS），实现了根据输入条件生成指定长度的组合。
  • 适用于需要处理分组和组合问题的场景，尤其是需要根据条件动态生成结果的场景。

如果有其他问题，欢迎随时提问！

四、Python算法源码

以下是 Python 代码的中文详细注释和逻辑讲解：

代码逻辑

# 输入获取
arr = eval(input())  # 读取输入的第一行，解析为列表
num = int(input())   # 读取输入的第二行，作为条件参数


# 算法入口
def getResult(arr, num):
    # 定义两个列表，分别存储小于 4 和大于等于 4 的元素
    link1 = []
    link2 = []

    # 对数组进行排序
    arr.sort()

    # 遍历数组，将元素分为两组
    for e in arr:
        if e < 4:
            link1.append(e)  # 小于 4 的元素加入 link1
        else:
            link2.append(e)  # 大于等于 4 的元素加入 link2

    # 存储最终结果的列表
    ans = []

    # 获取 link1 和 link2 的长度
    len1 = len(link1)
    len2 = len(link2)

    # 根据输入的条件 num 执行不同的逻辑
    if num == 1:
        # 如果 link1 或 link2 的长度为 1，调用 dfs 函数
        if len1 == 1 or len2 == 1:
            if len1 == 1:
                dfs(link1, 0, 1, [], ans)
            if len2 == 1:
                dfs(link2, 0, 1, [], ans)
        # 如果 link1 或 link2 的长度为 3，调用 dfs 函数
        elif len1 == 3 or len2 == 3:
            if len1 == 3:
                dfs(link1, 0, 1, [], ans)
            if len2 == 3:
                dfs(link2, 0, 1, [], ans)
        # 如果 link1 或 link2 的长度为 2，调用 dfs 函数
        elif len1 == 2 or len2 == 2:
            if len1 == 2:
                dfs(link1, 0, 1, [], ans)
            if len2 == 2:
                dfs(link2, 0, 1, [], ans)
        # 如果 link1 或 link2 的长度为 4，调用 dfs 函数
        elif len1 == 4 or len2 == 4:
            if len1 == 4:
                dfs(link1, 0, 1, [], ans)
            if len2 == 4:
                dfs(link2, 0, 1, [], ans)
    elif num == 2:
        # 如果 link1 或 link2 的长度为 2，调用 dfs 函数
        if len1 == 2 or len2 == 2:
            if len1 == 2:
                dfs(link1, 0, 2, [], ans)
            if len2 == 2:
                dfs(link2, 0, 2, [], ans)
        # 如果 link1 或 link2 的长度为 4，调用 dfs 函数
        elif len1 == 4 or len2 == 4:
            if len1 == 4:
                dfs(link1, 0, 2, [], ans)
            if len2 == 4:
                dfs(link2, 0, 2, [], ans)
        # 如果 link1 或 link2 的长度为 3，调用 dfs 函数
        elif len1 == 3 or len2 == 3:
            if len1 == 3:
                dfs(link1, 0, 2, [], ans)
            if len2 == 3:
                dfs(link2, 0, 2, [], ans)
    elif num == 4:
        # 如果 link1 或 link2 的长度为 4，直接将整个列表加入结果
        if len1 == 4 or len2 == 4:
            if len1 == 4:
                ans.append(link1)
            if len2 == 4:
                ans.append(link2)
    elif num == 8:
        # 如果 link1 和 link2 的长度都为 4，将两个列表合并后加入结果
        if len1 == 4 and len2 == 4:
            tmp = []
            tmp.extend(link1)
            tmp.extend(link2)
            ans.append(tmp)

    # 返回结果列表
    return ans


# 深度优先搜索（DFS）函数
def dfs(arr, index, level, path, res):
    # 如果当前路径的长度等于目标长度，将路径加入结果
    if len(path) == level:
        res.append(path[:])  # 使用 path[:] 创建 path 的副本
        return

    # 遍历数组，递归生成组合
    for i in range(index, len(arr)):
        path.append(arr[i])  # 将当前元素加入路径
        dfs(arr, i + 1, level, path, res)  # 递归调用
        path.pop()  # 回溯，移除当前元素


# 算法调用
print(getResult(arr, num))

代码讲解

  1. 输入处理：

    • 使用 input() 函数读取输入。
    • 第一行输入通过 eval() 解析为列表 arr。
    • 第二行输入作为条件参数 num。

  2. 数据分组：

    • 将数组 arr 排序并分为两组：
      • link1：存储小于 4 的元素。
      • link2：存储大于等于 4 的元素。

  3. 逻辑分支：

    • 根据输入的条件 num，执行不同的逻辑：
      • num == 1：处理长度为 1、2、3、4 的情况，调用 dfs 函数生成组合。
      • num == 2：处理长度为 2、3、4 的情况，调用 dfs 函数生成组合。
      • num == 4：处理长度为 4 的情况，直接将整个列表加入结果。
      • num == 8：处理 link1 和 link2 长度都为 4 的情况，将两个列表合并后加入结果。

  4. 深度优先搜索（DFS）：

    • dfs 函数用于生成指定长度的组合。
    • 通过递归和回溯，生成所有可能的组合，并将结果存入 res 列表。

  5. 结果输出：

    • 将结果列表 ans 返回并打印。

示例解析

输入
[1, 2, 3, 4, 5, 6, 7, 8]
2
运行结果
[[1, 2], [1, 3], [2, 3], [4, 5], [4, 6], [5, 6]]
  • 解析：
    • 输入数组 [1, 2, 3, 4, 5, 6, 7, 8] 被分为 link1 = [1, 2, 3] 和 link2 = [4, 5, 6, 7, 8]。
    • 输入 num = 2，表示需要生成长度为 2 的组合。
    • 最终结果为 link1 和 link2 中长度为 2 的所有组合。

总结

  • 该代码通过分组和深度优先搜索（DFS），实现了根据输入条件生成指定长度的组合。
  • 适用于需要处理分组和组合问题的场景，尤其是需要根据条件动态生成结果的场景。

如果有其他问题，欢迎随时提问！

五、C/C++算法源码：

以下是 C++ 代码的中文详细注释和逻辑讲解：

代码逻辑

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <sstream>
#include <iterator>
using namespace std;

// 输入获取
vector<int> arr; // 存储输入数组
int num;         // 存储输入的条件参数

// 算法入口
vector<vector<int>> getResult(const vector<int>& arr, int num) {
    // 定义两个列表，分别存储小于 4 和大于等于 4 的元素
    vector<int> link1, link2;

    // 遍历数组，将元素分为两组
    for (int e : arr) {
        if (e < 4) {
            link1.push_back(e); // 小于 4 的元素加入 link1
        } else {
            link2.push_back(e); // 大于等于 4 的元素加入 link2
        }
    }

    // 存储最终结果的列表
    vector<vector<int>> ans;

    // 获取 link1 和 link2 的长度
    int len1 = link1.size();
    int len2 = link2.size();

    // 根据输入的条件 num 执行不同的逻辑
    if (num == 1) {
        // 如果 link1 或 link2 的长度为 1，调用 dfs 函数
        if (len1 == 1) dfs(link1, 0, 1, {}, ans);
        if (len2 == 1) dfs(link2, 0, 1, {}, ans);
        // 如果 link1 或 link2 的长度为 3，调用 dfs 函数
        if (len1 == 3) dfs(link1, 0, 1, {}, ans);
        if (len2 == 3) dfs(link2, 0, 1, {}, ans);
        // 如果 link1 或 link2 的长度为 2，调用 dfs 函数
        if (len1 == 2) dfs(link1, 0, 1, {}, ans);
        if (len2 == 2) dfs(link2, 0, 1, {}, ans);
        // 如果 link1 或 link2 的长度为 4，调用 dfs 函数
        if (len1 == 4) dfs(link1, 0, 1, {}, ans);
        if (len2 == 4) dfs(link2, 0, 1, {}, ans);
    } else if (num == 2) {
        // 如果 link1 或 link2 的长度为 2，调用 dfs 函数
        if (len1 == 2) dfs(link1, 0, 2, {}, ans);
        if (len2 == 2) dfs(link2, 0, 2, {}, ans);
        // 如果 link1 或 link2 的长度为 4，调用 dfs 函数
        if (len1 == 4) dfs(link1, 0, 2, {}, ans);
        if (len2 == 4) dfs(link2, 0, 2, {}, ans);
        // 如果 link1 或 link2 的长度为 3，调用 dfs 函数
        if (len1 == 3) dfs(link1, 0, 2, {}, ans);
        if (len2 == 3) dfs(link2, 0, 2, {}, ans);
    } else if (num == 4) {
        // 如果 link1 或 link2 的长度为 4，直接将整个列表加入结果
        if (len1 == 4) ans.push_back(link1);
        if (len2 == 4) ans.push_back(link2);
    } else if (num == 8) {
        // 如果 link1 和 link2 的长度都为 4，将两个列表合并后加入结果
        if (len1 == 4 && len2 == 4) {
            vector<int> tmp;
            tmp.insert(tmp.end(), link1.begin(), link1.end());
            tmp.insert(tmp.end(), link2.begin(), link2.end());
            ans.push_back(tmp);
        }
    }

    // 去重处理
    set<vector<int>> uniqueAns;
    for (const auto& vec : ans) {
        uniqueAns.insert(vec);
    }
    ans.assign(uniqueAns.begin(), uniqueAns.end());

    // 返回结果列表
    return ans;
}

// 深度优先搜索（DFS）函数
void dfs(const vector<int>& arr, int index, int level, vector<int> path, vector<vector<int>>& res) {
    // 如果当前路径的长度等于目标长度，将路径加入结果
    if (path.size() == level) {
        res.push_back(path);
        return;
    }

    // 遍历数组，递归生成组合
    for (int i = index; i < arr.size(); ++i) {
        path.push_back(arr[i]); // 将当前元素加入路径
        dfs(arr, i + 1, level, path, res); // 递归调用
        path.pop_back(); // 回溯，移除当前元素
    }
}

// 算法调用
int main() {
    // 读取输入的第一行，解析为整数数组
    string input;
    getline(cin, input);
    istringstream iss(input);
    arr = vector<int>(istream_iterator<int>(iss), istream_iterator<int>());

    // 读取输入的第二行，作为条件参数
    cin >> num;

    // 调用算法函数并获取结果
    vector<vector<int>> result = getResult(arr, num);

    // 输出结果
    for (size_t i = 0; i < result.size(); ++i) {
        cout << '[';
        for (size_t j = 0; j < result[i].size(); ++j) {
            cout << result[i][j];
            if (j < result[i].size() - 1) cout << ", ";
        }
        cout << ']';
        if (i < result.size() - 1) cout << ", ";
    }
    cout << endl;

    return 0;
}

代码讲解

  1. 输入处理：

    • 使用 getline 读取输入的第一行，并通过 istringstream 解析为整数数组 arr。
    • 使用 cin 读取输入的第二行，作为条件参数 num。

  2. 数据分组：

    • 将数组 arr 分为两组：
      • link1：存储小于 4 的元素。
      • link2：存储大于等于 4 的元素。

  3. 逻辑分支：

    • 根据输入的条件 num，执行不同的逻辑：
      • num == 1：处理长度为 1、2、3、4 的情况，调用 dfs 函数生成组合。
      • num == 2：处理长度为 2、3、4 的情况，调用 dfs 函数生成组合。
      • num == 4：处理长度为 4 的情况，直接将整个列表加入结果。
      • num == 8：处理 link1 和 link2 长度都为 4 的情况，将两个列表合并后加入结果。

  4. 深度优先搜索（DFS）：

    • dfs 函数用于生成指定长度的组合。
    • 通过递归和回溯，生成所有可能的组合，并将结果存入 res 列表。

  5. 去重处理：

    • 使用 set<vector<int>> 对结果进行去重，确保结果中不包含重复的组合。

  6. 结果输出：

    • 将结果列表 result 格式化输出。

示例解析

输入
1 2 3 4 5 6 7 8
2
运行结果
[1, 2], [1, 3], [2, 3], [4, 5], [4, 6], [5, 6]
  • 解析：
    • 输入数组 [1, 2, 3, 4, 5, 6, 7, 8] 被分为 link1 = [1, 2, 3] 和 link2 = [4, 5, 6, 7, 8]。
    • 输入 num = 2，表示需要生成长度为 2 的组合。
    • 最终结果为 link1 和 link2 中长度为 2 的所有组合。

总结

  • 该代码通过分组和深度优先搜索（DFS），实现了根据输入条件生成指定长度的组合。
  • 适用于需要处理分组和组合问题的场景，尤其是需要根据条件动态生成结果的场景。

如果有其他问题，欢迎随时提问！


http://www.kler.cn/a/501215.html

相关文章：

  • 该虚拟机似乎正在使用中。 如果该虚拟机未在使用，请按“获取所有权(T)”按钮获取它的所有权。否则，请按“取消(C)”按钮以防损坏。
  • 什么是MVCC
  • sql server cdc漏扫数据
  • 漏洞扫描工具
  • Mysql--运维篇--主从复制和集群（主从复制I/O线程，SQL线程，二进制日志，中继日志，集群NDB）
  • 基于STM32的智能家居蓝牙系统（论文+源码）
  • Vscode辅助编码AI神器continue插件
  • PlantUml使用向导
  • Java堆内存分析
  • Spring Boot教程之五十五：Spring Boot Kafka 消费者示例
  • 基于Java 的高性能缓存库 Caffeine 详细介绍
  • golang单元测试
  • [QCustomPlot] 交互示例 Interaction Example
  • 项目开发实践——基于SpringBoot+Vue3实现的在线考试系统(五)
  • 银河麒麟服务器操作系统桌面任务栏网络图标消失问题
  • 使用RSyslog将Nginx Access Log写入Kafka
  • http常用状态码（204，304, 404, 504，502）含义
  • Day04-后端Web基础——Maven基础
  • Git 操作与技巧
  • 详解数据增强中的平移shft操作
  • 【C++入门】详解（中）
  • PySpark广播表连接解决数据倾斜的完整案例
  • 多模态人工智能在零售业的未来：通过GPT-4 Vision和MongoDB实现智能产品发现
  • Filebeat es
  • C# 解决“因为算法不同，客户端和服务器无法通信”的问题
  • vue3+ts+element-plus 对话框el-dialog设置圆角