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
举个例子
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 2 | 2 |
| 1 | 0 | 0 | 1 | 0 |
代码:
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