我将得到一个NxN矩阵。如果子矩阵满足以下条件,则被视为特殊:
- 它必须是正方形
- 所有数字必须是质数。
我需要计算给定矩阵中满足以下标准的子矩阵的总数。
例如,让样本输入为 =>
3
3 5 6
8 3 2
3 5 2
样例输出: 8
解释:
- 1x1:有7个质数,每个1x1矩阵都包含1个质数
- 2x2:只有右下角的子矩阵包含所有质数
- 3x3:没有3x3矩阵满足这些条件
因此最终答案是(7+1+0)= 8
我最近在面试中遇到了这个问题。我能想出一种暴力解决方案。有什么更好的方法来解决这个问题吗?
[更新] 我已经粘贴了我的尝试来解决这个问题。
class TestClass
{
public static boolean isPrime(int n)
{
if(n<2)
return false;
for(int i=2;i<=Math.sqrt(n);i++)
{
if(n%i==0)
return false;
}
return true;
}
public static boolean scan_matrix(boolean a[][], int start_i, int start_j, int n)
{
for(int i=start_i;i<start_i+n;i++)
{
for(int j=start_j;j<start_j+n;j++)
{
if(!a[i][j])
return false;
}
}
return true;
}
public static int count_valid_matrix(boolean a[][], int n, int N)
{
int result = 0;
for(int start_i=0;start_i<=N-n;start_i++)
{
for(int start_j=0;start_j<=N-n;start_j++)
{
if(scan_matrix(a, start_i, start_j, n))
result += 1;
}
}
return result;
}
public static void main(String args[]) throws Exception
{
Scanner s = new Scanner(System.in);
int N = s.nextInt();
boolean a[][] = new boolean[N][N];
int result = 0;
for(int i=0;i<N; i++)
{
for(int j=0;j<N;j++)
{
int num = s.nextInt();
a[i][j] = isPrime(num);
if(a[i][j])
result += 1;
}
}
int n = 2;
while(n<N)
{
result += count_valid_matrix(a, n, N);
n++;
}
System.out.println(result);
}
}