随笔 - 51, 文章 - 1, 评论 - 41, 引用 - 0
数据加载中……

两道程序题目

题一：找出字符串中最长的不重复的字母子串，字串不包括数字，区分大小写。如：a123bcBdba最长的子串bcBd。

分析：只考虑实现功能，较易实现。计算以src[i]为起始字母最大不重复子串的长度，找出最长的。
char *max_uniq_sub(char* src)
{
    int i, j, t;
    char *ret = 0;
    int maxlen = 0;

    for (i=0; src[i]!='\0'; i++)
    {
        /* 是否为数字 */
        if (src[i] >= '0' && src[i] <= '9')
            continue;

        for (j=i+1; src[j]!='\0'; j++)
        {
            /* 是否为数字 */
            if (src[j] >= '0' && src[j] <= '9')
                goto next;

            /* 是否与前面的重复 */
            for (t=i; t<j; t++)
            {
                if (src[j] == src[t])
                    goto next;
            }
        }
next:        /* 子串结束，是否是最长的 */
        if (j-i > maxlen)
        {
            ret = src+i;
            maxlen = j-i;
        }
    }

    return ret;
}
这个算法的时间复杂度最差O(n^3)，最好O(n)。最差时的例子：当字符串就是非重复子串。最好是的例子：数字字符串或者一个元素重复的字符串。

这个算法结构清晰，但有很多改进的地方。数据结构讲过一种字符串子串匹配算法，KMP算法。下面的改进算法就是吸取KMP算法的思想。子串遇到数字时和遇到相同的字母时，可以省去一些计算。
char* max_unqi_sub(char* src)
{
    char* ret = 0;
    int start = -1;    /*是否确定了子串的起始位置*/
    int maxlen = 0;
    int i=0, t=0;

    for (i=0; src[i]!=0; i++)
    {
        /* 是否为数字 */
        if (src[i] >= '0' && src[i] <= '9')
        {
            if (start != -1) /*子串的结束位置*/
            {
                if (i-start > maxlen)
                {
                    maxlen = i-start;
                    ret = src+start;
                }
                start = -1;    
            }
            continue;    
        }
        else
        {
            if (start == -1) /*子串起始位置*/
                start = i;
            for (t=start; t<i; t++)
            {
                if (src[i] == src[t]) /*子串的结束位置*/
                {    
                    if (i-start > maxlen)
                    {
                        maxlen = i-start;
                        ret = src+start;
                    }
                    start = t+1;    /*重新确定起始位置*/
                    break;
                }
            }
        }
    }
    if (i-start > maxlen)
    {
        maxlen = i-start;
        ret = src+start;
    }
    
    return ret;
}
算法的复杂度：最差Ｏ(n^2)，当字符串就是非重复子串。最好O(n)，当字符串是数字字符串或者一个元素重复的字符串

题二：一个自然数可以分解为若干个自然数相乘，求出每种分解自然数之和最少的一个。 如12=2*2*3，和为7=2+2+3
分析：如果把用穷举法把所有可能的组合计算出来，那无疑是复杂的。 假设a=b*c。其中b，c>=2。则a>=2*max{b,c}>=a+b。由此可见a因数分解后的和比a小。显然a的完全因数分解之后的和最小。问题就变成了自然数完全因数分解求和。
#include <math.h>
unsigned int minsum(unsigned int n)
{
    unsigned int sum = 0;
    unsigned int div_idx = 2;
    unsigned int sqrt_n=sqrt(n);
    
    while (1)
    {
        if (div_idx > sqrt_n)
            break;
        if (n % div_idx ==0)
        {
            sum += div_idx;
            n /= div_idx;
            sqrt_n = sqrt(n);
        }
        else
            div_idx++;
    }
    return sum+n;
}

posted on 2007-12-25 17:29 lemene 阅读(648) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理