LeetCode 2482.行和列中一和零的差值

给你一个下标从 0 开始的 m x n 二进制矩阵 grid 。

我们按照如下过程,定义一个下标从 0 开始的 m x n 差值矩阵 diff :

令第 i 行一的数目为 onesRowi 。
令第 j 列一的数目为 onesColj 。
令第 i 行零的数目为 zerosRowi 。
令第 j 列零的数目为 zerosColj 。
diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj
请你返回差值矩阵 diff 。

示例 1:

在这里插入图片描述

输入:grid = [[0,1,1],[1,0,1],[0,0,1]]
输出:[[0,0,4],[0,0,4],[-2,-2,2]]
解释:

  • diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 2 + 1 - 1 - 2 = 0
  • diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 2 + 1 - 1 - 2 = 0
  • diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 2 + 3 - 1 - 0 = 4
  • diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 2 + 1 - 1 - 2 = 0
  • diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 2 + 1 - 1 - 2 = 0
  • diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 2 + 3 - 1 - 0 = 4
  • diff[2][0] = onesRow2 + onesCol0 - zerosRow2 - zerosCol0 = 1 + 1 - 2 - 2 = -2
  • diff[2][1] = onesRow2 + onesCol1 - zerosRow2 - zerosCol1 = 1 + 1 - 2 - 2 = -2
  • diff[2][2] = onesRow2 + onesCol2 - zerosRow2 - zerosCol2 = 1 + 3 - 2 - 0 = 2
    示例 2:

在这里插入图片描述

输入:grid = [[1,1,1],[1,1,1]]
输出:[[5,5,5],[5,5,5]]
解释:

  • diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 3 + 2 - 0 - 0 = 5
  • diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 3 + 2 - 0 - 0 = 5
  • diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 3 + 2 - 0 - 0 = 5
  • diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 3 + 2 - 0 - 0 = 5
  • diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 3 + 2 - 0 - 0 = 5
  • diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 3 + 2 - 0 - 0 = 5

提示:

m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
grid[i][j] 要么是 0 ,要么是 1 。

法一:预处理一下nums,找出每行和每列1的个数,然后模拟即可:

class Solution {
public:
    vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
        int rowNum = grid.size();
        int colNum = grid[0].size();
        
        vector<int> rowOne(rowNum);
        vector<int> colOne(colNum);
        for (int i = 0; i < rowNum; ++i)
        {
            for (int j = 0; j < colNum; ++j)
            {
                if (grid[i][j] == 1)
                {
                    ++rowOne[i];
                    ++colOne[j];
                }
            }
        }

        vector<vector<int>> ans;
        for (int i = 0; i < rowNum; ++i)
        {
            ans.push_back({});
            for (int j = 0; j < colNum; ++j)
            {
                int curAns = rowOne[i] + colOne[j] - (colNum - rowOne[i]) - (rowNum - colOne[j]);
                ans.back().push_back(curAns);
            }
        }

        return ans;
    }
};

此算法时间复杂度为O(mn),空间复杂度为O(m+n)。

法二:法一基础上的小优化,我们预处理时,遇到1增加本行和本列的1的数量,遇到0时减少本行和本列1的数量,因为最后的结果中的某个元素可以看做本行1的个数减去本行0的个数加上本列1的个数减去本列1的个数:

class Solution {
public:
    vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
        int rowNum = grid.size();
        int colNum = grid[0].size();
        
        vector<int> rowOne(rowNum);
        vector<int> colOne(colNum);
        for (int i = 0; i < rowNum; ++i)
        {
            for (int j = 0; j < colNum; ++j)
            {
                if (grid[i][j] == 1)
                {
                    ++rowOne[i];
                    ++colOne[j];
                }
                else
                {
                    --rowOne[i];
                    --colOne[j];
                }
            }
        }

