新手问题 小菜鸟刷 LeetCode，第一道题就栽了。不过我怀疑是 LeetCode 解释器的问题
本人菜鸟一枚，今天刚刚开始刷 LeetCode 的算法题。打算从通过率最高的题开始刷，于是就选择了这一道： 把题目描述粘贴如下：
419. Battleships in a Board
Given an 2D board, count how many different 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 not a valid board - as battleships will always have a cell separating between them. Your algorithm should not modify the value of the board.
我一开始用了很多层 if 嵌套，大概写了 50 多行，通过了测试。后来转换思路，改进了一下程序，改进之后的代码如下：
def count_battleships(board)
count = 0
y = board[0].size
str = ""
board.each {|s| str << s.to_s}
str.size.times do |i|
if str[i] == "X" && (str[i+1] != "X" || (i+1)% y ==0) && str[i + y] != "X"
count += 1
end
end
return count
end
puts count_battleships(["X..X","...X","...X"])
奇怪的事情就在这时发生了，LeetCode OJ 上得到的结果是错误的，但是我在本地跑没问题，更奇怪的是，在 LeetCode 上 stdout 结果也是正确的，但是返回的结果就会自动乘以 2，我试了几个测试都是这样。截图如下。
我现在完全懵逼了，不知道是哪儿的问题，请大神指点。。
puts count_battleships(["X..X".split(''),"...X".split(''),"...X".split('')])
def count_battleships(board)
p board
end
Your stdout
[["X", ".", ".", "X"], [".", ".", ".", "X"], [".", ".", ".", "X"]]
因为 LeetCode 往你函数里输入的并不是 ['X..X','...X','...X'] 而是 [["X", ".", ".", "X"], [".", ".", ".", "X"], [".", ".", ".", "X"]]。
那个 Run Code Result 里会自动把 Input 的多维数组的第二维开始全部展开，非常迷。
count_battleships(%w(X..X ...X ...X)) # => 2
count_battleships([%w(X . . X), %w(. . . X), %w(. . . X)]) # => 4
在一开始 LeetCode 打给你的样例函数里
# @param {Character[][]} board
# @return {Integer}
def count_battleships(board)
end
就在注释里给你描述了参数是单字符组成的二维数组了。
另外被题主高超的数组下标加减法能力给搞晕了，一开始还没看懂代码到底在干什么。。。其实只要把 s.to_s 改成 s.join 就行了。
这个算法复杂度是 O(n) 的，理论上应该非常快，但是实测 109ms，比平均速度还要慢一些。因为为了能在一个字符串里操作，你把整个 board 重新生成了一遍。
花了五分钟，写了个 O(n) 的 DFS 解决方案，好久不写算法了，跑出来 75ms, beats 100.00% of ruby submissions。
# @param {Character[][]} board
# @return {Integer}
def count_battleships(board)
@board = board # Make it class visible for dfs to modify
@size_y = board.length
return 0 if @size_y == 0
@size_x = board[0].length
return 0 if @size_x == 0
count = 0
@size_y.times do |y|
@size_x.times do |x|
if @board[y][x] == 'X'
count += 1
dfs(x, y)
end
end
end
count
end
# Depth-first Search
def dfs(x, y)
return unless @board[y][x] == 'X'
@board[y][x] = '.' # Delete the pixel if searched
# Corner detection
dfs(x+1, y) unless x == @size_x - 1
dfs(x, y+1) unless y == @size_y - 1
end
不过其实可以不 DFS，按楼主扫一遍的思路的话，不操作数组也可以写，代码如下，
# @param {Character[][]} board
# @return {Integer}
def count_battleships(board)
board = board
size_y = board.length
return 0 if size_y == 0
size_x = board[0].length
return 0 if size_x == 0
count = 0
size_y.times do |y|
size_x.times do |x|
count += 1 if board[y][x] == 'X' && board[y][x+1] != 'X' && (board[y+1].nil? || board[y+1][x] != 'X')
end
end
count
end
跑出来也是 75ms, beats 100.00% of ruby submissions。复杂度一样的两个算法，DFS 那个会多写入和反复扫描几下，但会少判断几下，所以时间上总的来说是一样。