2023-04-07：求解矩阵得分点问题！——本文探讨蚂蚁金服算法面试题，介绍两种解决方案：递归和数学公式。文章附有代码和示例，

福大大架构师每日一题

发布于 2023-06-08 15:37:21

1320

发布于 2023-06-08 15:37:21

文章被收录于专栏：福大大架构师每日一题

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，否则根据公式计算得分点的数量，并返回结果。

该公式的计算过程是先计算矩阵中所有格子数量 n*m，然后减去不符合条件的行数 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));
}