資訊專欄INFORMATION COLUMN
摘要：題目要求假設(shè)有一個板，在板上用表示戰(zhàn)艦，已知板上任意兩個戰(zhàn)艦體之間一定會用隔開，因此不會出現(xiàn)兩個相鄰的情況?，F(xiàn)在要求用的時間復(fù)雜度和的空間復(fù)雜度來完成。戰(zhàn)艦頭即戰(zhàn)艦的左側(cè)和上側(cè)沒有其它的。
題目要求
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?
假設(shè)有一個2D板，在板上用X表示戰(zhàn)艦，已知板上任意兩個戰(zhàn)艦體之間一定會用.隔開，因此不會出現(xiàn)兩個X相鄰的情況?，F(xiàn)在要求用O(N)的時間復(fù)雜度和O(1)的空間復(fù)雜度來完成。
思路和代碼這題的思路非常清晰，我們只需要判斷哪個X是戰(zhàn)艦頭即可，當(dāng)我們遇到戰(zhàn)艦頭時，就將總戰(zhàn)艦數(shù)加一，其余時候都繼續(xù)遍歷。戰(zhàn)艦頭即戰(zhàn)艦的左側(cè)和上側(cè)沒有其它的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;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/73657.html
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 ...
摘要：題目給定一個二維網(wǎng)格和一個單詞，找出該單詞是否存在于網(wǎng)格中。單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中相鄰單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允許被重復(fù)使用。 題目 給定一個二維網(wǎng)格和一個單詞，找出該單詞是否存在于網(wǎng)格中。 單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中相鄰單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允...
摘要：題目給定一個二維網(wǎng)格和一個單詞，找出該單詞是否存在于網(wǎng)格中。單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中相鄰單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允許被重復(fù)使用。 題目 給定一個二維網(wǎng)格和一個單詞，找出該單詞是否存在于網(wǎng)格中。 單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中相鄰單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允...
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 ...
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 ...
閱讀 2497·2023-04-25 19:24
閱讀 1716·2021-11-11 16:54
閱讀 2842·2021-11-08 13:19
閱讀 3556·2021-10-25 09:45
閱讀 2563·2021-09-13 10:24
閱讀 3293·2021-09-07 10:15
閱讀 4046·2021-09-07 10:14
閱讀 2962·2019-08-30 15:56
