程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode]Surrounded Regions,解題報告

[LeetCode]Surrounded Regions,解題報告

編輯:C++入門知識

[LeetCode]Surrounded Regions,解題報告


目錄

目錄 前言 題目 思路1_DFS 思路2_BFS


前言

最近這兩天為了解決Android Rom適配一個底層的問題,天天熬夜到2點,導致原定了LeetCode刷題計劃都受到了影響。昨晚終於熬夜搞定,補充一道LeetCode解題報告。


題目

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


思路1_DFS

這道題目給出的提示是用廣度優先搜索(BFS),但是我憋了半天沒思路,因為平時我一般都是用BFS解決一些迷宮的題目。

於是,我還是想到換個思路,既然BFS不行,那就DFS(深度優先搜索)。思路如下:

最外層如果有‘O’的存在,那它一定不會被‘X’包圍的。這時需要遍歷board二維數組的最外層,需要4次for循環。 每次最外層遍歷的過程中,如果發現有‘O’,那我們可以嘗試進行上下左右四個方向的遍歷,如果再次發現有’O’,那當前的‘O’也是不會被‘X’包圍的,將這種‘O’轉換為‘K’。DFS的過程。 4次遍歷完成後,需要再次遍歷board數組。數組元素不為‘K’的都應該是被‘X’包圍的,因此統一改為‘X’。為‘K’的不要忘記要改回為‘O’。

DFS代碼如下:

public class Solution {
    private static int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static void solve(char[][] board) {
        int row = board.length;
        if (row < 2) {
            return ;
        }

        int column = board[0].length;
        if (column < 2) {
            return;
        }


        for (int j = 0; j < board[0].length; j ++) {
            if (board[0][j] == 'O') {
                dfsBoard(board, 0, j);
            }
        }

        for (int i = 1; i < board.length; i ++) {
            if (board[i][column - 1] == 'O') {
                dfsBoard(board, i, column - 1);
            }
        }

        for (int j = column - 2; j >= 0; j --) {
            if (board[row - 1][j] == 'O') {
                dfsBoard(board, row - 1, j);
            }
        }

        for (int i = row - 2; i >= 0; i --) {
            if (board[i][0] == 'O') {
                dfsBoard(board, i, 0);
            }
        }


        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < column; j ++) {             
                board[i][j] = board[i][j] == 'K' ? 'O' : 'X';
            }
        }
    }

    private static void dfsBoard(char[][] board, int x, int y) {        
        board[x][y] = 'K';
        for (int i = 0; i < directions.length; i ++) {
            int new_x = x + directions[i][0];
            int new_y = y + directions[i][1];
            if (new_x < 0 || new_x >= board.length || new_y < 0 || new_y >= board[0].length || board[new_x][new_y] != 'O') {
                continue;
            }
            dfsBoard(board, new_x, new_y);
        }
    }
}

本來以為結果會TLE,沒想到出乎我的意料,結果是Runtime Error,遞歸棧被爆掉了。

stack overflow error


思路2_BFS

DFS爆棧充分說明題目的提示還是很管用的,必須要用BFS啊。但是,上面DFS的方法給我們提供了很好的思路。爆棧的原因是:DFS棧深度不夠,那我們直接將這裡的DFS遍歷換成BFS不就可以了。

思路更改的地方:

每次最外層遍歷的過程中,如果發現有‘O’,那我們可以嘗試進行上下左右四個方向的遍歷,如果再次發現有’O’,將當前節點放入隊列中。放入隊列中的‘O’也是不會被‘X’包圍的,將這種‘O’轉換為‘K’即可。(ps:其實就是將棧實現改為隊列實現)

直接上AC代碼了:

public class Solution {
    private static class BoardPoint {
        private int x, y;

        public BoardPoint(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }

    private static int[][] directions = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    public static void solve(char[][] board) {
        int row = board.length;
        if (row < 2) {
            return;
        }

        int column = board[0].length;
        if (column < 2) {
            return;
        }

        for (int j = 0; j < board[0].length; j++) {
            if (board[0][j] == 'O') {
                bfsBoard(board, 0, j, row, column);
            }
        }

        for (int i = 1; i < board.length; i++) {
            if (board[i][column - 1] == 'O') {
                bfsBoard(board, i, column - 1, row, column);
            }
        }

        for (int j = column - 2; j >= 0; j--) {
            if (board[row - 1][j] == 'O') {
                bfsBoard(board, row - 1, j, row, column);
            }
        }

        for (int i = row - 2; i >= 0; i--) {
            if (board[i][0] == 'O') {
                bfsBoard(board, i, 0, row, column);
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                board[i][j] = board[i][j] == 'K' ? 'O' : 'X';
            }
        }
    }

    private static void bfsBoard(char[][] board, int x, int y, int row, int col) {
        ArrayDeque queue = new ArrayDeque();
        queue.push(new BoardPoint(x, y));
        while (!queue.isEmpty()) {
            BoardPoint point = queue.poll();
            board[point.getX()][point.getY()] = 'K';

            for (int i = 0; i < directions.length; i++) {
                int new_x = point.getX() + directions[i][0];
                int new_y = point.getY() + directions[i][1];

                if (new_x >= 0 && new_x < row && new_y >= 0 && new_y < col && board[new_x][new_y] == 'O') {
                    queue.push(new BoardPoint(new_x, new_y));
                }
            }
        }
    }

}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved