首页 > 代码库 > 战舰数量
战舰数量
版权声明：
本文由Faye_Zuo发布于http://www.cnblogs.com/zuofeiyi/, 本文可以被全部的转载或者部分使用，但请注明出处.
上周经历了人生中最艰辛的几天，所以刷题又耽误了3周多，今天重新开刷。又出现恍如隔世的感觉了！
来看看这道题：
Battleships in a Board(419)
一、我的思路：
1.初始化一个二维数组；
2.然后开始找字符x;
3.如果找到x,找它的邻居。
if(up down && no-left no-right) count++;
if(no-up no-down && left right) count++;
于是我按照自己的思路实现了一下程序，其实我知道我的思路是“暴力”的，当然程序跑起来了，但是结果千疮百孔。原因是我太多太多因素没有考虑到，这充分说明我的思路非常不缜密。并且我距离“算法”这两个字，还有好远好远！
但是进步的地方是，我至少有思路了，并且可以尝试写一下，并且跑起来了。
二、答案解析
此题用了一个很不错的技巧，他把战舰理解成蛇的样子，所以只找到top-left,也就是找到所谓蛇头。找到蛇头以后就可以找到蛇的数量了。
public class Battleship1 { public static void main(String[] args) { char[][] board = new char[][] { { ‘x‘, ‘.‘, ‘.‘, ‘x‘ }, { ‘.‘, ‘.‘, ‘.‘, ‘x‘ }, { ‘.‘, ‘.‘, ‘.‘, ‘x‘ } }; System.out.println("Battleship:" + Solution.countBattleships(board)); } public static class Solution { public static int countBattleships(char[][] board){ int count = 0; if (board == null || board.length == 0 || board[0].length == 0) { return 0; } for (int i = 0; i < board.length ; i++) { for (int j = 0; j < board[0].length; 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++; System.out.println("Battleship:"+count+"i="+i+","+"j="+j+","); } } return count; } } }
补充知识点：
continue:
在一个循环内部，如果执行完那个语句之后，continue；就不在执行本次循环内的continue之后的语句了。
三、题目变型
自己写一个简单的battleships,不过这个battleships是线性的，不是平面的。比如:…xxx.
运用上面的思路很快就写出来了。
public class battleShips1 { public static void main(String[] args) { char[] line={‘.‘,‘x‘,‘.‘,‘x‘,‘.‘,‘.‘,‘x‘,‘x‘}; System.out.println(Solution.countBattleships(line)); } public static class Solution{ public static int countBattleships(char[] line){ int count=0; if(line==null||line.length==0){ return 0; } for(int i=0;i<line.length;i++){ if(line[i]==‘.‘){ continue; } if(i>0&&line[i-1]==‘x‘){ continue; } count++; } return count; } } }
这道题这个算法非常的优秀，但是我短时间是不可能想到了。所以应该再多练习，我练习的题目还是太少太少了。我看了一下，leetcode现在只刷了11道。还差太远了！继续加油努力！不要想太多，学习本身其实也是一种幸福。
战舰数量
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。