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

每日刷题(一)——只出现一次的数字

前言

今天遇到一个位运算的题目,感觉很有意思,记录一下。

Question1

136. 只出现一次的数字

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

输入:nums = [2,2,1]
输出:1

Solution

拿到题目,可以首先可以想到最暴力的解法,首先遍历整个数组,将每个元素的数量都存在map中,随后遍历map即可得出答案。时间复杂度O(N)、空间复杂度O(N)。显然不满足常量额外空间的要求。

更优一点的方法是使用异或操作,因为对同一个数的两次异或会返回原值(异或还经常用于加密领域,有一类密码叫做异或密码)。声明一个变量,随后遍历整个数组,对每个数都与此变量进行一次异或操作,最后这个值就是答案。

Code

func singleNumber(nums []int) int {var temp intfor _ , v := range nums{temp ^= v}return temp}

Question2

137. 只出现一次的数字 II

给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。

输入:nums = [2,2,3,2]
输出:3

Solution

同样的,这题的暴力解法也可以使用map,但是会有额外的O(N)空间复杂度。

这题异或好像使用不了,因为都是奇数,查看题解后发现,居然可以统计每一个比特位1的个数,将其做余3的操作后,就可以得到答案中此比特位的位。所以遍历31次,得到每一个比特位的值,再拼接成最后的答案即可。时间复杂度为O(32N)= O(N),空间复杂度为O(1),代码如下:

Code

func singleNumber(nums []int) int {result := int32(0)for i := 0; i < 32; i++ {num:=int32(0)for _,v := range nums {num	+=  (int32(v) >> i) & 1}if num % 3 > 0{result |= (1<<i)}}return int(result)}

Question3

137. 只出现一次的数字 III

给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

输入:nums = [1,2,1,3,2,5]
输出:[3,5]
解释:[5, 3] 也是有效的答案。

Solution

同样的,这题的暴力解法也可以使用map,但是会有额外的O(N)空间复杂度。

这题可以使用异或来做,首先定义一个变量,将所有的数都与此变量进行异或,最后得到的结果就是两个只出现一次的异或的值。

通过这个值将nums里面的元素分为两组(两组中分别包含一个答案),对两组分别 使用异或,最后得到结果。

如何进行分组呢,我们的目的是两组汇总分别包含一个答案,所以可以根据两者的异或值,来找到某一个不一样的比特位,通过此比特位进行分组即可,代码如下:

Code

func singleNumber(nums []int) []int {
// 获得两个答案的异或值temp := 0for i := 0; i < len(nums); i++ {temp ^= nums[i]}//找到temp中第一个为1的比特位,根据异或的原理,说明在这个比特位上,两个答案一个为1,一个为0,以此比特位作为分组的依据index := 0for i := 0; i < 32; i++ {if (temp << i) & 1 == 1{index = ibreak}}var ans1 intvar ans2 intfor i := 0; i < len(nums); i++ {if (nums[i]<<i) & 1 == 0{ans1 ^= nums[i]}else{ans2 ^= nums[i]}}return []int{ans2,ans1}
}

总结

对于位运算的题目,要思考与、或、非、异或等操作,来合理完成题目的要求。

相关文章:

每日刷题(一)——只出现一次的数字

前言 今天遇到一个位运算的题目&#xff0c;感觉很有意思&#xff0c;记录一下。 Question1 136. 只出现一次的数字 给你一个 非空 整数数组 nums &#xff0c;除了某个元素只出现一次以外&#xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实…...

洛谷P5737 【深基7.例3】闰年展示 C语言/C++

【深基7.例3】闰年展示 题目描述 输入 x,yx,yx,y&#xff0c;输出 [x,y][x,y][x,y] 区间中闰年个数&#xff0c;并在下一行输出所有闰年年份数字&#xff0c;使用空格隔开。 输入格式 输入两个正整数 x,yx,yx,y&#xff0c;以空格隔开。 输出格式 第一行输出一个正整数&a…...

shell注释

注释对于任何编程语言都是不可忽视的重要组成部分&#xff0c;编写者通过注释来为其他人提供解释或提示&#xff0c;能有效提高代码的可读性。 Bash 同其他编程语言一样提供了两种类型注释的支持。 单行注释多行注释一、Bash 单行注释 在注释段落的开头使用 # &#xff0c;如下…...

