草庐IT

【LeetCode每日一题】找（一只或者多只）单身狗

陈大大陈 2023-04-10 原文

【LeetCode刷题】——找（一只或者多只）单身狗😎😎😎 

目录

💛找（一只或者多只）单身狗题目💛 

💪 解题思路的分享💪  （一只单身狗）

 😊题目源码的分享😊

💪 解题思路的分享💪  （多只单身狗）

 😊题目源码的分享😊

👉 本菜鸡&总结 👈

 

😎博客昵称：陈大大陈

😊座右铭：所谓觉悟，就是在漆黑的荒野上开辟出一条理当前进的光明大道。

😋博主简介：一名热爱C/C++和算法等技术，喜欢运动，爱胡思乱想却胸怀大志的小博主！

😚博主&唠嗑：早午晚哈喽Ciao！😄各位CSDN的朋友！😄我是博客新人陈大大陈，希望我的文章能为你带来帮助！欢迎大家在评论区畅所欲言！也希望大家多多为我提出您宝贵的建议！😘如果觉得我写的不错的话还请点个赞和关注哦~😘😘😘

💛找（一只或者多只）单身狗题目💛 

作业标题

找单身狗

作业内容

一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

例如：

有数组的元素是：1，2，3，4，5，1，2，3，4，6

只有5和6只出现1次，要找出5和6.

💪 解题思路的分享💪  （一只单身狗）

  • 我们需要用到 ^，也就是异或操作符。
  • “ ^ ”的异或指的是二进制中，对应的对应二进制位相同时异或为零，相异时异或为一
  • 我们知道，大小相同的数字异或结果一定为0，而0与任何数字进行异或大小不会改变。
  • 那么当单身狗只有一个时，我们可以直接让所有的数据异或在一起，这样最后得出来的就一定是那只单身狗了。

 😊题目源码的分享😊

我们来看下面的例子。

#include<stdio.h>
void Single_Dog(int *a, int sz,int *x)
{
	for (int i = 0; i < sz; i++)
	{
		*x ^= a[i];
	}
}
int main()
{
	int x = 0;
	int a[] = { 1,1,2,2,3,3,4,4,5 };
	int sz = sizeof(a) / sizeof(a[0]);
	Single_Dog(a, sz, &x);
	printf("单身狗是%d",x);
	return 0;
}

运行结果如下：

  成功找出单身狗5！

💪 解题思路的分享💪  （多只单身狗）

上面是只有一只单身狗的情况，如果单身狗有两只该怎么办呢？

  • 首先，我们肯定是不能把它们一股脑地异或到一起了，因为单身狗们大小既不相等也大概率不为0，肯定是找不出来的。
  • 不过我们知道，最后异或出来的结果肯定不为0，因为单身狗们的大小肯定不相等。
  • 那我们就找到了解题思路——通过将两只单身狗分组来达到上面只有一只单身狗的情况，然后分别异或到一起。
  • 分组的方法就可以按照异或的结果来，异或相同位0，相异为1，我们就可以找第一个不相等的位置来将单身狗分组，也就是异或结果二进制位里面第一个为1的位置，记录下这个位置。
  • 之后再定义两个变量用来作为两只单身狗，初始化为0。
  • 紧接着遍历数组，当所遍历到的数据右移上面所保存的位置和1按位与的结果为1时，就将它与x异或，反之就和y异或。
  • 这样一通操作下来，x和y就变成了单身狗的样子了！

 😊题目源码的分享😊

#include<stdio.h>
void Single_Dog(int* a,int sz,int *m,int *n)
{
	int i, pos = 0, ret = 0;
	for (i = 0; i < sz; i++)
	{
		ret^= a[i];
	}
	for (i = 0; i < 32; i++)
	{
		if (ret >> i == 1)
		{
			pos = i;
			break;
		}
	}
	for (i = 0; i < sz; i++)
	{
		if ((a[i]>>pos&1) == 0)
		{
			*m ^= a[i];
		}
		else if ((a[i] >> pos&1) == 1)
		{
			*n ^= a[i];
		}
	}
	
}
int main()
{
	int a[] = { 1,1,2,2,3,3,4,4,5,5,6,6,7,8 };
	int sz = sizeof(a) / sizeof(a[0]);
	int m = 0,  n = 0;
	Single_Dog(a, sz, &m, &n);
	printf("%d %d", m, n);
	return 0;
}

👉 本菜鸡&总结 👈

这篇博客旨在总结我自己阶段性的学习，要是能帮助到大家，那可真是三生有幸！😀如果觉得我写的不错的话还请点个赞和关注哦~我会持续输出编程的知识的！🌞🌞🌞 

这道题目的方法很难想到，实在不行的话咱们也可以直接采取暴力方式

也就是先排序，在经过一系列操作找出单身狗，不过这个方法有点太复杂了。

LeetCode每日ampquotgt

