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

解题思路
当模式中的第二个字符不是"*"时：
1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
而当模式中的第二个字符是"*"时：
如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
1、模式后移2字符，相当于"x*"被忽略；
2、字符串后移1字符，模式后移2字符；
3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为"*"可以匹配多位；

这里需要注意的是：Java里，要时刻检验数组是否越界。

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        if(pattern==null||str==null)
            return false;
        int s=0,p=0;
        return match(str,s,pattern,p);
    }
    public boolean match(char[] str, int s,char[] pattern,int p)
    {
        if(s==str.length&&p==pattern.length)
            return true;
        if(s!=str.length&&p==pattern.length)
            return false;
        if(p+1<pattern.length&&pattern[p+1]=='*')
        {
            if((s!=str.length&&pattern[p]==str[s])||(s!=str.length&&pattern[p]=='.'))
                return match(str,s,pattern,p+2)||match(str,s+1,pattern,p)||match(str,s+1,pattern,p+2);
            else
                return match(str,s,pattern,p+2);
        }
        if((s!=str.length&&pattern[p]==str[s])||(s!=str.length&&pattern[p]=='.'))
            return match(str,s+1,pattern,p+1);
        else
            return false;
    }
}

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

public class Solution {
    public boolean isNumeric(char[] str) {
        if(str.length<0)
            return false;
        //a-是否有符号，b-是否小数，c-是否是科学计数法
        boolean a=false,b=false,c=false;
        for(int i=0;i<str.length;i++)
        {
            if(str[i]=='e'||str[i]=='E')
            {
                if(c)
                    return false;
                if(i==str.length-1)
                    return false;
                c=true;
            }
            else if(str[i]=='+'||str[i]=='-')
            {
                if(!a&&i>0&&str[i-1]!='e'&&str[i-1]!='E')
                    return false;
                if(a&&str[i-1]!='e'&&str[i-1]!='E')
                    return false;
                a=true;
            }
            else if(str[i]=='.')
            {
                if(b||c)
                    return false;
                b=true;
            }
            else if(str[i]'9')
                return false;
        }
        return true;
    }
}

题目描述
面试题21 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

空间换时间解法

import java.util.*;
public class Solution {
    public void reOrderArray(int [] array) {
        ArrayList a=new ArrayList();
        ArrayList b=new ArrayList();
        for(int i=0;i<array.length;i++)
        {
            if(array[i]%2==1)
                a.add(array[i]);
            else
                b.add(array[i]);
        }
        for(int i=0;i<array.length;i++)
        {
            if(i<a.size())
                array[i]=a.get(i);
            else
                array[i]=b.get(i-a.size());
        }
    }
}

插入排序思想

public class Solution {
    public void reOrderArray(int [] array) {
        //相对位置不变，稳定性
        //插入排序的思想
        int m = array.length;
        int k = 0;//记录已经摆好位置的奇数的个数
        for (int i = 0; i < m; i++) {
            if (array[i] % 2 == 1) {
                int j = i;
                while (j > k) {//j >= k+1
                    int tmp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = tmp;
                    j--;
                }
                k++;
            }
        }
    }
}