三道面试题

不使用额外空间交换两个数解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-1000的一个排列丢失了三个数字怎样$O(n)$时间，$O(1)$额外空间找到
25个马 🐎！每次可以让5个马赛跑问最少几次能找出最快的三匹马

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

三道面试题

不使用额外空间交换两个数解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-1000的一个排列丢失了三个数字怎样$O(n)$时间，$O(1)$额外空间找到
25个马 🐎！每次可以让5个马赛跑问最少几次能找出最快的三匹马

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

三道面试题

不使用额外空间交换两个数解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-1000的一个排列丢失了三个数字怎样$O(n)$时间，$O(1)$额外空间找到
25个马 🐎！每次可以让5个马赛跑问最少几次能找出最快的三匹马

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