BattleshipsInABoard [source code]
public class BattleshipsInABoard {
static
/******************************************************************************/
public class Solution {
public int countBattleships(char[][] board) {
int m = board.length;
int n = board[0].length;
boolean[] memo = new boolean[n];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; ) {
if (board[i][j] == 'X') {
if (memo[j])
j += 2;
else if (j >= 1 && board[i][j - 1] == 'X') {
memo[j - 1] = false;
memo[j] = false;
j++;
} else {
memo[j] = true;
j++;
}
} else {
if (memo[j]) {
count++;
memo[j] = false;
}
if (j >= 1 && board[i][j - 1] == 'X' && !memo[j - 1]) {
count++;
memo[j] = false;
}
j++;
}
}
if (n >= 2 && board[i][n - 1] == 'X' && board[i][n - 2] == 'X')
count++;
}
for (boolean b : memo)
if (b)
count++;
return count;
}
}
/******************************************************************************/
public static void main(String[] args) {
BattleshipsInABoard.Solution tester = new BattleshipsInABoard.Solution();
String[] inputs = {
"X..X" +
"...X" +
"...X", "3", "4", "2",
"XX.X" +
"...X" +
"...X", "3", "4", "2",
"XX.X" +
"...X" +
".X.X", "3", "4", "3",
"", "0", "0", "0",
".X..X" +
".X..X" +
"....X" +
"X.XX." +
"X...X", "5", "5", "5",
};
for (int i = 0; i < inputs.length / 4; i++) {
char[][] board = buildBoard(inputs[4 * i], Integer.parseInt(inputs[1 + 4 * i]), Integer.parseInt(inputs[2 + 4 * i]));
int expected = Integer.parseInt(inputs[3 + 4 * i]);
System.out.println(Printer.seperator());
int output = tester.countBattleships(board);
System.out.println(Printer.wrapColor(Matrix.printMatrix(board), "magenta") + " -> " + output + Printer.wrapColor(", expected: " + expected, output == expected ? "green" : "red"));
}
}
public static char[][] buildBoard(String board, int m, int n) {
if (board.length() == 0) return new char[][]{{}};
char[] chs = board.toCharArray();
char[][] res = new char[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res[i][j] = chs[i * n + j];
}
}
return res;
}
}
其实之前的分段算法也算作是一个historical stream算法: 当你走到一个entry的时候, 你手上的信息就是
- 当前的entry
- 历史信息, 这里就是一个flag;
有些历史信息类算法的逻辑并非是那么好写, 主要是因为需要考虑的branch很多; 之前有一题总结过一个思路, 就是一个最简单的思路就是直接branch on current entry; 用这种方法写出来的逻辑不一定是最简练的, 但是肯定能够写出来一个对的;
但是这个逻辑方式其实也是有陷阱的, 这里第五个case就被坑了: 这个逻辑方式的特点是所有的branch(distinguished by entry value), 以及其内部的sub-branch(usually distinguished by flags/historical information)之间全部都是distinct的; 但是实际的情况是, 某一个entry, 是可能同时触发/符合两种情况的.
这个是我在entry false的branch一开始的代码:
else {
if (memo[j]) {
count++;
memo[j] = false;
j++;
} else if (j >= 1 && board[i][j - 1] == 'X' && !memo[j - 1]) {
count++;
memo[j] = false;
j++;
} else j++;
}
这个代码就是犯了这个错误. 这里的两个subbranch其实是分别判断current entry是vertical和horizontal两个方向上的run的termination. 一个没有意识到的问题是, 这两个方向上的run(for those both ending at this entry)之间是互相independent的, 所以这两者之间一个势不两立的对立关系, 用elif来做就不太好. 这里只好把逻辑改成conditional overridding的思路来做;
没有想到最后这个笨办法居然也这么麻烦; 我这个最后并没有做到O(1) space, 而且最后的速度是4ms (33%), 也不算优秀, 这个问题感觉还是没有想到最好的思路;
不过写过这么一个复杂的历史信息算法, 还是很大的锻炼;
不过最后这个算法只做到了O(N^2)的时间, 和O(N)的空间, 不够达到Follow-Up的要求;
这个问题其实我还是想的太复杂了, 套在了historicla stream算法的套子里就没有想出来;
这个是discussion的最优解:
Going over all cells, we can count only those that are the "first" cell of the battleship. First cell will be defined as the most top-left cell. We can check for first cells by only counting cells that do not have an 'X' to the left and do not have an 'X' above them.
public int countBattleships(char[][] board) {
int m = board.length;
if (m==0) return 0;
int n = board[0].length;
int count=0;
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (board[i][j] == '.') continue;
if (i > 0 && board[i-1][j] == 'X') continue;
if (j > 0 && board[i][j-1] == 'X') continue;
count++;
}
}
return count;
}
可以看到这个题目其实真的比我想的要简单的多. 这种count类问题我还是不够熟练; 之前那个island的问题的时候就做的不是很好; 当时好像也是想要用historial stream来做, 结果越写越复杂, 最后发现根本做不出来; 这题也是, 历史信息流算法要复杂的多;
而如果看清问题的本质, 就是一个数数问题, 会发现核心算法并不那么难;
话虽然这么说, counting这个本身也并不是一个就一定很简单的事情, 在counting的过程中还是有很多技巧和heuristic需要总结的.
count当中一个重要的问题就是怎么避免重复; 一般的思路, 比如是impose order, 不过这种heuristic真正具化到一个实际的问题上的时候, 并没有那么简单就可以应用的起来; 其实425当时也涉及到了很多这种问题的思考, 比如让你数tile什么的, 也都是要找到一个代表点, 或者基点作为每一个tile的id一样; 这里的这个做法也是这样, 就是纯粹按照counting的思路来想, 不要去套什么历史信息流的思路, 就可以了;
现在想想425上面学的很多东西还是真的很有用的;
他这个算法应该是达到了Follow-Up的要求了;
另外这个解好像就是submission上面的最优解, 比我的这个快1ms;
反正怎么说呢, 这个问题最后的教训就是, 首先要识别不同的问题套路, 不要什么问题来了, 尤其是要求你O(N)time的话, 上来就是只会用历史信息流来做, 有些不同的问题有不同的思考套路, 比如这一题, 就属于counting类; 其次就是, 咱们这次做了一个过于复杂的解, 也不丢人, 算是对于历史信息流算法的重温;
另外以上的代码是没有被简写过的, 就是因为不鼓励Premature Optmization, 不过这里给出一个稍微缩短了一点的版本:
public class Solution {
public int countBattleships(char[][] board) {
int m = board.length, n = board[0].length, count = 0;
boolean[] memo = new boolean[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; ) {
if (board[i][j] == 'X') {
if (memo[j]) j += 2;
else if (j >= 1 && board[i][j - 1] == 'X') {
memo[j - 1] = false;
memo[j++] = false;
} else memo[j++] = true;
} else {
if (memo[j]) {
count++;
memo[j] = false;
}
if (j >= 1 && board[i][j - 1] == 'X' && !memo[j - 1]) {
count++;
memo[j] = false;
}
j++;
}
}
if (n >= 2 && board[i][n - 1] == 'X' && board[i][n - 2] == 'X') count++;
}
for (boolean b : memo) if (b) count++;
return count;
}
}
Problem Description
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?
Difficulty:Medium
Total Accepted:26K
Total Submissions:42.2K
Contributor: ben65
Companies
microsoft