时间戳

首页 > 技术文章 > [LeetCode] Matrix 值修改系列，例题 Surrounded Regions，Set Matrix Zeroes

[LeetCode] Matrix 值修改系列，例题 Surrounded Regions，Set Matrix Zeroes

felixfang 2014-06-23 08:37 原文

引言

Matrix内部的值修改严格来讲放在一个系列里不大合适，因为对于不同的问题，所用的算法和技巧可能完全不同，权且这样归类，以后需要时再拆分吧。

 

例题 1

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

 

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X
class Solution {
public:
    void solve(vector<vector<char>> &board) {
    }
};

这道题的思路应该比较容易想到：

遍历最外层一圈，如果有O，就把其相邻的也设置为O。接着遍历全矩阵，把内层O置为X。

但是这样做的问题遍历全矩阵时，分不清遇到的O是内层还是外层。

因此改进的方法是遍历最外层时，将O及其相邻的字符都设为"Y"。遍历全矩阵时，把"O"设置为X，把"Y"设置回"O"。

 

寻找O的邻居时，用的自然是BFS。每遇到一个O，就通过BFS将它以及邻居设置为"Y"

代码：

class Solution {
struct Point{
    int h;
    int v;
    Point(int vp, int hp) : v(vp), h(hp) {};
};
public:
    void BFS(int startH, int startW, vector<vector<char>> &board, queue<Point> que){
        while(!que.empty()) que.pop();
        int W = board[0].size(), H = board.size();
        Point p(startH, startW);
        que.push(p);
        while(!que.empty()){
            Point cur = que.front();
            que.pop();
            board[cur.v][cur.h] = 'Y';
            for(int i = 0; i < 4; i++){ //扫描四个方向上的邻居
                if((cur.v+addV[i]) < H
                && (cur.h+addH[i]) < W
                && (cur.v+addV[i]) >= 0
                && (cur.h+addH[i]) >= 0 
                && board[cur.v+addV[i]][cur.h+addH[i]] == 'O'){
                    que.push(Point(cur.v+addV[i], cur.h+addH[i]));
                }
            }
        }
    }

    void solve(vector<vector<char>> &board) {
        if(board.size() == 0 || board[0].size() == 0) return;
        int W = board[0].size(), H = board.size();
        queue<Point> que;
        int i, j = 0;
        for(i = 0; i < W; ++i){
            if(board[0][i] == 'O') BFS(0, i, board, que);
            if(H > 1 && board[H-1][i] == 'O') BFS(H-1, i, board, que); //遇到'O'，调用BFS
        }
        for(i = 0; i < H; ++i){
            if(board[i][0] == 'O') BFS(i, 0, board, que);
            if(W > 1 && board[i][W-1] == 'O') BFS(i, W-1, board, que);
        }
        
        for(i = 0; i < H; ++i){ //再次遍历全数组
            for(j = 0; j < W; ++j){
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == 'Y') board[i][j] = 'O';
            }
        }
    }
private:
    int addV[4] = {1, 0 , -1, 0};
    int addH[4] = {0, 1, 0, -1};
};

 

这样提交上去，超时。

 

有什么办法可以缩短时间呢？回想思路可以发现：每次遇到O，我们都调用一次BFS，每一次调用BFS，都需要清空队列que，然后再push。

为什么不把所有的BFS并为一次呢？每次遇到O，我们只向队列que中push当前O所在的Point，最后调用一次BFS集中处理que，其效果是完全一样的，但是时间上却省去了每次清空队列的时间。

代码：

class Solution {
struct Point{
    int h;
    int v;
    Point(int vp, int hp) : v(vp), h(hp) {};
};
public:
    void solve(vector<vector<char>> &board) {
        if(board.size() == 0 || board[0].size() == 0) return;
        int W = board[0].size(), H = board.size();
        queue<Point> que;
        int i, j = 0;
        for(i = 0; i < W; ++i){
            if(board[0][i] == 'O') que.push(Point(0, i));
            if(H > 1 && board[H-1][i] == 'O') que.push(Point(H-1, i)); //遇到O，只push，不再调用BFS
        }
        for(i = 0; i < H; ++i){
            if(board[i][0] == 'O') que.push(Point(i, 0));
            if(W > 1 && board[i][W-1] == 'O') que.push(Point(i, W-1)); //遇到O，只push，不再调用BFS
        }
        while(!que.empty()){ //调用BFS
            Point cur = que.front();
            que.pop();
            board[cur.v][cur.h] = 'Y';
            for(int i = 0; i < 4; i++){
                if((cur.v+addV[i]) < H
                && (cur.h+addH[i]) < W
                && (cur.v+addV[i]) >= 0
                && (cur.h+addH[i]) >= 0 
                && board[cur.v+addV[i]][cur.h+addH[i]] == 'O'){
                    que.push(Point(cur.v+addV[i], cur.h+addH[i]));
                }
            }
        }
        
        for(i = 0; i < H; ++i){
            for(j = 0; j < W; ++j){
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == 'Y') board[i][j] = 'O';
            }
        }
    }
private:
    int addV[4] = {1, 0 , -1, 0};
    int addH[4] = {0, 1, 0, -1};
};

 

 

小结：

这种需要更改Matrix的值的题目，上面解法用到了很简单的技巧：“引入一个中间值 Y”，避免了混淆。

 

例题 2

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Could you devise a constant space solution?

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        
    }
};

 

这道题的困难之处在于“需要空间复杂度为常量”

有了上一题的启发，我们可以将0所在的行和列都设置为别的值X，最后将所有X设置为0。

但是这样做的弱点在于：

1. 每个元素都要被访问 >= 2次 (那些和0同行同列的元素被访问大于2次，那些不和0同行同列的元素被访问了2次)。

2. 如果题目改成vector<vector<bool> >，这种解法就失效了，因为没有第三个值可以引入。

 

如果空间复杂度要求是O(m+n)的话，我们会申明两个数组，分别来记录需要设为0的行号和列号。

进一步，如果如果空间复杂度要求是O(1)，我们虽然不能申明新数组，但是我们能用第一行和第一列来标记那些需要置为0的行和列。

当遇到 matix[i][j] == 0时，将matix[0][j] 和 matrix[i][0] 置为 0。

第一遍遍历matrix结束后，将所记录的行和列置为0。

这样做需要注意：如果第一行或者第一列有0，需要额外记录。

代码：

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        if(matrix.size() == 0) return;
        if(matrix[0].size() == 0) return;
        
        bool firstRowSet = false;
        bool firstColSet = false;
        int i, j;
        for(i = 0; i < matrix.size(); ++i){
            for(j = 0; j < matrix[i].size(); ++j){
                if(matrix[i][j] == 0){
                    if(i == 0) firstRowSet = true;
                    if(j == 0) firstColSet = true;
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        for(i = 1; i < matrix.size(); ++i){
            if(matrix[i][0] == 0){
                for(j = 1; j < matrix[i].size(); ++j)
                    matrix[i][j] = 0;
            }
        }
        
        for(j = 1; j < matrix[0].size(); ++j){
            if(matrix[0][j] == 0){
                for(i = 1; i < matrix.size(); ++i)
                    matrix[i][j] = 0;
            }
        }
        
        if(firstRowSet)
            for(j = 1; j < matrix[0].size(); ++j)
                matrix[0][j] = 0;
        if(firstColSet)
            for(i = 1; i < matrix.size(); ++i)
                matrix[i][0] = 0;
    }
};

 

 

 

 

推荐阅读