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

从零学算法2965

2965. 找出缺失和重复的数字
给你一个下标从 0 开始的二维整数矩阵 grid,大小为 n * n ,其中的值在 [1, n2] 范围内。除了 a 出现 两次,b 缺失 之外,每个整数都 恰好出现一次 。
任务是找出重复的数字a 和缺失的数字 b 。
返回一个下标从 0 开始、长度为 2 的整数数组 ans ,其中 ans[0] 等于 a ,ans[1] 等于 b 。
示例 1:
输入:grid = [[1,3],[2,2]]
输出:[2,4]
解释:数字 2 重复,数字 4 缺失,所以答案是 [2,4] 。
示例 2:
输入:grid = [[9,1,7],[8,9,2],[3,4,6]]
输出:[9,5]
解释:数字 9 重复,数字 5 缺失,所以答案是 [9,5] 。
提示:
2 <= n == grid.length == grid[i].length <= 50
1 <= grid[i][j] <= n * n
对于所有满足1 <= x <= n * n 的 x ,恰好存在一个 x 与矩阵中的任何成员都不相等。
对于所有满足1 <= x <= n * n 的 x ,恰好存在一个 x 与矩阵中的两个成员相等。
除上述的两个之外,对于所有满足1 <= x <= n * n 的 x ,都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 grid[i][j] == x

  • 最简单的,用数组统计每个数出现的次数,然后遍历数组即可
  •   public int[] findMissingAndRepeatedValues(int[][] grid) {int n = grid.length;int[] res = new int[2];int[] temp = new int[n * n + 1];for(int[] g : grid){for(int x : g){temp[x]++;}}for(int i = 1; i < temp.length; i++){if(temp[i] == 0)res[1] = i;else if(temp[i] == 2)res[0] = i;}return res;}
    
  • 数学方法:由于 a 出现两次,b 出现 0 次,所以当所有数相加时会得到 1+2+…+n + a - b,也就是说把数组中的所有数相加减去 1~n2 之和就能得到 d1 = a - b 。将所有数的平方和相加也是同理,减去 1~n2 的平方后就会剩下 d2 = a2-b2=(a+b)(a-b),最终我们可以得到 a - b = d1, a + b = d2 / d1,那么 a 和 b 就很容易计算了
  • 令 m = n2 1 − m 之和 = m ( 1 + m ) 2 { 1 - m 之和=\frac {m(1+m)} 2} 1m之和=2m(1+m)
  • 1 − m 的平方和 = m ( m + 1 ) ( 2 m + 1 ) 6 { 1 - m 的平方和=\frac {m(m+1)(2m+1)} 6} 1m的平方和=6m(m+1)(2m+1)
  •   public int[] findMissingAndRepeatedValues(int[][] grid) {int n = grid.length;int m = n * n;int[] res = new int[2];int d1 =  -m * (1 + m) / 2;long d2 = (long) -m * (m + 1) * (2 * m + 1) / 6;for(int[] row : grid){for(int x : row){d1 += x;d2 += x * x;}}int d = (int) (d2 / d1);res[0] = (d + d1) / 2;res[1] = (d - d1) / 2;return res;}
    
  • 位运算:如果我们额外加入 1 ~ m,最终会得到一个数出现 1 次,一个数出现 3 次,其余数出现两次,而异或后出现 1 次和出现 3 次是一样,即这些数的异或和就为 a^b,那么就相当于第 260 题了,从一堆出现两次的数字中找到只出现一次的两个数字。
  • 额外计算 1 到 n2 的异或和时,可以不遍历 1 ~ n 而用 O(1) 的计算公式
    的异或和
  •   public int[] findMissingAndRepeatedValues(int[][] grid) {int n = grid.length;int m = n * n;int or = 0;for(int[] row : grid){for(int x : row){or ^= x;}}or ^= n % 2 > 0 ? 1 : m;// 计算 or 最低位的 1 后面有几个 0// 下面会根据右移 one 位来分组// 其实核心思想还是根据 or 中为 1 的某一位来分类// 所以也可以按照第 260 题的写法令 one 为 xx1x// 下面分组就能按照 x & one 是否等于 0 来分组int one = Integer.numberOfTrailingZeros(or);int[] res = new int[2];// 以下两个循环都是为了把数组中的数以及额外的 1~m 按照// 对应于 one 的那一位为 0 还是 1 分类异或进结果数组// 反正重复的数都会被异或掉,所以最终数组会剩下 a 和 bfor(int x = 1; x <= m; x++){res[(x >> one) & 1] ^= x;}for(int[] row : grid){for(int x : row){res[(x >> one) & 1] ^= x;}}// 由于我们无法区分 res 中哪个是 a 哪个是 b// 所以我们根据数组中只存在 a 没有 b 来判断// 如果数组中某个数等于 res[0] 说明 res[0] 就是 a// 那么可以直接返回for (int[] row : grid) {for (int x : row) {if (x == res[0]) {return res;}}}return new int[]{res[1], res[0]};}
    

相关文章:

从零学算法2965

2965. 找出缺失和重复的数字 给你一个下标从 0 开始的二维整数矩阵 grid&#xff0c;大小为 n * n &#xff0c;其中的值在 [1, n2] 范围内。除了 a 出现 两次&#xff0c;b 缺失 之外&#xff0c;每个整数都 恰好出现一次 。 任务是找出重复的数字a 和缺失的数字 b 。 返回一个…...

【Mac版】Java生成二维码

软件版本 IntelliJ IDEA&#xff1a;2023.2 JDK&#xff1a;17 Tomcat&#xff1a;10.1.11 Maven&#xff1a;3.9.3 技术栈 servlet谷歌的&#xff1a;zxing 生成普通的黑白二维码在二维码中间添加一个小图标 github开源项目&#xff1a;qrcode qrcode开源项目的内部是基于z…...

ROS2自定义服务接口

ROS2自定义服务接口 在src/village_interface 下构建srv文件夹 src/village_interface/srv 下新建一个BorrowMoney.srv 遵循大小写编程规范 # 客户端请求 string name uint32 money # 中间这三个横杠很重要 不能删掉 --- # 服务端响应 bool success uint32 money接口编译 修改…...

linux /www/server/cron内log文件占用空间过大,/www/server/cron是什么内容,/www/server/cron是否可以删除

linux服务器长期使用宝塔自带计划任务&#xff0c;计划任务执行记录占用服务器空间过大&#xff0c;导致服务器根目录爆满&#xff0c;需要长期排查并删除 /www/server/cron 占用空间过大问题处理 /www/server/cron是什么内容&#xff1f;/www/server/cron是否可以删除&#xf…...

C++青少年简明教程:break语句、continue语句

C青少年简明教程&#xff1a;break语句、continue语句 break语句 只能用在switch语句和循环语句&#xff08;for循环、while循环和do-while循环&#xff09;中。作用&#xff1a;跳出switch语句或提前终止循环。 break语句的基本语法如下&#xff1a; break; break语句的示例…...

MySQL实战行转列(或称为PIVOT)实战sales的表记录了不同产品在不同月份的销售情况,进行输出

有一个sales的表&#xff0c;它记录了不同产品在不同月份的销售情况&#xff1a; productJanuaryFebruaryMarchProduct AJanuary10Product AFebruary20Product BJanuary5Product BFebruary15Product CJanuary8Product CFebruary12 客户需求展示为如下的样子&#xff1a; pro…...

牛客NC164 最长上升子序列(二)【困难 贪心+二分 Java/Go/PHP/C++】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237 思路 贪心二分 所谓贪心&#xff0c;就是往死里贪&#xff0c;所以对于最大上升子序列&#xff0c;结尾元素越小&#xff0c;越有利于后面接上其他的数&#xff0c;也就可能变…...

电子烟开发【恒压、恒有效算法】

恒压算法 pwm是通过软件模拟的 pwm满值运行是250全占空比 #define D_TARGET_AVERAGE_VOLTAGE 3500 //R_ADC1_Vout &#xff1a;发热丝两端AD值 //R_ADC_FVR &#xff1a;电池电压AD值 //FVR_VOLTAGE &#xff1a;电池AD参考电压 满电值AD //R_Smk1Duty &#xff1a;最后…...

基于Open3D的点云处理22-非阻塞可视化/动态可视化

官网测试用例:examples/python/visualization/non_blocking_visualization.py 非阻塞可视化,即实时更新点云数据; 如下,动态可视化ICP的匹配过程: import open3d as o3d import numpy as npif __name__ == "__main__":o3d.utility.set_verbosity_level(o3d.ut…...

C++面试题其一

C和C的区别 C和C都是广泛使用的编程语言&#xff0c;但它们有显著的区别&#xff1a; 语言范式&#xff1a; C&#xff1a;是一种过程化编程语言&#xff0c;强调过程和函数的使用。C&#xff1a;是一种多范式编程语言&#xff0c;支持面向对象编程、泛型编程和过程化编程。 …...

CentOS7某天的samba服务搭建操作记录(还没成功)

#CentOS7 yum软件仓库阿里云 samba服务器配置失败 sensors成功了 (花了200元组装H61测试机&#xff0c;75元的主板只有一块能用&#xff0c;垃圾板但又不完全能用&#xff09; 2024.5月的某天记录如下&#xff1a; https://blog.csdn.net/dszgf5717/article/details/53732182 …...

Qt Demo:基于TCP协议的视频传输Demo

目录 1.设计思路 2.Pro文件配置 3.头文件引入 4.界面设计 5.初始化设备函数 6.发起视频链接函数 7.初始化定时器模块函数 8.TCP链接模块函数 9.处理接收的数据线程函数 10.实现功能展示 设计思路 基于TCP协议的视频传输Demo&#xff0c;设计要实现的功能主要是TCP传输还有视频&…...

内存管理【C++】

内存分布 C中的内存区域主要有以下5种 栈&#xff08;堆栈&#xff09;&#xff1a;存放非静态局部变量/函数参数/函数返回值等等&#xff0c;栈是向下增长的【地址越高越先被使用】。栈区内存的开辟和销毁由系统自动执行 堆&#xff1a;用于程序运行时动态内存分配&#xff…...

D3D 顶点格式学习

之前D3D画三角形的代码中有这一句&#xff0c; device.VertexFormat CustomVertex.TransformedColored.Format; 这是设置顶点格式&#xff1b; 画出的三角形如下&#xff0c; 顶点格式是描述一个三维模型的顶点信息的格式&#xff1b;可以包含以下内容&#xff0c; 位置…...

gmssl vs2010编译

1、虚拟机win10 x64&#xff0c;离线安装vs2010和2010sp1补丁&#xff1b; 2、安装ActivePerl_v5.28.1.0000和nasm-2.16.03-installer-x64均是默认完整安装&#xff1b; nasm官网下载&#xff1a; Index of /pub/nasm/releasebuilds/2.16.03/win64https://www.nasm.us/pub/nas…...

容器化部署gitlab、jenkins,jenkins应用示例

一、容器化部署docker和docker conpose安装 Docker&Docker-compose的安装及部署_docker 20 使用什么版本docker-compose-CSDN博客 1.docker 安装脚本 cat >01_docker.sh<<EOF #!/bin/bash yum remove docker \docker-client \docker-client-latest \docker-co…...

基于STM32的轻量级Web服务器设计

文章目录 一、前言1.1 开发背景1.2 实现的功能1.3 硬件模块组成1.4 ENC28J60网卡介绍1.5 UIP协议栈【1】目标与特点【2】核心组件【3】应用与优势 1.6 添加UIP协议栈实现创建WEB服务器步骤1.7 ENC28J60添加UIP协议栈实现创建WEB客户端1.8 ENC28J60移植UIP协议并编写服务器测试示…...

用r语言处理 Excel数据当中的缺失值方法

以下是使用 R 编程语言处理 Excel 缺失数据的一些常见方法示例代码&#xff1a;&#xff08;无需循环&#xff09; 读取包含缺失数据的 Excel 文件 data <- read.csv(“your_file.csv”) 查看数据中是否有缺失值 sum(is.na(data)) 用平均值填充缺失值 data c o l u m …...

AWS 高防和阿里云高防深度对比

随着网络攻击的不断增加&#xff0c;企业对于网络安全的需求也越来越高。在这种情况下&#xff0c;高防护服务成为了企业网络安全的重要组成部分。AWS和阿里云作为全球领先的云计算服务提供商&#xff0c;都提供了高防护服务&#xff0c;但它们之间存在着一些差异。我们九河云一…...

ctfshow web 月饼杯II

web签到 <?php //Author:H3h3QAQ include "flag.php"; highlight_file(__FILE__); error_reporting(0); if (isset($_GET["YBB"])) {if (hash("md5", $_GET["YBB"]) $_GET["YBB"]) {echo "小伙子不错嘛&#xff…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...