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，否則根據公式計算得分點的數量，并傳回結果。

該公式的計算過程是先計算矩陣中所有格子數量 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));
}