[已解决]Python：每日一题 299

zltzlt

今天的题目：

在一个 01 矩阵中找到全为 1 的最大正方形，返回它的面积。

示例 1：

输入：
[
  [1, 0, 1, 0, 0],
  [1, 0, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 0, 0, 1, 0]
]
输出：4

示例 2：

输入：
[
  [0, 0, 0],
  [1, 1, 1]
]
输出：1

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Croper

2020-1-3 21:50:35

改良版，这下应该是O[n]了

1. def func299(grid):
   
2.     if len(grid)==0 or len(grid[0])==0:
   
3.         return 0
   
4.     ret=0
   
5.     for i in range(len(grid)):
   
6.         for j in range(len(grid[i])):
   
7.             if grid[i][j]==0:
   
8.                 continue
   
9.             
   
10.             if i>0 and j>0:
    
11.                 grid[i][j]=1+min(grid[i-1][j-1],grid[i-1][j],grid[i][j-1])
    
12. 
    
13.             ret=max(ret,grid[i][j])
    
14. 
    
15.     return ret**2
    

复制代码

跳转到最佳答案楼层

阴阳神万物主

这题，仿佛做过……
但是一下子找不到原题，于是新写一个：

1. def solve(photo):
   
2.     maxa = 0#最大的边长
   
3.     h,w = len(photo),(len(photo[0]) if photo else 0)
   
4.     for x in range(h):
   
5.         for y in range(w):
   
6.             a = 0#边长
   
7.             flg = photo[x][y]
   
8.             while flg:
   
9.                 a += 1
   
10.                 try:
    
11.                     for i in range(x,x+a+1):
    
12.                         if not photo[i][y+a]:
    
13.                             flg = False
    
14.                             break
    
15.                     else:
    
16.                         for j in range(y+a-1,y-1,-1):
    
17.                             if not photo[i][j]:
    
18.                                 flg = False
    
19.                                 break
    
20.                 except IndexError:
    
21.                     break
    
22.             if a == h or a == w:
    
23.                 return a*a
    
24.             maxa = max(a,maxa)
    
25.     return maxa*maxa
    
26. if __name__ == '__main__':
    
27.     print('示例1 输出：',solve([
    
28.   [1, 0, 1, 0, 0],
    
29.   [1, 0, 1, 1, 1],
    
30.   [1, 1, 1, 1, 1],
    
31.   [1, 0, 0, 1, 0]
    
32. ]))
    
33.     print('示例2 输出：',solve([
    
34.   [0, 0, 0],
    
35.   [1, 1, 1]
    
36. ]))
    

复制代码

我用了 try 不算违规吧？

kinkon

水平没达到，但还是很热衷看每日一贴，占位看楼下的了

zltzlt

阴阳神万物主 发表于 2020-1-3 21:18
这题，仿佛做过……

嗯，再做一次

Croper

先写一个，感觉时间复杂度能压倒O[n],一会想法再优化下。

1. def func299(grid):
   
2.     if len(grid)==0 or len(grid[0])==0:
   
3.         return 0
   
4.     ret=0
   
5.     for i in range(len(grid)):
   
6.         for j in range(len(grid[i])):
   
7.             if grid[i][j]==0:
   
8.                 continue
   
9.             
   
10.             if i>0 and j>0:
    
11.                 grid[i][j]=grid[i-1][j-1]+1
    
12. 
    
13.             for k in range(1,grid[i][j]):
    
14.                 if (grid[i-k][j]==0 or grid[i][j-k]==0):
    
15.                     grid[i][j]=k
    
16.                     break
    
17. 
    
18.             ret=max(ret,grid[i][j])
    
19. 
    
20.     return ret**2

复制代码

塔利班

1. def f299(M):
   
2.     I,J=len(M),len(M[0])
   
3.     D=min(I,J)
   
4.     if D:
   
5.         for d in range(D,0,-1):
   
6.             for i in range(I-d+1):
   
7.                 for j in range(J-d+1):
   
8.                     if M[i][j]:
   
9.                         if [e[j:j+d] for e in M[i:i+d]]==[[1]*d for _ in range(d)]:
   
10.                             return d**2
    
11.     return 0

复制代码

先写个

Croper

改良版，这下应该是O[n]了

1. def func299(grid):
   
2.     if len(grid)==0 or len(grid[0])==0:
   
3.         return 0
   
4.     ret=0
   
5.     for i in range(len(grid)):
   
6.         for j in range(len(grid[i])):
   
7.             if grid[i][j]==0:
   
8.                 continue
   
9.             
   
10.             if i>0 and j>0:
    
11.                 grid[i][j]=1+min(grid[i-1][j-1],grid[i-1][j],grid[i][j-1])
    
12. 
    
13.             ret=max(ret,grid[i][j])
    
14. 
    
15.     return ret**2
    

复制代码

fan1993423

1. from itertools import product
   
2. def fun299(lst):
   
3.     if not len(lst) or not len(lst[0]):
   
4.         return 0
   
5.     result=[]
   
6.     coordinate=[]
   
7.     width,height=len(lst[0]),len(lst)
   
8.     for i in range(height):
   
9.         for j in range(width):
   
10.             if lst[i][j]:
    
11.                 d=min(height-i,width-j)
    
12.                 for h in range(1,d+1):
    
13.                     k=list(range(h))
    
14.                     for m,n in product(k,repeat=2):
    
15.                         coordinate.append(lst[i+m][j+n])
    
16.                     if 0 not in coordinate:
    
