当前位置: 首页 > news >正文

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]谁更大,维护一下最大值即可,那么复杂度降低为M
M*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没刷题了&#xff0c;汗颜 题目链接&#xff1a;leetcode面试题17 1.题目 给定一个正整数、负整数和 0 组成的 N M 矩阵&#xff0c;编写代码找出元素总和最大的子矩阵。 返回一个数组 [r1, c1, r2, c2]&#xff0c;其中 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安装 参考&#xff1a; https://blog.csdn.net/sw150811426/article/details/137147783 下载&#xff1a; https://nodejs.org/dist/v20.15.1/ 安装&#xff1a; 点击下载msi直接运行安装 安装完直接cmd打开可以&#xff0c;默认安装就已经添加了环境变量&…...

操作系统概念(黑皮书)阅读笔记

操作系统概念&#xff08;黑皮书&#xff09;阅读笔记 进程和内存管理部分章节 导论&#xff1a; 操作系统类似于政府&#xff0c;其本身不能实现任何有用功能&#xff0c;而是提供一个方便其他程序执行有用工作的环境 ​ 个人理解&#xff1a;os是government的作用&#xff0…...

matlab gui下的tcp client客户端编程框架

GUI界面 函数外定义全局变量 %全局变量 global TcpClient; %matlab作为tcpip客户端 建立连接 在“连接”按钮的回调函数下添加以下代码&#xff1a; global TcpClient;%全局变量 TcpClient tcpip(‘192.168.1.10’, 7, ‘NetworkRole’,‘client’); %连接到服务器地址和端…...

Matplotlib : Python 的绘图库

Matplotlib 是一个 Python 的绘图库&#xff0c;广泛用于生成各种静态、动态、交互式的图表。它基于 NumPy&#xff0c;一个用于科学计算的 Python 库。Matplotlib 可以用于生成出版质量级别的图表&#xff0c;并且提供了丰富的定制选项&#xff0c;以适应不同用户的需求。以下…...

数据编织 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 分组 和 嵌套 选择器 分组选择器 举个例子&#xff0c;多个标签有同一个样式&#xff0c;就可以不一个一个分开写&#xff0c;使用分组选择器 比如&#xff1a; h1 {color:green; } h2 {color:green; } p {color:green; } 就可以写为&#xff1a; h1,h2,p {color…...

必备神器!三款优秀远程控制电脑软件推荐

嘿&#xff0c;各位职场小伙伴们&#xff0c;今儿个咱们来聊聊个挺实用又带点“科技范儿”的话题——电脑远程控制那点事儿。作为刚踏入职场不久的新人&#xff0c;我深刻体会到&#xff0c;在这信息爆炸的时代&#xff0c;掌握几招远程操作的技能&#xff0c;简直就是给自个儿…...

关于正运动学解机器人手臂算法

机器人正运动学是机器人学的一个分支&#xff0c;研究机器人的运动和位置之间的关系。它通过解析机器人的结构和关节参数&#xff0c;以及给定的关节角度&#xff0c;来计算机器人的末端执行器的位置和姿态。 机器人正运动学算法通常使用DH&#xff08;Denavit-Hartenberg&…...

MySQL 约束 (constraint)

文章目录 约束&#xff08;constraint)列级约束和表级约束给约束起名字&#xff08;constraint)非空约束&#xff08;no null)检查约束&#xff08;check)唯一性约束 (unique)主键约束 (primary key)主键分类单一主键复合主键主键自增 &#xff08;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版全开源 免授权 附搭建教程

本文来自&#xff1a;最新源支付系统源码 V7版全开源 免授权 附搭建教程 - 源码1688 简介&#xff1a; 最新源支付系统源码_V7版全开源_免授权_附详细搭建教程_站长亲测 YPay是专为个人站长打造的聚合免签系统&#xff0c;拥有卓越的性能和丰富的功能。它采用全新轻量化的界面…...

HTML:lang属性作用

lang作用 用法常见语言代码优点示例结构效果说明分析HTML 基础结构导航栏内容部分总结 扩展 用法 HTML 文档级别: 在 <html> 标签上使用 lang 属性&#xff0c;指定整个文档的语言。 <!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 库&#xff0c;用于将敏感信息&#xff08;如密码&#xff09;安全地存储在操作系统的密码管理器中。它支持多种平台…...

[css3] 如何设置边框颜色渐变

div {border: 4px solid;border-image: linear-gradient(to right, #8f41e9, #578aef) 1; }参考&#xff1a; 5种CSS实现渐变色边框&#xff08;Gradient borders方法的汇总...

Redux +Toolkit 工具包快速入门

您将学到什么 如何设置并使用 Redux Toolkit 和 React-Redux 先决条件 熟悉ES6 语法和功能了解 React 术语&#xff1a;JSX、State、Function Components 、 Props和Hooks理解Redux 术语和概念 1、基本使用 1.1、安装 Redux Toolkit 和 React- Redux 将 Redux Toolkit 和 Rea…...

【Python数据增强】图像数据集扩充

前言&#xff1a;该脚本用于图像数据增强&#xff0c;特别是目标检测任务中的图像和标签数据增强。通过应用一系列数据增强技术&#xff08;如旋转、平移、裁剪、加噪声、改变亮度、cutout、翻转等&#xff09;&#xff0c;生成多样化的图像数据集&#xff0c;以提高目标检测模…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...