文档章节

LeetCode——419. Battleships in a Board

守恒的猫
 守恒的猫
发布于 2017/04/01 15:55
字数 564
阅读 50
收藏 0

题型:DFS

题目:

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?

 

Subscribe to see which companies asked this question.

 

翻译(抄的):

给定一个2维板,计算其中包含多少艘不同的战舰。战舰用字符'X'表示,空白槽位用'.'表示。你应该假设如下规则:

  • 给定的板子是有效的,只包含战舰和空白槽位。
  • 战舰只能水平或者竖直放置。
  • 战舰的尺寸可能不同。
  • 两艘战舰之间在水平方向或者竖直方向至少包含一个空间—不会存在相邻的战舰。

你的算法不应该修改board的值。

 

思路:

一种思路是简单遍历,因为题目给了方便,战舰之间没有相邻的(这里要理解,战舰是1-N个X组成,而不是一个)

 

另一种思路是DFS深搜,概括来讲就是对每一个点去深搜遍历它所有的相邻点,通过一个set来维护遍历过的点,这样每一个点可以得到它相邻的所有点,即一艘战舰,再检查下一个点就可以先判断在不在set里,是不是已经属于统计过的某个战舰了。

 

代码(python):

class Solution(object):
    def countBattleships(self, board):
        """
        :type board: List[List[str]]
        :rtype: int
        """
        found_set = set()
        ans = 0
        row_len = len(board)
        col_len = len(board[0] if row_len else [])
        def dfs(x, y):
            for movex, movey in zip((1,0,-1,0),(0,1,0,-1)):
                nx, ny = x + movex, y + movey
                if 0 <= nx < row_len and 0 <= ny < col_len:
                    if (nx,ny) not in found_set and board[nx][ny] == 'X':
                        found_set.add((nx, ny))
                        dfs(nx,ny)
                        
        for x in xrange(row_len):
            for y in xrange(col_len):
                if board[x][y] == 'X' and (x,y) not in found_set:
                    ans += 1
                    found_set.add((x,y))
                    dfs(x,y)
        return ans

 

A掉

© 著作权归作者所有

共有 人打赏支持
守恒的猫
粉丝 5
博文 42
码字总数 58827
作品 0
房山
私信 提问
计算战舰的个数 Battleships in a Board

问题: Given an 2D board, count how many battleships are in it. The battleships are represented with s, empty slots are represented with s. You may assume the following rules: Y......

叶枫啦啦
2018/01/04
0
0
HDU 6138 Fleet of the Eternal Throne 后缀数组+字典树

Fleet of the Eternal Throne Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 461 Accepted Submission(s): 141 Problem Descrip......

ProLightsfxjh
2017/08/19
0
0
nomasp 博客导读:Lisp/Emacs、Algorithm、Android

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/44966625 Profile Introduction to Blog 您能看到这篇博客导读...

nomasp
2015/09/17
0
0
双人网络舰船游戏--Java Battleships

Java Battleships是一个双人网络游戏。它包括的舰船有驱逐舰,扫雷艇和鱼雷船。每种舰船有不同的武器,运动方式,装甲和雷达。你必须在C:BATTLESHIPS下运行server.bat,再运行gui.bat。...

匿名
2009/07/21
2.4K
0
[LeetCode] Word Search

★ 题目 https://leetcode.com/problems/word-search/ Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially ad......

u013553529
2018/01/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

js算法总结

数列求和 等差数列求和 function sum(a0,d,n){//a0->首项,d->公差,n->项数//(首项+末项)*项数/2return (a1+(a1+d*n))*n/2;} 等比数列求和 function sum(a0,q,n){//a0->首项,q->公......

祖达
33分钟前
1
0
小白?转型?毕业生?外行学习快速入行大数据开发指南

这篇文章中,本文将针对三种不同的、想要进入数据科学领域的人群,给出自己的经验,帮助他们迅速有效入行。 虽然没有适合每个人的万能解决方案,但这三类建议值得想转行的你一看。 第1类:新...

董黎明
40分钟前
1
0
好文 | MySQL 索引B+树原理,以及建索引的几大原则

MySQL事实上使用不同的存储引擎也是有很大区别的,下面猿友们可以了解一下。 一、存储引擎的比较 注:上面提到的B树索引并没有指出是B-Tree和B+Tree索引,但是B-树和B+树的定义是有区别的。 ...

Java爬坑之路
44分钟前
1
0
mysql group by 和 Order By 执行顺序

1.在写统计的时候,我们会用到统计首单,这样里面设计到排序。写子查询的方式当然可以实现, 但是我们有时候,需要创建视图,视图不支持带子查询的。 加了排序后会返回,排序后的哪个第一条数...

kuchawyz
48分钟前
2
0
Spring Boot 2.X 如何添加拦截器?

最近使用SpringBoot2.X搭建了一个项目,大部分接口都需要做登录校验,所以打算使用注解+拦截器来实现,在此记录下实现过程。 一、实现原理 1. 自定义一个注解@NeedLogin,如果接口需要进行登...

花漾年华
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部