腾讯面试：猴子偷吃了哪根香蕉？
The following article is from 爱码有道 Author 点击关注👉👉
来源丨经授权转自 爱码有道（ID：aimayoudao）
作者丨爱码有道
大家好，我是道哥。今天，我们来聊一道腾讯面试的题目。
不要觉得腾讯的面试题一定很难，当然，也不要掉以轻心地觉得它很简单，一起来看看题目：
有n根香蕉，分别编号1~n, 无序地放在一起。夜晚，一只猴子偷吃了其中的1根香蕉。第二天早晨，管理员生气了，他该怎样找出被偷吃的香蕉的编号呢？请编程求解。
方法一: 数学计算
我们来看看偷吃前后的变化：显然，原来的和是：
2+4+1+3=10
后来的和是：
2+1+3=6
他们的差是：
10-6=4
所以，被偷吃的香蕉的编号就是4. 想到这里，你可能不禁感慨，腾讯的面试题会这么简单吗？显然，这种解法是有问题的，也是无法通过面试的。
为什么呢？如上总共只有4个香蕉，即n=4, 一旦n的值非常大，上述的加法计算，可能导致整数越界。所以，利用加法计算，并不是很好的方法。
方法二: 排序算法
我们对剩下来的香蕉进行排序：排序后，我们遍历1~n, 看看数字在哪个地方断开了，很显然，在4这里断开了，所以被吃的香蕉的编号就是4.
一般来说，应聘者应该有这样一种直觉，很多时候，如果需要通过排序来做，那么这个方法很可能不是最优的。
在该问题中，无论是用哪种排序算法，时间复杂度和空间复杂度都无法达到最优，显然，也是无法通过面试的。
方法三: 异或算法
我们再来看看偷吃前后的变化：我们考虑对虚线框中的数进行异或，很显然，x与x的异或值是0，又由于异或可交换可结合，所以，可以把上述所有的数字进行异或，最后的值就是4，且看：
x = 2^4^1^3^2^1^3
利用异或的交换律和结合律：
x = (2^2)^4^(1^1)^(3^3)
也即：
x = (0)^4^(0)^(0)=4
这种异或运算很巧妙，时间复杂度是O(n), 空间复杂度是O(1)，也是最佳的算法，能通过面试。接下来，我们来编程计算x的值，即
x = 1^2^3^4^2^1^3
编程实现
C++程序如下：
#include <iostream>using namespace std;
int main(){ int n = 4; int a[3] = {2, 1, 3}; // 被偷吃后的香蕉号 int x = 0; for (int i = 1; i <= n; i++) { x ^= i; // 原来的异或值 } for (int i = 0; i < n - 1; i++) { x ^= a[i]; } cout << x << endl; return 0;}结果：4
1、我的阿里二面，为什么MySQL选择Repeatable Read作为默认隔离级别？
点分享
点点赞
点在看