引言：随着在这个行业越来越久，慢慢发现，其实在面试过程中，面试官考察候选人的专业技能是一方面，另一方面还会考察你的思维敏捷度，也就是算法能力。技能知识能决定你的下限，但算法能体现你的上限。
可能提及算法，大多数人都会想到LeetCode，但其实在面试官首次考察候选人与所投递的岗位匹配度时，除了考察你的基础知识储备，还会考察你的逻辑思维敏捷度，但这一过程并不会要你立即写出代码，因为你的基础面还没过。
一般来说，这类题，属于拿分题。但就我的经历来说，如果没听过或者做过类似的，往往会陷入思维陷阱，不能跳出！更多时候遇到了这类题总会感觉怎么那么像脑筋急转弯呢？往往事后诸葛亮，愧疚不已！
今天，就来梳理一下，这类面试中的逻辑思维题。【实则不难！】
-
、分金条【阿里面试真题】
【题目：】工人为农场主工作了七天，要用一根金条作为报酬。你怎样分，尽量使切的刀数最少？
【答案：】金条按1/7, 2/7, 4/7分三份，第一天给1/7，第二天给2/7，换回工人手里的1/7，如此类推。
-
、烧香【百度面试真题】
【题目：】有两根不均匀的香，每根烧完需要1小时。用怎样的方法测出45分钟的时间？
【答案：】点燃A的两端，并且点燃B的一端，当A燃尽，此时B燃了30分钟，再点燃B的另一端，等B燃尽，就是45分钟。
-
、帽子【微软面试真题】
【题目：】红帽子黑帽子问题
一群人开舞会，每人都戴着一顶帽子。帽子只有红和黑两种，其中黑的至少有一顶。每个人能看到其它人的帽子颜色，但看不到自己的。
大家先一起做一个游戏，规则如下：
所有人先看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的黑帽子，就打自己一个耳光。
游戏开始：第一次关灯，没有声音。
于是打开灯再看一遍，第二次关灯，依然鸦雀无声。
一直到第三次关灯，才有声音响起。问：有多少人戴着黑帽子？
【答案：】有三个人戴着黑帽子。
首先梳理问题条件：帽子只有红和黑两种，其中黑的至少有一顶，人数未知。
过程梳理：第一次关灯，为什么没有人打耳光，是因为场上最少有1个人戴着黑帽子，在等待对方扇耳光，然而不会确定的情况下，不会去做，因此没有声音。第二次关灯也没有人打耳光，是因为场上至少有2个人戴着黑帽子，在等待对方扇耳光，在黑帽子视角，如果此时已经存在除了他之外的两个黑帽子，连续两次关灯都没有扇耳光，那么就能确定自己是最后那个黑帽子。
-
、倒水【大厂面试真题】
【题目：】给你一个容量为5升的杯子和一个容量为3升的杯子，水不限使用，要求精确得到4升水。
【答案：】穷举法实现比较方便，其基本思想是用：用小桶容量的倍数对大桶的容量进行取余。
3 % 5 = 3
6 % 5 = 1
9 % 5 = 4 。即：用3升的桶装满水，倒入5升水中，5升每次满了就倒掉，用小桶倒三次，5升大桶中就为4升水。
【总结：】思路：不断用小桶装水倒入大桶，大桶满了立即清空，每次判断下二个桶中水的容量是否等于指定容量。
-
、倒水升级题【京东面试题】
【题目：】给你一个容量为7升的杯子和一个容量为11升的杯子，水不限使用，要求精确得到4升水。
用上一题的穷举法思路：用小桶容量的倍数对大桶的容量去取余。
7 % 11 = 7
14 % 11 = 3
21 % 11 = 10
28 % 11 = 6
35 % 11 = 2。
-
欧几里算法：解决倒水问题
原理：A和B辗转相除取得最大公约数D后, D是可以由A和B倒水得出来的。如果D为C的约数，则一定可以达到要求。
Gcd(a,b) = aX +bY，gcd代表最小公约数
a = 3、b = 5
1 = 3x(-3)+5x2
a = 7 、b= 11
1 = 7x(3) + 11x(-2)
3空5【3】
3空5【1】
3空5【4】
7【4】11空
7【1】11空
7【5】11空
7【2】11空
综上，通过欧几里算法可以得出和穷举法相同的结果，说明这个算法可行，并且可以根据X、Y的值，确定从哪个桶倒到哪个桶，次数更少。【推荐使用】
-
兔子问题
【题目：】有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少?
【答案：】斐波那契数列问题经典解法。
第一个月：1对
第二个月：1对
第三个月：2对
第四个月：3对
……
斐波那契数列：f(n) = f(n-1)+f(n-2) 【n>1，f(0)=0；f(1)=1】
代码解决：滑动窗口解法（非递归）
public class Fibonacci {
public int fib(int n) {
int n1 = 0, n2 = 1, sum;
for(int i = 0; i < n; i++){
sum = (n1 + n2);
n1 = n2;
n2 = sum;
}
return n1;
}
}
