随笔 - 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-> 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;
}
算法的复杂度:最差O(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 阅读(649) 评论(0)  编辑 收藏 引用


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