首页
学习
活动
专区
工具
TVP
发布
您找到你想要的搜索结果了吗?
是的
没有找到

LeetCode笔记:419. Battleships in a Board

大意: 给出一个2D面板,计算其中有多少不同的战舰战舰由‘X’表示,空地由‘.’表示。你可以假设满足下面的规则: 你会接受到一个有效的面板,只由战舰和空地组成。 战舰只能是水平的或者垂直的。...两个战舰之间至少有一个空地 - 没有相连的战舰。 例子: 上面的面板上有两艘战舰。...无效的例子: 这是一个无效的面板,你不会接受到 - 因为两艘战舰一定会有空白的点。 进阶: 你能不能使用O(1)的内存,并且不修改面板的值来完成?...我们最好从左上角开始,遍历每个点,如果有X,就看它往右和往下有没有相邻的X,有的话也算做一艘战舰。已经检查过的点我们就不检查了,所以用一个二维数组来记录检查过的点。...,只记录这种新战舰的个数,很节省空间和时间。

29420

2022-04-22:给你一个大小为 m x n 的矩阵 board 表示甲板,其中,每个单元格可以是一艘战舰 X 或者是一

2022-04-22:给你一个大小为 m x n 的矩阵 board 表示甲板,其中,每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ,返回在甲板 board 上放置的 战舰 的数量。...战舰 只能水平或者垂直放置在 board 上。换句话说,战舰只能按 1 x k(1 行,k 列)或 k x 1(k 行,1 列)的形状建造,其中 k 可以是任意大小。...两艘战舰之间至少有一个水平或垂直的空位分隔 (即没有相邻的战舰)。 输入:board = [["X",".",".","X"],[".",".",".","X"],[".",".","."...甲板上的战舰。 来自米哈游。 答案2022-04-22: 并查集或者岛问题都行,但这不是最优解。 数战舰的左上角,统计左上角的点的个数就行。 时间复杂度:O(N**2)。 代码用rust编写。

34930

纽约大学的好奇AI特别会提问,桌游玩得比人还666

在开始介绍他们的研究之前,我们先了解一下AI玩的桌游——《战舰》——是个怎样的游戏。 ?...“战舰”。...每块棋盘上随机分布着3艘战舰,颜色分别是蓝色、红色、紫色,宽度是1,长度分别是2、3、4,朝向可能是水平、垂直,除了战舰之外的方块是浅灰色的,代表“水”。 ?...因此,他们先让人类玩这个游戏,然后记录下人类玩家所提出的问题,然后将这些问题转换成概念组件,例如“蓝色的战舰有多长?”这个问题是关于长度的,“蓝色和红色战舰相连吗?”是关于位置的。...更让人印象深刻的是,这个玩《战舰》游戏的程序能构建出“终极问题”,包含一系列的数学计算,比如将一艘战舰的长度加上另一艘战舰长度的10倍等等。

63940

2022-04-22:给你一个大小为 m x n 的矩阵 board 表示甲板,其中,每个单元格可以是一艘战舰 ‘X‘ 或者是一个空位 ‘.‘ ,返回在甲板 b

2022-04-22:给你一个大小为 m x n 的矩阵 board 表示甲板,其中,每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ,返回在甲板 board 上放置的 战舰 的数量。...战舰 只能水平或者垂直放置在 board 上。换句话说,战舰只能按 1 x k(1 行,k 列)或 k x 1(k 行,1 列)的形状建造,其中 k 可以是任意大小。...两艘战舰之间至少有一个水平或垂直的空位分隔 (即没有相邻的战舰)。 输入:board = ["X",".",".","X",".",".",".","X",".",".",".","X"]。...甲板上的战舰。 来自米哈游。 答案2022-04-22: 并查集或者岛问题都行,但这不是最优解。 数战舰的左上角,统计左上角的点的个数就行。 时间复杂度:O(N**2)。 代码用rust编写。

30610

前缀树问题-LeetCode 409、412、414、415、419、421

return res; } }; 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/add-strings 【LeetCode #419】甲板上的战舰...给定一个二维的甲板, 请计算其中有多少艘战舰。...战舰用 'X'表示,空位用 '.'表示。你需要遵守以下规则: 给你一个有效的甲板,仅由战舰或者空位组成。 战舰只能水平或者垂直放置。...换句话说,战舰只能由 1xN (1 行, N 列)组成,或者 Nx1 (N 行, 1 列)组成,其中N可以是任意大小。 两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。...解题思路: 这是一个很巧妙的思路,只需要检查一个X的点的左边和上边是否也是X,如果是,则当前X不是战舰,否则战舰数+1,这样的话就可以进行一次遍历就好了。

41910

Starship Troopers(树状dp) hdu1011

Input 5 1050 1040 1040 2065 3070 301 21 32 42 51 120 7-1 -1 Sample Output 50 7 题意: 第一行给出n个房间和m艘星际战舰的数量...必须从第一个房间开始向后,每20个虫子需要用一艘战舰,不足20(包括0)需要1艘.所以m==0,直接输出0换行continue。 用dp[i][j]记录答案,其中i表示根节点,j表示派出j艘战舰。...为根节点的物品组(可以视为一个物品组)还是不选择,就是看谁更大     dp[index][j]=max(dp[index][j],dp[index][j-k]+dp[v][k]);  (j-k表示已经派了k艘战舰...,然后收获为dp[v][k],dp[index][j]原本表示派出j艘战舰的收获,但是还没有递归回去,所以暂时为前面初始化的值)   至于存储数据问题,可以用邻阶矩阵或数组套用,我用的是c++.c++stl...k++)//在占领这个点的条件下,可以分配出去的点的数量(总数-z),                                                  //例如j==m,能分配出去的战舰就是占领这个点后剩下的战舰

33610
领券