最小矩阵宽度 - 华为OD统一考试(D卷)

OD统一考试(D卷)

分值: 200分

题解: Java / Python / C++

华为od机试真题

题目描述

给定一个矩阵,包含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

题解

这是一个滑动窗口类型的问题。

滑动窗口: 适用于解决连续子数组或子字符串的最优问题,例如最小子数组和、最长连续不重复子字符串等。通过滑动窗口,可以在线性时间内解决这些问题,而不需要使用暴力的穷举法。

具体解题思路如下:

  1. 初始化两个指针 leftright,它们定义了一个滑动窗口,初始时窗口为空。
  2. 遍历右指针 right,在每一步将当前右指针所在的列的所有元素加入一个哈希表 cntMap 中,记录每个元素的出现次数。
  3. 当哈希表 cntMap 覆盖了目标哈希表 targetCntMap 时,说明当前窗口包含了数组中所有的整数,此时更新最小长度 ans,并将左指针 left 向右移动,缩小窗口。
  4. 重复步骤 2 和 3,直到右指针 right 遍历完所有列。
  5. 如果最小长度 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机试算法题库#
全部评论

相关推荐

宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-11 13:34
offe从四面八方来:我真的没时间陪你闹了
点赞 评论 收藏
分享
机械打工仔:有说的你怀疑一下就行了,直接问也太实诚了
点赞 评论 收藏
分享
评论
8
4
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务