419. 甲板上的战舰 Medium

2024-06-12 01:20
文章标签 战舰 419 medium 甲板

本文主要是介绍419. 甲板上的战舰 Medium,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给你一个大小为 m x n 的矩阵 board 表示甲板,其中,每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ,返回在甲板 board 上放置的 战舰 的数量。

战舰 只能水平或者垂直放置在 board 上。换句话说,战舰只能按 1 x k1 行,k 列)或 k x 1k 行,1 列)的形状建造,其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 (即没有相邻的战舰)。

示例 1:

输入:board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出:2

示例 2:

输入:board = [["."]]
输出:0

提示:

 ·m == board.length

 ·n == board[i].length

 ·1 <= m, n <= 200

 ·board[i][j] 是 '.' 或 'X'

进阶:你可以实现一次扫描算法,并只使用 O(1) 额外空间,并且不修改 board 的值来解决这个问题吗?

题目大意:在不修改board的情况下计算甲板上的战舰个数。

分析:在扫描过程中,必定先扫描到一艘船的左上角的'X'。因此若扫描到的'X'的左边或者上边还有'X',则说明这艘船已经被扫描过了,不必增加战舰个数;否则说明这个'X'是该船的左上角,该船第一次被扫描到,战舰个数+1。

class Solution {
public:int countBattleships(vector<vector<char>>& board) {int M=board.size(),N=board[0].size(),ans=0;for(int i=0;i<M;++i){for(int j=0;j<N;++j){if(board[i][j]=='X'&&(!i||board[i-1][j]!='X')&&(!j||board[i][j-1]!='X')){++ans;}}}return ans;}
};

这篇关于419. 甲板上的战舰 Medium的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1052794

相关文章

Leetcode 152. 乘积最大子数组(Medium)

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续  子数组 (该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 示例 1: 输入: nums = [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。 示例 2: 输入: nums = [-2,0,-1]输出: 0解释: 结果不能为 2,

Linux 挂载须知: mount 一些小问题 mount: no medium found on /dev/sr0

我属于window+VM+ubuntu的配置,有时需要把windows上的文件,挂载到虚拟机上去。然后每次使用命令的时候会出现如下的问题:                其实解决问题很简单,但是由于我自己的粗心而花费了很长的时间:    这个时候一定要确认,虚拟机的设置处是否勾选了   具体如下图所示:                 然后按照  如下的命令:   mount

[Meachines] [Medium] Lightweight LDAP密码嗅探+TRP00F 自动化权限提升+openssl 权限提升

信息收集 IP AddressOpening Ports10.10.10.119TCP:22,80,389 $ nmap -p- 10.10.10.119 --min-rate 1000 -sC -sV PORT STATE SERVICE VERSION22/tcp open ssh OpenSSH 7.4 (protocol 2.0)| ssh-hostkey:|

海力士A-DIE颗粒内存条震撼发布:毁灭者星际战舰DDR5内存条登场

**海力士A-DIE颗粒内存条震撼发布:毁灭者星际战舰内存条登场** 近日,海力士正式发布了全新一代A-DIE颗粒内存条——毁灭者星际战舰DDR5 7200RGB电竞内存条。这款内存条凭借其卓越的性能和先进的技术,成为数码爱好者关注的焦点。 导语: 海力士在内存领域一直保持着领先地位,此次发布的毁灭者星际战舰内存条,更是其技术创新的结晶。该产品采用了最新的A-DIE颗粒技术,旨在

[Meachines] [Medium] Bitlab 标签自动填充登录+GitLab+Docker横向+Postgresql+逆向工程

信息收集 IP AddressOpening Ports10.10.10.114TCP:22,80 $ nmap -p- 10.10.10.114 --min-rate 1000 -sC -sV PORT STATE SERVICE VERSION22/tcp open ssh OpenSSH 7.6p1 Ubuntu 4ubuntu0.3 (Ubuntu Linux; pr

[Meachines] [Medium] SecNotes XSRF跨站请求伪造+SMB-Webshell上传+Linux子系统命令历史记录泄露权限提升

信息收集 IP AddressOpening Ports10.10.10.97TCP:80,445,8808 $ nmap -p- 10.10.10.97 --min-rate 1000 -sC -sV PORT STATE SERVICE VERSION80/tcp open http Microsoft IIS httpd 10.0| http

[Meachines] [Medium] Bastard Drupal 7 Module Services-RCE+MS15-051权限提升

信息收集 IP AddressOpening Ports10.10.10.9TCP:80,135,49154 $ nmap -p- 10.10.10.9 --min-rate 1000 -sC -sV PORT STATE SERVICE VERSION80/tcp open http Microsoft IIS httpd 7.5| http-methods:

[Leetcode 230][Medium] 二叉搜索树中第 K 小的元素-大根堆/优先队列/DFS深度优先搜索

目录 一、题目描述 二、整体思路 三、代码 一、题目描述 题目地址 二、整体思路         大根堆/优先队列         看到第K小的元素(Top K)问题,第一时间想到快速排序/大根堆/优先队列。比较简单的思路是把所有结点加入到优先队列,然后重复出队列操作使得队列中元素数量为k,此时队首元素即为第K小的元素。优先队列的数据结构是大根堆,在遇见比堆顶小的元

2288. 价格减免 Medium

句子 是由若干个单词组成的字符串,单词之间用单个空格分隔,其中每个单词可以包含数字、小写字母、和美元符号 '$' 。如果单词的形式为美元符号后跟着一个非负实数,那么这个单词就表示一个 价格 。  ·例如 "$100"、"$23" 和 "$6" 表示价格,而 "100"、"$" 和 "$1e5 不是。 给你一个字符串 sentence 表示一个句子和一个整数 discount 。对于每个表示价格

VLF inhomogeneous medium中实现RombergIntegral

首先进入Sorce Code Edit界面,这个默认用户已经掌握,如果不会,可以查看软件中的帮助文件。 首先。左侧中选择Snippet Body选项卡,然后在其中输入需要被积分的函数表达式,例如如下函数。 然后回到开始的Main Function选项卡中写程序调用该积分核函数并设定上下限即可。操作如下: 之后点击OK保存并回到主界面运行即可。