当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.419.Battleships in a Board

LeetCode.419.Battleships in a Board


题目描述

Given an 2D board, count how many battleships are in it. The battleships are represented with ‘X’s, empty slots are represented with ‘.’s. You may assume the following rules:

  • You receive a valid board, made of only battleships or empty slots.
  • Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
  • At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example:

X..X
...X
...X

In the above board there are 2 battleships.
Invalid Example:

...X
XXXX
...X

This is an invalid board that you will not receive - as battleships will always have a cell separating between them.
Follow up:
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?


解题过程

这道题刚看的时候没思路,感觉挺复杂挺乱的,然后多读几遍题意,用测试用例试着分析分析,慢慢就有思路了。
题意就是有一个二维矩阵,计算里面连续的数列(1xN,Nx1)个数,数列只能是水平或垂直连续的,不会斜着出现,并且也不会有任意两个数列挨着。
解题思路最基本的是遍历二维矩阵遇到x就加1,但要排除连续数列的重复加1,什么情况下有连续数列呢?按从左到右、从上到下遍历来说,只能是当前位置左边或上边挨着已经有x的情况,所以再把排除情况考虑进去即可。

代码如下,满足一次遍历、O(1)额外空间、不修改原数组的进阶要求。但是效率不高,我多了一步,先加再减费时了,看别人提交的高效代码,思路是一样的,但稍微处理下能进一步缩短时间。

package _419_BattleshipsInBoard;

class Solution {
    public int countBattleships(char[][] board) {
        int count=0;
        for(int i=0; i<board.length; i++)
            for(int j=0; j<board[i].length; j++){
                if(board[i][j]=='X'){ //新出现x
                    count++; //先加1
                    if(j>=1 && board[i][j-1]=='X')//如果左边是x,不能重复计数,减1
                        count--;
                    if(i>=1 && board[i-1][j]=='X')//如果上边是x,不能重复计数,减1
                        count--;
                }
            }
        return count;
    }
}

public class BattleshipsInBoard {
    public static void main(String[] args){
        Solution solution = new Solution();
        char[][] board= {{'X','.','.','X'},{'.','.','.','X'},{'.','.','.','X'}};
        System.out.println(solution.countBattleships(board));
    }
}

GitHub代码


上一篇 LeetCode.191.Number of 1 Bits

下一篇 java.util.Arrays

阅读
580
阅读预计3分钟
创建日期 2018-01-12
修改日期 2018-01-12
类别
百度推荐