首页 > 代码库 > 战舰数量

战舰数量

版权声明:

    本文由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道。还差太远了!继续加油努力!不要想太多,学习本身其实也是一种幸福。

 

战舰数量