算法实现

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

解答如下：

/* 数字的格式可以用A[.[B]][e|EC]或者.B[e|EC]表示，其中A和C都是整数（可以有正负号，也可以没有），而B是一个无符号整数 */
class Solution {
public:
    //扫描0-9的数位，对应B
    bool scanUnInterge(char* string)
    {
        size_t start = index;
        while ((index < strlen(string)) && ('0' <= string[index]) && ('9' >= string[index]))
        {
            index++;
        }
        return index > start;
    }
    //扫描+或-或空起始的0-9的数位，对应A,C
    bool scanInterger(char* string)
    {
        if ((index < strlen(string)) && (('-' == string[index]) || ('+' == string[index])))
        {
            index++;
        }
        return scanUnInterge(string);
    }
    bool isNumeric(char* string)
    {
        if (!string)
        {
            return false;
        }
        bool flag = scanInterger(string);
        if ((index < strlen(string)) && ('.' == string[index]))
        {
            index++;
            //这里用||的原因，.前面后面可以不跟着数字。注：这里flag一定要放在||后面！！
            flag = scanUnInterge(string) || flag;
        }
        if ((index < strlen(string)) && (('e' == string[index]) || 'E' == string[index]))
        {
            index++;
            //这里用&&的原因，e|E前面后面都必须要有数字
            flag = scanInterger(string) && flag;
        }
        //注：index==strlen(string)一定要加!!反例1a123
        return (flag && (index == strlen(string)));
    }
private :
    size_t index = 0;
};

class Solution {
public:
bool match(char* str, char* pattern)
{
if ((NULL == str) || (NULL == pattern))
{
return false;
}
return matchCore(str, pattern);
}

bool matchCore(char* str, char* pattern)
{
    if (('\0' == *str) && ('\0' == *pattern))
    {
        return true;
    }
    if (('\0' != *str) && ('\0' == *pattern))
    {
        return false;
    }

    /* 分*匹配和.匹配 */
    if ('*' == *(pattern + 1))
    {
        if ((*str == *pattern) || (('.' == *pattern) && ('\0' != *str)))
        {
            return (matchCore(str + 1, pattern) || matchCore(str, pattern + 2));
        }
        else
        {
            return matchCore(str, pattern + 2);
        }
    }
    /* 单个字符匹配或与.匹配，则字符与模式都要更新 */
    if ((*str == *pattern) || (('.' == *pattern) && ('\0' != *str)))
    {
        return matchCore(str + 1, pattern + 1);
    }
    return false;
}

};

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

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        if ((NULL == str) || (NULL == pattern))
        {
            return false;
        }
        return matchCore(str, pattern);
    }
    
    bool matchCore(char* str, char* pattern)
    {
        if (('\0' == *str) && ('\0' == *pattern))
        {
            return true;
        }
        if (('\0' != *str) && ('\0' == *pattern))
        {
            return false;
        }

        /* 分*匹配和.匹配 */
        if ('*' == *(pattern + 1))
        {
            if ((*str == *pattern) || (('.' == *pattern) && ('\0' != *str)))
            {
                return (matchCore(str + 1, pattern) || matchCore(str, pattern + 2));
            }
            else
            {
                return matchCore(str, pattern + 2);
            }
        }
        /* 单个字符匹配或与.匹配，则字符与模式都要更新 */
        if ((*str == *pattern) || (('.' == *pattern) && ('\0' != *str)))
        {
            return matchCore(str + 1, pattern + 1);
        }
        return false;
    }
};

题3：数组中重复的数字
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        bool found = false;
        int count = 0;// 扩展时下标，如果只第一个用不到
        if ((NULL == numbers) || (0 == length))
        {
            return false;
        }

        int* hashTable = new int[length];
        memset(hashTable, 0, length * sizeof(int));
        for (int i = 0; i < length; i++)
        {
            hashTable[numbers[i]]++;
        }


        for (int i = 0; i < length; i++)
        {
            if (hashTable[numbers[i]] > 1)
            {
                duplication[count++] = numbers[i];
                found = true;
                break;
            }
        }

        delete[]hashTable;
        return found;
    }
};