有关【LeetCode每日一题】找（一只或者多只）单身狗的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  3. 蓝桥杯C/C++VIP试题每日一练之报时助手 - 2

    ?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是：　　如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。　　如果m不为0，则将时读出来，然后将分读出来，如5

  4. Python：每日一题之小张的衣服（优先队列、哈夫曼编码） - 2

    题目描述小张买了 n 件白色的衣服，他觉得所有衣服都是一种颜色太单调，希望对这些衣服进行染色，每次染色时，他会将某种颜色的所有衣服寄去染色厂，第 i 件衣服的邮费为 ai​ 元，染色厂会按照小张的要求将其中一部分衣服染成同一种任意的颜色，之后将衣服寄给小张，请问小张要将 n 件衣服染成不同颜色的最小代价是多少？输入描述第一行为一个整数 n ，表示衣服的数量。第二行包括 n 个整数a1​,a2​...an​ 表示第 i 件衣服的邮费为 ai​ 元。（1≤n≤10^5,1≤ai​≤10^9 ）输出描述输出一个整数表示小张所要花费的最小代价。输入输出样例输入551321输出25 思考🤔：题意：意思是

  5. ruby - 应该 validate_format_of 。 not_with 在框架中有问题(或者在我的理解中) - 2

    我将以下代码放入RSpec测试中:it{shouldvalidate_format_of(:email).not_with('test@test')}并设置实际的类:validates:email,:presence=>true,:format=>/\b[A-Z0-9._%-]+@(?:[A-Z0-9-]+\.)+[A-Z]{2,4}\b/i当我运行测试时，我得到:失败:1)用户失败/错误:它{应该validate_format_of(:email).not_with('test@test')}当电子邮件设置为“test@test”时，预期错误包括“can'tbeblank”，得到错误

  6. Ruby 等同于 C#'s ' yield' 关键字，或者，在不预分配内存的情况下创建序列 - 2

    在C#中，您可以这样做:publicIEnumerableGetItems(){for(inti=0;i这将返回一个包含1000万个整数的可枚举序列，而无需在该长度的内存中分配一个集合。有没有一种方法可以在Ruby中做同样的事情？我要处理的具体示例是将矩形数组展平为要枚举的值序列。返回值不必是Array或Set，而是某种只能按顺序而不是索引迭代/枚举的序列。因此，整个序列不需要同时分配到内存中。在.NET中，这是IEnumerable和IEnumerable.对Ruby世界中此处使用的术语的任何澄清都会有所帮助，因为我更熟悉.NET术语。编辑也许我最初的问题还不够清楚——我认为yiel

  7. ruby-on-rails - 你可以用ruby重新定义一个类吗？或者这只是在 irb - 2

    我启动了irb，然后输入:类点结束然后我再次输入，但添加了一些其他内容。Irb没有提示我正在定义一个已经存在的类。 最佳答案 其实你并没有重新定义Point类，你重新打开了它。一个小代码片段来说明差异:classPointdeffooendendclassPointdefbarendend现在Point有两个方法:foo和bar。所以Point的第二个定义并没有取代之前的定义，而是添加了它。这在ruby​​脚本和irb中都是可能的(标准库中的类也是可能的，而不仅仅是您自己的类)。也可以真正重新定义类，通过使用remove_const

  8. Ruby:如何将变量设置为 0，或者如果已经设置，则递增 1 - 2

    我知道||=运算符，但我认为它不会对我有帮助...尝试创建一个数组来计算对象数组中“类型”的数量。array.eachdo|c|newarray[c.type]=newarray[c.type]?newarray[c.type]+1?0end有没有更优雅的方式来做到这一点？ 最佳答案 types=Hash.new(-1)#Itfeelslikethisshouldbe0,buttobe#equivalenttoyourexampleitneedstobe-1array.eachdo|c|types[c.type]+=1end

  9. ruby-on-rails - ruby::Module 或者只是 Module - 2

    我正在慢慢浏览Rails源代码，以便更好地掌握ruby​​和Rails。在以下rails类中test_case.rb这条线是classTestCase我想知道执行以下操作是否有任何区别classTestCase这可能看起来微不足道，但这些事情对于学习一门新语言来说很重要。如果我删除前导::，测试仍然针对ActiveSupport运行，那么它做了什么......:P 最佳答案 ::Test确保您获得名为Test的顶层模块。后一种情况(Test::Unit::TestCase)不能确保Test是顶层模块，例如，它可能是一个类。这意味着它

  10. 前端基于DOM或者Canvas实现页面水印 - 2

    🐱个人主页：不叫猫先生🙋‍♂️作者简介：前端领域新星创作者、阿里云专家博主，专注于前端各领域技术，共同学习共同进步，一起加油呀！💫系列专栏：vue3从入门到精通、TypeScript从入门到实践📢资料领取：前端进阶资料以及文中源码可以找我免费领取🔥前端学习交流：博主建立了一个前端交流群，汇集了各路大神，一起交流学习，期待你的加入！(文末有我wx或者私信)目录前言一、vue自定义指令directive讲解二、基于DOM的实现方式1.思路整理2.新建index.vue3.新建`directives`文件4.在`directives`文件下创建`index.ts`文件5.在`main.ts`中全局引

随机推荐