[已解决]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]了

def func299(grid):
    if len(grid)==0 or len(grid[0])==0:
        return 0
    ret=0
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j]==0:
                continue
            
            if i>0 and j>0:
                grid[i][j]=1+min(grid[i-1][j-1],grid[i-1][j],grid[i][j-1])

            ret=max(ret,grid[i][j])

    return ret**2

跳转到最佳答案楼层

阴阳神万物主

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

def solve(photo):
    maxa = 0#最大的边长
    h,w = len(photo),(len(photo[0]) if photo else 0)
    for x in range(h):
        for y in range(w):
            a = 0#边长
            flg = photo[x][y]
            while flg:
                a += 1
                try:
                    for i in range(x,x+a+1):
                        if not photo[i][y+a]:
                            flg = False
                            break
                    else:
                        for j in range(y+a-1,y-1,-1):
                            if not photo[i][j]:
                                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([
  [1, 0, 1, 0, 0],
  [1, 0, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 0, 0, 1, 0]
]))
    print('示例2 输出：',solve([
  [0, 0, 0],
  [1, 1, 1]
]))

我用了 try 不算违规吧？

kinkon

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

zltzlt

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

嗯，再做一次

Croper

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

def func299(grid):
    if len(grid)==0 or len(grid[0])==0:
        return 0
    ret=0
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j]==0:
                continue
            
            if i>0 and j>0:
                grid[i][j]=grid[i-1][j-1]+1

            for k in range(1,grid[i][j]):
                if (grid[i-k][j]==0 or grid[i][j-k]==0):
                    grid[i][j]=k
                    break

            ret=max(ret,grid[i][j])

    return ret**2

塔利班

def f299(M):
    I,J=len(M),len(M[0])
    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[i][j]:
                        if [e[j:j+d] for e in M[i:i+d]]==[[1]*d for _ in range(d)]:
                            return d**2
    return 0

先写个

Croper

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

def func299(grid):
    if len(grid)==0 or len(grid[0])==0:
        return 0
    ret=0
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j]==0:
                continue
            
            if i>0 and j>0:
                grid[i][j]=1+min(grid[i-1][j-1],grid[i-1][j],grid[i][j-1])

            ret=max(ret,grid[i][j])

    return ret**2

fan1993423

from itertools import product
def fun299(lst):
    if not len(lst) or not len(lst[0]):
        return 0
    result=[]
    coordinate=[]
    width,height=len(lst[0]),len(lst)
    for i in range(height):
        for j in range(width):
            if lst[i][j]:
                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[i+m][j+n])
                    if 0 not in coordinate:
                        result.append(h)
                    coordinate=[]
    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

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

def fun299(martrix):
    def isBiger(martrix,index_x,index_y,maxlenth):#给定点寻找以其为正方形左上顶点的最大边长
        if maxlenth != 0:
            for i in range(0,maxlenth):
                totalSum = sum(martrix[index_x + i][index_y:(index_y + maxlenth)])
                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[index_x + maxlenth + index][index_y:(index_y + maxlenth + index + 1)])
                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[index_x + i][index_y + maxlenth + index] == 0:
                            if index > 0:
                                return maxlenth + index
                            else:
                                return None
            index = index + 1
  
                         
    
    m = len(martrix)#行数
    n = len(martrix[0])#列数
       
    maxlenth = 0#最大边长
    index_x = 0#行号
    index_y = 0#列号

    rightgate = n - 1#右边界
    bottomgate = m - 1#下边界
    
    while rightgate >= 0 and index_x <= bottomgate:
        if martrix[index_x][index_y] == 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

Stubborn

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

from typing import List
import math

def maximalRectangle(square: List[List[str]]) -> int:
    if not square or not square[0]:
        return 0
    nums = [int(''.join(row), base=2) for row in square]
    ans, N = 0, len(nums)
    for i in range(N):
        j, num = i, nums[i]
        while j < N:
            num = num & nums[j]
            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))