【剑指】3.3 高质量代码之完整性

其他章节的代码段中，限于篇幅没有强调代码的完整性。但一个深刻教训是，面试编程时千万不要只考虑基本情况就开始动手，要提前和面试官沟通好基本情况、边界情况以及错误输入。测试用例也自己先写好，尽量不要等到面试官给出用例后发现有问题再去补救。

面试题16：数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。不使用类库求base的exponent次方，不需要考虑大数问题。

解题思路

看到该题目，可能最直接的想法是把底数base相乘指数exponent次。当然这时候就会考虑到指数为0、为负数怎么办。指数为负数就需要取绝对值计算后再对结果取倒数。此时又会考虑到底数为0则取倒数会出错，而数学上0的任意次方都是0(0的0次方无意义)，则可以先对底数作判断。那么不难写出如下代码：

public double exponent(double base,int exponent){
    boolean isNegative=false;
    double result=1.0;
    if(base==0.0) return 0;
    if(exponent==0){
        return 1;
    }else if(exponent<0){
        isNegative=true;
        exponent=-exponent;
    }
    //核心计算部分，到这里已经保证底数不为0，指数为正数
    for(int i=1;i<=exponent;i++){
        result*=base;
    }
    return isNegative?1.0/result:result;
}

上面是保证代码完整性，而为了优化计算速度可将核心计算部分封装成一个方法并加以改进，避免for循环中重复计算（O(exponent)->O(log exponent)），并使用位运算来判断奇偶和实现除2：

private double getResult(double base, int exponent){
    if(exponent==1) return base;
    double result=getResult(base,exponent>>1);
    return (exponent&1)==1?result*result*base:result*result;
}

面试题17：打印从1到最大的n位数

题目描述

输入数字n，按顺序打印出从1到最大的n位十进制数，比如输入3，则从1一直打印到最大的三位数999。

解题思路

考查这一题可能的输入：n为负数或0怎么办，n超过了整形或长整形所能表示的最大整数位数怎么办？归根结底打印出来的是字符，那么可以用字符数组表示要打印的数。每一位都是从0到9，那么整个打印其实是n个0到9的全排列。0~9可以用迭代，而n位组合则可以用递归。

class PrintNumber {
    //外部调用入口，初始化字符数组并递归填充数组
    public void print(int n) {
        if (n<=0) return;
        char[] num=new char[n];
        print(num,0);
    }

    //递归填充数组的每一位实现全排列
    private void print(char[] num,int index) {
        //传入的下标等于数组长度时填充完毕，调用打印方法
        if (index == num.length) {
            print(num);
            System.out.println();
            return;
        }
        //每次对当前位进行填充并递归填充下一位
        for (int i = 0; i < 10; i++) {
            num[index]=(char)(i+'0');
            print(num,index+1);
        }
    }

    //实际打印方法，通过trim标记避开数组前面的0
    private void print(char[] num) {
        boolean trim=true;
        for (char c : num) {
            if (!(trim && c == '0')) {
                System.out.print(c);
                trim = false;
            }
        }
    }
}

面试题18：删除链表的节点

题目描述

给出单向链表的头结点和其中的某一节点，在O(1)时间内删除该节点。

解题思路

通常删除节点需要知道链表的上一个节点，这需要从头遍历链表。为了实现O(1)的时间效率，可将下一节点复制到要删除的节点中并删除下一节点（Java中由gc删除）。要删除的节点是最后一个点时，仍需从头遍历。

public void deleteNode(ListNode head, ListNode target) {
    //防御型编程
    if (head==null||target==null) return;

    //如果目标是链表尾
    if (target.next == null) {
        //如果链表只有一个节点
        if (head == target) {
            head=null;
            return;
        }
        ListNode post;
        while (head.next != null) {
            post=head;
            head=head.next;
            if (head == target) {
                post.next=head.next;
                return;
            }
        }
    }
    
    //一般情况,gc会自动回收之前的target.next
    target.val=target.next.val;
    target.next=target.next.next;
}

面试题19：正则表达式匹配

题目描述

请实现一个函数用来匹配包括.和*的正则表达式。模式中的字符'.'表示任意一个字符，而*表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，与模式均不匹配。

示例

输入：
字符串"aaa"和模式"a.a"||模式"ab*ac*a"||模式"aa.a"||模式"ab*a"
输出：
分别为true||true||false||false

解题思路

Java本身对正则表达式提供了支持，而题目中的.和*规则也和一般正则表达式吻合。所以可以直接使用类库。

import java.util.regex.*;
public class Solution {
    public boolean match(char[] str, char[] pattern){
        String p=new String(pattern);
        String s=new String(str);
        Pattern pat= Pattern.compile(p);
        Matcher m=pat.matcher(s);
        return m.matches();
    }
}

你甚至可以直接使用String类提供的方法

public boolean match(char[] str, char[] pattern)
    {
        return new String(str).matches(new String(pattern));
    }

当然，本题的考点不在于此，面试中如果只会这样做而不进一步思考原理可能就被Pass。题目想要考查的是对状态机的理解与使用，可以参考LeetCode 8. 字符串转换整数 (atoi) (opens new window)。状态机的状态转换可由递归调用实现，限状态机要给出递归的停止条件。

