最新华为OD机试真题-最小矩阵宽度(200分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓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.
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测