当前位置:网站首页>Written interview topic: looking for the lost pig
Written interview topic: looking for the lost pig
2020-11-08 10:30:34 【Oc ccy4urvn】
Original published in :
Today's National Day , The Mid Autumn Festival, too , It's really rare . stay 21 Century's 100 During the year , have only 4 Year is like this . At home today , With family , Cook and eat , Do housework , Read some idle books , By the way, write something , I'll go out later , And then come back and run .
The campus autumn recruitment has begun in succession , I wish the students in school get their favorite offer, I also wish the students who are recruited by the society to change jobs smoothly .
today , Let's see A An interview question for the company :
Yes n Pigs , Take the car to the vegetable market , The pigs were pasted with 1~n The number of , All of a sudden , A pig jumped out of the car and ran away , Ask for the number of the pig that escaped .
The pig is still very poor , Slip away , We also need to track down the numbers . below , Let's look at algorithms .
Algorithm 1: Making difference method
Ideas :
Step1: To calculate the 1~n And a.
Step2: Find the sum of the numbers of the remaining pigs b.
Step3: a-b That's the number of the pig .
The disadvantage of this algorithm is : seek 1~n And , It might spill over .
Algorithm 2: Tagging
Ideas : Open up an array m, use m[i]=0 or 1 To record i Whether there is , For lost pigs j, There must be m[j]=0.
The disadvantage of this algorithm is : The space complexity is O(n)
Algorithm 3: Sequencing
Ideas : Sort the rest of the pigs , The pig that is running away j At the number of , There must be a break , So they know j The specific value of .
The disadvantage of this algorithm is : Let's take the example of fast track , Neither time complexity nor space complexity is optimal .
Algorithm 4: Exclusive or law ( The best algorithm )
Ideas :
Step1: To calculate the 1~n Exclusive or values a.
Step2: Find the exclusive or value of the number of the remaining pigs b.
Step3: seek a and b Exclusive or values , It's the number of the pig that escaped j.
The principle is as follows :
hypothesis n=5, The number of the lost pig is 3, So the number of the remaining pigs is 2, 4, 1, 5, Let's calculate :
j = 1^2^3^4^5^2^4^1^5
obviously , According to the exchange law of XOR , The above operations can be simplified , as follows :
j = 1^1^2^2^4^4^5^5^3 = 3
This gives you the number of the pig that's gone . here , The time complexity is O(n), The space complexity is O(1), This is the best algorithm . As for the procedure , It's simple , So I won't go back to .
In the previous post , We can actually see , XOR is a special kind of “ Addition and subtraction ”, therefore , Algorithm 1 Sum algorithm 4 It's a wonderful thing to do the same . About binary XORs , You can refer to :
The circuit principle of computer addition and proteus Simulation
版权声明
本文为[Oc ccy4urvn]所创,转载请带上原文链接,感谢
边栏推荐
- 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