對于如何算 n 的階乘，只要你知道階乘的定義，我想你都知道怎么算，但如果在面試中，面試官拋給你一道與階乘相關，看似簡單的算法題，你還真不一定能夠給出優雅的答案！本文將分享幾道與階乘相關的案例，且難度遞增。

案例一

給定一個整數 N，那么 N 的階乘 N! 末尾有多少個 0？例如： N = 10，則 N！= 3628800，那么 N! 的末尾有兩個0。

有些人心想，這還不簡單，直接算出 N！的值，然后用除以 10 來判斷多少個 0 就可以了。

有些人則這樣想，直接算 N！的值再來除以 10 判斷多少個 0 的話肯定會出現溢出問題，于是開始思索：一個數乘以 10 就一定會在末尾產生一個零，于是，我們可以從“哪些數相乘能夠得到 10 ”入手。

沒錯，只有 2 * 5 才會產生 10。

注意，4 * 5 = 20 也能產生 0 啊，不過我們也可以把 20 進行分解啊，20 = 10 * 2。

于是，問題轉化為 N! 種能夠分解成多少對 2*5，再一步分析會發現，在 N！中能夠被 2 整除的數一定比能夠被 5 整除的數多，于是問題就轉化為求 1…n 這 n 個數中能夠被 5 整除的數有多少個，注意，像 25 能夠被 5整除兩次，所以25是能夠產生 2 對 2 * 5滴。有了這個思路，代碼如下：

int f(int n){int sum = 0;for(int i = 1; i <= n; i++){int j = i;while(j % 5 == 0){sum++;j = j / 5;}}return sum; } 復制代碼

有些人想出了這個規律，很是得意，然而，這還不是面試官要的答案，大家想一個問題，

當 N = 20 時，1~20 可以產生幾個 5 ？答是 4 個，此時有 N / 5 = 4。

當 N = 24 時，1~24 可以產生幾個 5 ？答是 4 個，此時有 N / 5 = 4。

當 N = 25 時，1~25 可以產生幾個 5？答是 6 個，主要是因為 25 貢獻了兩個 5，此時有 N / 5 + N / 5^2 = 6。

…

可以發現 產生 5 的個數為 sum = N/5 + N/5^2 + N/5^3+….

于是，最優雅的寫法應該是這樣：

int f(int n){int sum = 0;while(n! = 0){sum += n / 5;n = n / 5;} } 復制代碼

這時，你就可以自信這把代碼扔給面試官了。

案例2

求 N! 的二進制表示中最低位 1 的位置。例如 3！=6，二進制為 1010，所以 最低位 1 的位置在第二位。

沒有思路？請仔細想一下這道題與上道題的關系！

仔細想一下，這道題不也是求末尾有多少個 0 嗎？你求出了末尾有多少個0自然知道 1 的位置（0的個數加1就是1的位置了），只不過，這道題是求二進制末尾有多少個 0。

由于是二進制，所以每次乘以 2 末尾就會產生一個 0 。

于是，模仿上面一道題，求 N！含有多少個 2 的個數。心想，幸好我做個類似了，于是一波操作猛如虎，一分鐘就寫出了代碼：

int f(int n){int sum = 0;while(n! = 0){sum += n / 2;n = n / 2;} } 復制代碼

面試官：還能在優化嗎？

什么鬼？還要在優化？我都 O(logn) 時間復雜度了。

還記得我之前講解了幾道有關位運算的嗎？這道題確實可以用位運算來優化，除以 n / 2 == n >> 1。不過位運算的速度快多了，于是，優化后的代碼如下：

int f(int n){int sum = 0;while(n! = 0){n >>= 1;sum += n;} } 復制代碼

還能在優化嗎？

可以，不過我先不講，因為我覺得，這已經夠快了。后面講其他題可能會把這道題再拿出來講。

如果你能寫出這樣的代碼，已經算很牛逼了。

案例三

給你一個數 N，輸出 N! 的值。

沒錯，就是這么簡單，直接讓你求階乘的值。

這個時候，你就要小心了，千萬別一波操作

long long sum = 1; for(int i = 1; i <= n; i++){sum *= i;} 復制代碼

一個 for 循環，馬上搞定。

因為你不知道 n 的范圍，有可能你用 long long 也是會溢出的，所以這個時候應該要問一下面試官有沒有限定 n 的范圍。

