Python：每日一题 299
今天的题目：在一个 01 矩阵中找到全为 1 的最大正方形，返回它的面积。
示例 1：
输入：
[
,
,
,
]
输出：4
示例 2：
输入：
[
,
]
输出：1
{:10_298:}欢迎大家一起答题！{:10_298:} 本帖最后由 阴阳神万物主 于 2020-1-4 01:32 编辑
这题，仿佛做过……
但是一下子找不到原题，于是新写一个：
def solve(photo):
maxa = 0#最大的边长
h,w = len(photo),(len(photo) if photo else 0)
for x in range(h):
for y in range(w):
a = 0#边长
flg = photo
while flg:
a += 1
try:
for i in range(x,x+a+1):
if not photo:
flg = False
break
else:
for j in range(y+a-1,y-1,-1):
if not photo:
flg = False
break
except IndexError:
break
if a == h or a == w:
return a*a
maxa = max(a,maxa)
return maxa*maxa
if __name__ == '__main__':
print('示例1 输出：',solve([
,
,
,
]))
print('示例2 输出：',solve([
,
]))
我用了 try 不算违规吧？
水平没达到，但还是很热衷看每日一贴，占位看楼下的了 阴阳神万物主 发表于 2020-1-3 21:18
这题，仿佛做过……
嗯，再做一次{:5_109:} 本帖最后由 Croper 于 2020-1-3 22:17 编辑
先写一个，感觉时间复杂度能压倒O,一会想法再优化下。def func299(grid):
if len(grid)==0 or len(grid)==0:
return 0
ret=0
for i in range(len(grid)):
for j in range(len(grid)):
if grid==0:
continue
if i>0 and j>0:
grid=grid+1
for k in range(1,grid):
if (grid==0 or grid==0):
grid=k
break
ret=max(ret,grid)
return ret**2 def f299(M):
I,J=len(M),len(M)
D=min(I,J)
if D:
for d in range(D,0,-1):
for i in range(I-d+1):
for j in range(J-d+1):
if M:
if for e in M]==[*d for _ in range(d)]:
return d**2
return 0先写个 改良版，这下应该是O了def func299(grid):
if len(grid)==0 or len(grid)==0:
return 0
ret=0
for i in range(len(grid)):
for j in range(len(grid)):
if grid==0:
continue
if i>0 and j>0:
grid=1+min(grid,grid,grid)
ret=max(ret,grid)
return ret**2
本帖最后由 fan1993423 于 2020-1-4 16:42 编辑
from itertools import product
def fun299(lst):
if not len(lst) or not len(lst):
return 0
result=[]
coordinate=[]
width,height=len(lst),len(lst)
for i in range(height):
for j in range(width):
if lst:
d=min(height-i,width-j)
for h in range(1,d+1):
k=list(range(h))
for m,n in product(k,repeat=2):
coordinate.append(lst)
if 0 not in coordinate:
result.append(h)
coordinate=[]
return max(result)**2 if len(result) else 0
效率我先不考虑哈，我觉得先解出来再说，楼主可以测一下时间，当然不知道对不对。
不知道允不允许空列表，还是把空列表的弄成0吧。 阴阳神万物主 发表于 2020-1-3 21:18
这题，仿佛做过……
但是一下子找不到原题，于是新写一个：
我用了 try 不算违规吧？
当然不算犯规{:10_256:} 阴阳神万物主 发表于 2020-1-3 21:18
这题，仿佛做过……
但是一下子找不到原题，于是新写一个：
我用了 try 不算违规吧？
输入大矩阵超时。 塔利班 发表于 2020-1-3 21:39
先写个
输入大矩阵超时 不用说，我这个肯定超时了 fan1993423 发表于 2020-1-4 11:37
效率我先不考虑哈，我觉得先解出来再说，楼主可以测一下时间，当然不知道对不对。
不知道允不允许空列表 ...
输入 [,,,,,,,,,] 报错：ValueError: max() arg is an empty sequence zltzlt 发表于 2020-1-4 16:44
输入 [,,,,,,,
你确定，我这边输出0 fan1993423 发表于 2020-1-4 16:46
你确定，我这边输出0
嗯，改后的代码可以了，输入大矩阵超时 zltzlt 发表于 2020-1-4 16:49
嗯，改后的代码可以了，输入大矩阵超时
嗯，可能我的复杂度比他们都高，毕竟都用上product。还是来看一下大神的解法 zltzlt 发表于 2020-1-4 16:49
嗯，改后的代码可以了，输入大矩阵超时
这么辛苦，就不加荣誉，不加鱼币啊{:10_256:} Croper 发表于 2020-1-3 21:50
改良版，这下应该是O了
思路好巧，佩服 版主，我又来了，这次我又来了一个超长代码，请您笑纳。{:5_109:}
def fun299(martrix):
def isBiger(martrix,index_x,index_y,maxlenth):#给定点寻找以其为正方形左上顶点的最大边长
if maxlenth != 0:
for i in range(0,maxlenth):
totalSum = sum(martrix)
if totalSum < maxlenth:
return None
index = 0
while True:
if (index_x + maxlenth - 1 + (index + 1))> (m-1) or(index_y + maxlenth - 1 + (index + 1))> (n-1):
if index > 0:
return maxlenth + index
else:
return None
else:
sum_x = sum(martrix)
if sum_x < (maxlenth + index + 1):
if index > 0:
return maxlenth + index
else:
return None
else:
for i in range(0,maxlenth + index + 1):
if martrix == 0:
if index > 0:
return maxlenth + index
else:
return None
index = index + 1
m = len(martrix)#行数
n = len(martrix)#列数
maxlenth = 0#最大边长
index_x = 0#行号
index_y = 0#列号
rightgate = n - 1#右边界
bottomgate = m - 1#下边界
while rightgate >= 0 and index_x <= bottomgate:
if martrix == 0:
pass
else:
temp = isBiger(martrix,index_x,index_y,maxlenth)
if temp == None:
pass
else:
maxlenth = temp
rightgate = n - 1 - maxlenth
bottomgate = m - 1 - maxlenth
index_y = index_y + 1
if index_y <= rightgate:
pass
else:
index_y = 0
index_x = index_x + 1
return maxlenth*maxlenth 之前在做过一个找矩形的题目，本质上，从矩形变成正方形，也没差，所以不再额外改代码了
from typing import List
import math
def maximalRectangle(square: List]) -> int:
if not square or not square:
return 0
nums =
ans, N = 0, len(nums)
for i in range(N):
j, num = i, nums
while j < N:
num = num & nums
if not num:
break
l, curnum = 0, num
while curnum:
l += 1
curnum = curnum & (curnum << 1)
ans = max(ans, l * (j-i+1))
j += 1
return int(math.sqrt(ans))
页:
[1]
2