419. 甲板上的战舰

快评

题目的背景是海战棋:http://zh.battleship-game.org/

解题思路

  1. 先从左到右逐行扫描,遇到无相邻行区域(连续1格或更多)则计入1艘军舰,注意处理边缘;
  2. 先从上到下逐列扫描,遇到无相邻行区域(连续2格或更多,因为1格的情况已经在第1点计入过,所以不能重复计算)则计入1艘军舰,注意处理边缘;

时间复杂度O(N),N=m*n(矩形面积);空间复杂度O(1),常数空间即可处理。

image.png

还有一种更快的一次扫描做法:枚举起点,符合题意的军舰左上角必为空(超出棋盘亦视为空)。

代码

func countBattleships(board [][]byte) int {
    result := 0
    count := 0

    in_ship := false
    for i, row := range board{
        for j := range row{
            if (board[i][j]=='X') && (i-1<0||board[i-1][j]=='.') && (i+1==len(board)||board[i+1][j]=='.'){
                if in_ship==false{
                    in_ship=true
                }
            }else{
                if in_ship==true{
                    in_ship=false
                    result++
                }
            }
        }
        if in_ship==true{
            result++
        }
        in_ship=false
    }

    for j:=0;j<len(board[0]);j++{
        for i:=0;i<len(board);i++{
            if (board[i][j]=='X') && (j-1<0||board[i][j-1]=='.') && (j+1==len(board[0])||board[i][j+1]=='.'){
                if in_ship==false{
                    in_ship=true
                }
                count++
            }else{
                if in_ship==true{
                    in_ship=false
                    if count>1{
                        result++
                    }
                    count=0
                }
            }
        }
        if in_ship==true && count>1{
            result++
        }
        in_ship=false
        count=0
    }

    return result
}

类似文章

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注