专栏首页眯眯眼猫头鹰的小树杈leetcode419. Battleships in a Board

leetcode419. Battleships in a Board

题目要求

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?

假设有一个2D板,在板上用X表示战舰,已知板上任意两个战舰体之间一定会用.隔开,因此不会出现两个X相邻的情况。现在要求用O(N)的时间复杂度和O(1)的空间复杂度来完成。

思路和代码

这题的思路非常清晰,我们只需要判断哪个X是战舰头即可,当我们遇到战舰头时,就将总战舰数加一,其余时候都继续遍历。战舰头即战舰的左侧和上侧没有其它的X

    public int countBattleships(char[][] board) {
        int count = 0;
        if(board == null || board.length == 0 || board[0].length == 0) return count;
        for(int i = 0 ; i<board.length ; i++) {
            for(int j = 0 ; j<board[i].length ; j++) {
                if(board[i][j] == 'X') {
                    if((i > 0 && board[i-1][j] == 'X') ||
                            (j > 0 && board[i][j-1] == 'X')) {
                        continue;
                    }
                    count++;
                }
            }
        }
        return count;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode529. Minesweeper

    Let's play the minesweeper game (Wikipedia),online game)!

    眯眯眼的猫头鹰
  • leetcode446. Arithmetic Slices II - Subsequence

    从一个无序的整数数组中,找到所有等差子数列的数量。这里需要注意,等差子数列要求从原数组中找出Pk个下标的元素,其中P0 < P1 < P2... < Pk,且满...

    眯眯眼的猫头鹰
  • 猫头鹰的深夜翻译:分布式系统Toolkit模式

    过去几年容器逐渐成为了打包和部署代码的流行的方式。容器镜像解决很多现有的打包和部署工具所带来的问题,初次以外,还为我们提供了构建分布式应用的全新的思路。就如SO...

    眯眯眼的猫头鹰
  • python 实现 2048 游戏 (二)

    上一篇文章中,我们梳理了实现简易版 2048 游戏的基本知识,这篇文章将介绍如何实现各个模块。换句话说,上一次我们确定了旅行的目的地,这一次就让我们自由畅行在山...

    用户2870857
  • leetcode: 37. Sudoku Solver

    …and its solution numbers marked in red.

    JNingWei
  • Swift 有效的数独 - LeetCode

    判断一个数独是否有效,根据:Sudoku Puzzles - The Rules。 (数独规则: 每一行不能有重复的数字;每一列不能有重复的数字;将数独框划分...

    韦弦zhy
  • java 并发编程基础

    总线(Bus)是计算机各种功能部件之间传送信息的公共通信干线,它是由导线组成的传输线束, 按照计算机所传输的信息种类,计算机的总线可以划分为数据总线、地址总线和...

    CoffeeLand
  • 2018最新区块链白皮书大全

    用户1408045
  • JDBC注册驱动程序三种方式

    一、DriverManager.registerDriver(new com.microsoft.sqlserver.jdbc.SQLServerDriver...

    用户2192970
  • Flink的DataSource三部曲之三:自定义

    本文是《Flink的DataSource三部曲》的终篇,前面都是在学习Flink已有的数据源功能,但如果这些不能满足需要,就要自定义数据源(例如从数据库获取数据...

    程序员欣宸

扫码关注云+社区

领取腾讯云代金券