目录

题目

思路

Code

---

题目

假设我们有一系列测试用例，每个测试用例会覆盖测试若干个代码模块。
我们用一个二维数组 cases 来表示这些测试用例的覆盖情况，其中 cases [ i ][ j ］为1表示第 i 个测试用例覆盖了第 j 个模块，为0则表示未覆盖
求一个最小的测试用例集合，使得该集合能够覆盖所有代码模块。返回最小集合的大小，如果不存在能够覆盖所有代码模块的测试用例集合，则返回﹣1
输入描述
第一行输入是两个整数，分别代表用例总数和代码模块总数 j 
从第二行开始的 i 行，每一行有 j 个整数（0或1)，每个整数之间用空格分隔；每一行代表一个用例对代码模块的覆盖情况
参数取值范围
cases [ i ]. length = j 
cases [ i ][ j ]=0或1
1<= i <=20
1<= j <=20
输出描述
覆盖所有代码模块使用的最小用例集合的大小int，如果不存在能够覆盖所有模块的测试用例集合则返回-1

样例1
输入
3 2
1 0
1 0
1 0
输出
-1
说明
该输入代表有3个测试用例，有2个代码模块，第一个测试用例[1,0]可以覆盖第1个代码模块，第2、3个测试用例相同。

该输入不存在用例集合可以覆盖所有的程序，所以返回-1。

样例2
输入
4 4
1 0 1 0
0 1 0 1
1 1 0 0
0 0 1 1
输出
2
说明
输入代表有4个测试用例，有4个代码模块，针对该输入，可以使用用例0和用例1覆盖所有模块，也可以选择使用用例2和用例3覆盖所有模块，均满足最小用例数要求，所以返回2。

样例3
输入
3 2
1 0
0 1
1 1
输出
1
说明
输入代表有4个测试用例，有2个代码模块，针对该输入，可以使用用例2即可覆盖所有模块，满足最小用例数要求，所以返回1。

思路

最小集合覆盖问题（Minimum Set Cover），它是一个经典的 NP 完全问题。

我们有：

• T个测试用例（1 ≤ T ≤ 20）

• M 个代码模块（1 ≤ M ≤ 20）

每个测试用例都可以覆盖一部分模块，我们需要找出最少数量的测试用例，使得这些用例合并后，能覆盖所有模块。

由于 T≤20，我们可以使用状态压缩枚举法 —— 枚举所有可能的测试用例组合（最多 2^20 种，大概一百万种，性能可接受）。

步骤如下：

1. 将每个测试用例的模块覆盖信息压缩成一个整数的“位掩码”，比如 [1,0,1,0] → 1010（二进制）→ 10（十进制）

2. 目标模块集合也是一个全为1的掩码，比如模块数为 4，目标掩码就是 1111 → 15

3. 枚举所有非空测试用例子集，将子集中所有测试用例的掩码做“或”运算，看看是否能得到目标掩码。

4. 找到所有能覆盖的子集中，测试用例数量最少的那个。

Python

def min_test_cases_to_cover_all_modules(cases, module_count):
    n = len(cases)
    target_mask = (1 << module_count) - 1  # 目标掩码，全1表示所有模块都要覆盖

    # 把每个测试用例转换成一个掩码形式
    masks = []
    for case in cases:
        mask = 0
        for i, val in enumerate(case):
            if val == 1:
                mask |= (1 << i)
        masks.append(mask)

    min_count = float('inf')

    # 枚举所有子集（从1到2^n-1）
    for subset in range(1, 1 << n):
        combined_mask = 0
        count = 0
        for i in range(n):
            if (subset >> i) & 1:
                combined_mask |= masks[i]
                count += 1
        if combined_mask == target_mask:
            min_count = min(min_count, count)

    return min_count if min_count != float('inf') else -1


# 读取输入
t, m = map(int, input().split())
cases = [list(map(int, input().split())) for _ in range(t)]
print(min_test_cases_to_cover_all_modules(cases, m))

 Java

import java.util.*;