面試官：沒有限定！

這下好了，這道階乘的題，難度頓時上升了，說實話，我敢保證大部分人還真沒去實現過。所以，今天我就帶大家來實現一下，以防以后真的被問到。結果最熟悉的題頓時不知道怎么下手好。

這個時候，我們就必須用字符串來存放所求的值的，在相乘的時候也是用字符串來相乘，說白了，就是要會求兩個大整數相乘。

下面我們先來實現一個求兩個大整數相乘的函數。一種比較簡單的方法就是，像我們小學那會一樣，讓個位數與另一個數的其他數相乘，然后讓十位數與另一個的其他數相乘，最后在把他們進行相加。

實現代碼如下：

public static String mul(String s1, String s2) {// 先把字符串轉化為 字符數組。char[] c1 = s1.toCharArray();char[] c2 = s2.toCharArray();int len = c1.length + c2.length;// 用來存放兩個數的積,字符的初始值為 '\u0000'，也就是 0char[] c = new char[len];// 由于大整數的低位是在字符串的末尾，所以我們從末尾遍歷來計算for (int i = c1.length - 1; i >= 0; i--) {int index = len - 1;int res = 0;//用來存放進位for (int j = c2.length - 1; j >= 0; j--) {int temp = (c1[i]-'0') * (c2[j]-'0') + c[index] + res;res = temp / 10;c[index--] = (char)(temp % 10);}// 每趟乘下來的進位要進行保存。c[index] = (char)res;len--;}// 最后把c中的字符加上 '0'for (int i = 0; i < c.length; i++) {c[i] += '0';}String s = new String(c);// n位數乘以m位數得到積位 (m+n)位數或者(n+m-1)位數// 我們只需要判斷c[0]是否為0，為0則把它舍棄。if(c[0] == '0')return s.substring(1);elsereturn s;} 復制代碼

注意，一定要自己實現一遍，一定要自己實現一遍，因為原理簡單，但手動實現就不一定那么簡單了，容易出現bug。

采用這種方法的話，兩個大整數相乘的時間復雜度為 O(n)，其實還有更快的方法，大概時間復雜度是 O(n^1.6)，不過代碼有點小復雜。

知道了兩個大整數相乘之后，我們再來算我們的階乘，就好做了，我們每次相乘的時候，只需要把它當作兩個大整數重復乘就可以了。代碼如下：

// N 的階乘public static String f(int n) {String s = "1";Integer t = null;for (int i = 2; i <= n; i++) {t = i;s = 大整數相乘.mul(s,t.toString());}return s;}// 大整數相乘public static String mul(String s1, String s2) {// 先把字符串轉化為 字符數組。char[] c1 = s1.toCharArray();char[] c2 = s2.toCharArray();int len = c1.length + c2.length;// 用來存放兩個數的積,字符的初始值為 '\u0000'，也就是 0char[] c = new char[len];// 由于大整數的低位是在字符串的末尾，所以我們從末尾遍歷來計算for (int i = c1.length - 1; i >= 0; i--) {int index = len - 1;int res = 0;//用來存放進位for (int j = c2.length - 1; j >= 0; j--) {int temp = (c1[i]-'0') * (c2[j]-'0') + c[index] + res;res = temp / 10;c[index--] = (char)(temp % 10);}// 每趟乘下來的進位要進行保存。c[index] = (char)res;len--;}// 最后把c中的字符加上 '0'for (int i = 0; i < c.length; i++) {c[i] += '0';}String s = new String(c);// n位數乘以m位數得到積位 (m+n)位數或者(n+m-1)位數// 我們只需要判斷c[0]是否為0，為0則把它舍棄。if(c[0] == '0')return s.substring(1);elsereturn s;} 復制代碼

時間復雜度是 O(n^3)。如果要優化的話，主要是在大整數相乘這里進行優化。

總結

是不是覺得，階乘也沒有那么簡單了？這三道與階乘相關的題，應該是比較常見的題吧，今天跟大家分享一波，希望大家有時間的話，自己也用代碼實現一下，特別是算 N!。后面會繼續跟大家分享一些我覺得不錯的算法題以及一些算法技巧，敬請關注。

轉載于:https://juejin.im/post/5c909c25f265da611d742410

總結

以上是生活随笔為你收集整理的阶乘很简单？恕我直言，阶乘相关的面试题你还真不一定懂！的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。