【C++入门(上篇)】C++入门学习

前言&#xff1a; 在之前的学习中&#xff0c;我们已经对初阶数据结构进行相应了学习&#xff0c;加上之前C语言的学习功底。今天&#xff0c;我们将会踏上更高一级“台阶”的学习-----即C的学习&#xff01;&#xff01;&#xff01; 文章目录1.C 简介1.1什么是C1.2.C的发展史…...

【密码学】 一篇文章讲透数字签名

【密码学】 一篇文章讲透数字签名 数字签名介绍 数字签名&#xff08;又称公钥数字签名&#xff09;是只有信息的发送者才能产生的别人无法伪造的一段数字串&#xff0c;这段数字串同时也是对信息的发送者发送信息真实性的一个有效证明。它是一种类似写在纸上的普通的物理签名…...

POI导入导出、EasyExcel批量导入和分页导出

文件导入导出POI、EasyExcel POI&#xff1a;消耗内存非常大&#xff0c;在线上发生过堆内存溢出OOM&#xff1b;在导出大数据量的记录的时候也会造成堆溢出甚至宕机&#xff0c;如果导入导出数据量小的话还是考虑的&#xff0c;下面简单介绍POI怎么使用 POI导入 首先拿到文…...

手把手教你做微信公众号

手把手教你做微信公众号 微信公众号可以通过注册的方式来建立。 1.进入微信公众平台 首先&#xff0c;在浏览器中搜索微信公众号&#xff0c;网页第一个就是&#xff0c;如下图所示&#xff0c;我们点进去。 2.注册微信平台账号 进入官网之后&#xff0c;如下图所示&#…...

python-在macOS上安装python库 xlwings失败的解决方式

问题&#xff1a;python库 xlwings安装失败 今天&#xff0c;看到网上有wlwings库&#xff0c;可以用来处理excel表格&#xff0c;立刻想试一试。结果&#xff0c;安装这个python库失败了。经过排查&#xff0c;问题解决。 安装过程和错误提示&#xff1a; 我用最简单直接的…...

【Linux】进程间通信(匿名管道和命名管道通信、共享内存通信)

文章目录1、进程间通信1.1 进程的通信1.2 如何让进程间通信&#xff1f;1.3 进程间通信的本质2、管道通信2.1 匿名管道2.2 匿名管道通信2.3 命名管道2.4 命名管道的通信3、SystemV中的共享内存通信3.1 共享内存3.2 共享内存的通信3.3 共享内存的缺点以及数据保护3.4 共享内存的…...

漏洞分析: WSO2 API Manager 任意文件上传、远程代码执行漏洞

漏洞描述 某些WSO2产品允许不受限制地上传文件&#xff0c;从而执行远程代码。以WSO2 API Manager 为例&#xff0c;它是一个完全开源的 API 管理平台。它支持API设计&#xff0c;API发布&#xff0c;生命周期管理&#xff0c;应用程序开发&#xff0c;API安全性&#xff0c;速…...

详解Android 13种 Drawable的使用方法

前言关于自定义View&#xff0c;相信大家都已经很熟悉了。今天&#xff0c;我想分享一下关于自定义View中的一部分&#xff0c;就是自定义Drawable。Drawable 是可绘制对象的一个抽象类&#xff0c;相对比View来说&#xff0c;它更加的纯粹&#xff0c;只用来处理绘制的相关工作…...

MakeFile教程

前言 当我们需要编译一个比较大的项目时&#xff0c;编译命令会变得越来越复杂&#xff0c;需要编译的文件越来越多。其 次就是项目中并不是每一次编译都需要把所有文件都重新编译&#xff0c;比如没有被修改过的文件则不需要重 新编译。工程管理器就帮助我们来优化这两个问题…...

Spring使用mongoDB步骤

1. 在Linux系统使用docker安装mongoDB 1.1. 安装 在docker运行的情况下&#xff0c;执行下述命令。 docker run \ -itd \ --name mongoDB \ -v mongoDB_db:/data/db \ -p 27017:27017 \ mongo:4.4 \ --auth执行docker ps后&#xff0c;出现下列行&#xff0c;即表示mongoDB安…...

