GuilinDev

Lc0419

05 August 2008

419 Battleships in a Board

计算二维数组上可以放多少个X - 修改值

值修改

具体做法,根据从左到右和从上到下的顺序遍历数组,碰到字符为’X’则向下或向右寻找,直到找不到’X’,并且把走过的点都重置为’.’

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    private int rows;
    private int cols;

    public int countBattleships(char[][] board) {
        if (board == null || board.length == 0) return 0;
        rows = board.length;
        cols = board[0].length;
        int sum = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if ('X' == board[i][j]) {
                    //由于战舰只能水平或者垂直放置,所以可以先确定下方向
                    if (j + 1 < cols && board[i][j + 1] == 'X') {
                        search(board, i, j, false);
                    } else if (i + 1 < rows && board[i + 1][j] == 'X') {
                        search(board, i, j, true);
                    }
                    sum++;
                }
            }
        }
        return sum;
    }

    private void search(char[][] board, int i, int j, boolean isVertical) {
        if (i == rows || j == cols || board[i][j] == '.') return;
        board[i][j] = '.';
        if (isVertical) {
            search(board, i + 1, j, isVertical);
        } else {
            search(board, i, j + 1, isVertical);
        }
    }
}

进阶

  上面的写法虽然完成了题目要求,但进阶要求是不修改并且在O(1)额外空间内完成。

  现在第一种做法虽然空间使用了O(1)但没有达到不修改甲板值的效果,可以稍微对上面的算法进行改进,将改值部分去掉,然后碰到’X’时,检查上方或左方是否有’X’,若存在,就代表已经计数过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    private int rows;
    private int cols;

    public int countBattleships(char[][] board) {
        if (board == null || board.length == 0) {
            return 0;
        }
        rows = board.length;
        cols = board[0].length;
        int sum = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if ('X' == board[i][j]) {
                    if (search(board, i - 1, j) && search(board, i, j - 1)) {
                        sum++;
                    }
                }
            }
        }
        return sum;
    }

    private boolean search(char[][] board, int i, int j) {
        if (i == -1 || j == -1 || board[i][j] == '.') return true;
        return board[i][j] != 'X';
    }
}