剑指offer-消失的数字、数组中出现的次数
消失的数字

解法一:求和相减
假设nums为[0,1,2,4],消失的数字为3,完整的数组应该是[0,1,2,3,4],则sum1=0+1+2+4=7,sum2=0+1+2+3+4=10,我们很容易发现
sum2-sum1 = 0+1+2+3+4 - 0+1+2+4 = 3,即为消失的数字。因此,我们可以采用先相加再相减的方法,就可以求出消失的数字。
代码如下:
int missingNumber(int* nums, int numsSize)
{int tmp = 0;int talg = 0;for (int i = 0;i <= numsSize;i++){tmp = tmp + i;//求数组下标之和}for (int j = 0;j < numsSize;j++){talg += nums[j];//求数组元素之和}return tmp - talg;
}
解法二:异或
首先我们得清楚异或 ^ 的原理:
相同为0,相异为1,并且0^任何数都等它本身
a ^ a = 0、a ^ b = b ^ a、0 ^ a = a 、(a!=b)
那么根据上述的原理我们便可以使用异或进行解题:
首先异或上所有数,n即为此数组元素个数,即ret = 0 ^ 1^ 2^ …^n
然后对数组元素异或,nums[0]^ nums[1] ^ …^ nums[numsSize-1]
然后异或这二者,即
ret = 0^ 1^ 2^ 3^ …^ n^ nums[0] ^ nums[1]^ …^nums[numsSize-1]
最终ret就为消失的数字
打个比方:nums[] = {2,3,4,5,6}
ret = 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 1.
int missingNumber(int* nums, int numsSize)
{//异或int ret = 0;//先异或0-n的所有数for(int i = 0; i <= numsSize; ++i){ret ^= i;}//再将ret与数组所有数异或for(int i = 0; i < numsSize; ++i){ret ^= nums[i];}return ret;
}
数组中出现的次数

同上可得,此题采用异或的位运算是最合适的。
int* singleNumbers(int* nums, int numsSize, int* returnSize) {int ret = 0;int i = 0;int num1 = 0;int num2 = 0;int pos = 0;int* arr = (int*)malloc(2 * sizeof(int));//通过0对自身依次异或,将两个单独的数的异或后的结果找出for (i = 0; i < numsSize; i++){ret ^= nums[i];}//找到异或后结果的二进制序列,找出为1的位数for (i = 0; i < 32; i++){if ((ret >> i) & 1 == 1){pos = i;break;}}//找到位数后,将按其他数的这个位数是否为1,还是为0进行分离,形成两组数,分别自身异或,最后剩下的就是单独的数。for (i = 0; i < numsSize; i++){if ((nums[i] >> pos) & 1 == 1){num1 ^= nums[i];}else{num2 ^= nums[i];}}arr[0] = num1;arr[1] = num2;*returnSize = 2;return arr;
}
相关文章:
剑指offer-消失的数字、数组中出现的次数
消失的数字 解法一:求和相减 假设nums为[0,1,2,4],消失的数字为3,完整的数组应该是[0,1,2,3,4],则sum101247,sum20123410,我们很容易发现 sum2-sum1 01234 - 0124 3,即为消失的数字。因此,我们可以采用先…...
axios请求配置baseURL选项
在src同级目录创建 (1).env.delelopment : 开发模式时调用 (2).env.production :生产模式时调用 (3).env.testing : 测试模式时调用 # 页面标题 VITE_APP_TITLE 若依管理系统# 生产环境配…...
风储VSG-基于虚拟同步发电机的风储并网系统MATLAB仿真
MATLAB2021b版本仿真模型:风力发电机模块、储能控制模块、功率计算模块、VSG控制模块、电压电流双环控制模块。永磁同步风机输出功率、储能系统输出功率以及逆变器输出功率曲线。直流母线电压波动曲线。逆变器输出电压、电流曲线。完整模型见博主资源!&a…...
vim常用命令
vim常用三种模式 命令模式(Command mode) 插入模式(Insert mode) 末行模式(Last line mode) (一)进入命令模式 vi 或者 vim(二)命令模式 -> 插入模式 &…...
华为OD机试 - 最差产品奖 | 机试题算法思路 【2023】
最近更新的博客 华为OD机试 - 简易压缩算法(Python) | 机试题算法思路 【2023】 华为OD机试题 - 获取最大软件版本号(JavaScript) 华为OD机试 - 猜字谜(Python) | 机试题+算法思路 【2023】 华为OD机试 - 删除指定目录(Python) | 机试题算法思路 【2023】 华为OD机试 …...
HR:你会Python数据分析吗?
之前看到一个段子: 以前去面试,HR会问你“精通office吗?” 现在去面试,HR会问你“会Python数据分析吗?” 图片来源:网络 大数据时代,无论是数据分析师、研发,到运营、市场、产品经…...
算法18:LeetCode_链表相关算法题
链表无小事,只要是涉及到链表的算法题,边界值的设定尤为重要,而且及其容易出错误。这就要求我们平时多加练习。但是,我们在面试和笔试的过程中往往会碰到链表相关的题目,所以我们在笔试的时候一般都会借助系统提供的工…...
SpringBoot集成Tomcat服务
文章目录一、Tomcat集成1、依赖层级2、自动化配置二、Tomcat架构三、Tomcat配置1、基础配置2、属性配置类3、配置加载分析四、周期管理方法1、控制类2、核心方法使用的成本越低,内部封装越复杂; 一、Tomcat集成 1、依赖层级 在SpringBoot框架的web依赖…...
【机器学习】决策树-C4.5算法
1.C4.5算法 C4.5算法与ID3相似,在ID3的基础上进行了改进,采用信息增益比来选择属性。ID3选择属性用的是子树的信息增益,ID3使用的是熵(entropy, 熵是一种不纯度度量准则),也就是熵的变化值&…...
actipro-winforms-controls-23.1.0 Crack
actipro-winforms一组用于构建漂亮的 Windows 窗体桌面应用程序的 UI 控件,用于构建 IDE 的高级停靠窗口、MDI、属性网格、树控件和文件夹/文件浏览器,用于常见数据类型、自动完成、屏蔽编辑和代码编辑的强大编辑器,功能区、图表、微型图表、…...
适合打游戏用的蓝牙耳机有哪些?吃鸡无延迟的蓝牙耳机推荐
现在手游的兴起,让游戏市场变得更加火爆,各种可以提高玩家体验的外设也越来越多,除了提升操作的外置按键与手柄外,能带来更出色音质与舒心使用的游戏耳机,整体氛围感更好,让玩家在细节上占据优势࿰…...
1000:入门测试题目[不一样的题解][85种写法]【A+B问题】
题目: 1000:入门测试题目 时间限制: 1000 ms 内存限制: 32768 KB 提交数: 262857 通过数: 158152 【题目描述】 求两个整数的和。 【输入】 一行,两个用空格隔开的整数。 【输出】 两个整数的和。 【输入样例】 2 3 【输出样例】…...
FastReport .NET 2023.1.13 Crack
FastReport .NET 使用来自 ADO .NET 数据源的数据。它可以排序和过滤数据行,使用主从关系和查找数据列。一切都可以通过点击几下鼠标来完成。 直接连接到 ADO、MS SQL 或基于 xml 的数据库。其他连接器可作为插件使用。 能够从 IEnumerable 类型的业务对象中获取数…...
unzip: cannot find zipfile directory in one of
下面是执行flutter doctor 后报错内容 End-of-central-directory signature not found. Either this file is not a zipfile, or it constitutes one disk of a multi-part archive. In the latter case the central directory and zipfile comment will be found on the last …...
RFC4543: Galois Message Authentication Code (GMAC);CONFIG_CRYPTO_GCM
在2010年这个算法被Linux社区加进来:说明算法还是挺重要,普遍使用。 commit 73c89c15b959adf06366722c4be8d2eddec0a529 Author: Tobias Brunner <tobias@strongswan.org> Date: Sun Jan 17 21:52:11 2010 +1100crypto: gcm - Add RFC4543 wrapper for GCMThis patc…...
【YOLOv5】 02-标注图片,训练并使用自己的模型
在上一篇文章中,我们完成了YOLOv5的安装和测试。如果想检测自定义目标,就需要用到LabelImg来对图片打标签,本篇文章介绍了LabelImg安装与使用,以及如何训练并使用自己的模型。一、安装LabelImg输入如下命令进行安装:pi…...
2023.2.15日学习内容(用户的增删改查)
1,如果前端时间需要年月日,不需要时分秒,则一般情况下再数据库里面操作即可2.正常情况下,以后所有的查询都不能用* 查询所有列3.删除思路逻辑1)点击删除按钮需要对其进行监听2)对于重要的信息删除应该给用户…...
车载以太网 - 测试用例设计 - 时间参数 - 11
前面已经介绍过DoIP相关的时间参数信息,然而对于时间参数信息相关的测试用例该如何设计呢?个人认为这是用例中最好设计的一类,这类的用例只需要按照定义去设计写测试用例即可,难的是自动化脚本开发和手动测试执行。毕竟时间参数一般都是毫秒级的验证,就算是秒级的我们也很…...
【C#个人错题笔记】
观前提醒 记录一些我不会或者少见的内容,不一定适合所有人 字符串拼接 int a3,b8; Console.WriteLine(ab);//11 Console.WriteLine("ab");//ab Console.WriteLine(a""b);//38 Console.WriteLine("ab"ab);//ab38 Console.WriteLine…...
JavaScript刷LeetCode拿offer-树的遍历
什么是树 一种分层数据的抽象模型。前端工作中常见的树包括:DOM树,级联选择,树形控件JS中没有树,可以用Object和Array构建树树的常用操作:深度/广度优先遍历,先中后序遍历 深度优先遍历 访问根节点对根节…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