【蓝牙mesh】access层(接入层)协议介绍

【蓝牙mesh】access层&#xff08;接入层&#xff09;协议介绍 Access层简介 Access层定义了应用层如何使用upper协议层的接口&#xff0c;它不仅定义了应用层的格式&#xff0c;还定义了应用数据在upper层的加密和解密。当收到下层的数据包时&#xff0c;它会检查数据的netke…...

【一天一门编程语言】JavaScript 语言程序设计极简教程

JavaScript 语言程序设计极简教程 用 markdown 格式输出答案。 不少于3000字。细分到2级目录。 一、JavaScript 简介 1.1 什么是 JavaScript JavaScript 是一种由Netscape的LiveScript发展而来的脚本语言&#xff0c;是一种动态类型、弱类型、基于原型的语言&#xff0c;内…...

CMake调试器出炉:调试你的CMake脚本

Visual Studio 开发团队一直和 Kitware 紧密合作&#xff0c;致力于开发一个用于调试 CMake 脚本的调试器。 我们将继续这个工作&#xff0c;以便开发人员社区可以通过添加新功能和对其他 DAP 功能的支持来共同改进它。 我们很高兴地宣布&#xff0c;CMake 调试器的预览版现在…...

题解 # 二维矩阵最大矩形问题#

题目&#xff1a; 小明有一张N*M的方格纸&#xff0c;且部分小方格中涂了颜色&#xff0c;部分小方格还是空白。 给出N (2<Ns30)和M(2sMs30)的值&#xff0c;及每个小方格的状态(&#xff08;被涂了颜色小方格用数字1表示&#xff0c;空白小方格用数字0表示)&#xff1b; 请…...

奔四的路上,依旧倔强的相信未来

本文首发于2022年12月31日 原标题: 奔四的路上,依旧倔强的相信未来!–我的2022年终总结 读大学那几年,一直保持着写日记和做计划的习惯,还记得大学毕业刚开始打工的时候,我的床头的墙上一定会画一张表,写上一个月的计划和一周的计划 计划也会有完不成的时候,但加深了…...

61 k8s + rancher + karmada容器化部署

文章目录 一、什么是rancher二、为什么使用rancher三、rancher安装1、细部介绍四、图形化操作1、执行2、补充五、 karmada1、官网2、细部介绍一、什么是rancher 1、Rancher 是一个 全栈式 的 Kubernetes 容器管理平台,为你提供在任何地方都能成功运行 Kubernetes 的工具。 二…...

Vue3的新特性变化,上手指南!

文章目录一、Vue3相比Vue2&#xff0c;更新了什么变化&#xff1f;二、Proxy 代理响应式原理三、组合式 API (Composition API)setup()函数:ref()函数reactive()函数组合式 setup 中使用 Props 父向子传递参数计算属性watch&#xff08;数据监视&#xff09;watchEffect&#x…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...

​​企业大模型服务合规指南:深度解析备案与登记制度​​

伴随AI技术的爆炸式发展&#xff0c;尤其是大模型&#xff08;LLM&#xff09;在各行各业的深度应用和整合&#xff0c;企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者&#xff0c;还是积极拥抱AI转型的传统企业&#xff0c;在面向公众…...

拟合问题处理

在机器学习中&#xff0c;核心任务通常围绕模型训练和性能提升展开&#xff0c;但你提到的 “优化训练数据解决过拟合” 和 “提升泛化性能解决欠拟合” 需要结合更准确的概念进行梳理。以下是对机器学习核心任务的系统复习和修正&#xff1a; 一、机器学习的核心任务框架 机…...

鸿蒙Navigation路由导航-基本使用介绍

1. Navigation介绍 Navigation组件是路由导航的根视图容器&#xff0c;一般作为Page页面的根容器使用&#xff0c;其内部默认包含了标题栏、内容区和工具栏&#xff0c;其中内容区默认首页显示导航内容&#xff08;Navigation的子组件&#xff09;或非首页显示&#xff08;Nav…...