LeetCode Set Matrix Zeroes：常數空間矩陣置零

LeetCode Set Matrix Zeroes：常數空間矩陣置零

給定 m×n 矩陣，若元素為 0，將其所在行列全部置 0。要求原地修改，空間 O(1)。

方法一：兩個標記數組（空間 O(m+n)）

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<bool> row(m, false), col(n, false);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (matrix[i][j] == 0) row[i] = col[j] = true;
    for (int i = 0; i < m; i++)
        if (row[i]) fill(matrix[i].begin(), matrix[i].end(), 0);
    for (int j = 0; j < n; j++)
        if (col[j])
            for (int i = 0; i < m; i++) matrix[i][j] = 0;
}

方法二：常數空間（利用首行首列作標記）

1. 先記錄首行、首列是否原本含 0（firstRowZero, firstColZero）。
2. 遍歷 ，若 matrix[i][j]==0，標記 和 。
3. 根據首行首列標記，將對應行列置 0（從 1 開始）。
4. 最後根據 firstRowZero, firstColZero 處理首行首列。

void setZeroesO1(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    bool firstRowZero = false, firstColZero = false;
    for (int j = 0; j < n; j++) if (matrix[0][j] == 0) { firstRowZero = true; break; }
    for (int i = 0; i < m; i++) if (matrix[i][0] == 0) { firstColZero = true; break; }
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
    for (int i = 1; i < m; i++)
        if (matrix[i][0] == 0)
            fill(matrix[i].begin(), matrix[i].end(), 0);
    for (int j = 1; j < n; j++)
        if (matrix[0][j] == 0)
            for (int i = 0; i < m; i++) matrix[i][j] = 0;
    if (firstRowZero) fill(matrix[0].begin(), matrix[0].end(), 0);
    if (firstColZero) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}

fill / fill_n 用法補充

• fill(first, last, val)：將迭代器區間 [first, last) 賦值 val。
• fill_n(first, n, val)：從 first 開始賦值 n 個元素。
• 適用於任意容器（vector, array, 指針等）。

vector<int> v(8);
fill(v.begin(), v.begin()+4, 5);      // 前 4 個置 5
fill_n(v.begin()+3, 3, 8);            // 從第 3 個開始 3 個置 8
// v: 5 5 5 8 8 8 0 0

迭代器 vs 指針

複雜度

• 時間：O(m*n)，三次遍歷矩陣。
• 空間：O(1)，僅用常數額外變量。

此題核心在於「用矩陣自身存儲標記信息」，是原地算法設計的典範，同類思想還適用於「找缺失數字」「數組去重」等問題。

1. 上一篇文章： NYOJ 488 素數環：DFS 回溯構造質數和環
2. 下一篇文章： POJ 2356 Find a Multiple：鴿籠原理必有解

C++ 入門

HDU 2845 Beans：二維 DP 吃豆子遊戲

問題描述 M×N 矩陣，每格有一顆豆子，值為品質值。吃掉 (

C++ 關鍵字 explicit：禁止構造函數隱式轉換，避免驚喜式 Bug

隱式轉換的「驚喜」 C++ 允許單參數構造函數定義從參數類型

POJ 1915 Knight Moves：雙向 BFS 求騎士最短步數

POJ 1915 Knight Moves：雙向 BFS 求

HDU 4472 Count：諧和關係配置計數 DP（約數狀態壓縮）

HDU 4472 Count 題目深度解析 村莊關係形成樹狀