当前位置:网站首页>笔试面试题目:求丢失的猪
笔试面试题目:求丢失的猪
2020-11-08 10:30:34 【osc_ccy4urvn】
原文发表于:
今天国庆,也是中秋,实在难得。在21世纪的100年内,仅有4年是这样的。今天在家里,陪家人,做饭吃,干家务活,看点闲书,顺便写点东西,待会出去逛逛,然后回来跑跑步。
校园秋招陆续开始了,祝在校同学拿到心仪的offer,也祝社招的同学跳槽顺利。
今天,我们来看下A公司的一个面试题:
有n只猪,用车拉到菜市场去卖,这群猪的身上分别贴了1~n的编号,突然,有一只猪从车上跳下溜走了,求溜走的猪的编号。
这猪还是挺可怜的,溜走了,也要追查编号。下面,我们来看看算法。
算法1:作差法
思路:
Step1: 计算出1~n的和a.
Step2: 求剩余猪的编号之和b.
Step3: a-b即为溜走猪的编号。
这种算法的缺点是:求1~n的和,可能会溢出。
算法2:标记法
思路:开辟一个数组m,用m[i]=0或1来记录i是否存在,针对丢失的猪j, 必有m[j]=0.
这种算法的缺点是:空间复杂度为O(n)
算法3:排序法
思路:对剩余的猪进行排序,在溜走的猪j的编号处,必然出现断裂,从而知道j的具体值。
这种算法的缺点是:以快排为例,时间复杂度和空间复杂度都无法达到最优。
算法4:异或法(最佳算法)
思路:
Step1: 计算出1~n的异或值a.
Step2: 求剩余猪的编号异或值b.
Step3: 求a和b的异或值,即为溜走的猪的编号j.
原理如下:
假设n=5, 丢失的猪的编号是3, 那么剩余的猪的编号是2, 4, 1, 5,下面我们来计算:
j = 1^2^3^4^5^2^4^1^5
显然,根据异或的交换律性质,可以对上述运算进行简化,如下:
j = 1^1^2^2^4^4^5^5^3 = 3
这就求出了溜走的猪的编号。此时,时间复杂度是O(n), 空间复杂度是O(1), 这是最佳算法。至于程序,很简单,故不再赘述。
在之前的文章中,我们其实可以看到,异或是一种特殊的“加减法”,所以,算法1和算法4是有异曲同工之妙的。关于二进制的异或,可以参考:
版权声明
本文为[osc_ccy4urvn]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4302796/blog/4707993
边栏推荐
- C++ 数字、string和char*的转换
- C++学习——centos7上部署C++开发环境
- C++学习——一步步学会写Makefile
- C++学习——临时对象的产生与优化
- C++学习——对象的引用的用法
- C++编程经验(6):使用C++风格的类型转换
- Won the CKA + CKS certificate with the highest gold content in kubernetes in 31 days!
- C + + number, string and char * conversion
- C + + Learning -- capacity() and resize() in C + +
- C + + Learning -- about code performance optimization
猜你喜欢
-
C + + programming experience (6): using C + + style type conversion
-
Latest party and government work report ppt - Park ppt
-
在线身份证号码提取生日工具
-
Online ID number extraction birthday tool
-
️野指针?悬空指针?️ 一文带你搞懂!
-
Field pointer? Dangling pointer? This article will help you understand!
-
HCNA Routing&Switching之GVRP
-
GVRP of hcna Routing & Switching
-
Seq2Seq实现闲聊机器人
-
【闲聊机器人】seq2seq模型的原理
随机推荐
- LeetCode 91. 解码方法
- Seq2seq implements chat robot
- [chat robot] principle of seq2seq model
- Leetcode 91. Decoding method
- HCNA Routing&Switching之GVRP
- GVRP of hcna Routing & Switching
- HDU7016 Random Walk 2
- [Code+#1]Yazid 的新生舞会
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- HDU7016 Random Walk 2
- [code + 1] Yazid's freshman ball
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- Qt Creator 自动补齐变慢的解决
- HALCON 20.11:如何处理标定助手品质问题
- HALCON 20.11:标定助手使用注意事项
- Solution of QT creator's automatic replenishment slowing down
- Halcon 20.11: how to deal with the quality problem of calibration assistant
- Halcon 20.11: precautions for use of calibration assistant
- “十大科学技术问题”揭晓!|青年科学家50²论坛
- "Top ten scientific and technological issues" announced| Young scientists 50 ² forum
- 求反转链表
- Reverse linked list
- js的数据类型
- JS data type
- 记一次文件读写遇到的bug
- Remember the bug encountered in reading and writing a file
- 单例模式
- Singleton mode
- 在这个 N 多编程语言争霸的世界,C++ 究竟还有没有未来?
- In this world of N programming languages, is there a future for C + +?
- es6模板字符
- js Promise
- js 数组方法 回顾
- ES6 template characters
- js Promise
- JS array method review
- 【Golang】️走进 Go 语言️ 第一课 Hello World
- [golang] go into go language lesson 1 Hello World