有趣的BAT逻辑面试题分享

一、异或思维

1.1、在成对存在的数组中（即数组中的每个数必然存在另一个与其值相等的一个数），被程序员误插入了一个数（即该数在这个数组中唯一），如何找出这个数？

• 答案：将所有数化为二进制，做异或。

1.2、在成对存在的数组中（即数组中的每个数必然存在另一个与其值相等的一个数），被程序员误插入了两个数（即这两个数在这个数组中都是唯一），如何找出这两个数？

• 答案：异或所有数，所得结果相当于混入的这两个数的异或，取其不为0的某一位，按照这一位将数组元素分成两组（一组为0，一组为1），两组组内异或，分别得到这两个数。

1.3、判断一个数是否为奇数？
答案：目前为止，最为简洁的两种方式如下：

方式一：
public static boolean isOdd(int i) {
    return i >> 1 << 1 != i;
}
方式二：
public static boolean isOdd(int i) {
    return (i & 1) == 1;
}

参考博客：
jdk那些类的底层实现使用过位运算

二、数组相关

2.1、给定一个数组a[]，一次遍历在其中找出最大（最小）的元素。

• 答案：冒泡排序。

2.2、给定一个数组a[]，找出其中某两个数的和等于给定的一个数M。

• 答案：首先快排（从小到大），然后头尾两个指针，若头尾指向的数之和大于M，尾指针减减，否则头指针加加。

2.3、给定一个数组a[]，在其中找k个数（k>=2），使得其和等于给定的一个数M，没有返回false。

• ​​​​​​​答案：动态规划的思想。

三、过桥问题

3.1、 四人过桥问题：速度设为v1,v2,v3,v4，满足v1>v2>v3>v4，单独过河时间满足：t1< t2 < t3 < t4，此时正在下雨，四人只有一把伞，于是两人共有一把伞过河，过桥速度以最慢的为主，过河后需要其中一个送伞回去，问如何安排过河时间最短？

答案：

• 方案一：正常思维会认为v1速度最快，让他每次回头送伞最合适，于是v1分别与其他人过河再回头送伞，总时间：t2+t3+t4+2*t1。
• 方案二：考虑到v1>v2>>>v3>v4（即v1、v2远远大于v3、v4），可以让v1、v2先过河，v1回头送伞，v3、v4一起过河，v2回头送伞，然后v1、v2再过河， 总时间：t2+t1+t4+t2+t2。综合考虑，本题回答动态规划为最佳答案。

四、随机问题

4.1、存在函数A（）可以产生0~9 的随机数，且等概率的产生每个随机数，现在需要编写一个函数B（），使得产生数字1、2、3的概率为0.2,数字4的概率为0.4。
​​​​​​​答案：

   public int B( ){
         Switch（A（））{
              Case 0,6,7,8,9: B( );
              ​​​​​​​Case 1,2,3: Print(1 or 2 or 3);break;
              ​​​​​​​Case 4,5:Print(4);break;
         }
   }

五、称重问题

5.1、四盒外观一模一样的巧克力豆，分别叫A、B、C、D，其中有一盒巧克力豆比其他盒都的要重一克，如何通过一次称量，找出这盒巧克力豆。
​​​​​​​答案：

• 方法一：如果是显示重量的秤，则从第一盒取1个，第二盒取2个，第三盒取3个，第四盒取4个，重量比正常重几克就是第几盒。
• 方法二：不显示重量的秤，每边放两盒，则能知道那边重，再分别取走一盒，看余下的是否平衡。