2023-04-07：求解矩阵得分点问题！——本文探讨蚂蚁金服算法面试题，介绍两种解决方案：递归和数学公式。文章附有代码和示例，适合算法爱好者和面试备战者参考。
原创2023-04-07：求解矩阵得分点问题！——本文探讨蚂蚁金服算法面试题，介绍两种解决方案：递归和数学公式。文章附有代码和示例，适合算法爱好者和面试备战者参考。
原创
2023-04-07：得分的定义 :
含有大小2*2的矩阵，要么：
1 0
0 1 可以得1分
要么
0 1
1 0 可以得1分
那么一个任意大小的矩阵就有若干得分点，比如
0 1 0
1 0 1
这个矩阵就有2个得分点。
给定正数N，正数M，求所有可能的情况里，所有的得分点总和。
1 <= N、M <= 10^9。
来自蚂蚁金服。
答案2023-04-07：
算法一：
这个算法是利用递归来生成所有可能的矩阵，并且统计其中符合条件的得分点的数量。具体而言，该算法首先判断输入的 n 和 m 是否满足小于 2 的条件，如果满足，则直接返回 0，否则创建一个二维数组 matrix，对其进行递归处理，从左到右、从上到下枚举每一个格子，将其置为 1 或 0，然后递归到下一个格子，计算符合条件的得分点数量，最后返回总得分点数。
在具体实现过程中，由于矩阵中只会有大小为 2x2 的子矩阵产生得分点，因此可以先遍历整个矩阵，查找是否存在符合条件的 2x2 子矩阵，并记录得分点的数量，最后返回总得分点数。
时间复杂度：O(2^(n*m))，因为该算法需要生成所有可能的矩阵，并对每一个矩阵进行遍历和判断，因此时间复杂度与矩阵的大小 n 和 m 成指数关系。
空间复杂度：O(nm)，因为该算法需要创建一个二维数组来存储矩阵，数组大小为 nm。
算法二：
该算法则是通过数学公式来计算得分点的数量，从而避免了生成所有可能矩阵的过程，具体而言，该算法首先判断输入的 n 和 m 是否满足小于 2 的条件，如果满足，则直接返回 0，否则根据公式计算得分点的数量，并返回结果。
该公式的计算过程是先计算矩阵中所有格子数量 nm，然后减去不符合条件的行数 n 和列数 m，再加上只包含一个得分点的情况，最后乘以包含 2 个得分点的情况的数量。其中，包含 2 个得分点的情况的数量可以使用位运算来计算，即左移 (n m - 3) 个二进制位，表示从 n * m 个格子中选择任意两个作为得分点的所有可能方案的数量。
总体而言，这两种算法都能够计算出所有可能的得分点的数量，但是它们的实现方式和时间复杂度略有不同。第一种算法的时间复杂度为 O(2^(n*m))，会随着 n 和 m 的增加而指数级增长，因此对于较大的 n 和 m 值，其运行时间可能会非常长；而第二种算法的时间复杂度仅为 O(1)，与输入规模无关，因此能够在更短的时间内计算出结果，但是需要一定的数学知识和技巧来推导公式。
时间复杂度：O(1)，因为该算法不需要生成所有可能的矩阵，只需要根据输入的 n 和 m 计算公式即可得到结果，因此时间复杂度与输入规模无关。
空间复杂度：O(1)，因为该算法只需要使用常数级别的额外空间来存储中间变量和结果。
rust完整代码如下：
fn score1(n: i32, m: i32) -> i32 {
if n < 2 || m < 2 {
return 0;
}
let mut matrix = vec![vec![0; m as usize]; n as usize];
process(&mut matrix, 0, 0, n, m)
}
fn process(matrix: &mut Vec<Vec<i32>>, i: i32, j: i32, n: i32, m: i32) -> i32 {
if i == n {
let mut score = 0;
for r in 1..n {
for c in 1..m {
if check(&matrix, r, c) {
score += 1;
}
}
}
return score;
}
if j == m {
return process(matrix, i + 1, 0, n, m);
}
let mut score = 0;
matrix[i as usize][j as usize] = 1;
score += process(matrix, i, j + 1, n, m);
matrix[i as usize][j as usize] = 0;
score += process(matrix, i, j + 1, n, m);
score
}
fn check(m: &Vec<Vec<i32>>, r: i32, c: i32) -> bool {
(m[(r - 1) as usize][(c - 1) as usize] == 0
&& m[r as usize][(c - 1) as usize] == 1
&& m[(r - 1) as usize][c as usize] == 1
&& m[r as usize][c as usize] == 0)
|| (m[(r - 1) as usize][(c - 1) as usize] == 1
&& m[r as usize][(c - 1) as usize] == 0
&& m[(r - 1) as usize][c as usize] == 0
&& m[r as usize][c as usize] == 1)
}
fn score2(n: i32, m: i32) -> i32 {
if n < 2 || m < 2 {
return 0;
}
(n * m - m - n + 1) * (1 << (n * m - 3))
}
fn main() {
let n = 3;
let m = 4;
println!("{}", score1(n, m));
println!("{}", score2(n, m));
}
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。