確保代碼完整性

• 在擼業務代碼時候，經常面對的是接口的設計，在設計之初，我們必然要先想好入參，之后自然會有參數的校驗過程，此時我們需要把可能的輸入都想清楚，從而避免在程序中出現各種紕漏。但是難免面面俱到，有什么辦法能覆蓋整個入參的校驗呢，我們可以考慮黑盒測試，用測試用例去覆蓋，我們編碼之前考慮測試用例，如果能先設計黑盒測試的測試用例，那么自然我們需要注意的校驗點就出來了。我們一般都從功能測試，邊界測試，負面測試三方面設計測試用例，確保代碼的完整性。

錯誤的處理

• 我們在編碼過程中，會遇到各種各樣的異常情況，我們有3中方式將錯誤信息床底給函數的調用者。
  • 第一種，函數的返回值來告知調用者是否出錯，比如我們在API設計的時候，給定返回對象中有一個狀態，用狀態引擎的方式給定調用者具體的調用成功與否，并且在返回值中給定錯誤對象信息，這種方案最大的問題是使用不方便，因為我們不能直接吧計算結果給調用方，同時也不能將函數的計算結果直接作為參數傳遞給其他函數。
  • 第二種，定義一個全局變量，在發生錯誤時候，我們設置全局變量值為某個特殊值，這種方法比第一種要方便，因為調用者可以直接使用返回值，我們可以設計一個特定的函數用來判斷返回值的分析，判斷是否錯誤。這種方案也有問題，在于全局變量可能被人遺忘，因為N多個調用方，我只關注你給的調用結果，你的實現多調用方應該透明。
  • 第三種，異常，這是微服務調用中常用的方式，當函數運行異常時候，我們拋出一個自定義異常。函數調用者更具異常信息就能知道錯誤原因，從而做相應處理。這種問題在于拋出異常會打亂正常的執行順序，對程序的性能會有影響。

數值的整數次方

• 案例：實現函數 double power（double base， int exponent）， 求base的exponent次方，不能使用函數庫，同時不需要考慮大數問題。

• 在java.lang包中有pow函數可以用來求乘方，以上問題求解類似于pow函數的功能，初見題目其實非常簡單，可以用一個循環得出如下代碼：

public static double power(double base, int exponent){if(base == 0 || base == 1){return base;}if(exponent == 0){return 1d;}if(exponent == 1){return base;}double result = 1.0;for (int i = 0; i < exponent; i++) {result *= base;}return result;}

• 指數次冪的大小，直接左冪次的乘法，如上只考慮了正整數次冪顯然不是正確的解法，我們可以有如下優化

/*** 求解一個數base 的exponent次冪* */public static double power(double base, int exponent){if(base == 0 || base == 1){return base;}if(exponent == 0){return 1d;}if(exponent == 1){return base;}double result = 1.0;for (int i = 0; i < Math.abs(exponent); i++) {result *= base;}if(exponent > 0){return result;}return 1/result;}

• 如上實現方案中，已經考慮到了邊界值，正負次冪情況，基本上是一個健全的實現方案，但是還有優化的空間，例如，我們在double的比較中，直接判斷的是base == 0，此處是有問題的，因為在計算機內標識小數的時候，（double和float類型小數）直接用 這種方式判斷是誤差的，我在之前價格計算遇到的問題相關文章中也有過詳細的解釋。
• 修改后，判斷兩個小數是否相等，只能判斷他們只差的絕對值是不是在一個很小的范圍內，如果相差很小，可以認為相等，我們將 等于判斷用如下equal方法電梯

/*** 浮點數判斷是否相等* */public static boolean equals(double num, double num1){if((num - num1 > -0.00000001) && (num - num1) < 0.00000001 ){return true;}return false;}

• 最高效率的解法，在上面的解法中，每次求值都需要循環exponent次，在求解數值的冪次時候，我們想到的了之前 遞歸與循環中講到的斐波那契數列的非大眾解法，也是時間復雜度最低的解法，我們先有如下公式：

• 情況一
  $$a^n=a^{n/2}?a^{n/2},n為偶數$$

• 情況二
  $$a^n=a^{(n?1)/2}?a^{(n?1)/2}?a,n為奇數$$

• 我們求解a的n次冪，可以按照如上公式來解決，時間復雜度是O(nlogn)，因此自然的想到了遞歸實現方式。如下實現：

/*** 實現Math.pow(a,b)* */public static double powerWithUnsignedExponent(double base, int exponent){if(base == 0 || base == 1){return base;}if(exponent == 0){return 1d;}if(exponent == 1){return base;}double result = powerWithUnsignedExponent(base, exponent >> 1);result*=result;if((exponent & 1) == 1){result*=base;}return result;}

• 以上，我們用二分法的思想做遞歸，并在判斷奇數偶數的地方用與操作進行判斷，奇數的二進制位 低位必然是1，偶數正好相反是 0 ，因此我們讓原數與 1 進行與操作，可以區分出奇偶性。位運算相關的知識在之前的文章 數據結構與算法–位運算中有詳細介紹。

打印1 到最大的n位數

• 題目：輸入數字n， 按順序打印出從1 到最大的n為十進制數。比如，輸入3，則打印出1,2，3，…999。

