Colin’s Blog

A C++ Programmer

三道面试题

三道面试题

  1. 不使用额外空间交换两个数 解1:加法减法 解2:异或
 1void f(int &a, int &b)
 2{
 3    a = a + b;
 4    b = a - b;
 5    a = a - b;
 6}
 7
 8void ff(int &a, int &b)
 9{
10    a = a ^ b;
11    b = a ^ b;
12    a = a ^ b;
13}
  1. 1-1000的一个排列 丢失了三个数字 怎样$O(n)$时间,$O(1)$额外空间找到

  2. 25个马 🐎! 每次可以让5个马赛跑 问最少几次能找出最快的三匹马

答案:7次可以。暂时不知道咋证明7次是最少的。 https://math.stackexchange.com/questions/1361065/why-6-races-are-not-sufficient-in-the-25-horses-5-tracks-problem 一个证明