2024年4月13日美团春招实习试题【第一题:好子矩阵】-题目+题解+在线评测【模拟】
- 题目描述:
- 输入描述
- 输出描述
- 样例
- 解题思路一:模拟
- 解题思路二:思路二
- 解题思路三:直接判断
题目描述:
塔子哥定义一个矩阵是”好矩阵”,当且仅当该矩阵所有元素都相同。 现在塔子哥拿到了一个矩阵,她想知道该矩阵有多少2*2的子知阵是好矩阵?
输入描述
第一行输入两个正整数m和n,代表输入矩阵的行数和列数。
接下来的n行,每行输入m个正整数a(i,j),代表塔子哥拿到的矩阵。
1<=n,m<=100
1 < = a ( i , j ) < = 1 0 9 1<=a_{(i,j)}<=10^9 1<=a(i,j)<=109
输出描述
2*2好子矩阵的数量
样例
输入
3 3
1 2 1
1 1 1
1 1 3
输出
1
说明
只有左下角一个好子矩阵。
OJ链接:
https://codefun2000.com/p/P1819
解题思路一:模拟
m, n = map(int, input().split())
matrix = [[0] * n for _ in range(m)]
for i in range(m):row = list(map(int, input().split()))matrix[i] = row
def goodMatrix(matrix, x, y):t = matrix[x][y]if t == matrix[x+1][y] and t == matrix[x+1][y+1] and t == matrix[x][y+1]:return Truereturn Falsecnt = 0
for i in range(m-1):for j in range(n-1):if goodMatrix(matrix, i, j):cnt += 1
print(cnt)
时间复杂度:O(nm)
空间复杂度:O(1)
解题思路二:思路二
import collectionsn, m = map(int, input().split())
mat = list()
for _ in range(n):mat.append(list(map(int, input().split())))bad_start = collections.defaultdict(list)
ret = 0for i in range(n-1):for j in range(m-1):if j not in bad_start[i] and mat[i][j+1] == mat[i][j]:if mat[i+1][j+1] != mat[i][j+1]:bad_start[i].append(j+1)else:if mat[i+1][j] != mat[i+1][j+1]:bad_start[i+1].append(j)else:ret += 1print(ret)
时间复杂度:O(nm)
空间复杂度:O(1)
解题思路三:直接判断
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for i in range(n - 1):for j in range(m - 1):if g[i][j] == g[i + 1][j] and g[i + 1][j] == g[i][j + 1] and g[i][j + 1] == g[i + 1][j + 1]:ans += 1
print(ans)# python
n,m = map(int,input().split())
matrix=[]
for _ in range(n):row=list(map(int, input().split()))matrix.append(row)
count=0
for i in range(n-1):for j in range(m-1):if matrix[i][j] == matrix[i+1][j]==matrix[i][j+1]==matrix[i+1][j+1]:count+=1
print(count)# java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] g = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {g[i][j] = scanner.nextInt();}}int ans = 0;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < m - 1; j++) {if (g[i][j] == g[i + 1][j] && g[i + 1][j] == g[i][j + 1] && g[i][j + 1] == g[i + 1][j + 1]) {ans++;}}}System.out.println(ans);scanner.close();}
}# c++
#include <iostream>
#include <vector>using namespace std;int main() {int n, m;cin >> n >> m;vector<vector<int>> g(n, vector<int>(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> g[i][j];}}int ans = 0;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < m - 1; j++) {if (g[i][j] == g[i + 1][j] && g[i + 1][j] == g[i][j + 1] && g[i][j + 1] == g[i + 1][j + 1]) {ans++;}}}cout << ans << endl;return 0;
}
时间复杂度:O(nm)
空间复杂度:O(1)