public class Regex {
    public boolean match(char[] str,char[] pattern) {
        if (str==null||pattern==null) return false;
        return match(str,0,pattern,0);
    }

    public boolean match(char[] str, int strIndex, char[] pattern, int patternIndex) {
        //如果字符串与模式都已经匹配到结尾则返回true
        if (strIndex==str.length&& patternIndex==pattern.length) return true;
        //如果模式已经结束，而字符串不为空则返回false
        if (patternIndex==pattern.length) return false;

        //如果模式的下一字符存在，且为*时
        if ((patternIndex + 1)<pattern.length&&pattern[patternIndex + 1] == '*') {
            //如果当前的字符串可访问且与当前模式匹配
            if (strIndex<str.length&&(str[strIndex] == pattern[patternIndex] || pattern[patternIndex] == '.')) {
                //*匹配一个该模式字符，字符指针后移，模式进入下一状态（其实这种情况可以不写，可由两次递归表示：多个+0个）
                return //match(str,strIndex+1,pattern,patternIndex+2)|| 
                        //*匹配多个该模式字符，字符指针后移，模式保持在该状态
                        match(str,strIndex+1,pattern,patternIndex)||
                        //*匹配0个该模式字符，字符指针不变，模式进入下一状态
                        match(str,strIndex,pattern,patternIndex+2);
            } else {
                //当前字符与当前模式不匹配的话说明*匹配0个当前模式，字符指针不变，模式进入下一状态
                return match(str,strIndex,pattern,patternIndex+2);
            }
        }
        //否则如果当前字符串可访问且当前字符串与当前模式匹配则进入下一状态
        if (strIndex<str.length&&(str[strIndex] == pattern[patternIndex]|| pattern[patternIndex] == '.')) {
            return match(str,strIndex+1,pattern,patternIndex+1);
        }
        return false;
    }
}

面试题20：表示数值的字符串

题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

解题思路

同样地，可以直接使用正则表达式[+\-]?\d+(\.\d+)?([Ee][+\-]?\d+)?来判断:

public boolean isNumeric(char[] str) {
    String s=new String(str);
    Pattern p=Pattern.compile("[+\\-]?\\d+(\\.\\d+)?([Ee][+\\-]?\\d+)?");
    Matcher m=p.matcher(s);
    return m.matches();
}

面试题21：调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分（牛客网上新增的要求：并保证奇数和奇数，偶数和偶数之间的相对位置不变）。

解题思路

一种直接的方法可能是，扫描到偶数时就取出该数字，并将后面的所有数字前移1位，再将该偶数放入数组末尾，显然其时间复杂度是O(n^2)，不能让人满意。

那么可以尝试使用额外的O(n)空间，采用一个大小相同的数组arr，扫描原数组两遍。第一遍扫描到奇数时就依次复制进arr中，第二遍扫描到偶数时依次复制进arr中。最后再将arr整体复制回原数组，这种做做法的时间复杂度为O(3n)=O(n)。

public void reOrderArray(int [] array) {
    int[] arr=new int[array.length];
    int index=0;
    for(int i=0;i<array.length;i++){
        if(array[i]%2==1){
            arr[index]=array[i];
            index++;
        }
    }
    for(int i=0;i<array.length;i++){
        if(array[i]%2==0){
            arr[index]=array[i];
            index++;
        }
    }
    System.arraycopy(arr,0,array,0,array.length);
}

那么有没有不使用额外O(n)空间的算法呢，当然有。维护两个指针分别从数组的首尾向中间扫描，左指针扫描到偶数时停下，右指针扫描到奇数时停下。当左指针大于右指针时跳出循环，否则交换两个数字。

public void reOrderArray2(int[] array) {
    int left=0,right=array.length-1;
    while (left < right) {
        while ((array[left] & 1) == 1) {
            ++left;
        }
        while ((array[right] & 1) == 0) {
            --right;
        }
        if (left < right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        } else {
            break;
        }
    }
}

以上解法满足要求，虽然有嵌套循环，但是两个指针加起来只移动了n次。还可以可以用另一种思路，指针都从从左向右扫描，左指针扫描到偶数停下，右指针从停下的左指针开始出发扫描到奇数时停下交换，扫描到数组末尾都是偶数则说明已满足条件。

public void reOrderArray3(int[] array) {
    int left=0,right=0;
    while (right < array.length) {
        while ((array[left] & 1) == 1) {
            ++left;
        }
        right=left+1;
        while ((array[right] & 1) == 0) {
            if (right < array.length-1) {
                ++right;
            } else {//如果right已抵达数组右侧则说明left及其右侧都是偶数
                return;
            }
        }
        //停止while循环说明此时的array[right]为奇数
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}

值得注意的是，除了第一种方法，后面两种方法都不能保证奇数间或偶数间的相对位置不变，要想满足牛客的要求并且不能使用O(n)额外空间的话就需要用时间复杂度为O(n^2)的in-place算法。