百度2017笔试题:寻找n个员工中未打卡的那一个
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了百度2017笔试题:寻找n个员工中未打卡的那一个,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2391字,纯文字阅读大概需要4分钟。
内容图文
![百度2017笔试题:寻找n个员工中未打卡的那一个](/upload/InfoBanner/zyjiaocheng/1066/41b1c18f388642b7b82d07176d2018ca.jpg)
声明:图片来自网络,笔者只是试着做了一下,然后做个记录。
拿到这个题目的时候,笔者首先想到的是二分。两个数组,一个是全体员工的集合A;一个是缺少一人的集合B。对A,B排序,再对B进行二分,得到B的中间员工的工号mid,若A[mid] == B[mid],那么缺席员工的工号在mid之后,继续二分;若A[mid] < B[mid],那么缺席员工的工号在mid之前,继续二分。值得注意的是,这里A[mid]是不会大于B[mid]的。另外,这里的二分仅针对缺席工号在数组中间的情况。若缺席工号在数组(当然是排序后)首尾,单独处理即可。
1 #include <bits/stdc++.h> 2usingnamespace std; 3 4 typedef longlong LL; 5#define MOD 1000000007ll 6#define PI acos(-1.0) 7constdouble EPS = 1e-6; 8//const double PI = acos(-1.0); 9constint INF = 0x3f3f3f3f; 10//const LL MOD = 1e9+7;1112 template <class T> inline T bigMod(T p, T e, T M){ 13longlong ret = 1; 14for(; e > 0; e >>= 1){ 15if(e & 1) ret = (ret * p) % M; 16 p = (p * p) % M; 17 } return (T)ret % M; // Attention: bigMod(p, 0, 1), so ret has to module M.18} 19 template <class T> inline T modInverse(T a, T M){return bigMod(a, M-2, M);} 20 template <class T> inline T gcd(T a, T b){return b ? gcd(b, a%b) : a;} 21int main() { 22int T; 23 scanf("%d", &T); 24for (int i = 1; i <= T; ++i) { 25 vector<int> total; 26 vector<int> arrive; 27int num; cin >> num; 28for (int j = 0; j < num; ++j) { 29int employee; cin >> employee; 30 total.push_back(employee); 31 } 32for (int j = 0; j < num - 1; ++j) { 33int arriver; cin >> arriver; 34 arrive.push_back(arriver); 35 } 36/*** binary search 37 sort(total.begin(), total.end()); 38 sort(arrive.begin(), arrive.end()); 39 if (total[0] != arrive[0]) cout << total[0] << endl; 40 else if (total[num-1] != arrive[num-2]) cout << total[num-1] << endl; 41 else { 42 int left = 0, right = num - 2; 43 while(left <= right) { 44 int mid = left + (right - left)/2; 45 if (total[mid] == arrive[mid]) { 46 left = mid + 1; 47 }else if (total[mid] < arrive[mid]){ 48 right = mid - 1; 49 } 50 } 51 cout << total[left] << endl; 52 }*/53int num1 = 0; 54for (auto iter = total.begin(); iter != total.end(); ++iter) { 55 num1 = num1 ^ *iter; 56 } 57int num2 = 0; 58for (auto iter = arrive.begin(); iter != arrive.end(); ++iter) { 59 num2 = num2 ^ *iter; 60 } 61 cout << (num1 ^ num2) << endl; 62 } 63return0; 64 }
后来有个朋友提出了一个更好的方法,简直漂亮。利用异或的思想。
我们先来看这样一个表达式: p ^ q = m, m等于p,q的异或。那么有,p = q ^ m, q = p ^ m。
现在,回过头来看这个题目。我们把A中的元素互相异或得到m;把B中的元素互相异或得到p。那么,没来的哪个员工工号是q=m^p。
代码的实现也综合在上诉代码中。
原文:http://www.cnblogs.com/letgo/p/5870016.html
内容总结
以上是互联网集市为您收集整理的百度2017笔试题:寻找n个员工中未打卡的那一个全部内容,希望文章能够帮你解决百度2017笔试题:寻找n个员工中未打卡的那一个所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。