algo-aha

螺旋打印矩阵

由外向内螺旋

• https://leetcode.com/problems/spiral-matrix/
• https://leetcode.com/problems/spiral-matrix-ii/

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if (matrix.empty()) return {};
    const int R = matrix.size(), C = matrix[0].size();
    const vector<vector<int>> dirs = {{0,1},{1,0},{0,-1},{-1,0}}; // 右下左上
    vector<int> numSteps = {C, R-1};
    int r = 0, c = -1;
    int cur = 0; // 方向，4种
    vector<int> ans;
    while (numSteps[cur % 2]) {
        for (int i = 0; i < numSteps[cur % 2]; i++) {
            r += dirs[cur][0], c += dirs[cur][1];
            ans.push_back(matrix[r][c]);
        }
        numSteps[cur % 2]--;
        cur = (cur + 1) % 4;
    }
    return ans;
}

由内向外螺旋

• https://leetcode.com/problems/spiral-matrix-iii/

vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
    // 往右下左上方向不断走1,1,2,2,3,3,4,4,5,5,...步
    // 从索引i（0-based）生成步数的通式是 i/2+1
    const vector<vector<int>> dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    vector<vector<int>> ans;
    ans.push_back({r0, c0});

    int r = r0, c = c0;
    for (int i = 0; ans.size() < R * C; i++) {
        auto &dir = dirs[i%4]; // 方向
        for (int k = 0; k < i / 2 + 1; k++) { // 走i/2+1步
            r += dir[0], c += dir[1];
            if (0 <= r && r < R && 0 <= c && c < C) ans.push_back({r, c});
        }
    }
    return ans;
}

来回遍历次对角线方向

• https://leetcode.com/problems/diagonal-traverse

同一次对角线上两个点r、c一增一减，r+c相等。

vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
    if (matrix.empty()) return {};
    const int R = matrix.size(), C = matrix[0].size();
    vector<vector<int>> diags(R + C - 1);
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            diags[r+c].push_back(matrix[r][c]);
        }
    }
    vector<int> ans;
    for (int i = 0; i < diags.size(); i++) {
        if (i % 2 == 0) {
            ans.insert(end(ans), rbegin(diags[i]), rend(diags[i]));
        } else {
            ans.insert(end(ans), begin(diags[i]), end(diags[i]));
        }
    }
    return ans;
}

联想：同一主对角线上两点r、c同增减，r-c相等

NxN矩阵顺时针旋转90度

• https://leetcode.com/problems/rotate-image/

void rotate(vector<vector<int>>& matrix) {
    // 旋转90度跟"转置"有关
    // 顺时针旋转90度 <=等价=> 先把行倒排、再转置
    // 1 2 3      7 8 9      7 4 1 
    // 4 5 6  =>  4 5 6  =>  8 5 2
    // 7 8 9      1 2 3      9 6 3
    reverse(begin(matrix), end(matrix));
    const int N = matrix.size();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
}

如果是左转90度，那就是先先转置、再把行倒排。

01矩阵中各点到最近0值的距离

• https://leetcode.com/problems/01-matrix/

两遍扫描更新距离矩阵dist[][]，第一遍从上到下从左到右、第二遍从下到上从右到左。

vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
    const int INF = 1e7;
    const int R = matrix.size(), C = matrix[0].size();
    vector<vector<int>> dist(R, vector<int>(C, INF));

    // 上=>下、左=>右
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (matrix[r][c] != 0) {
                if (r > 0) dist[r][c] = min(dist[r][c], dist[r-1][c] + 1);
                if (c > 0) dist[r][c] = min(dist[r][c], dist[r][c-1] + 1);
            } else {
                dist[r][c] = 0;
            }
        }
    }        
    // 下=>上、右=>左
    for (int r = R - 1; r >= 0; r--) {
        for (int c = C - 1; c >= 0; c--) {
            if (matrix[r][c] != 0) {
                if (r + 1 < R) dist[r][c] = min(dist[r][c], dist[r+1][c] + 1);
                if (c + 1 < C) dist[r][c] = min(dist[r][c], dist[r][c+1] + 1);
            }
        }
    }
    return dist;
}