LeetCode:最大正方形


题目

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

示例 1:

1
2
输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:4

示例 2:

2021-03-17-23-17-12

输入:matrix = [[“0”,”1”],[“1”,”0”]]
输出:1

示例 3:

1
2
输入:matrix = [["0"]]
输出:0

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j]'0''1'

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximal-square

思路

如图将每个数字转换为坐标系位置,如图取最大,可依次循环:淡红→蓝→绿,判定是否为正方形,并取最长即可。

代码

Go

代码本地运算正常,符合结果;但提交结果却不对,搞不明白 LeetCode ~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package main

import (
"fmt"
"math"
"strconv"
)

// 点信息
type point struct {
x, y, value int
}

type sec struct {
x_min, x_max, y_min, y_max int
}

func maximalSquare(matrix [][]byte) int {
points := convertPoint(matrix)

sec := sec{1, len(matrix[0]), 1, len(matrix)}
r := 0

for y := sec.y_min; y <= sec.y_max; y++ {
for x := sec.x_min; x <= sec.x_max; x++ {
point := points[strconv.Itoa(x)+"_"+strconv.Itoa(y)]

num := squareMax(point, points, sec)
if num >= r {
r = num
}
}
}

// fmt.Println(points)

return r
}

func squareMax(point point, points map[string]point, sec sec) int {
// 如果值不为1
if point.value != 1 {
return 0
}

r := 0

for i := 0; i <= int(math.Min(float64(sec.y_max-point.y), float64(sec.x_max-point.x))); i++ {
flag := true

for t := 0; t < i; t++ {
if points[strconv.Itoa(point.x+t)+"_"+strconv.Itoa(point.y)].value != 1 ||
points[strconv.Itoa(point.x)+"_"+strconv.Itoa(point.y+t)].value != 1 ||
points[strconv.Itoa(point.x+t)+"_"+strconv.Itoa(point.y+t)].value != 1 {
flag = false
break
}
}

if flag {
r += 1
}
}

return r * r
}

func convertPoint(matrix [][]byte) map[string]point {
var points map[string]point

points = make(map[string]point)

for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[i]); j++ {
points[strconv.Itoa(i+1)+"_"+strconv.Itoa(j+1)] = point{
x: i + 1,
y: j + 1,
value: int(matrix[i][j]),
}
}
}

return points
}

func main() {
fmt.Println(maximalSquare([][]byte{
{1, 0, 1, 0, 0}, {1, 0, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 0, 0, 1, 0},
}))
fmt.Println(maximalSquare([][]byte{
{0, 1}, {1, 0},
}))
fmt.Println(maximalSquare([][]byte{
{0},
}))
}

评论