17.                         result.append(h)
    
18.                     coordinate=[]
    
19.     return max(result)**2 if len(result) else 0

复制代码

效率我先不考虑哈，我觉得先解出来再说，楼主可以测一下时间，当然不知道对不对。
不知道允不允许空列表，还是把空列表的弄成0吧。

zltzlt

阴阳神万物主 发表于 2020-1-3 21:18
这题，仿佛做过……
但是一下子找不到原题，于是新写一个：
我用了 try 不算违规吧？

当然不算犯规

zltzlt

阴阳神万物主 发表于 2020-1-3 21:18
这题，仿佛做过……
但是一下子找不到原题，于是新写一个：
我用了 try 不算违规吧？

输入大矩阵超时。

zltzlt

塔利班 发表于 2020-1-3 21:39
先写个

输入大矩阵超时

fan1993423

不用说，我这个肯定超时了

zltzlt

fan1993423 发表于 2020-1-4 11:37
效率我先不考虑哈，我觉得先解出来再说，楼主可以测一下时间，当然不知道对不对。
不知道允不允许空列表 ...

输入 [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] 报错：ValueError: max() arg is an empty sequence

fan1993423

zltzlt 发表于 2020-1-4 16:44
输入 [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0 ...

你确定，我这边输出0

zltzlt

fan1993423 发表于 2020-1-4 16:46
你确定，我这边输出0

嗯，改后的代码可以了，输入大矩阵超时

fan1993423

zltzlt 发表于 2020-1-4 16:49
嗯，改后的代码可以了，输入大矩阵超时

嗯，可能我的复杂度比他们都高，毕竟都用上product。还是来看一下大神的解法

fan1993423

zltzlt 发表于 2020-1-4 16:49
嗯，改后的代码可以了，输入大矩阵超时

这么辛苦，就不加荣誉，不加鱼币啊

fan1993423

Croper 发表于 2020-1-3 21:50
改良版，这下应该是O[n]了

思路好巧，佩服

TJBEST

版主，我又来了，这次我又来了一个超长代码，请您笑纳。

1. def fun299(martrix):
   
2.     def isBiger(martrix,index_x,index_y,maxlenth):#给定点寻找以其为正方形左上顶点的最大边长
   
3.         if maxlenth != 0:
   
4.             for i in range(0,maxlenth):
   
5.                 totalSum = sum(martrix[index_x + i][index_y:(index_y + maxlenth)])
   
6.                 if totalSum < maxlenth:
   
7.                     return None
   
8.         index = 0
   
9.         while True:
   
10.             if (index_x + maxlenth - 1 + (index + 1))> (m-1) or  (index_y + maxlenth - 1 + (index + 1))> (n-1):
    
11.                 if index > 0:
    
12.                     return maxlenth + index
    
13.                 else:
    
14.                     return None
    
15.             else:
    
16.                 sum_x = sum(martrix[index_x + maxlenth + index][index_y:(index_y + maxlenth + index + 1)])
    
17.                 if sum_x < (maxlenth + index + 1):
    
18.                     if index > 0:
    
19.                         return maxlenth + index
    
20.                     else:
    
21.                         return None
    
22.                 else:
    
23.                     for i in range(0,maxlenth + index + 1):
    
24.                         if martrix[index_x + i][index_y + maxlenth + index] == 0:
    
25.                             if index > 0:
    
26.                                 return maxlenth + index
    
27.                             else:
    
28.                                 return None
    
29.             index = index + 1
    
30.   
    
31.                         
    
32.    
    
33.     m = len(martrix)#行数
    
34.     n = len(martrix[0])#列数
    
35.       
    
36.     maxlenth = 0#最大边长
    
37.     index_x = 0#行号
    
38.     index_y = 0#列号
    
39. 
    
40.     rightgate = n - 1#右边界
    
41.     bottomgate = m - 1#下边界
    
42.    
    
43.     while rightgate >= 0 and index_x <= bottomgate:
    
44.         if martrix[index_x][index_y] == 0:
    
45.             pass
    
46.         else:
    
47.             temp = isBiger(martrix,index_x,index_y,maxlenth)
    
48.             if temp == None:
    
49.                 pass
    
50.             else:
    
51.                 maxlenth = temp
    
52.                 rightgate = n - 1 - maxlenth
    
53.                 bottomgate = m - 1 - maxlenth
    
54.         index_y = index_y + 1
    
55.         if index_y <= rightgate:
    
56.             pass
    
57.         else:
    
58.             index_y = 0
    
59.             index_x = index_x + 1
    
60.     return maxlenth*maxlenth

复制代码

Stubborn

之前在做过一个找矩形的题目，本质上，从矩形变成正方形，也没差，所以不再额外改代码了

1. from typing import List
   
2. import math
   
3. 
   
4. def maximalRectangle(square: List[List[str]]) -> int:
   
5.     if not square or not square[0]:
   
6.         return 0
   
7.     nums = [int(''.join(row), base=2) for row in square]
   
8.     ans, N = 0, len(nums)
   
9.     for i in range(N):
   
10.         j, num = i, nums[i]
    
11.         while j < N:
    
12.             num = num & nums[j]
    
13.             if not num:
    
14.                 break
    
15.             l, curnum = 0, num
    
16.             while curnum:
    
17.                 l += 1
    
18.                 curnum = curnum & (curnum << 1)
    
19.             ans = max(ans, l * (j-i+1))
    
20.             j += 1
    
21.     return int(math.sqrt(ans))

复制代码