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

    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编写。

    48630

    LeetCode笔记:419. Battleships in a Board

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

    40620

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

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

    72740

    【CodeForces】567D - One-Dimensional Battle Ships & 【51Nod】1521 - 一维战舰(STL - set & 二分)

    51Nod链接:点击打开链 CodeForces链接:点击打开链接 1521 一维战舰 题目来源: CodeForces 基准时间限制:1 秒 空间限制:131072...KB 分值: 10 难度:2级算法题 爱丽丝和鲍博喜欢玩一维战舰的游戏。...在游戏开始的时候,爱丽丝放k个战舰在这个表格中,并不把具体位置告诉鲍博。每一只战舰的形状是 1×a 的长方形(也就是说,战舰会占据a个连续的方格)。这些战舰不能相互重叠,也不能相接触。...当他点到某个格子的时候,爱丽丝会告诉他那个格子是否被某只战舰占据。如果是,就说hit,否则就说miss。 但是这儿有一个问题!爱丽丝喜欢撒谎。他每次都会告诉鲍博miss。...第一行有三个整数n,k和a(1≤n,k,a≤2*10^5),表示表格的大小,战舰的数目,还有战舰的大小。输入的n,k,a保证是能够在1×n的表格中放入k只大小为a的战舰,并且他们之间不重叠也不接触。

    12910

    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编写。

    46710

    前缀树问题-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,这样的话就可以进行一次遍历就好了。

    59010

    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,能分配出去的战舰就是占领这个点后剩下的战舰

    42110
    领券