Leetcode面试经典150题-221.最大正方形

  解法都在代码里,不懂就留言或者私信

class Solution {
    /**本题一看就是典型的动态规划,要找以每个点为右下角的正方形的面积,然后取最大的
    这个题要注意找规律,我找到的规律如下:1.以第一行为右下角的,因为正方形是边长相同的,所以第一行为右下角最大正方形只能是自己,自己是1就是1,不是1就是0
    2. 以第一列为右下角的也是一样。
    3. 以普通位置为右下角的最大正方形,首先看自己是不是1,如果自己不是1,那就肯定是0,如果自己是1,取它的左上、左、上三个点的最小面积,加1就是它的解
    自己可以多画几个二维矩阵找找规律
    */
    public int maximalSquare(char[][] matrix) {
        /**空矩阵的校验,健壮性校验 */
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        /**如果矩阵只有一个数字,那就是0最大面积就是0,是'1'最大面积就是1*/
        if(matrix.length == 1 && matrix[0].length == 1) {
            return matrix[0][0] == '1'? 1 : 0;
        }
        /**其他的不过多枚举了,直接动态规划解吧,dp[i][j]代表以(i,j)为右下角的最大正方形的边长*/
        int[][] dp = new int[matrix.length][matrix[0].length];
        /**定义最大值变量 */
        int maxArea = 0;
        /**初始化第一行和第一列*/
        for(int j = 0; j < dp[0].length; j++) {
            dp[0][j] = matrix[0][j] == '1'? 1 : 0;
            /**这里其实是dp[0][j]* dp[0][j],反正最大就是1,懒得写了 */
            maxArea = Math.max(maxArea, dp[0][j]);
        }
        for(int i = 1; i < dp.length; i++) {
            dp[i][0] = matrix[i][0] == '1'? 1 : 0;
            /**这里其实是dp[i][0]* dp[i][0],反正最大就是1,懒得写了 */
            maxArea = Math.max(maxArea, dp[i][0]);
        }
        /**初始化普通位置 */
        for(int i = 1; i < dp.length; i++) {
            for(int j = 1; j < dp[i].length; j++) {
                if(matrix[i][j] == '1') {
                    dp[i][j] = matrix[i][j] == '1'? Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1 : 0;
                    maxArea = Math.max(maxArea, dp[i][j]*dp[i][j]);
                }
            }
        }
        return maxArea;
    }
}

 相信我这就是最优解,矩阵就是m*n,你不过完能知道答案吗

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/872642.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ADC——模数转换器

一、转换流程 在处理器中主要进行ADC 1、AD转换流程 &#xff1a;采样、保持、量化、编码 通过比较器获得的电信号转换数字信号&#xff0c;根据自己需求&#xff0c;如果要求速率就可以使用较多的比较器&#xff0c;不要求速率考虑成本就可以使用较少的比较器&#xff0c;将最…

Vue学习笔记 二

4、Vue基础扩展 4.1 插槽 组件的最大特性就是复用性&#xff0c;而用好插槽能大大提高组件的可复用能力在Vue中插槽是很重要的存在&#xff0c;通过插槽&#xff0c;我们可以把父组件中指定的DOM作用到子组件的任意位置&#xff0c;后面我们坐项目用到的组件库比如element-ui…

5、Django Admin后台移除“删除所选”操作

默认情况下&#xff0c;Django Admin后台的listview模型列表页&#xff0c;会有一个Delete Selected删除所选操作。假设你需要再从Hero管理模型中移除该删除操作。 ModelAdmin.get_actions方法可以返回所有的操作方法。通过覆盖此方法&#xff0c;移除其中delete_selected方法…

Python 优雅编程:会报恩的代码(五)

文章目录 引言从文本搜索指定单词&#xff0c;不区分单词的大小写使用 str.lower()使用 re 模块 从文本搜索多个单词&#xff0c;依旧不区分单词的大小写使用 str.lower() 和循环使用 re 模块 反复执行 re.compile&#xff0c;re 是否会缓存编译结果&#xff1f;结语 引言 在 …

苹果mac数据恢复概率大吗 mac数据恢复专业软件哪个好用

一般情况下&#xff0c;当我们把电脑中的数据删掉后&#xff0c;都会保存在回收站里面&#xff0c;但如果回收站被清空了或者数据在回收站中没有找到的话&#xff0c;那么&#xff0c;之前被删掉的数据还能恢复吗&#xff1f;恢复的概率有多大呢&#xff1f; 答案是可以的&…

链式栈、队列

1、链式栈&#xff1a; 声明&#xff1a; #ifndef _STACK_H #define _STACK_H #include<stdlib.h>typedef int DataType;typedef struct snode //节点 {DataType data;struct snode *pnext; }SNode_t;typedef struct stack //链表 {SNode_t *ptop;int clen; }St…

【python】—— Python爬虫实战:爬取珠海市2011-2023年天气数据并保存为CSV文件

