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

【位运算问题】Leetcode 136、137、260问题详解及代码实现

Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。

 

🌈个人主页:主页链接

🌈算法专栏:专栏链接

     我会一直往里填充内容哒!

🌈LeetCode专栏:专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出

🌈代码仓库:Gitee链接

🌈点击关注=收获更多优质内容🌈

 

目录

先来了解一下异或^:

136. 只出现一次的数字

137. 只出现一次的数字 II

260. 只出现一次的数字 III

完结撒花:


这三个问题都为位运算中异或^的特性,所以放在一起. 可以看看之前的这篇文章有对接下俩涉及的概念lowbitx的具体讲解:位运算专题

先来了解一下异或^:

相同为0,不同则为1,这是在二进制编码中

101111^10111=000001010^0101=1111

放到一个整形数据来看,相同的数字就被消去了

此外,任意一个数异或0都为他本身 (这从二进制编码来理解也很好理解,0的二进制编码全为0,任意一个数与其异或不同的就是若干位的1)

x^x=0
x^0=x

 此外 ,异或满足结合律与交换律

a ^ b = c  => a ^ c = b  => b ^ c = a (交换律)
a ^ b ^ c = a ^ (b ^ c) = (a ^ b)^ c (结合律)

异或的特性就这么多,现在开始解题吧.

136. 只出现一次的数字

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

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

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

这题很简单,利用异或里同项相消,异项保留的特点,直接遍历^每一个数字返回遍历后的结果就可以了

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for (auto e: nums) ret ^= e;return ret;}
};

137. 只出现一次的数字 II

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

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

输入:nums = [2,2,3,2]
输出:3
输入:nums = [0,1,0,1,0,1,99]
输出:99

数组中有且仅有1个数字出现1次 其余均出现了3次。

在32位环境下一个数的二进制位由32个0/1构成。取数组中的每一个数的某一二进制位相加,得到的一定是三的倍数,或者三的倍数加一(当那唯一出现一次的数该二进制位也是1的时候)。
知道这个规律后,我们定义一个初始循环表示ans的第i位数。之后内嵌一个循环遍历数组中的每一个数。

若总数不为3的倍数,则说明该位上有唯一出现一次的数的1,将其拼到ans上。

 

class Solution {
public:int singleNumber(vector<int>& nums) {int ans=0;for(int i=0;i<32;i++){int total=0;for(auto num:nums){total+=(num>>i)&1;}if(total%3){ans|=1<<i;}}return ans;}
};

260. 只出现一次的数字 III

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

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

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

这题是第一题的升级版,有两个元素恰好出现一次,参照第一题的做法,若将这一个数组分为两个组,将这唯一出现的两个元素分别放入这两个组中,执行第一题的异或操作,最后剩下来的就是唯一出现的数字.

那么如何将两个数字分开放呢? 

观察二进制位出现的规律,一个位就两种可能,要么是1,要么是0,所以我们只要找到这两个数不相同的那一个位,以此来区分就可

 

先将所有数据^,因为除这两个数字外,其余都是两两出现,^后的结果为这两个数字的结果.

再用lowbit思想 返回其第一个出现1的数字(异或完lowbit返回的是这两个数字第一个不相同的位)

在进行一个循环将每一个数与这个数,无非就两种结果,将这两种结果分组,即可

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:vector<int> singleNumber(vector<int>& nums) {vector<int>ans1;vector<int>ans2;vector<int>ans3(2);long tag=0;for(auto n:nums)tag^=n;long ans=0;ans=tag&(-tag);//lowbitfor(auto n:nums){if(n&ans){ans3[0]^=n;}else ans3[1]^=n;}return ans3;}
};

完结撒花:

🌈本篇博客的内容【Leetcode 136、137、260问题详解及代码实现】已经结束。

🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。

🌈诸君,山顶见!

相关文章:

【位运算问题】Leetcode 136、137、260问题详解及代码实现

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…...

同花顺2023届春招内推

同花顺2023届春招开始啦&#xff01; 同花顺是国内首家上市的互联网金融信息服务平台&#xff0c;如果你对互联网金融感兴趣&#xff0c;如果你有志向在人工智能方向发挥所长&#xff0c;如果你也是一个激情澎湃的小伙伴&#xff0c;欢迎加入我们&#xff01;岗位类别&#xf…...

深入Kafka核心设计与实践原理读书笔记第三章消费者

消费者 消费者与消费组 消费者Consumer负责定于kafka中的主题Topic&#xff0c;并且从订阅的主题上拉取消息。与其他消息中间件不同的在于它有一个消费组。每个消费者对应一个消费组&#xff0c;当消息发布到主题后&#xff0c;只会被投递给订阅它的消费组的一个消费者。 如…...

IDEA 中使用 Git 图文教程详解

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

【Linux系统】进程概念

目录 1 冯诺依曼体系结构 2 操作系统(Operator System) 概念 设计OS的目的 定位 总结 系统调用和库函数概念 3 进程 3.1 基本概念 3.2 描述进程-PCB 3.2 组织进程 3.3 查看进程 3.4 通过系统调用获取进程标示符 3.5 进程状态 在了解进程概念前我们还得了解下冯诺…...

上课睡觉(2023寒假每日一题 4)