        vector<vector<int>> ans;
        for (int i = 0; i < rowNum; ++i)
        {
            ans.push_back({});
            for (int j = 0; j < colNum; ++j)
            {
                ans.back().push_back(rowOne[i] + colOne[j]);
            }
        }

        return ans;
    }
};

此算法时间复杂度为O(mn),空间复杂度为O(m+n)。

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

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

相关文章

用于审核、优化和跟踪的 18 种顶级 SEO 工具

DIY SEO工具 需要自己动手 &#xff08;DIY&#xff09; SEO 工具吗&#xff1f;以下是帮助您自己实现 SEO 目标的最佳工具&#xff1a; SEO Checker&#xff1a; 最适合评估和提高 SEO 性能。Google Analytics 4&#xff1a;最适合跟踪 SEO 结果。Moz Pro&#xff1a;最适合…

清华大学1748页CTF竞赛入门指南,完整版开放下载!

CTF是一种针对信息安全领域的经济性挑战&#xff0c;旨在通过解决一系列的难题来寻找隐藏的“flag”。CTF比赛战队一般是以高校、科研单位、企业、信息安全从业者或社会团体组成。对于网安爱好者及从业者来说&#xff0c;拥有“CTF参赛经验”也是求职中的加分项。 前几天分享的…

C++ Qt开发:QFileSystemWatcher文件监视组件

Qt 是一个跨平台C图形界面开发库&#xff0c;利用Qt可以快速开发跨平台窗体应用程序&#xff0c;在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置&#xff0c;实现图形化开发极大的方便了开发效率&#xff0c;本章将重点介绍如何运用QFileSystemWatcher组件实现对文件或…

分享axios+MQTT简单封装示例

MQTT&#xff08;Message Queuing Telemetry Transport&#xff0c;消息队列遥测传输协议&#xff09;&#xff0c;是一种基于发布/订阅&#xff08;publish/subscribe&#xff09;模式的"轻量级"通讯协议&#xff0c;该协议构建于TCP/IP协议上&#xff0c;由IBM在19…

git fatal: detected dubious ownership in repository at ‘xxx‘ 彻底解决方法

前言 在 windows 重置后&#xff0c; git 仓库无法正常使用 git 的所有 命令&#xff0c;运行任何 git 命令&#xff0c;都会提示如下&#xff1a; $ git log fatal: detected dubious ownership in repository at D:/rk/rk3568/nanopi/uboot-rockchip D:/rk/rk3568/nanopi/u…

深入理解并发编程:解锁现代软件性能的关键

在当今快速发展的软件开发世界中&#xff0c;并发编程已经成为一种无法回避的重要议题。它涉及到如何在同一时间内处理多个任务&#xff0c;以此来提升应用程序的性能和响应速度。互联网服务的高并发需求以及多核处理器的普及使得并发编程成为了现代软件工程的一个核心组成部分…

瑞芯微RV系列-超级编码

参加开发者大会,逛了相应的workshop,对超级编码技术很感兴趣,RK做了很多事情,挺好的!!!

Type-C接口小家电使用PD诱骗芯片获取充电器的5V9V12V20V供电

随着Type-C接口的逐渐普及&#xff0c;小家电设备慢慢开始采用Type-C&#xff0c;淘汰了以往的DC接口&#xff0c;Type-C接口在小家电设备中的应用也越来越广泛。Type-C接口支持大电流宽电压范围&#xff0c;如何确保设备能够正确识别并使用各种电压&#xff08;例如5V、9V、12…

it-tools工具箱

it-tools 是一个在线工具集合&#xff0c;包含各种实用的开发工具、网络工具、图片视频工具、数学工具等 github地址&#xff1a;https://github.com/CorentinTh/it-tools 部署 docker run -d --name it-tools --restart unless-stopped -p 8080:80 corentinth/it-tools:lat…

【前端Vue】社交信息头条项目完整笔记第1篇:一、项目初始化【附代码文档】

