leetcode面试题17.最大子矩阵
sooooooo long没刷题了,汗颜
题目链接:leetcode面试题17
1.题目
给定一个正整数、负整数和 0 组成的 N × M 矩阵,编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2],其中 r1, c1 分别代表子矩阵左上角的行号和列号,r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵,返回任意一个均可。
n,m<-200
2.分析
1)最初想到的版本:
首先f[i][j][0]表示第i行前j个格子的前缀和,f[i][j][1]表示第j列前i个格子的前缀和,那么以len1,len2,col1,col2为左上角和右下角的矩阵的子矩阵和为:f[len2][col2][2]-f[len2][col1-1][2]-f[len1-1][col2][2]+f[len1-1][col1-1][2];但这样我们就需要枚举len1,len2,col1,col2,复杂度为NNMM
2)在此基础上优化,我们可以发现,在确定了len1,len2,col1时,我们只需要使得f[len2][col2][2]-f[len1-1][col2][2]最大即可,那么我们把col1从n-1->0枚举的过程中可以逐步去比较当前最大的f[len2][col2][2]-f[len1-1][col2][2]和当col2=col1时的f[len2][col2][2]-f[len1-1][col2][2]谁更大,维护一下最大值即可,那么复杂度降低为MM*N,可以AC
3.代码
class Solution {
public:int f[210][210][5];static bool mycmp(vector<int> x,vector<int> y){return x[0]>y[0];}int get_sum(int len1,int len2,int col1,int col2){return f[len2][col2][2]-f[len1-1][col2][2];}vector<int> getMaxMatrix(vector<vector<int>>& matrix) {memset(f,0,sizeof(f));int m=matrix.size(),n=matrix[0].size();for(int i=0;i<m;i++)for(int j=0;j<n;j++){int len=i+1,col=j+1,c=matrix[i][j];f[len][col][0]=f[len-1][col][0]+c;f[len][col][1]=f[len][col-1][1]+c;f[len][col][2]=f[len-1][col-1][2]+f[len][col-1][1]+f[len-1][col][0]+c;}int ans=matrix[0][0],r1=0,r2=0,c1=0,c2=0;for(int i=0;i<m;i++)for(int k=i;k<m;k++){int len1=i+1,len2=k+1,col2=n;int col_sum=f[len2][col2][2]-f[len1-1][col2][2];for(int j=n-1;j>=0;j--){int col1=j+1;if(get_sum(len1,len2,col1,j+1)>col_sum){col_sum=get_sum(len1,len2,col1,j+1);col2=j+1;}int ans_test=f[len2][col2][2]-f[len2][col1-1][2]-f[len1-1][col2][2]+f[len1-1][col1-1][2];if(ans_test>ans){ans=ans_test;r1=i,c1=j,r2=k,c2=col2-1;}}}vector<int> ans_vec;ans_vec.push_back(r1);ans_vec.push_back(c1);ans_vec.push_back(r2);ans_vec.push_back(c2);return ans_vec;}};
相关文章:
leetcode面试题17.最大子矩阵
sooooooo long没刷题了,汗颜 题目链接:leetcode面试题17 1.题目 给定一个正整数、负整数和 0 组成的 N M 矩阵,编写代码找出元素总和最大的子矩阵。 返回一个数组 [r1, c1, r2, c2],其中 r1, c1 分别代表子矩阵左上角的行号和…...
计算机网络:构建联结的基础
目录 1. 网络拓扑结构 1.1 星型拓扑 1.2 环型拓扑 1.3 总线型拓扑 1.4 网状拓扑 2. 传输介质 2.1 双绞线 2.2 同轴电缆 2.3 光纤 2.4 无线电波 3. 协议栈模型 3.1 OSI模型 3.2 TCP/IP模型 4. 网络设备 4.1 交换机 4.2 路由器 4.3 网关 4.4 防火墙 5. IP地址…...
node和npm安装;electron、 electron-builder安装
1、node和npm安装 参考: https://blog.csdn.net/sw150811426/article/details/137147783 下载: https://nodejs.org/dist/v20.15.1/ 安装: 点击下载msi直接运行安装 安装完直接cmd打开可以,默认安装就已经添加了环境变量&…...
操作系统概念(黑皮书)阅读笔记
操作系统概念(黑皮书)阅读笔记 进程和内存管理部分章节 导论: 操作系统类似于政府,其本身不能实现任何有用功能,而是提供一个方便其他程序执行有用工作的环境 个人理解:os是government的作用࿰…...
matlab gui下的tcp client客户端编程框架
GUI界面 函数外定义全局变量 %全局变量 global TcpClient; %matlab作为tcpip客户端 建立连接 在“连接”按钮的回调函数下添加以下代码: global TcpClient;%全局变量 TcpClient tcpip(‘192.168.1.10’, 7, ‘NetworkRole’,‘client’); %连接到服务器地址和端…...
Matplotlib : Python 的绘图库
Matplotlib 是一个 Python 的绘图库,广泛用于生成各种静态、动态、交互式的图表。它基于 NumPy,一个用于科学计算的 Python 库。Matplotlib 可以用于生成出版质量级别的图表,并且提供了丰富的定制选项,以适应不同用户的需求。以下…...
数据编织 VS 数据仓库 VS 数据湖
目录 1. 什么是数据编织?2. 数据编织的工作原理3. 代码示例4. 数据编织的优势5. 应用场景6. 数据编织 vs 数据仓库6.1 数据存储方式6.2 数据更新和实时性6.3 灵活性和可扩展性6.4 查询性能6.5 数据治理和一致性6.6 适用场景6.7 代码示例比较 7. 数据编织 vs 数据湖7.1 数据存储…...
CSS(十一)——CSS分组和嵌套,尺寸(Dimension)
CSS 分组 和 嵌套 选择器 分组选择器 举个例子,多个标签有同一个样式,就可以不一个一个分开写,使用分组选择器 比如: h1 {color:green; } h2 {color:green; } p {color:green; } 就可以写为: h1,h2,p {color…...
必备神器!三款优秀远程控制电脑软件推荐
嘿,各位职场小伙伴们,今儿个咱们来聊聊个挺实用又带点“科技范儿”的话题——电脑远程控制那点事儿。作为刚踏入职场不久的新人,我深刻体会到,在这信息爆炸的时代,掌握几招远程操作的技能,简直就是给自个儿…...
关于正运动学解机器人手臂算法
机器人正运动学是机器人学的一个分支,研究机器人的运动和位置之间的关系。它通过解析机器人的结构和关节参数,以及给定的关节角度,来计算机器人的末端执行器的位置和姿态。 机器人正运动学算法通常使用DH(Denavit-Hartenberg&…...
MySQL 约束 (constraint)
文章目录 约束(constraint)列级约束和表级约束给约束起名字(constraint)非空约束(no null)检查约束(check)唯一性约束 (unique)主键约束 (primary key)主键分类单一主键复合主键主键自增 (auto_increment) 外键约束外什…...
用python程序发送文件(python实例二十六)
目录 1.认识Python 2.环境与工具 2.1 python环境 2.2 Visual Studio Code编译 3.文件上传 3.1 代码构思 3.2 服务端代码 3.3 客户端代码 3.4 运行结果 4.总结 1.认识Python Python 是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。 Python 的设计具…...
最新源支付系统源码 V7版全开源 免授权 附搭建教程
本文来自:最新源支付系统源码 V7版全开源 免授权 附搭建教程 - 源码1688 简介: 最新源支付系统源码_V7版全开源_免授权_附详细搭建教程_站长亲测 YPay是专为个人站长打造的聚合免签系统,拥有卓越的性能和丰富的功能。它采用全新轻量化的界面…...
HTML:lang属性作用
lang作用 用法常见语言代码优点示例结构效果说明分析HTML 基础结构导航栏内容部分总结 扩展 用法 HTML 文档级别: 在 <html> 标签上使用 lang 属性,指定整个文档的语言。 <!DOCTYPE html> <html lang"en"> <head><meta charse…...
Android SurfaceFlinger——纹理的绘制流程(二十八)
在系统开机动画的播放流程中,会从给定的资源文件中加载纹理数据并初始化一个 OpenGL 纹理对象,这里我们就来解析软件模拟纹理的绘制流程。 一、纹理概述 在 Android 的 SurfaceFlinger 系统组件中,纹理(Texture)是一个核心概念,特别是在涉及到图形渲染和显示的过程中。 …...
深入解析Memcached:C#中的应用与实战案例
目录 Memcached简介Memcached的特点Memcached的工作原理Memcached的应用场景Memcached的安装和配置Memcached与C#的集成 引入依赖配置Memcached客户端C#代码示例 存储数据读取数据删除数据深入解析Memcached 数据存储和过期策略分布式架构性能优化实战案例 缓存数据库查询结果实…...
keyring 库
目录 安装 keyring 基本用法 1. 设置密码 2. 获取密码 3. 删除密码 4. 返回当前使用的默认密钥环 5. 列出所有密码 支持的后端 keyring 是一个 Python 库,用于将敏感信息(如密码)安全地存储在操作系统的密码管理器中。它支持多种平台…...
[css3] 如何设置边框颜色渐变
div {border: 4px solid;border-image: linear-gradient(to right, #8f41e9, #578aef) 1; }参考: 5种CSS实现渐变色边框(Gradient borders方法的汇总...
Redux +Toolkit 工具包快速入门
您将学到什么 如何设置并使用 Redux Toolkit 和 React-Redux 先决条件 熟悉ES6 语法和功能了解 React 术语:JSX、State、Function Components 、 Props和Hooks理解Redux 术语和概念 1、基本使用 1.1、安装 Redux Toolkit 和 React- Redux 将 Redux Toolkit 和 Rea…...
【Python数据增强】图像数据集扩充
前言:该脚本用于图像数据增强,特别是目标检测任务中的图像和标签数据增强。通过应用一系列数据增强技术(如旋转、平移、裁剪、加噪声、改变亮度、cutout、翻转等),生成多样化的图像数据集,以提高目标检测模…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
uniapp 小程序 学习(一)
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...
Vue 3 + WebSocket 实战:公司通知实时推送功能详解
📢 Vue 3 WebSocket 实战:公司通知实时推送功能详解 📌 收藏 点赞 关注,项目中要用到推送功能时就不怕找不到了! 实时通知是企业系统中常见的功能,比如:管理员发布通知后,所有用户…...
