用php做的订票网站,网站建设熊猫建站,制作网站规划书,如何建立一个学校网站题目描述
给定一个矩阵#xff0c;包含 N * M 个整数#xff0c;和一个包含 K 个整数的数组。
现在要求在这个矩阵中找一个宽度最小的子矩阵#xff0c;要求子矩阵包含数组中所有的整数。
输入描述
第一行输入两个正整数 N#xff0c;M#xff0c;表示矩阵大小。
接下…题目描述
给定一个矩阵包含 N * M 个整数和一个包含 K 个整数的数组。
现在要求在这个矩阵中找一个宽度最小的子矩阵要求子矩阵包含数组中所有的整数。
输入描述
第一行输入两个正整数 NM表示矩阵大小。
接下来 N 行 M 列表示矩阵内容。
下一行包含一个正整数 K。
下一行包含 K 个整数表示所需包含的数组K 个整数可能存在重复数字。
所有输入数据小于1000。
输出描述
输出包含一个整数表示满足要求子矩阵的最小宽度若找不到输出 -1。
用例输入
2 5
1 2 2 3 1
2 3 2 3 2
3
1 2 32我们需要找到一个子矩阵包含数字 1、2 和 3并且每个数字的频率都至少是它在数组中出现的次数。
当窗口的列范围为 [3, 4] 时
窗口包括列[3, 1] 和 [3, 2]仍然包含数字 1、2 和 3。
2 5
1 1 3 2 3
1 3 2 3 4
3
1 1 45解题思路
宽度最小长度不限。其实就是找一个列区间。 滑动窗口法使用滑动窗口在矩阵的列中查找子矩阵保证窗口内包含所有需要的数字。窗口宽度从小到大逐步尝试以找到最小的有效宽度。 具体步骤 对于每一行记录每列的数字出现情况。维护一个滑动窗口该窗口内的列包含所有需要的数字及其频率。随着窗口的扩大检查该窗口是否满足条件。如果满足条件尝试收缩窗口以找到最小宽度。 最终结果输出最小宽度如果没有找到有效的子矩阵输出 -1。
代码
#include iostream
#include vector
#include map
#include climits
#include algorithm
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin n m;vectorvectorint matrix(n, vectorint(m));for (int i 0; i n; i) {for (int j 0; j m; j) {cin matrix[i][j];}}int k;cin k;mapint, int re; // 存储所需的数字及其频率for (int i 0; i k; i) {int num;cin num;re[num];}int min_width INT_MAX;// 初始化最小宽度为最大值// i 为列区间的起始for (int i 0; i m; i) {mapint, int cur;// 当前窗口内的数字频率int ok 0; // 当前窗口包含的满足条件的数字个数// 滑动窗口的右边界for (int j i; j m; j) {// 更新当前窗口的数字频率 把j列的数据加进去for (int t 0; t n; t) {int num matrix[t][j];if (re.count(num)) {cur[num];// 当数字的频率达到了要求的数量时if (cur[num] re[num]) {ok;}}}// 当前窗口包含所有需要的数字更新最小宽度if (ok re.size()) {min_width min(min_width, j - i 1);}}}// 输出结果if (min_width INT_MAX) {cout -1 endl;}else {cout min_width endl;}
}
