最新华为OD机试真题-最小矩阵宽度(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎在线评测链接

最小矩阵宽度(200分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🥮 最小矩阵宽度

问题描述

给定一个包含 个整数的矩阵和一个包含 个整数的数组，要求在这个矩阵中找一个宽度最小的子矩阵，该子矩阵包含数组中所有的整数。

输入格式

第一行输入两个正整数 和 ，表示矩阵大小。

接下来 行，每行包含 个整数，表示矩阵的内容。

然后输入一个正整数 。

最后一行包含 个整数，表示需要包含的数组， 个整数可能存在重复数字。

所有输入数据小于 。

输出格式

输出一个整数，表示满足要求的子矩阵的最小宽度。如果找不到，输出 -1。

样例输入

2 5
1 2 2 3 1
2 3 2 3 2
3
1 2 3

样例输出

2

样例解释

在样例中，矩阵第 0 和 3 列包含了 1、2、3，矩阵第 3 和 4 列包含了 1、2、3，所以最小宽度为 2。

数据范围

题解

这个问题可以使用滑动窗口和哈希表来解决。先用滑动窗口遍历矩阵的列，记录当前窗口内每个数字的出现次数。当窗口内包含数组中所有的数字时，记录当前窗口的宽度，并尝试收缩窗口来找到最小宽度。

参考代码

• Python

def min_width(matrix, n, m, k, required):
    # 计算每个数字所需的次数
    count_needed = {}
    for num in required:
        count_needed[num] = count_needed.get(num, 0) + 1
    
    # 初始化滑动窗口中的数字计数
    count_in_window = {}
    left = 0
    min_width = m + 1
    
    def is_valid():
        for num in count_needed:
            if count_in_window.get(num, 0) < count_needed[num]:
                return False
        return True
    
    for right in range(m):
        for i in range(n):
            count_in_window[matrix[i][right]] = count_in_window.get(matrix[i][right], 0) + 1
        
        while is_valid():
            min_width = min(min_width, right - left + 1)
            for i in range(n):
                count_in_window[matrix[i][left]] -= 1
            left += 1
    
    return min_width if min_width <= m else -1

if __name__ == "__main__":
    n, m = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(n)]
    k = int(input())
    required = list(map(int, input().split()))
    print(min_width(matrix, n, m, k, required))

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        int k = sc.