• 題目看去來非常簡單，一個循環可以搞定，我們有如下代碼：

/*** 打印 1 ~ n位最大整數，* ex： n=3， 1~999* */public static void print1ToMaxOfNDigits(int n){int number = 1;int i = 0;while(i++ < n){number *=10;}for (int i1 = 0; i1 < number; i1++) {System.out.println(i1);}}

• 看起來是沒有問題，并且程序能正常執行，但是這里沒有考慮到整數的表示范圍問題
  • 整型數據 32 位，4 個字節，能標識的范圍是 -2³¹ ~ 2 ³²
  • 長整型數據64位，8 字節，能標識的范圍 -2⁶³~ 2⁶⁴
• 但是以上案例中的n是沒有上限的，也就是我們無論用long還是int都會達到最大數據無法標識問題，因此必須用其他方案來實現這次的累加，可以用字符串或者字符數組來模擬累加的操作。
• 通過以上分析，我們需要解決兩件事情：
  • 用字符串標識數字上的模擬加法
  • 打印用字符串表達的數字。
• 有如下代碼

/*** 打印 1 ~ n位最大整數，* ex： n=3， 1~999* */public static void print1ToMaxOfNDigitsByChars(int n){if(n<=0){return;}char[] number = new char[n];for (int i = 0; i < number.length; i++) {number[i] = '0';}while (!increment(number)){printCharArr(number);}}/*** 字符模擬加法*/public static boolean increment(char[] chars){boolean isOverflow = false;int takeOver = 0;for (int i = chars.length-1; i >= 0; i--) {//添加進位，初始為0不影響int nSum = chars[i] - '0' + takeOver;//+1 操作if(i == chars.length-1 ){nSum ++;}if(nSum >= 10){if(i==0){isOverflow = true;}else {nSum -= 10;takeOver = 1;chars[i] = (char) ('0' + nSum);}}else {chars[i] = (char)('0' + nSum);break;}}return isOverflow;}/*** 打印數字，取出首字母中'0'* */public static void printCharArr(char[] chars){if(chars == null || chars.length <= 0){return;}boolean begin = true;for (int i = 0; i < chars.length; i++) {if(begin && chars[i] != '0'){begin = false;}if(!begin){System.out.print(chars[i]);}}System.out.println();}

• 以上代碼，increment實現字符串number上的 加法，printCharArr負責打印。

• increment 需要注意的是，進位的規則實現，已經數據是否越界，因為我們需要打印的是N位數，當 我們遍歷到 第N 位的時候，并且第N位的大小 >= 10 ，此時觸發進位規則的時候，就達到了我們的最大值。

• printCharArr 打印功能雖然簡單，但是在字符串標識的數字中，必然會有前n-x位的字符是無需打印的 ‘0’ ，因為我們需要將093，打印成 93 才是我們程序需要的值，我們用一個標志位begin 來遍歷之前的所有0 ，當達到第一個非0 操作的時候，將begin標志位設置為true。才開始打印后面的字符。

• 終極解法，以上思路是完全可以實現的，但是用字符串來實現加法的 復雜度過于高，即使我們能在短時間內寫出來，很可能也會有紕漏，我們換一種思路，我們需要打印0 ~ 999 ，也就是一個三位字符數組，每一位數組都是0~ 9 這10 中情況，我們將他看成一個排列組合，只要將所有情況按照排列組合的順序打印出來，就可以變相的完成累加的工作。

• 全排列用遞歸表示非常容易。數字的第一位設置0~9 ，然后遞歸設置下一位0 ~ 9依次遞歸到第n位。如下實現：

/*** 遞歸打印1 ~ 最大n位整數* */public static void print1ToMaxOfNDigitsRecursively(int n){if(n <= 0){return;}char[] number = new char[n];for (int i = 0; i < number.length; i++) {number[i] = '0';}for (int i = 0; i < 10; i++) {number[0] = (char)(i+'0');print1ToMaxOfNDigitsRecursively(number, 0);}}public static void print1ToMaxOfNDigitsRecursively(char[] number, int index){if(index == number.length -1){printCharArr(number);return;}for (int i = 0; i < 10; i++) {number[index + 1] = (char)('0' + i);print1ToMaxOfNDigitsRecursively(number, index +1);}}

• 如上遞歸實現，我們在遞歸中只有在最高位完成字符串設置的時候才開始打印（index == number.length -1），因為我們將整個字符數組看成是一個排列的一種可能性，即使這個數字是001 ，我們也必須設置完后面的兩個 0 才開始打印。

啟示錄

• 第一個，陷阱在于大數問題，需要找到合適的數據結構來表示大數據問題。
• 第二個，在于時間復雜度，每個算法都應該考慮時間復雜度，應該思考不同的方法時間效率問題。
• 第三個，考慮問題的全面新，在整數的 n次冪問題中，需要考慮到非常多的邊界問題，很多會忽略底數為0 指數為負的情況
• 第四個，還是n次冪中對效率的需求，這個數學公式的運用還是需要靠積累，靠臨時來想是不可能的

上一篇：數據結構與算法–位運算
下一篇：數據結構與算法–代碼魯棒性案例分析

總結

以上是生活随笔為你收集整理的数据结构与算法--代码完整性案例分析的全部內容，希望文章能夠幫你解決所遇到的問題。

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