有 NNN 堆石子&#xff0c;每堆的石子数量分别为 a1,a2,…,aNa_1,a_2,…,a_Na1​,a2​,…,aN​。 你可以对石子堆进行合并操作&#xff0c;将两个相邻的石子堆合并为一个石子堆&#xff0c;例如&#xff0c;如果 a[1,2,3,4,5]a[1,2,3,4,5]a[1,2,3,4,5]&#xff0c;合并第 2,32…...

【Selenium学习】Selenium 中常用的基本方法

1&#xff0e;send_keys 方法模拟键盘键入此方法类似于模拟键盘键入。以在百度首页搜索框输入“Selenium”为例&#xff0c;代码如下&#xff1a;# _*_ coding:utf-8 _*_ """ name:zhangxingzai date:2023/2/13 form:《Selenium 3Python 3自动化测试项目实战》 …...

python练习——简化路径

项目场景&#xff1a; 给你一个字符串 path &#xff0c;表示指向某一文件或目录的 Unix 风格 绝对路径 &#xff08;以 /开头&#xff09;&#xff0c;请你将其转化为更加简洁的规范路径。在 Unix 风格的文件系统中&#xff0c;一个点&#xff08;.&#xff09;表示当前目录本…...

2023新华为OD机试题 - 火星文计算2(JavaScript) | 刷完必过

火星文计算 2 题目 已知火星人使用的运算符号为#;$ 其与地球人的等价公式如下 x#y=4*x+3*y+2 x$y=2*x+y+3 x y是无符号整数 地球人公式按照 c 语言规则进行计算 火星人公式中#符优先级高于$ 相同的运算符按从左到右的顺序运算 输入 火星人字符串表达式结尾不带回车换行 输入…...

前端插件重磅来袭

“你值得拥有”专栏系列上新啦&#xff0c;今日推出“手写前端插件”项目&#xff0c;作为一个前端中高级工程师&#xff0c;手写前端树形菜单插件、弹出层插件、日历插件、分页插件、选项卡插件、进度条插件等是必备的技能&#xff0c;让你的前端技术百尺竿头更进一步&#xf…...

深入工厂|高精密多层板是如何被智造出来的?

或许有很多人从网络上见过各种教程&#xff0c;告诉你单层板是什么&#xff0c;多层板是什么&#xff0c;他们该如何做出来&#xff0c;但是在具体制造时却全凭想象&#xff0c;今天&#xff0c;就让我们来实地看看&#xff0c;精密的多层板是如何被制造出来的&#xff01;今天…...

代理模式动态代理

什么是代理模式&#xff1f; 代理模式是开发中常见的一种设计模式&#xff0c;使用代理模式可以很好的对程序进行横向扩展。代理&#xff0c;顾名思义就是一个真实对象会存在一个代理对象&#xff0c;并且代理对象可以替真实对象完成相应操作&#xff0c;外部通过代理对象来访…...

Mysql之二进制日志

目录 二进制日志 12-37 二进制日志格式 基于行的二进制日志 基于语句的二进制日志 混合格式二进制日志 复制日志 12-42 故障安全 (Crash-Safe) 复制 多源复制 二进制日志 12-37 二进制日志&#xff1a; • 包含数据和模式更改及其时间戳 – 基于语句 或 基于行 的日志…...

kail工具的使用--- cewl

1.介绍 Cewl是一款采用Ruby开发的应用程序&#xff0c;可以给他的爬虫指定URL地址和爬取深度&#xff0c;还可以添加外部链接&#xff0c;接下来Cewl会给你返回一个字典文件&#xff0c;你可以把字典用到类似John the Ripper这样的密码破解工具中。 2.使用 输入以下命令之后…...

【蓝桥杯集训1】前缀和专题(2 / 5)

目录 前缀和模板 &#xff01;3956. 截断数组 - 前缀和枚举 前缀和模板 活动 - AcWing import java.util.*;class Main {static int N100010;static int[] anew int[N],snew int[N];public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nex…...

基于模块联邦的微前端实现方案

一、 微前端应用案例概述 当前案例中包含三个微应用&#xff0c;分别为 Marketing、Authentication 和 Dashboard Marketing&#xff1a;营销微应用&#xff0c;包含首页组件和价格组件 Authentication&#xff1a;身份验证微应用&#xff0c;包含登录组件 Dashboard&#x…...

【单目标优化算法】食肉植物优化算法(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

ANTLR4入门学习(四)

ANTLR4入门学习&#xff08;四&#xff09;一、设计语法1.语法2.ANTLR核心标记3.常见计算机语言模式4.左右递归5.识别常见的语法结构5.1 匹配标识符5.2 匹配数字5.3 匹配字符串常量5.4 匹配注释和空白字符5.5 基础的语法规则5.6 划定词法分析器和语法分析器的界线一、设计语法 …...

Android okhttp3中发送websocket消息,并通过mockwebserver将一个安卓设备模拟成服务器接发消息

websocket 提供了客户端和服务端的长链接&#xff0c;允许客户端和服务端双向发送消息 okhttp 提供了使用websocket 相关接口议。同时为方便单元测试&#xff0c;又提供了mockwebserver可以把一个安卓客户端作为服务端接受消息。 websocket使用 权限 <uses-permission an…...

MySQL系统变量和自定义变量

1 系统变量1.1 查看系统变量可以使用以下命令查看 MySQL 中所有的全局变量信息。SHOW GLOBAL VARIABLES; MySQL 中的系统变量以两个“”开头。global 仅仅用于标记全局变量&#xff1b;session 仅仅用于标记会话变量&#xff1b;首先标记会话变量&#xff0c;如果会话变量不存在…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...