一昵观、前言
前幾個(gè)星期的面試題都有點(diǎn)稀奇古怪碳抄，這個(gè)星期來(lái)一個(gè)正常點(diǎn)的題目愉老，可是這題目可能對(duì)于個(gè)別人來(lái)說(shuō)是如此的熟悉但又很陌生。因?yàn)槟鞘俏覀兏咧袝r(shí)常做的題目剖效，現(xiàn)在卻還給老師了嫉入。那讓我們好好回憶一下。
二璧尸、題目
6× 9的的方格中咒林，起點(diǎn)的左下角，終點(diǎn)在右上角爷光，從起點(diǎn)到終點(diǎn)垫竞，只能從下向上，從左向右走蛀序，問(wèn)一共有多少種不同的走法欢瞪。
A. 4200
B. 5005
C. 1005
D. 以上都不正確
三、解題
當(dāng)然這道題有點(diǎn)異議哼拔，為什么這樣說(shuō)呢引有？因?yàn)轭}目沒(méi)有明確說(shuō)明是按方格來(lái)走還是按照線來(lái)走。
首先我們嘗試下按方格來(lái)走倦逐，得到的結(jié)果是什么譬正？要想知道結(jié)果，我們需要知道題目想考察我們什么檬姥，很顯然曾我，題目其實(shí)考察我們高中非常熟悉的排列組合的問(wèn)題，完完全全就是高中的題目健民，可是現(xiàn)在可能對(duì)于我們來(lái)說(shuō)又是如此的陌生抒巢。這道題如果按方格來(lái)走的話，結(jié)果就是 C(5, 13) = 1287 秉犹。13 是哪里來(lái)的蛉谜，5 又是哪里來(lái)的稚晚，思考之前，我們可以先看一張圖型诚。
根據(jù)圖片可以看出客燕，13 就從左下角到右上角一個(gè)要走的格子數(shù)，5 就是走的行數(shù)狰贯，為什么是從 13 個(gè)中選 5 個(gè)來(lái)組合就知道一共有多少種走法呢也搓？其實(shí)因?yàn)槲覀冎灰懒诵袛?shù)的 5 個(gè)的位置我們就知道列數(shù) 8 個(gè)格子的位置，當(dāng)然你也可以 13 選 8 涵紊，結(jié)果都是一樣的傍妒。為啥一樣，貼一張圖來(lái)回憶起我們遺忘的記憶吧摸柄。
因此颤练，按走的是格子來(lái)算，結(jié)果是 C(5, 13) = C(8, 13) = 1287
其實(shí)這道題目想表達(dá)的意思是按線來(lái)算的塘幅，可是原理還是跟上面一樣的
因此昔案，按走的是線來(lái)算，結(jié)果是 C(6, 15) = C(9, 15) = 5005
四电媳、類(lèi)似的題目
其實(shí)這種題目很多大企業(yè)大公司都會(huì)作為面試題，比如我們來(lái)看看下面兩道類(lèi)似的題目：
1.阿里巴巴的筆試題目
說(shuō) 16 個(gè)人按順序去買(mǎi)燒餅庆亡，其中 8 個(gè)人每人身上只有一張 5 塊錢(qián)匾乓，另外 8 個(gè)人每人身上只有一張 10 塊錢(qián)。燒餅 5 塊一個(gè)又谋，開(kāi)始時(shí)燒餅店老板身上沒(méi)有錢(qián)拼缝。16 個(gè)顧客互相不通氣，每人只買(mǎi)一個(gè)彰亥。問(wèn)這 16 個(gè)人共有多少種排列方法能避免找不開(kāi)錢(qián)的情況出現(xiàn)咧七。
假設(shè)付 5 塊錢(qián)的人都是 1，付 10 塊錢(qián)的人都是 0 任斋，則排隊(duì)順序可能為1111111100000000 或各種 1 與 0 的排列組合继阻，那么總共的排列順序就是C（16，8）废酷，這里跟上面的都是一樣的瘟檩，但是為了避免找不開(kāi)錢(qián)，則從左到右時(shí)澈蟆，不能有 0 的數(shù)目小于 1 的數(shù)目的情況出現(xiàn)墨辛。如果出現(xiàn)這種情況，則必然存在第2m+1 個(gè)數(shù)目時(shí)（即某個(gè)奇數(shù)數(shù)目）趴俘，前 2m+1 個(gè)數(shù)目中有 m+1個(gè)0睹簇，m 個(gè) 1 奏赘。那么在剩余的 16-2m-1 個(gè)數(shù)目中，即 15-2m 個(gè)數(shù)目中太惠，必然存在著 8-m-1 個(gè) 0 志珍，8-m 個(gè) 1 ，即 7-m 個(gè) 0 垛叨，8-m 個(gè) 1 ÷着矗現(xiàn)在再把剩余的 16-2m-1 個(gè)數(shù)目中的 0 與 1 互換，則為 8-m 個(gè)0嗽元，7-m 個(gè) 1 敛纲，這個(gè)時(shí)候，整個(gè)數(shù)列就變?yōu)榱?9 個(gè) 0剂癌，7 個(gè) 1 淤翔。所以一個(gè)不符合要求的數(shù)目為 9 個(gè) 0 和 7 個(gè) 1 組成。因此佩谷，結(jié)果為 C（16旁壮，8）-C（16，9）= 12870 - 11440 = 1430
2.2012騰訊實(shí)習(xí)招聘筆試題
在圖書(shū)館一共6個(gè)人在排隊(duì)谐檀，3個(gè)還《面試寶典》一書(shū)抡谐，3個(gè)在借《面試寶典》一書(shū)，圖書(shū)館此時(shí)沒(méi)有了面試寶典了桐猬，求他們排隊(duì)的總數(shù)麦撵？
其實(shí)這些問(wèn)題可以轉(zhuǎn)化為下面的格路問(wèn)題，從左下角到右上角溃肪，不能是對(duì)角線免胃，有多少種方案。不過(guò)加了限制條件而已惫撰，這道題跟阿里巴巴那道面試題一樣羔沙，結(jié)果為：結(jié)果為 C（6，3）-C（6厨钻，4）= 20 - 15 = 5
五扼雏、編程
GitHub:https://github.com/TwoWater/Interview/tree/master/Interview
package com.liangdianshui;
/**
* <p>
* 6× 9的的方格中，起點(diǎn)的左下角莉撇，終點(diǎn)在右上角呢蛤，從起點(diǎn)到終點(diǎn)，只能從下向上棍郎，從左向右走其障，問(wèn)一共有多少種不同的走法。
* A. 4200
* B. 5005
* C. 1005
* D. 以上都不正確
* </p>
*
* @author liangdianshui
*
*/
public class Catalan {
public static void main(String[] args) {
System.out.println(func(6, 9));
}
public static int func(int m, int n) {
if (m < 1 || n < 1) {
return 1;
}
return func(m - 1, n) + func(m, n - 1);
}
}
