从零学算法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} 1−m之和=2m(1+m)
- 1 − m 的平方和 = m ( m + 1 ) ( 2 m + 1 ) 6 { 1 - m 的平方和=\frac {m(m+1)(2m+1)} 6} 1−m的平方和=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,大小为 n * n ,其中的值在 [1, n2] 范围内。除了 a 出现 两次,b 缺失 之外,每个整数都 恰好出现一次 。 任务是找出重复的数字a 和缺失的数字 b 。 返回一个…...
【Mac版】Java生成二维码
软件版本 IntelliJ IDEA:2023.2 JDK:17 Tomcat:10.1.11 Maven:3.9.3 技术栈 servlet谷歌的:zxing 生成普通的黑白二维码在二维码中间添加一个小图标 github开源项目: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服务器长期使用宝塔自带计划任务,计划任务执行记录占用服务器空间过大,导致服务器根目录爆满,需要长期排查并删除 /www/server/cron 占用空间过大问题处理 /www/server/cron是什么内容?/www/server/cron是否可以删除…...
C++青少年简明教程:break语句、continue语句
C青少年简明教程:break语句、continue语句 break语句 只能用在switch语句和循环语句(for循环、while循环和do-while循环)中。作用:跳出switch语句或提前终止循环。 break语句的基本语法如下: break; break语句的示例…...
MySQL实战行转列(或称为PIVOT)实战sales的表记录了不同产品在不同月份的销售情况,进行输出
有一个sales的表,它记录了不同产品在不同月份的销售情况: productJanuaryFebruaryMarchProduct AJanuary10Product AFebruary20Product BJanuary5Product BFebruary15Product CJanuary8Product CFebruary12 客户需求展示为如下的样子: pro…...
牛客NC164 最长上升子序列(二)【困难 贪心+二分 Java/Go/PHP/C++】
题目 题目链接: https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237 思路 贪心二分 所谓贪心,就是往死里贪,所以对于最大上升子序列,结尾元素越小,越有利于后面接上其他的数,也就可能变…...
电子烟开发【恒压、恒有效算法】
恒压算法 pwm是通过软件模拟的 pwm满值运行是250全占空比 #define D_TARGET_AVERAGE_VOLTAGE 3500 //R_ADC1_Vout :发热丝两端AD值 //R_ADC_FVR :电池电压AD值 //FVR_VOLTAGE :电池AD参考电压 满电值AD //R_Smk1Duty :最后…...
基于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都是广泛使用的编程语言,但它们有显著的区别: 语言范式: C:是一种过程化编程语言,强调过程和函数的使用。C:是一种多范式编程语言,支持面向对象编程、泛型编程和过程化编程。 …...
CentOS7某天的samba服务搭建操作记录(还没成功)
#CentOS7 yum软件仓库阿里云 samba服务器配置失败 sensors成功了 (花了200元组装H61测试机,75元的主板只有一块能用,垃圾板但又不完全能用) 2024.5月的某天记录如下: 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,设计要实现的功能主要是TCP传输还有视频&…...
内存管理【C++】
内存分布 C中的内存区域主要有以下5种 栈(堆栈):存放非静态局部变量/函数参数/函数返回值等等,栈是向下增长的【地址越高越先被使用】。栈区内存的开辟和销毁由系统自动执行 堆:用于程序运行时动态内存分配ÿ…...
D3D 顶点格式学习
之前D3D画三角形的代码中有这一句, device.VertexFormat CustomVertex.TransformedColored.Format; 这是设置顶点格式; 画出的三角形如下, 顶点格式是描述一个三维模型的顶点信息的格式;可以包含以下内容, 位置…...
gmssl vs2010编译
1、虚拟机win10 x64,离线安装vs2010和2010sp1补丁; 2、安装ActivePerl_v5.28.1.0000和nasm-2.16.03-installer-x64均是默认完整安装; nasm官网下载: 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 缺失数据的一些常见方法示例代码:(无需循环) 读取包含缺失数据的 Excel 文件 data <- read.csv(“your_file.csv”) 查看数据中是否有缺失值 sum(is.na(data)) 用平均值填充缺失值 data c o l u m …...
AWS 高防和阿里云高防深度对比
随着网络攻击的不断增加,企业对于网络安全的需求也越来越高。在这种情况下,高防护服务成为了企业网络安全的重要组成部分。AWS和阿里云作为全球领先的云计算服务提供商,都提供了高防护服务,但它们之间存在着一些差异。我们九河云一…...
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 "小伙子不错嘛ÿ…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
