粤嵌—2024/5/28—最大正方形(✔)


代码实现:

方法一:模拟——超时

int maximalSquare(char **matrix, int matrixSize, int *matrixColSize) {
    int maxSide = 0;
    if (matrix == NULL || matrixColSize == NULL || matrixSize <= 0 
                                        || matrixColSize[0] <= 0) {
        return 0;
    }
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < matrixColSize[0]; j++) {
            if (matrix[i][j] == '1') { // 起点
                int k = 1;
                int flag = 1;
                while (flag) {
                    if (i + k >= matrixSize || j + k >= matrixColSize[0]) {
                        flag = 0;
                        break;
                    }
                    for (int x = i; x <= i + k && x < matrixSize; x++) {
                        for (int y = j; y <= j + k && y < matrixColSize[0]; y++) {
                            if (matrix[x][y] == '0') {
                                flag = 0;
                                break;
                            }
                        }
                        if (!flag) {
                            break;
                        }
                    }
                    if (!flag) {
                        break;
                    }
                    k++;
                }
                if (maxSide < k) {
                    maxSide = k;
                }
            }
        }
	}
    return maxSide * maxSide;
}

方法二:动态规划

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) > (b) ? (b) : (a))

int maximalSquare(char **matrix, int matrixSize, int *matrixColSize) {
    int maxSide = 0;
    int dp[matrixSize][matrixColSize[0]];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < matrixSize; i++) {
        if (matrix[i][0] == '1') {
            maxSide = max(maxSide, 1);
            dp[i][0] = 1;
        }
    }
    for (int j = 0; j < matrixColSize[0]; j++) {
        if (matrix[0][j] == '1') {
            maxSide = max(maxSide, 1);
            dp[0][j] = 1;
        }
    }
    for (int i = 1; i < matrixSize; i++) {
        for (int j = 1; j < matrixColSize[0]; j++) {
            if (matrix[i][j] == '1') {
                dp[i][j] = min((min(dp[i - 1][j], dp[i - 1][j - 1])), 
                                                    dp[i][j - 1]) + 1;
            }
            if (maxSide < dp[i][j]) {
                maxSide = dp[i][j];
            }
        }
    }
    return maxSide * maxSide;
}

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

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

相关文章

Mybatis枚举类型转换

Mybatis枚举类型转换 类型转换器源码分析 在Mybatis的TypeHandlerRegistry中&#xff0c;添加了常用的类转换器&#xff0c;其中默认的枚举类型转换器是EnumTypeHandler。 public final class TypeHandlerRegistry {....public TypeHandlerRegistry(Configuration configura…

windows帐户自动被锁定解决方法

处理方法方法一&#xff1a; 运行-gpedit.msc&#xff0c;打开组策略&#xff0c; 处理方法方法二&#xff1a; 运行-gpedit.msc&#xff0c;打开组策略&#xff0c; 在本地组策略编辑器页面中&#xff0c;选择计算机配置 > Windows设置 > 安全设置 > 账户策略 > 账…

leetCode. 85. 最大矩形

