其他
阿里面试:妙解三道唯一数题目
The following article is from 涛歌依旧 Author 点击关注👉👉
点击关注公众号,一周多次包邮送书
来源:经授权转自 涛歌依旧(ID:ai_taogeyijiu_2021)
作者:涛哥
题目一(简单)
分析1:用记录次数的方法,空间复杂度不过关,无法通过阿里的面试。
分析2:用排序的方法,时间复杂度不过关,自然无法通过阿里的面试。
分析3:采用异或的方法,直接得出结果,可以通过阿里的面试,程序:
#include <iostream>
using namespace std;
int main()
{
int a[] = {3, 4, 6, 5, 5, 6, 4};
int n = sizeof(a) / sizeof(a[0]);
int result = 0;
for(int i = 0; i < n; i++)
{
result ^= a[i];
}
cout << result << endl; // 3
return 0;
}
上述程序的结果是3,其背后的逻辑是:
result = 3 ^ 4 ^ 6 ^ 5 ^ 5 ^ 6 ^ 4
= 3 ^ (4 ^ 4) ^ (5 ^ 5) ^ (6 ^ 6)
= 3 ^ 0 ^ 0 ^ 0
= 3
题目之二(不难)
奇数派 | 偶数派 |
3,5,5 | 8,4,6,6,4 |
#include <iostream>
using namespace std;
int main()
{
int a[] = {3, 8, 4, 6, 5, 5, 6, 4};
int n = sizeof(a) / sizeof(a[0]);
int result1 = 0;
int result2 = 0;
for(int i = 0; i < n; i++)
{
if (a[i] % 2 != 0) // 奇数
{
result1 ^= a[i];
}
else // 偶数
{
result2 ^= a[i];
}
}
cout << result1 << endl; // 3
cout << result2 << endl; // 8
return 0;
}
经自测,程序结果正确。结果为3和8.
题目之三(困难)
3 | 7 | |
二进制 | 0011 | 0111 |
整数 | 二进制 | 类别 |
3 | 0011 | 蓝系 |
7 | 0111 | 红系 |
4 | 0100 | 红系 |
6 | 0110 | 红系 |
2 | 0010 | 蓝系 |
2 | 0010 | 蓝系 |
4 | 0100 | 红系 |
6 | 0110 | 红系 |
然后,分别对蓝系和红系进行异或,就求出了3和7,程序如下:
#include <iostream>
using namespace std;
int getOXR(int a[], int n)
{
int result = 0;
for(int i = 0; i < n; i++)
{
result ^= a[i];
}
return result;
}
int getMask(int r)
{
int mask = 1;
while((mask & r) == 0)
{
mask <<= 1;
}
return mask;
}
void getResult(int a[], int n, int &A, int &B)
{
int result = getOXR(a, n);
int mask = getMask(result);
for (int i = 0; i < n; i++)
{
if (mask & a[i])
{
A ^= a[i];
}
}
B = A ^ result;
}
int main()
{
int a[] = {3, 7, 4, 6, 2, 2, 4, 6};
int n = sizeof(a) / sizeof(a[0]);
int A = 0, B = 0;
getResult(a, n, A, B);
cout << A << endl; // 7
cout << B << endl; // 3
return 0;
}
经自测,程序结果正确。结果为7和3.
异或逻辑简介
我们来看如下电路图的动图,它实现的是一位二进制的异或逻辑,其实就是不带进位的二进制加法。
D1 | 操作 | D2 | D3 |
0 | 异或 | 0 | 0 |
0 | 异或 | 1 | 1 |
1 | 异或 | 0 | 1 |
1 | 异或 | 1 | 0 |
推荐阅读
• 漫画:程序员的社会地位• Edge浏览器真的越来越过分了 竟然篡改用户隐私设置收集数据• 腾讯终面:孤单的QQ号码怎么找?• 再见了VMware,一款更轻量级的虚拟机!• List 转 Map, 齐活!• 使用 JavaScript 进行数据分组最优雅的方式• 这篇 MySQL 索引和 B+Tree 讲的太通俗易懂!
👇更多内容请点击👇