数据结构与算法--代码完整性案例分析

朴灿烈づ我的快乐病毒、 2022-11-13 04:05 205阅读 0赞

#### 确保代码完整性 ####

*  在撸业务代码时候，经常面对的是接口的设计，在设计之初，我们必然要先想好入参，之后自然会有参数的校验过程，此时我们需要把可能的输入都想清楚，从而避免在程序中出现各种纰漏。但是难免面面俱到，有什么办法能覆盖整个入参的校验呢，我们可以考虑黑盒测试，用测试用例去覆盖，我们编码之前考虑测试用例，如果能先设计黑盒测试的测试用例，那么自然我们需要注意的校验点就出来了。我们一般都从功能测试，边界测试，负面测试三方面设计测试用例，确保代码的完整性。

#### 错误的处理 ####

*  我们在编码过程中，会遇到各种各样的异常情况，我们有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类型小数）直接用 这种方式判断是误差的，我在之前[价格计算遇到的问题][Link 1]相关文章中也有过详细的解释。
 *  修改后，判断两个小数是否相等，只能判断他们只差的绝对值是不是在一个很小的范围内，如果相差很小，可以认为相等，我们将 等于判断用如下equal方法电梯

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

*  最高效率的解法，在上面的解法中，每次求值都需要循环exponent次，在求解数值的幂次时候，我们想到的了之前 [递归与循环中讲到的斐波那契数列的非][Link 2]大众解法，也是时间复杂度最低的解法，我们先有如下公式：
 *  情况一  
     a n = a n / 2 ∗ a n / 2 , n 为 偶 数 a^n = a^\{n/2\}\* a^\{n/2\} , n为偶数 an=an/2∗an/2,n为偶数
 *  情况二  
     a n = a ( n − 1 ) / 2 ∗ a ( n − 1 ) / 2 ∗ a , n 为 奇 数 a^n = a^\{(n-1)/2\}\* a^\{(n-1)/2\}\*a , n为奇数 an=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 进行与操作，可以区分出奇偶性。位运算相关的知识在之前的文章 [数据结构与算法–位运算][Link 3]中有详细介绍。

##### 打印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 个字节，能标识的范围是 -231 ~ 2 32
     *  长整型数据64位，8 字节，能标识的范围 -263~ 264
 *  但是以上案例中的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次幂中对效率的需求，这个数学公式的运用还是需要靠积累，靠临时来想是不可能的

[上一篇：数据结构与算法–位运算][Link 3]  
[下一篇：数据结构与算法–代码鲁棒性案例分析][Link 4]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/106181869
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/114886125
[Link 3]: https://blog.csdn.net/liaojiamin0102/article/details/114941988
[Link 4]: https://blog.csdn.net/liaojiamin0102/article/details/115330657