★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：为敢（WeiGanTechnologies）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10333099.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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) orNx1(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 }
请发表评论