程式語言 - LeetCode - C - 2906. Construct Product Matrix


參考資訊：
https://algo.monster/liteproblems/2906

題目：


方法： 

// 原始公式
(位置0) = grid[0][1] * grid[1][0] * grid[1][1]
(位置1) = grid[0][0] * grid[1][0] * grid[1][1]
(位置2) = grid[0][0] * grid[0][1] * grid[1][1]
(位置3) = grid[0][0] * grid[0][1] * grid[1][0]

// 轉換成一維
(位置0) = grid[1] * grid[2] * grid[3]
(位置1) = grid[0] * grid[2] * grid[3]
(位置2) = grid[0] * grid[1] * grid[3]
(位置3) = grid[0] * grid[1] * grid[2]

// Prefix (由前往後)
(位置0) = 1
(位置1) = grid[0]
(位置2) = grid[0] * grid[1]
(位置3) = grid[0] * grid[1] * grid[2]

// Suffix (由後往前)
(位置0) = grid[1] * grid[2] * grid[3]
(位置1) = grid[2] * grid[3]
(位置2) = grid[3]
(位置3) = 1

// Result = Prefix * Suffix
(位置0) = 1 * grid[1] * grid[2] * grid[3]
(位置1) = grid[0] * grid[2] * grid[3]
(位置2) = grid[0] * grid[1] * grid[3]
(位置3) = grid[0] * grid[1] * grid[2] * 1

解答： 

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** constructProductMatrix(int** grid, int gridSize, int* gridColSize, int* returnSize, int** returnColumnSizes)
{
    typedef long long ll;
    const int MOD = 12345;
 
    int i = 0;
    int j = 0;
    int row_size = gridSize;
    int col_size = gridColSize[0];
    int total = row_size * col_size;
    ll *q = calloc(total, sizeof(ll));
    ll *prefix = calloc(total, sizeof(ll));
    ll *suffix = calloc(total, sizeof(ll));
    int **r = calloc(row_size, sizeof(int *));

    *returnSize = row_size;
    *returnColumnSizes = calloc(row_size, sizeof(int));

    for (i = 0; i < row_size; i++) {
        r[i] = calloc(col_size, sizeof(int));

        (*returnColumnSizes)[i] = col_size;
    }

    for (i = 0; i < total; i++) {
        prefix[i] = 1;
        suffix[i] = 1;
    }

    for (i = 0; i < row_size; i++) {
        for (j = 0; j < col_size; j++) {
            q[(i * col_size) + j] = grid[i][j];
        }
    }

    for (i = 1; i < total; i++) {
        prefix[i] = (prefix[i - 1] * q[i - 1]) % MOD;
    }
    for (i = total - 2; i >= 0; i--) {
        suffix[i] = (suffix[i + 1] * q[i + 1]) % MOD;
    }

    for (i = 0; i < total; i++) {
        int v = (prefix[i] * suffix[i]) % MOD;

        r[i / col_size][i % col_size] = v;
    }

    return r;
}