[智力题]面试总结
目錄
1.給一個瞎子52張撲克牌，并告訴他里面恰好有10張牌是正面朝上的。要求這個瞎子把牌分成兩堆，使得每堆牌里正面朝上的牌的張數一樣多。瞎子應該怎么做？
2.如何用一枚硬幣等概率地產生一個1到3之間的隨機整數？如果這枚硬幣是不公正的呢？
3.30枚面值不全相同的硬幣擺成一排，甲、乙兩個人輪流選擇這排硬幣的其中一端，并取走最外邊的那枚硬幣。如果你先取硬幣，能保證得到的錢不會比對手少嗎？
4.一個環形軌道上有n個加油站，所有加油站的油量總和正好夠車跑一圈。證明，總能找到其中一個加油站，使得初始時油箱為空的汽車從這里出發，能夠順利環行一圈回到起點。
5.初始時，兩個口袋里各有一個球。把后面的n-2個球依次放入口袋，放進哪個口袋其概率與各口袋已有的球數成正比。這樣下來，球數較少的那個口袋平均期望有多少個球？
6.考慮一個n*n的棋盤，把有公共邊的兩個格子叫做相鄰的格子。初始時，有些格子里有病毒。每一秒鐘后，只要一個格子至少有兩個相鄰格子染上了病毒，那么他自己也會被感染。為了讓所有的格子都被感染，初始時最少需要有幾個帶病毒的格子？給出一種方案并證明最優性。
7.在一個m*n的棋盤上，有k個格子里放有棋子。是否總能對所有棋子進行紅藍二染色，使得每行每列的紅色棋子和藍色棋子最多差一個？
8.任意給一個88的01矩陣，你每次只能選一個33或者4*4的子矩陣并把里面的元素全部取反。是否總有辦法把矩陣里的所有數全部變為1？
9.五個洞排成一排，其中一個洞里藏有一只狐貍。每個夜晚，狐貍都會跳到一個相鄰的洞里；每個白天，你都只允許檢查其中一個洞。怎樣才能保證狐貍最終會被抓住？
10.一個經典老題是說，把一個333的立方體切成27個單位立方體，若每一刀切完后都允許重新擺放各個小塊的位置，最少可以用幾刀？答案仍然是6刀，因為 正中間那個單位立方體的6個面都是后來才切出來的，因此怎么也需要6刀。考慮這個問題：若把一個nnn的立方體切成一個個單位立方體，最少需要幾刀？
1.給一個瞎子52張撲克牌，并告訴他里面恰好有10張牌是正面朝上的。要求這個瞎子把牌分成兩堆，使得每堆牌里正面朝上的牌的張數一樣多。瞎子應該怎么做？
題目：給一個瞎子52張撲克牌，并告訴他里面恰好有10張牌是正面朝上的。要求這個瞎子把牌分成兩堆，使得每堆牌里正面朝上的牌的張數一樣多。瞎子應該怎么做？（瞎子摸不出牌是正面或者是反面，但是卻可以隨意翻動每一張牌）
解析：這里面要注意點是括號里面給出的信息，瞎子看不見但是可以翻動牌面，所以解題是大概率用到翻牌的，留心一下，然后就是兩個數值52和10，這個也需要留心一下，最后要注意一個小的點，使得堆牌里正面朝上的牌的張數一樣多，并不意味著左右兩堆正面朝上的牌都是5張。現在你可以嘗試著自己解一下方案。
最終解答：將52張牌分為2堆，一堆10張，另一堆42張，將10張的那一堆全部翻面一次就可以了。
分析：
? ? ? ?10張堆 ? ? ? ? ? ? ? ? 翻起來后 ? ? ? ? ? ? ? ? ? ? ? 42張堆
向上 ? ? ? 向下 ? ? ? ? 向上 ? ? ? ? 向下 ? ? ? ? ? ? ?向上 ? ? ? ?向下
1 ? ? ? ? ? ? 9 ? ? ? ? ? ? ? 9 ? ? ? ? ? ? ? 1 ? ? ? ? ? ? ? ? ? 9 ? ? ? ? ? 33
2 ? ? ? ? ? ? 8 ? ? ? ? ? ? ? 8 ? ? ? ? ? ? ? 2 ? ? ? ? ? ? ? ? ? 8 ? ? ? ? ? 34
3 ? ? ? ? ? ? 7 ? ? ? ? ? ? ? 7 ? ? ? ? ? ? ? 3 ? ? ? ? ? ? ? ? ? 7 ? ? ? ? ? 35
........
10 ? ? ? ? ?0 ? ? ? ? ? ? ? 0 ? ? ? ? ? ? ? 10 ? ? ? ? ? ? ? ? 0 ? ? ? ? ? ?42 ? ??
從這張表我們就可以清楚的get到這道題的關鍵核心，那就是只有10張牌是正面向上的，所以分成兩堆的話，必然正面向上的牌數量和為10，但是此時兩邊正面向上的牌數并不一定相等（一個是n，一個是10-n）（n自然是1~10的整數），所以我們還需要一個前置條件，就是把其中一個堆的牌數安排為10張，那么這個10張牌堆將所有的牌全部反面（正面向上牌數從n也變成10-n），就必然和另一個42張牌堆的正面向上的牌數量相等。
2.如何用一枚硬幣等概率地產生一個1到3之間的隨機整數？如果這枚硬幣是不公正的呢？
答案：如果是公正的硬幣，則投擲兩次，“正反”為1，“反正”為2，“正正”為3，“反反”重來。
如果是不公正的硬幣，注意到出現“正反”和“反正”的概率一樣，因此令“正反反正”、“反正正反”、“正反正反”分別為1、2、3，其余情況重來。另一種更妙的辦法是，投擲三次硬幣，“正反反”為1，“反正反”為2，“反反正”為3，其余情況重來。
3.30枚面值不全相同的硬幣擺成一排，甲、乙兩個人輪流選擇這排硬幣的其中一端，并取走最外邊的那枚硬幣。如果你先取硬幣，能保證得到的錢不會比對手少嗎？
答案：先取者可以讓自己總是取奇數位置上的硬幣或者總是取偶數位置上的硬幣。數一數是奇數位置上的面值總和多還是偶數位置上的面值總和多，然后總是取這些位置上的硬幣就可以了。
4.一個環形軌道上有n個加油站，所有加油站的油量總和正好夠車跑一圈。證明，總能找到其中一個加油站，使得初始時油箱為空的汽車從這里出發，能夠順利環行一圈回到起點。
答案：總存在一個加油站，僅用它的油就足夠跑到下一個加油站（否則所有加油站的油量加起來將不夠全程）。把下一個加油站的所有油都提前搬到這個加 油站來，并把油已被搬走的加油站無視掉。在剩下的加油站中繼續尋找油量足以到達下個加油站的地方，不斷合并加油站，直到只剩一個加油站為止。顯然從這里出 發就能順利跑完全程。
另一種證明方法：先讓汽車油箱里裝好足夠多的油，隨便從哪個加油站出發試跑一圈。車每到一個加油站時，記錄此時油箱里剩下的油量，然后把那個加油站的油全部裝上。試跑完一圈后，檢查剛才路上到哪個加油站時剩的油量最少，那么空著油箱從那里出發顯然一定能跑完全程。
5.初始時，兩個口袋里各有一個球。把后面的n-2個球依次放入口袋，放進哪個口袋其概率與各口袋已有的球數成正比。這樣下來，球數較少的那個口袋平均期望有多少個球？
答案：先考慮一個看似無關的問題——怎樣產生一個1到n的隨機排列。首先，在紙上寫下數字1；然后，把2寫在1的左邊或者右邊；然后，把3寫在最 左邊，最右邊，或者插進1和2之間……總之，把數字i等概率地放進由前面i-1個數產生的（包括最左端和最右端在內的）共i個空位中的一個。這樣生成的顯 然是一個完全隨機的排列。
我們換一個角度來看題目描述的過程：假想用一根繩子把兩個球拴在一起，把這根繩子標號為1。接下來，把其中一個小球分裂成兩個小球，這兩個小球用 標號為2的繩子相連。總之，把“放進第i個球”的操作想象成把其中一個球分裂成兩個用標有i-1的繩子相連的小球。聯想我們前面的討論，這些繩子的標號事 實上是一個隨機的全排列，也就是說最開始繩子1的位置最后等可能地出現在每個地方。也就是說，它兩邊的小球個數(1,n-1)、(2,n-2)、 (3,n-3)、……、(n-1,1)這n-1種情況等可能地發生。因此，小袋子里的球數大約為n/4個。準確地說，當n為奇數時，小袋子里的球數為 (n+1)/4；當n為偶數時，小袋子里的球數為n^2/(4n-4)。
6.考慮一個n*n的棋盤，把有公共邊的兩個格子叫做相鄰的格子。初始時，有些格子里有病毒。每一秒鐘后，只要一個格子至少有兩個相鄰格子染上了病毒，那么他自己也會被感染。為了讓所有的格子都被感染，初始時最少需要有幾個帶病毒的格子？給出一種方案并證明最優性。
答案：至少要n個，比如一條對角線上的n個格子。n個格子也是必需的。當一個新的格子被感染后，全體被感染的格子所組成的圖形的周長將減少0個、 2個或4個單位（具體減少了多少要看它周圍被感染的格子有多少個）。又因為當所有格子都被感染后，圖形的周長為4n，因此初始時至少要有n個被感染的格 子。
7.在一個m*n的棋盤上，有k個格子里放有棋子。是否總能對所有棋子進行紅藍二染色，使得每行每列的紅色棋子和藍色棋子最多差一個？
答案：可以。建一個二分圖G(X,Y)，其中X有m個頂點代表了棋盤的m個行，Y有n個頂點代表了棋盤的n個列。第i行第j列有棋子就在X(i) 和Y(j)之間連一條邊。先找出圖G里的所有環（由于是二分圖，環的長度一定是偶數），把環里的邊紅藍交替染色。剩下的沒染色的圖一定是一些樹。對每棵樹 遞歸地進行操作：去掉一個葉子節點和對應邊，把剩下的樹進行合法的紅藍二染色，再把剛才去掉的頂點和邊加回去，給這個邊適當的顏色以滿足要求。
8.任意給一個88的01矩陣，你每次只能選一個33或者4*4的子矩陣并把里面的元素全部取反。是否總有辦法把矩陣里的所有數全部變為1？
答案：不能。大矩陣中有36個33的小矩陣和25個44的小矩陣，因此總共有61種可能的操作。顯然，給定一個操作序列，這些操作的先后順序 是無關緊要的；另外，在一個操作序列中使用兩種或兩種以上相同的操作也是無用的。因此，實質不同的操作序列只有2^61種。但8*8的01矩陣一共有 2^64種，因此不是每種情況都有辦法達到目的。
9.五個洞排成一排，其中一個洞里藏有一只狐貍。每個夜晚，狐貍都會跳到一個相鄰的洞里；每個白天，你都只允許檢查其中一個洞。怎樣才能保證狐貍最終會被抓住？
答案：按照2, 3, 4, 2, 3, 4的順序檢查狐貍洞可以保證抓住狐貍。為了說明這個方案是可行的，用集合F表示狐貍可能出現的位置，初始時F = {1, 2, 3, 4, 5}。如果它不在2號洞，則第二天狐貍已經跑到了F = {2, 3, 4, 5}。如果此時它不在3號洞，則第三天狐貍一定跑到了F = {1, 3, 4, 5}。如果此時它不在4號洞，則再過一晚后F = {2, 4}。如果此時它不在2號洞，則再過一天F = {3, 5}。如果此時它不在3號洞，再過一天它就一定跑到4號洞了。
方案不是唯一的，下面這些方案都是可行的：
2, 3, 4, 4, 3, 2
4, 3, 2, 2, 3, 4
4, 3, 2, 4, 3, 2
10.一個經典老題是說，把一個333的立方體切成27個單位立方體，若每一刀切完后都允許重新擺放各個小塊的位置，最少可以用幾刀？答案仍然是6刀，因為 正中間那個單位立方體的6個面都是后來才切出來的，因此怎么也需要6刀。考慮這個問題：若把一個nnn的立方體切成一個個單位立方體，最少需要幾刀？
答案：事實上，從一個更強的命題出發反而能使問題變得更簡單。對于一個abc的長方體，我們需要f(a)+f(b)+f(c)刀，其中 f(x)=?log(x)/log(2)?。只需要注意到，在整個過程中的任何一步，切完當前最大的塊所需要的刀數也就等于整個過程還需要的刀數，因為其 它小塊需要的刀數都不會超過最大塊所需刀數，它們都可以與最大塊一道并行處理。這表明，我們的最優決策即是讓當前的最大塊盡可能的小，也就是說要把當前的 最大塊盡可能相等地切成兩半。利用數學歸納法，我們可以很快得到本段開頭的結論。
總結
- 上一篇： Python函数中的变量作用域
- 下一篇： [leetcode]110.平衡二叉树