leetCode. 85. 最大矩形 部分参考上一题链接 leetCode.84. 柱状图中最大的矩形 此题思路 代码 class Solution { public:int largestRectangleArea( vector<int>& h ) {int n h.size();vector<int> left( n ), right( n );stack<int> st;// 求每个矩形…

电商API接口可实现的功能(京东API接口|天猫API接口)

电商API接口是电子商务领域中一种技术解决方案&#xff0c;它允许不同的软件系统之间进行交互和数据交换。 在电商场景下&#xff0c;电商API接口可以实现的功能非常丰富&#xff0c;例如&#xff1a; 商品管理&#xff1a;获取商品列表、商品详情、搜索商品、上下架商品等&a…

大模型日报|今日必读的 5 篇大模型论文

大家好&#xff0c;今日必读的大模型论文来啦&#xff01; 1.Meta 领衔&#xff1a;一文读懂视觉语言建模&#xff08;VLM&#xff09; 人们正在尝试将大型语言模型&#xff08;LLMs&#xff09;扩展到视觉领域。从可以引导我们穿越陌生环境的视觉助手&#xff0c;到仅使用高…

Mysql 备份恢复 mysqldump与xtrabackup备份

1.1 备份的原因 备份是数据安全的最后一道防线&#xff0c;对于任何数据丢失的场景&#xff0c;备份虽然不一定能恢复百分之百的数据 (取决于备份周期)&#xff0c;但至少能将损失降到最低。衡量备份恢复有两个重要的指标&#xff1a;恢复点目标(RPO) 和恢复时间目标(RTO)&…

【Android14 ShellTransitions】(一)开篇

说来惭愧&#xff0c;AndroidU都已经开发这么久了&#xff0c;但是我还没有整理过ShellTransition相关的知识。我本来希望能够系统的写一篇关于ShellTransition的笔记出来&#xff0c;但是发现一来这是一个比较庞大的模块&#xff0c;二来我个人能力有限&#xff0c;对ShellTra…

Pytorch入门需要达到的效果

会搭建深度学习环境和依赖包安装 使用Anaconda创建环境、在pytorch官网安装pytorch、安装依赖包 会使用常见操作&#xff0c;例如matmul&#xff0c;sigmoid&#xff0c;softmax&#xff0c;relu&#xff0c;linear matmul操作见文章torch.matmul()的用法 sigmoid&#xff0…

greendao实现增删改查

说明&#xff1a;最近碰到一个需求&#xff0c;在安卓上使用greendao框架&#xff0c;实现增删改查数据 效果图&#xff1a; step1: // Top-level build file where you can add configuration options common to all sub-projects/modules. buildscript {repositories {go…

使用nexus搭建的docker私库,定期清理无用的镜像,彻底释放磁盘空间

一、背景 我们使用nexus搭建了docker镜像&#xff0c;随着推送的镜像数量越来越多&#xff0c;导致nexus服务器的磁盘空间不够用了。于是&#xff0c;我们急需先手动删除一些过期的镜像&#xff0c;可发现磁盘空间并没有释放。 那么&#xff0c;如何才能彻底释放掉呢&#xff…

Android - failed to set system property

记录一次疏忽&#xff0c;起因是我需要在自定义的 receiver 中保存 property 方便&#xff0c;方便在三方 app 中使用&#xff0c;结果直接崩溃了&#xff0c;虽然结果保存成功了&#xff0c;但是这种情况也是无法接收的&#xff0c;错误日志如下&#xff1a; M006082 05-25 1…

[数据集][目标检测]航空发动机缺陷检测数据集VOC+YOLO格式291张4类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;291 标注数量(xml文件个数)&#xff1a;291 标注数量(txt文件个数)&#xff1a;291 标注类别…

Python 点云处理-点云半径滤波

点云半径滤波 一、介绍二、代码示例三、结果示例其他参考:C++ 中点云半径滤波 一、介绍 点云半径滤波:删除点云一定范围内没有达到足够多领域的所有点云。通俗的讲:就是要求点云P在半径为R内需要有M个领域点,若在点P的R范围内领域点个数大于M个,则保留该点云,领域点个数…

拌合楼系统开发(二十)解决海康DS-TVL224系列屏幕显示二维码思路

前言&#xff1a; 需求是想在通过程序动态控制显示屏显示二维码&#xff0c;最开始有些担心led这种点阵屏会不会对二维码显示出来后无法识别&#xff0c;实际测时候发现是没问题的。对于显示文字和语音播报&#xff0c;csdn上已经有大神有完整的代码。 海康威视道闸进出口LED屏…

java高级——String字符串探索(在jvm底层中如何实现,常量池中怎么查看)

java高级——String字符串探索&#xff08;在jvm底层中如何实现&#xff0c;常量池中怎么查看&#xff09; 文章介绍提前了解的知识点1. 常量池2. Jvm虚拟机3. 字节码 String类详解1. String对象在申明后将不可修改&#xff0c;是不可变类2. String进行相加相减等操作时一定会创…

常见的螺纹防松措施有哪些?——SunTorque智能扭矩系统

智能扭矩系统-智能拧紧系统-扭矩自动控制系统-SunTorque 螺纹连接作为机械工程中常见的连接方式&#xff0c;其稳定性和可靠性对于整个机械系统的正常运行至关重要。然而&#xff0c;由于振动、冲击、温度变化等因素的影响&#xff0c;螺纹连接往往会出现松动现象&#xff0c;…

react中子传父信息

思路是&#xff1a; 在父组件定义一个函数接受参数&#xff0c;接收的参数用于接收子组件的信息&#xff0c;把函数传给子组件&#xff0c;子组件调用父亲传来的函数并把要告诉父亲的话传到函数中&#xff0c;就实现了子传父消息 import { useState } from reactimport { use…

C++学习/复习7--泛型编程/函数模板/类模板

一、泛型编程 1.Swap()函数的模板实现 二、函数模板 1.概念 2.格式 3.实例化 &#xff08;1&#xff09;隐式与显示 注意事项&#xff1a;隐式与显示类型转换会产生临时变量&#xff0c;临时变量有常性&#xff0c;所以形参前加const 三、类模板 1.定义 2.例1 3.例2 4.注意事…

nginx流量监控:goAccess安装与使用

关于goAccess GoAccess 是一款实时、快速的日志分析工具&#xff0c;专门设计用于分析Web服务器日志&#xff0c;特别是Nginx日志。 安装 &#xff08;1&#xff09;准备相关依赖 # Missing development libraries for ncursesw # centOS yum install -y ncurses-devel # U…

qmt量化交易策略小白学习笔记第7期【qmt策略之股票快照指标】

qmt策略之股票快照指标 qmt更加详细的教程方法&#xff0c;会持续慢慢梳理。 也可找寻博主的历史文章&#xff0c;搜索关键词查看解决方案 &#xff01; 感谢关注&#xff0c;需免费开通量化回测与咨询实盘权限&#xff0c;可以和博主联系&#xff01; 股票快照指标 提供标…