社交媒体-信息头条项目完整开发笔记完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;一、项目初始化使用 Vue CLI 创建项目,加入 Git 版本管理,调整初始目录结构,导入图标素材。二、登录注册准备,实现基本登录功能,登录状态提示,表单验证。三、个人中心&am…

浏览器一键重新发起请求

一、需求场景 在前端开发过程中&#xff0c;经常会需要重新请求后台进行代码调试&#xff0c;之前的常规方法是刷新浏览器页面或者点击页面进行交互&#xff0c;这样对多个请求的场景就很方便&#xff0c;但是往往很多时候我们只是单纯的想重新发起一个请求&#xff08;多个请求…

找出单身狗1,2

目录 1. 单身狗12. 单身狗2 1. 单身狗1 题目如下&#xff1a; 思路&#xff1a;一部分人可能会使用对数组排序&#xff0c;遍历数组的方式去找出只出现一次的数字&#xff0c;但这种方法的时间复杂度过高&#xff0c;有时候可能会不满足要求。 有一种十分简便的方法是使用异或…

VITS 模型详解与公式推导:基于条件变分自编码器和对抗学习的端到端语音合成模型

参考文献&#xff1a; [1] Kim J, Kong J, Son J. Conditional variational autoencoder with adversarial learning for end-to-end text-to-speech[C]//International Conference on Machine Learning. PMLR, 2021: 5530-5540. [2] Su J, Wu G. f-VAEs: Improve VAEs with co…

Day25:安全开发-PHP应用文件管理模块包含上传遍历写入删除下载安全

目录 PHP文件操作安全 文件包含 文件删除 文件编辑 文件下载 云产品OSS存储对象去存储文件(泄漏安全) 思维导图 PHP知识点 功能&#xff1a;新闻列表&#xff0c;会员中心&#xff0c;资源下载&#xff0c;留言版&#xff0c;后台模块&#xff0c;模版引用&#xff0c;框…

单机版openstack安装

说明&#xff1a; 本文环境&#xff1a;CentOS 7 x64位 1.创建虚拟机 2.在虚拟机中安装 centos 7&#xff08;最小安装&#xff09;&#xff0c;修改主机名&#xff1a;openstack&#xff0c;设置 root 密码&#xff1a;12345678 3. 网卡设置&#xff0c;重启网络服务&#…

黑马点评-好友关注实现

关注和取关 针对用户的操作&#xff0c;可以对用户进行关注和取消关注功能&#xff1a; 需要实现两个接口&#xff1a; 关注和取关接口 判断是否关注的接口 接口&#xff1a; //关注和取关 PutMapping("/{id}/{isFollow}") public Result follow(PathVariable(&…

听 GPT 讲 client-go 源代码 (22)

分享更多精彩内容&#xff0c;欢迎关注&#xff01; File: client-go/applyconfigurations/core/v1/attachedvolume.go 在client-go项目中&#xff0c;client-go/applyconfigurations/core/v1/attachedvolume.go文件的作用是为Kubernetes的CoreV1 API对象AttachedVolume提供应用…

2024如何搭建测试平台?理清思路很重要!

01、职责 一个健康的测试平台体系&#xff0c;对测试人员的职责分工、协作模式会有不同的要求。 测试平台核心的职责是完成高质量的交付已满足业务需求。测试活动包括单元测试、集成测试、接口测试、性能测试等&#xff0c;都是通过这些测试手段&#xff0c;协同整个测试平台…

JsonCreator注解InvalidDefinitionException报错解决

"stack_trace": "c.f.j.d.e.InvalidDefinitionException: More than one argument (#0 and left as delegating for Creator [constructor for (

ArcGIS学习(十一)公服设施服务区划分与评价

ArcGIS学习(十一)公服设施服务区划分与评价 本任务带来的内容是公服设施服务区划分与公服设施服务区评价。本任务包括两个关卡: 公服设施服务区划分公服设施服务区空间价值评价1.公服设施服务区划分 首先,来看看这个案例的场景和基础数据。我们以上海市图书馆为例进行分析…