最小矩阵宽度 - 华为OD统一考试(D卷)
OD统一考试(D卷)
分值: 200分
题解: Java / Python / C++
题目描述
给定一个矩阵,包含N*M个整数,和一个包含K个整数的数组。 现在要求在这个矩阵中找一个宽度最小的子短阵,要求子矩阵包含数组中所有的整数。
输入描述
第一行输入两个正整数 N, M 表示矩阵大小。
接下来 N 行 M列表示矩阵内容。
下一行包含一个正整数K。
下一行包含K个整数,表示所需包含的数组,K个整数可能存在重复数字, 所有输入数据小于 1000。
输出描述
输出包含一个整数,表示满足要求子矩阵的最小宽度,若找不到,输出-1.
示例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
输入:
2 5
1 2 2 3 1
1 3 2 3 4
3
1 1 4
输出:
5
说明:
短阵第1、2、3、4、5列包含了1、1、4
题解
这是一个滑动窗口类型的问题。
滑动窗口: 适用于解决连续子数组或子字符串的最优问题,例如最小子数组和、最长连续不重复子字符串等。通过滑动窗口,可以在线性时间内解决这些问题,而不需要使用暴力的穷举法。
具体解题思路如下:
- 初始化两个指针
left
和right
,它们定义了一个滑动窗口,初始时窗口为空。- 遍历右指针
right
,在每一步将当前右指针所在的列的所有元素加入一个哈希表cntMap
中,记录每个元素的出现次数。- 当哈希表
cntMap
覆盖了目标哈希表targetCntMap
时,说明当前窗口包含了数组中所有的整数,此时更新最小长度ans
,并将左指针left
向右移动,缩小窗口。- 重复步骤 2 和 3,直到右指针
right
遍历完所有列。- 如果最小长度
ans
未被更新,则输出 -1;否则输出ans
。这样可以通过滑动窗口的方式寻找满足要求子矩阵的最小宽度。在代码中,使用哈希表
cntMap
维护当前窗口的元素出现次数,通过左右指针的移动来不断调整窗口的大小。
Java
import java.util.HashMap;
import java.util.Scanner;
/**
* @author code5bug
*/
class Main {
/**
* 计算满足要求子矩阵的最小宽度
*
* @param n 矩阵的行数
* @param m 矩阵的列数
* @param targetCntMap 目标数据hash计数
* @param matrix 矩阵
* @return 满足要求子矩阵的最小宽度,若找不到,输出-1
*/
public static int solve(int n, int m, HashMap<Integer, Integer> targetCntMap, int[][] matrix) {
HashMap<Integer, Integer> cntMap = new HashMap<>();
int ans = Integer.MAX_VALUE;
// 利用滑动窗口寻找满足要求子矩阵的最小宽度
// 窗口大小 [left, right]
for (int left = 0, right = 0; right < m; right++) {
// 将当前右指针 right 所在的列的所有元素加入哈希表 cntMap 中
for (int row = 0; row < n; row++) cntMap.merge(matrix[row][right], 1, Integer::sum);
// 当哈希表 cntMap 覆盖了哈希表 targetCntMap 时,更新最小长度 ans,并将左指针 left 向右移动缩小窗口(继续尝试寻找更小的矩阵宽度)
while (mapCover(cntMap, targetCntMap)) {
ans = Math.min(ans, right - left + 1);
// 将当前左指针 left 所在的列的所有元素从哈希表 cntMap 中删除
for (int k = 0; k < n; k++) cntMap.merge(matrix[k][left], -1, Integer::sum);
left++;
}
}
// 如果最小长度 ans 未被更新,则输出 -1;否则输出 ans
return (ans == Integer.MAX_VALUE) ? -1 : ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), 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.nextInt(); // 输入数组 t 的长度 k
int[] t = new int[k]; // 用于存储数组 t 的一维数组
HashMap<Integer, Integer> targetCntMap = new HashMap<>();
// 读取数组 t 的元素,并将其存储到哈希表 targetCntMap 中
for (int i = 0; i < k; i++) {
t[i] = sc.nextInt();
targetCntMap.merge(t[i], 1, Integer::sum);
}
int ans = solve(n, m, targetCntMap, matrix);
System.out.println(ans);
}
// 检查哈希表 cntMap 是否覆盖了哈希表 targetMap
public static boolean mapCover(HashMap<Integer, Integer> cntMap, HashMap<Integer, Integer> targetMap) {
for (Integer i : targetMap.keySet()) {
if (cntMap.getOrDefault(i, 0) < targetMap.get(i)) {
return false;
}
}
return true;
}
}
Python
from collections import Counter
from math import inf
def solve(n, m, target_cnt_map, matrix):
""" 计算满足要求子矩阵的最小宽度 """
def map_cover(cnt_map, target_map):
""" 检查哈希表 cntMap 是否覆盖了哈希表 targetMap """
for key, val in target_map.items():
if cnt_map.get(key, 0) < val:
return False
return True
ans = inf
cnt_map = Counter()
left = 0
for right in range(m):
for row in range(n):
cnt_map[matrix[row][right]] = cnt_map.get(matrix[row][right], 0) + 1
while map_cover(cnt_map, target_cnt_map):
ans = min(ans, right - left + 1)
for k in range(n):
cnt_map[matrix[k][left]] -= 1
left += 1
return -1 if ans == inf else ans
if __name__ == "__main__":
n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
k = int(input())
t = list(map(int, input().split()))
target_cnt_map = Counter(t)
ans = solve(n, m, target_cnt_map, matrix)
print(ans)
from math import inf
from collections import Counter
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
k = int(input())
tcnt = Counter(list(map(int, input().split())))
def map_cover(smap, tmap) -> bool:
for k, v in tmap.items():
if smap.get(k, 0) < v:
return False
return True
cnt = Counter()
l, r = 0, 0
min_width = inf
while r < m:
cnt.update([g[i][r] for i in range(n)])
r += 1
while map_cover(cnt, tcnt):
min_width = min(min_width, r - l)
for i in range(n):
cnt[g[i][l]] -= 1
l += 1
print(min_width if min_width != inf else -1)
C++
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// 检查哈希表 cntMap 是否覆盖了哈希表 targetMap
bool mapCover(unordered_map<int, int>& cntMap, unordered_map<int, int>& targetMap) {
for (auto& entry : targetMap) {
if (cntMap[entry.first] < entry.second) {
return false;
}
}
return true;
}
/**
* 计算满足要求子矩阵的最小宽度
*
* @param n 矩阵的行数
* @param m 矩阵的列数
* @param targetCntMap 目标数据hash计数
* @param matrix 矩阵
* @return 满足要求子矩阵的最小宽度,若找不到,输出-1
*/
int solve(int n, int m, unordered_map<int, int>& targetCntMap, vector<vector<int>>& matrix) {
unordered_map<int, int> cntMap;
int ans = INT_MAX;
// 利用滑动窗口寻找满足要求子矩阵的最小宽度
// 窗口大小 [left, right]
for (int left = 0, right = 0; right < m; right++) {
// 将当前右指针 right 所在的列的所有元素加入哈希表 cntMap 中
for (int row = 0; row < n; row++) {
cntMap[matrix[row][right]]++;
}
// 当哈希表 cntMap 覆盖了哈希表 targetCntMap 时,更新最小长度 ans,并将左指针 left 向右移动缩小窗口(继续尝试寻找更小的矩阵宽度)
while (mapCover(cntMap, targetCntMap)) {
ans = min(ans, right - left + 1);
// 将当前左指针 left 所在的列的所有元素从哈希表 cntMap 中删除
for (int k = 0; k < n; k++) {
cntMap[matrix[k][left]]--;
}
left++;
}
}
// 如果最小长度 ans 未被更新,则输出 -1;否则输出 ans
return (ans == INT_MAX) ? -1 : ans;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> matrix(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> matrix[i][j];
}
}
int k;
cin >> k; // 输入数组 t 的长度 k
vector<int> t(k); // 用于存储数组 t 的一维数组
unordered_map<int, int> targetCntMap;
// 读取数组 t 的元素,并将其存储到哈希表 targetCntMap 中
for (int i = 0; i < k; i++) {
cin >> t[i];
targetCntMap[t[i]]++;
}
int ans = solve(n, m, targetCntMap, matrix);
cout << ans << endl;
return 0;
}
🙏整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏
#华为##华为od##华为od题库##华为od机试##华为OD机试算法题库#