leetcode419. Battleships in a Board

xiaokai 发布于2019-08-16 15:42 / 2188人阅读

摘要：题目要求假设有一个板，在板上用表示战舰，已知板上任意两个战舰体之间一定会用隔开，因此不会出现两个相邻的情况。现在要求用的时间复杂度和的空间复杂度来完成。战舰头即战舰的左侧和上侧没有其它的。

题目要求

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 0 && board[i-1][j] == "X") ||
                            (j > 0 && board[i][j-1] == "X")) {
                        continue;
                    }
                    count++;
                }
            }
        }
        return count;
    }

云服务器 GPU云服务器 Battleships Board Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73657.html

[LeetCode] 289. Game of Life

Problem According to the Wikipedias article: The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. Given a board with m ...

Ajian 2019-08-19 11:16 评论0 收藏0
【Leetcode】79.单词搜索

摘要：题目给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中相邻单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。题目给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中相邻单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允...

Caicloud 2019-08-19 11:16 评论0 收藏0
【Leetcode】79.单词搜索

摘要：题目给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中相邻单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。题目给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中相邻单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允...

ruicbAndroid 2019-07-30 17:57 评论0 收藏0
[LeetCode] 212. Word Search II

Problem Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where adjacent cells are those ...

Flands 2019-08-16 13:40 评论0 收藏0
[LeetCode] 37. Sudoku Solver

Problem Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row.Each ...

alaege 2019-08-19 11:14 评论0 收藏0