[+]文章目录

回数

回数的概念比较好玩,就是说有这么一个字符串str, 长度为n, 现在index开始从0->index/2遍历,那么str[index] = str[n-1-index],那么这种数据就是我们通常说的回数。比如说a = “a”是回数, a = “aba”是回数, a = "strarts"也是回数。因为这道题目比较简单,所以很多公司都喜欢用它来检查程序员的基本编程能力。不光如此,它还能考察程序员考虑问题是否周密,是否从不同角度考虑问题。

比如说,现在我们要求字符串中的字符必须是小写字母或者大写字母,不能是其他字符,那该怎么写?朋友们可以试试。

int isSymbolRight(const char* str, int length)  
{  
    int index;  
    char symbol;  

    for(index = 0; index < length; index++){  
        symbol = str[index];  

        if(symbol >= 'a' && symbol <= 'z' || symbol >= 'A' && symbol <= 'Z')  
            continue;  

        return 0;  
    }  

    return 1;  
}  

int isAnagramOrNot(const char* str, int length)  
{  
    int index;  

    if(NULL == str || 0 == length)  
        return 0;  

    if(!isSymbolRight(str, length))  
        return 0;  

    for(index = 0; index < (length >> 1); index ++){  
        if(str[index] != str[length -1 -index])  
            return 0;  
    }  

    return 1;  
}  

上面的方法只是传统上的比较方法,如果面试的考官说用递归的方法怎么计算呢?朋友们可以再试一下。

int _isAnagramOrNot(const char* str, int length){  
    if(0 == length || 1 == length)  
        return 1;  

    return (str[0] == str[length -1]) ? _isAnagramOrNot(str +1, length-2) : 0;  
}  

int isAnagramOrNot(const char* str, int length)  
{  
    if(NULL == str || 0 == length)  
        return 0;  

    if(!isSymbolRight(str, length))  
        return 0;  

    return _isAnagramOrNot(str, length);  
}  

那么,我们把难度再提高一些,如果比较的数据很多,有1000万个,那么怎么利用多核编程提高数据的处理速度呢?

int _isAnagramOrNot(const char* str, int start, int end, int length)  
{  
    int index;  
    char symbol;  

    for(index = 0; index < length; index ++){  
        if(str[start + index] != str[end -1 - index])  
            return 0;  

        symbol = str[start + index];  
        if(symbol >= 'a' && symbol <= 'z' ||  
            symbol >= 'A' && symbol <= 'Z')  
            continue;  

        return 0;  
    }  

    return 1;  
}  

int isAnagramOrNot(const char* str, int length)  
{  
    int index;  
    int start[2];  
    int end[2];  
    int result[2] = {0};  

    if(NULL == str || 0 == length)  
        return 0;  

    start[0] = 0;  
    start[1] = length >> 2;  
    end[0] = length;  
    end[1] = length - (length >>2);  

#pragma omp parallel for  
    for(index = 0; index < 2; index ++)  
        result[index] = _isAnagramOrNot(str, start[index], end[index], length >> 2);  

    return (result[0] && result[1]) ? 1 : 0;  
}  

总结:

(1)从上面的题目可以看出,即使很简单的题目,也可以考察应聘者的总和能力

(2)提高算法执行效率的途径很多,朋友们平时课可以多多留意、多多积累

(3)所有算法的执行都是以正确性和健壮性为前提的,必须建立在充分测试的基础之上


« 前一篇