public class Main {
    public static int minCover(int[][] cases, int m) {
        int n = cases.length;
        int target = (1 << m) - 1; // 所有模块的目标掩码
        int[] masks = new int[n];

        // 将每个用例转换为掩码形式
        for (int i = 0; i < n; i++) {
            int mask = 0;
            for (int j = 0; j < m; j++) {
                if (cases[i][j] == 1) {
                    mask |= (1 << j);
                }
            }
            masks[i] = mask;
        }

        int res = Integer.MAX_VALUE;
        for (int subset = 1; subset < (1 << n); subset++) {
            int union = 0, count = 0;
            for (int i = 0; i < n; i++) {
                if ((subset & (1 << i)) != 0) {
                    union |= masks[i];
                    count++;
                }
            }
            if (union == target) {
                res = Math.min(res, count);
            }
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt(), m = sc.nextInt();
        int[][] cases = new int[t][m];
        for (int i = 0; i < t; i++)
            for (int j = 0; j < m; j++)
                cases[i][j] = sc.nextInt();

        System.out.println(minCover(cases, m));
    }
}

 C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minCover(vector<vector<int>>& cases, int m) {
    int n = cases.size();
    int target = (1 << m) - 1;
    vector<int> masks(n);

    // 构造每个测试用例的掩码
    for (int i = 0; i < n; ++i) {
        int mask = 0;
        for (int j = 0; j < m; ++j) {
            if (cases[i][j] == 1) {
                mask |= (1 << j);
            }
        }
        masks[i] = mask;
    }

    int res = INT_MAX;
    for (int subset = 1; subset < (1 << n); ++subset) {
        int union_mask = 0, count = 0;
        for (int i = 0; i < n; ++i) {
            if ((subset >> i) & 1) {
                union_mask |= masks[i];
                count++;
            }
        }
        if (union_mask == target) {
            res = min(res, count);
        }
    }
    return res == INT_MAX ? -1 : res;
}

int main() {
    int t, m;
    cin >> t >> m;
    vector<vector<int>> cases(t, vector<int>(m));
    for (int i = 0; i < t; ++i)
        for (int j = 0; j < m; ++j)
            cin >> cases[i][j];

    cout << minCover(cases, m) << endl;
    return 0;
}

 JavaScript

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];
rl.on("line", line => {
    input.push(line.trim());
    if (input.length === parseInt(input[0].split(" ")[0]) + 1) {
        const [t, m] = input[0].split(" ").map(Number);
        const cases = input.slice(1).map(line => line.split(" ").map(Number));
        console.log(minCover(cases, m));
        rl.close();
    }
});

function minCover(cases, m) {
    const n = cases.length;
    const target = (1 << m) - 1;
    const masks = cases.map(row => {
        return row.reduce((mask, bit, i) => bit ? mask | (1 << i) : mask, 0);
    });

    let res = Infinity;
    for (let subset = 1; subset < (1 << n); subset++) {
        let union = 0, count = 0;
        for (let i = 0; i < n; i++) {
            if ((subset >> i) & 1) {
                union |= masks[i];
                count++;
            }
        }
        if (union === target) {
            res = Math.min(res, count);
        }
    }
    return res === Infinity ? -1 : res;
}

 C语言

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main() {
    int t, m;
    scanf("%d %d", &t, &m);
    int cases[20][20];
    int masks[20];
    for (int i = 0; i < t; i++) {
        int mask = 0;
        for (int j = 0; j < m; j++) {
            scanf("%d", &cases[i][j]);
            if (cases[i][j]) mask |= (1 << j);
        }
        masks[i] = mask;
    }

    int target = (1 << m) - 1;
    int res = INT_MAX;

    for (int subset = 1; subset < (1 << t); subset++) {
        int union_mask = 0;
        int count = 0;
        for (int i = 0; i < t; i++) {
            if ((subset >> i) & 1) {
                union_mask |= masks[i];
                count++;
            }
        }
        if (union_mask == target && count < res) {
            res = count;
        }
    }

    printf("%d\n", res == INT_MAX ? -1 : res);
    return 0;
}

【华为od机试真题Python+JS+Java合集】【超值优惠】：Py/JS/Java合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java】：Java真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。