目录 目标 准备工作 爬取数据的开始时间和结束时间 爬取数据并解析 将数据转换为DataFrame并保存为CSV文件 本文将介绍如何使用Python编写一个简单的爬虫程序,以爬取珠海市2011年至2023年的天气数据,并将这些数据保存为CSV文件。我们将涉及到以下知识点: 使用r…

金九银十,自动化测试面试题精选【美团二面】

面试一般分为技术面和hr面&#xff0c;形式的话很少有群面&#xff0c;少部分企业可能会有一个交叉面&#xff0c;不过总的来说&#xff0c;技术面基本就是考察你的专业技术水平的&#xff0c;hr面的话主要是看这个人的综合素质以及家庭情况符不符合公司要求&#xff0c;一般来…

Kubernetes 上安装 Jenkins

安装 Helm curl https://raw.githubusercontent.com/helm/helm/main/scripts/get-helm-3 | bash添加 Jenkins Helm 仓库 首先添加 Jenkins Helm 仓库 helm repo add jenkins https://charts.jenkins.io helm repo update安装 Jenkins 使用 Helm 安装 Jenkins 的最新版本&…

uni-app应用更新(Android端)

关于app更新&#xff0c;uni-app官方推荐的是 uni-upgrade-center&#xff0c;看了下比较繁琐&#xff0c;因此这里自己实现检查更新并下载安装的逻辑。 1.界面效果 界面中的弹框和 进度条采用了uView 提供的组件 2.检查更新并下载安装 一、版本信息配置在服务端&#xff0c…

时装爱好者的网页购物天堂:Spring Boot技术探索

第2章相关技术 2.1 B/S架构 B/S结构的特点也非常多&#xff0c;例如在很多浏览器中都可以做出信号请求。并且可以适当的减轻用户的工作量&#xff0c;通过对客户端安装或者是配置少量的运行软件就能够逐步减少用户的工作量&#xff0c;这些功能的操作主要是由服务器来进行控制的…

详解TensorRT的C++高性能部署以及C++部署Yolo实践

详解TensorRT的C高性能部署 一. ONNX1. ONNX的定位2. ONNX模型格式3. ONNX代码使用实例 二、TensorRT1 引言 三、C部署Yolo模型实例 一. ONNX 1. ONNX的定位 ONNX是一种中间文件格式&#xff0c;用于解决部署的硬件与不同的训练框架特定的模型格式的兼容性问题。 ONNX本身其…

JAVA数据导出为Excel

目录 一、导入依赖 二、使用的相关类 1、XSSFWorkbook 构造方法 创建表 操作表 保存表 样式和格式 日期处理 密码保护 其他 2、XSSFSheet 获取属性和信息 行操作 列操作 表的属性 合并单元格 保护表 页眉和页脚 注释 其它 3、XSSFRow 获取属性和信息 单…

单点登录OAuth2.0

OAuth 2.0&#xff08;Open Authorization 2.0&#xff09;是OAuth协议的第二个版本&#xff0c;于2012年正式成为RFC 6749标准。在OAuth 2.0之前&#xff0c;OAuth 1.0版本已经为Web应用提供了一定程度的授权功能&#xff0c;但随着时间的推移&#xff0c;这些版本逐渐显露出一…

Nginx: TCP建立连接的优化和启用Fast Open功能

TCP 建立连接优化 在三次握手中&#xff0c;相关TCP的内核参数可优化这一过程 net.ipv4.tcp_syn_retries 6net.ipv4.tcp_synack_retries 5net.ipv4.tcp_syncookies 0net.ipv4.tcp_max_syn_backlognet.core.somaxconnnet.core.netdev_max_backlog 1 &#xff09; net.ipv4…

C语言之猜数字小游戏

哈喽&#xff0c;大家好&#xff01;我是冰淇淋加点糖。今天我们来用前面所学的知识来开发一个猜数字的小游戏&#xff0c;锻炼我们的编程能力和编程思维。 猜数字小游戏功能简介 1.随机生成一个1-100的数字。 2.玩家用户开始猜数字。 > 猜大了&#xff0c;提醒猜大了…

【知识库系列】MPR/多模态方向观察:图像视频与3D生成

多模态背后的backbone会长成什么样&#xff1f; 各种模态到梯度下降到最后会不会都差不多&#xff1f; Sora 是不是已经被追上了? 我们真的把视频数据都用好了吗&#xff1f; 知识库完整文档&#xff1a; MPR/多模态方向观察&#xff1a;图像视频与3D生成&#xff1a;https…

SpringBoot实现前后端传输加密设计

在Web应用中&#xff0c;确保前后端之间的数据传输安全是非常重要的。这通常涉及到使用HTTPS协议、数据加密、令牌验证等安全措施。本文通过将前后端之间的传输数据进行加密&#xff0c;用于在Spring Boot应用中实现前后端传输加密设计。 一、数据加密方案 即使使用了HTTPS&…

java利用JXL操作excel

通过JXL操作Excel JXL是韩国人所著,目前停止更新,只支持xls格式,即2007之前的版本 import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStream; import java.net.URL; import java…

c# checkbox的text文字放到右边

checkbox的text文字放到右边 实现方法如下图 特此记录 anlog 2024年9月2日