221. 最大正方形

题目描述:

在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

示例:

输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0 输出: 4

思路:

这道题是动态规划,所以我们要找到动态方程

dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1

举个例子

10111
11122
10010

代码:

class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
row = len(matrix)
col = len(matrix[0])
res = [[0] * col for _ in range(row)]
print(res)
max_len = 0
for i in range(row):
for j in range(col):
if i == 0:
res[0][j] = int(matrix[0][j])
elif j == 0:
res[i][0] = int(matrix[i][0])
elif matrix[i][j] == "1":
res[i][j] = min(res[i - 1][j], res[i][j - 1], res[i - 1][j - 1]) + 1
max_len = max(max_len, res[i][j])
return max_len * max_len

764. 最大加号标志

题目描述:

在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中,除了在 mines 中给出的单元为 0,其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶?返回加号标志的阶数。如果未找到加号标志,则返回 0。

一个 k" 阶由 1 组成的“轴对称”加号标志具有中心网格 grid[x][y] = 1 ,以及4个从中心向上、向下、向左、向右延伸,长度为 k-1,由 1 组成的臂。下面给出 k" 阶“轴对称”加号标志的示例。注意,只有加号标志的所有网格要求为 1,别的网格可能为 0 也可能为 1。

示例:

输入: N = 5, mines = [[4, 2]]
输出: 2
解释: 11111
11111
11111
11111
11011 在上面的网格中,最大加号标志的阶只能是2。一个标志已在图中标出。

思路:

动态规划

先有一个例子,描述动态规划的过程

例如:N = 3, mines = [[1,1]]

那么,就可以得到这样的grid

创建这样二维数组[[3,3,3],[3,0,3],[3,3,3]]

我们0行然后每列用十字架样式进行遍历,从左上角到右下角遍历,具体操作看代码:

我们首先看第0行第0列,进行操作变成:[[1,2,1],[2,0,3].[1,3,3]]

依次类推:

最后变成:[[1,1,1],[1,0,1],[1,1,1]]

代码:

class Solution:
def orderOfLargestPlusSign(self, N: int, mines: List[List[int]]) -> int:
dp = [[N] * N for _ in range(N)] for x, y in mines:
dp[x][y] = 0 # print(dp)
for i in range(N):
left = 0
right = 0
up = 0
down = 0
for j, k in zip(range(N), range(N - 1, -1, -1)):
left = left + 1 if dp[i][j] != 0 else 0
right = right + 1 if dp[i][k] != 0 else 0
up = up + 1 if dp[j][i] != 0 else 0
down = down + 1 if dp[k][i] != 0 else 0 dp[i][j] = min(dp[i][j], left)
dp[i][k] = min(dp[i][k], right)
dp[j][i] = min(dp[j][i], up)
dp[k][i] = min(dp[k][i], down) res = 0
for i in range(N):
for j in range(N):
res = max(res, dp[i][j])
return res
05-01 23:00