前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode笔记:419. Battleships in a Board

LeetCode笔记:419. Battleships in a Board

作者头像
Cloudox
发布2021-11-23 15:53:40
3020
发布2021-11-23 15:53:40
举报
文章被收录于专栏:月亮与二进制月亮与二进制

问题:

Given an 2D board, count how many different 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:

In the above board there are 2 battleships. Invalid Example:

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’表示,空地由‘.’表示。你可以假设满足下面的规则:

  • 你会接受到一个有效的面板,只由战舰和空地组成。
  • 战舰只能是水平的或者垂直的。也就是说,只能是 1xN(一行N列)或者 Nx1(N行一列)的形状,N可以是任何尺寸。
  • 两个战舰之间至少有一个空地 - 没有相连的战舰。 例子:

上面的面板上有两艘战舰。 无效的例子:

这是一个无效的面板,你不会接受到 - 因为两艘战舰一定会有空白的点。 进阶: 你能不能使用O(1)的内存,并且不修改面板的值来完成?

思路:

这道题的情景很像我们玩的战船游戏,所以做起来也很有意思。

我们最好从左上角开始,遍历每个点,如果有X,就看它往右和往下有没有相邻的X,有的话也算做一艘战舰。已经检查过的点我们就不检查了,所以用一个二维数组来记录检查过的点。

代码(Java):

代码语言:javascript
复制
public class Solution {
    public int countBattleships(char[][] board) {
        int result = 0;
        // 用来记录有没有判断过
        int[][] tempBoard = new int[board.length][board[0].length];
        for (int i = 0; i < tempBoard.length; i++) {
            for (int j = 0; j < tempBoard[0].length; j++) tempBoard[i][j] = 0;
        }
        
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (tempBoard[i][j] == 0) {
                    if (board[i][j] - 'X' == 0) {
                        System.out.println(i + " " + j);
                        if (j+1 < board[0].length && board[i][j+1] - 'X' == 0) {// 竖向战舰
                            for (int k = j+1; k < board[0].length; k++) {
                                if (board[i][k] - 'X' == 0) tempBoard[i][k] = 1;
                                else break;
                            }
                        } else if (i+1 < board.length && board[i+1][j] - 'X' == 0) {// 横向战舰
                            for (int k = i+1; k < board.length; k++) {
                                if (board[k][j] - 'X' == 0) tempBoard[k][j] = 1;
                                else break;
                            }
                        }
                        
                        tempBoard[i][j] = 1;
                        result ++;
                    }
                }
            }
        }
        
        return result;
    }
}

他山之石:

代码语言:javascript
复制
    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;
    }

上面我的做法其实用了O(n)的内存,而且要进行多次循环,很耗时,这个就简单多了,每次遇到一个坐标,如果它既不是空地,他的上面和左边也没有X,那就说明这是一个新战舰,只记录这种新战舰的个数,很节省空间和时间。

合集:https://github.com/Cloudox/LeetCode-Record

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017/11/23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题:
  • 大意:
  • 思路:
  • 代码(Java):
  • 他山之石:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档