题解 | #最大正方形#

最大正方形

http://www.nowcoder.com/practice/0058c4092cec44c2975e38223f10470e

描述

这是一篇面对初级coder的题解。
知识点:动态规划 二维vector使用
难度:二星


题解

给定一个由'0'和'1'组成的2维矩阵,返回该矩阵中最大的由'1'组成的正方形的面积
分析:
与NC109相比,由于寻找的正方形较为规整 所以可以动态规划


方法一:暴力求解

遍历数组 对于每一个可能是1的点 循环扩大正方形面积
扩大面积时可按如下方法遍历 保证只遍历一遍:

class Solution {
public:
    int findsquare(vector<vector<char> >& matrix,int i,int j,int l,int w)
    {
        int ans=1;//最小1
        //循环加L型 扩大正方形
        while(1)
        {
            for(int side=0;side<ans+1;side++)//左侧竖列 由上到下
            {
                if(l<=i+ans||w<=j+side||'0'==matrix[i+ans][j+side])
                    return ans;
            }
            for(int side=0;side<ans+1;side++)//下侧横行 由左到右
            {
                if(l<=i+side||w<=j+ans||'0'==matrix[i+side][j+ans])
                    return ans;
            }
            ans++;
        }
        
        return ans;
    }
    int solve(vector<vector<char> >& matrix) {
        int ans=0;//返回答案
        int l=matrix.size() ,w=matrix[0].size();//矩阵长宽
        for(int i=0;i<l;i++)//双重遍历
        {
            for(int j=0;j<w;j++)
            {
                if('1'==matrix[i][j])//=1 是正方形
                {
                int maxsquare=findsquare(matrix,i,j,l,w);//迭代判断最大边长
                if(ans<maxsquare)
                    ans=maxsquare;//当前值大于最大值 记录最大边长
                }
            }
        }
        return ans*ans;//返回面积
    }
};

时间复杂度:其中 是矩阵的行数和列数。需要遍历整个矩阵寻找每个 1,遍历矩阵的时间复杂度是 对于每个可能的正方形,最坏情况下,其边长不超过 和  中的最小值,需要遍历每个元素判断,故最坏情况时间复杂度,最好情况即使最大正方形边长为1,时间复杂度
空间复杂度O(1):没有额外使用的空间

运行时间3ms 占用内存396KB


方法二:动态规划

从[1,1]开始遍历进行动态规划

递归公式
matrix[i][j] = min(matrix[i - 1][j], min(matrix[i - 1][j - 1], matrix[i][j - 1])) + 1;
注:这里为了节约内存,直接在原数组上输出,最开始+1相当于是在char上+1 故要最后转化为int
class Solution {
public:
    int solve(vector<vector<char> >& matrix) {
        int ans=0;//返回答案
        int l=matrix.size() ,w=matrix[0].size();//矩阵长宽
        for (int i=1;i<l;i++) 
        {
            for (int j=1;j<=w;j++) 
            {
                if(matrix[i][j]=='1')//符合递归条件
                {
                    //递推公式
                    matrix[i][j] = min(matrix[i - 1][j], min(matrix[i - 1][j - 1], matrix[i][j - 1])) + 1;
                    //记录最大的边长
                    ans = max(ans, (int)matrix[i][j]);
                }
            }
        }
        return (ans-'0')*(ans-'0');//转化为10进制输出
    }
};
运行时间3ms 占用内存384KB
时间复杂度:其中  和是矩阵的行数和列数。需要遍历整个矩阵寻找每个 1
空间复杂度O(1):直接在原数组上进行操作,没有额外使用的空间

有递推性质的问题可以考虑动态规划
原数组不要的时候可以直接在原数组上输出

阿Q的题解 文章被收录于专栏

阿Q秋招刷过的题

全部评论

相关推荐

06-14 19:09
门头沟学院 Java
darius_:给制造业搞的,什么物料管理生产管理,设备管理点检,最最关键的就是一堆报表看板。个人觉得没啥技术含量都是些基本的crud,但是业务很繁琐那种
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务