新手问题 小菜鸟刷 LeetCode,第一道题就栽了。不过我怀疑是 LeetCode 解释器的问题

ca01ei · 2016年10月27日 · 最后由 ca01ei 回复于 2016年10月30日 · 4458 次阅读

本人菜鸟一枚,今天刚刚开始刷 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) 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 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,我试了几个测试都是这样。截图如下。

我现在完全懵逼了,不知道是哪儿的问题,请大神指点。。

求救!!有人来帮帮我么。

https://leetcode.com/faq/ 你看他们的解释器版本,本机上可以装一个试一试。

把你puts那句去掉试试

#3 楼 @piecehealth puts 我是为了验证值加上的,去掉也不对。。

@ca01ei

puts count_battleships(["X..X".split(''),"...X".split(''),"...X".split('')])

#2 楼 @pengedy 谢谢指导,但是貌似不是版本的问题,我试了一下,换上 LeetCode 的版本,还是不行。

没问题的呀

#6 楼 @ca01ei 我是说,LeetCode 上的 input 是使用二维数组的,运行我上面的代码,你函数的结果就得到 4 了

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 那个会多写入和反复扫描几下,但会少判断几下,所以时间上总的来说是一样。

#10 楼 @dsh0416 原来是二元数组的问题,多谢解答,很详细。受益匪浅。

ca01ei 关闭了讨论。 12月05日 15:11
需要 登录 后方可回复, 如果你还没有账号请 注册新账号