• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode419. 甲板上的战舰 | Battleships in a Board

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:为敢(WeiGanTechnologies)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10333099.html
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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?


给定一个二维的甲板, 请计算其中有多少艘战舰。 战舰用 \'X\'表示,空位用 \'.\'表示。 你需要遵守以下规则:

  • 给你一个有效的甲板,仅由战舰或者空位组成。
  • 战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成,或者 Nx1 (N 行, 1 列)组成,其中N可以是任意大小。
  • 两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。

示例 :

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

在上面的甲板中有2艘战舰。

无效样例 :

...X
XXXX
...X

你不会收到这样的无效甲板 - 因为战舰之间至少会有一个空位将它们分开。

进阶:

你可以用一次扫描算法,只使用O(1)额外空间,并且不修改甲板的值来解决这个问题吗?


20ms

 1 class Solution {
 2     func countBattleships(_ board: [[Character]]) -> Int {
 3         
 4         var battle = 0
 5         
 6         for r in 0..<board.count{
 7             
 8             for c in 0..<board[0].count{
 9                 
10                 if board[r][c] == "X"{
11                     var cellLeft = "."
12                     var cellUp = "."
13                     if c > 0 {
14                         cellLeft = String(board[r][c-1])
15                     }
16                     if r > 0{
17                         cellUp = String(board[r-1][c])
18                     }
19                     
20                     if cellUp == "." && cellLeft == "."{
21                         battle += 1
22                     }
23                 }
24                 
25             }
26         }
27         
28         return battle
29     }
30 }

28ms

 1 class Solution {
 2     func countBattleships(_ board: [[Character]]) -> Int {
 3         guard !board.isEmpty && !board[0].isEmpty else {
 4             return 0
 5         }
 6 
 7         var board = board
 8         let xChar = Character("X")
 9         let dotChar = Character(".")
10         var result = 0
11         for row in 0..<board.count {
12             for column in 0..<board[0].count {
13                 let char = board[row][column]
14                 if char != xChar {
15                     continue
16                 }
17 
18                 board[row][column] = dotChar
19                 if row < board.count - 1 && board[row + 1][column] == xChar {
20                     var row2 = row + 1
21                     while row2 <= board.count - 1 && board[row2][column] == xChar {
22                         board[row2][column] = dotChar
23                         row2 += 1
24                     }
25                 } else if column < board[0].count - 1 && board[row][column + 1] == xChar {
26                     var column2 = column + 1
27                     while column2 <= board[0].count - 1 && board[row][column2] == xChar {
28                         board[row][column2] = dotChar
29                         column2 += 1
30                     }
31                 }
32                 
33                 result += 1
34             }
35         }
36 
37         return result
38     }
39 }

152ms

 1 class Solution {
 2     func countBattleships(_ board: [[Character]]) -> Int {
 3         let row = board.count
 4         guard row > 0 else {
 5             return 0
 6         }
 7         let column = board[0].count
 8         var num = 0
 9         
10         for i in 0..<row {
11             for j in 0..<column {
12                 if board[i][j] == "X" && (i == 0 || board[i - 1][j] != "X") && (j == 0 || board[i][j - 1] != "X") {
13                     num += 1
14                 }
15             }
16         }
17         return num
18     }
19 }

172ms

 1 class Solution {
 2     func countBattleships(_ board: [[Character]]) -> Int {
 3         var board = board
 4         if board.isEmpty || board[0].isEmpty {return 0}
 5         var m:Int = board.count
 6         var n:Int = board[0].count
 7         var res:Int = 0
 8         var visited:[[Bool]] = [[Bool]](repeating:[Bool](repeating:false,count:n),count:m)
 9         for i in 0..<m
10         {
11             for j in 0..<n
12             {
13                 if board[i][j] == "X" && !visited[i][j]
14                 {
15                     var vertical:Int = 0
16                     var horizontal:Int = 0
17                     dfs(&board, &visited, &vertical, &horizontal, i, j)
18                     if vertical == i || horizontal == j
19                     {
20                         res += 1
21                     }
22                 }                
23             }           
24         }
25         return res
26     }
27     
28     func dfs(_ board:inout [[Character]],_ visited:inout[[Bool]],_ vertical:inout Int,_ horizontal:inout Int,_ i:Int,_ j:Int)
29     {
30         var m:Int = board.count
31         var n:Int = board[0].count
32         if i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] == "."
33         {
34             return
35         }
36         vertical |= i
37         horizontal |= j
38         visited[i][j] = true
39         dfs(&board, &visited, &vertical, &horizontal, i - 1, j)
40         dfs(&board, &visited, &vertical, &horizontal, i + 1, j)
41         dfs(&board, &visited, &vertical, &horizontal, i, j - 1)
42         dfs(&board, &visited, &vertical, &horizontal, i, j + 1)
43     }
44 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode788.旋转数字|RotatedDigits发布时间:2022-07-13
下一篇:
[Swift]LeetCode130. 被围绕的区域 | Surrounded Regions发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap