leetcode419. Battleships in a Board

xiaokai 發布于2019-08-16 15:42 / 2310人閱讀

摘要：題目要求假設有一個板，在板上用表示戰艦，已知板上任意兩個戰艦體之間一定會用隔開，因此不會出現兩個相鄰的情況。現在要求用的時間復雜度和的空間復雜度來完成。戰艦頭即戰艦的左側和上側沒有其它的。

題目要求

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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