给定一个 � × � n×m 列的 01 01 矩阵(只包含数字 0 0 或 1 1 的矩阵) 再执行 � Q 次询问 每次询问给出一个 � A 行 � B 列的 01 01 矩阵 求该矩阵是否在原矩阵中出现过
时间: 2024-05-25 11:17:55 浏览: 17
解题思路:
暴力枚举
- 对于每个查询矩阵,遍历原矩阵的每个可能的起点,再以该起点为左上角,判断查询矩阵是否与原矩阵中的子矩阵相等。
时间复杂度:$O(QnmAB)$
哈希
- 对于每个查询矩阵和原矩阵的每个可能的起点,计算该子矩阵的哈希值,再比较两个哈希值是否相等。
时间复杂度:$O(Qnm+nmAB)$
KMP
- 对于每个询问矩阵,将其转换为字符串。
- 对于原矩阵的每一行,将其转换为字符串,使用 KMP 算法在其中匹配询问矩阵转换后的字符串。
- 对于原矩阵的每一列,将其转换为字符串,使用 KMP 算法在其中匹配询问矩阵转换后的字符串。
时间复杂度:$O(Q(n+m)(nm+AB))$
AC 自动机
- 对于每个询问矩阵,将其转换为字符串。
- 将所有行和列转换为字符串,构建 AC 自动机。
- 在 AC 自动机上匹配询问矩阵转换后的字符串。
时间复杂度:$O(Q(AB+(n+m)(nm+AB)))$
代码实现:
暴力枚举
时间复杂度:$O(QnmAB)$
空间复杂度:$O(nm)$
C++ 代码
相关问题
给定一个n行m列的二维矩阵,每个位置的数字取值为0
这个矩阵可以被看作一个灰度图像,其中每行表示图像中的一行像素,每列表示图像中的一列像素。由于每个位置的数字都取值为0,因此该图像为完全黑色。在计算机视觉和图像处理领域,通常需要将图像矩阵中的像素值进行变换、滤波、编码等操作,以便完成图像分析、识别、压缩等任务。但如果矩阵中的像素值全为0,这些操作就无法实现,因为没有像素信息可供利用。
在数学中,矩阵是一个二维数组,通常表示为一个大写字母,例如A、B、C等。每个矩阵的元素都可以用小写字母表示,例如a[i,j]、b[i,j]、c[i,j]等。矩阵的乘法、加法、转置等运算在数学中有着丰富的理论基础和广泛的应用。在计算机科学中,矩阵也广泛应用于许多领域,例如机器学习、图形学、物理模拟、信号处理等。二维矩阵也可以看作是一个二维网格,其中每个位置的数字对应该网格的一个格点。因此,矩阵中的数字可以表示为该网格中的一个点的坐标,例如a[i,j]对应网格中的第i行第j列的点。
c++给定一个 � × � n×m 的矩阵,如果一个元素为 0 0,则将其所在行和列的所有元素都改为 0 0
要实现将矩阵中为0的元素所在行和列的所有素都改为0,可以按照以下步骤进行操作:
1. 首先,创建一个大小与原矩阵相同的辅助矩阵,用于记录哪些行和列需要被置为0。
2. 遍历原矩阵的每个元素,如果当前元素为0,则将辅助矩阵对应的行和列标记为需要置为0。
3. 再次遍历原矩阵的每个元素,如果当前元素所在的行或列在辅助矩阵中被标记为需要置为0,则将当前元素置为0。
下面是C++代码示例:
```cpp
#include <iostream>
#include <vector>
void setZeroes(std::vector<std::vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix.size();
std::vector<bool> rowFlag(rows, false); // 记录需要置为0的行
std::vector<bool> colFlag(cols, false); // 记录需要置为0的列
// 遍历原矩阵,记录需要置为0的行和列
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
rowFlag[i] = true;
colFlag[j] = true;
}
}
}
// 将需要置为0的行和列对应的元素置为0
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (rowFlag[i] || colFlag[j]) {
matrix[i][j] = 0;
}
}
}
}
int main() {
std::vector<std::vector<int>> matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
std::cout << "原矩阵:" << std::endl;
for (const auto& row : matrix) {
for (const auto& num : row) {
std::cout << num << " ";
}
std::cout << std::endl;
}
setZeroes(matrix);
std::cout << "置零后的矩阵:" << std::endl;
for (const auto& row : matrix) {
for (const auto& num : row) {
std::cout << num << " ";
}
std::cout << std::endl;
}
return 0;
}
```
运行结果如下:
```
原矩阵:
1 1 1
1 0 1
1 1 1
置零后的矩阵:
1 0 1
0 0 0
1 0 1
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)