Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4389055
  • 博文数量: 291
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 7924
  • 用 户 组: 普通用户
  • 注册时间: 2016-07-06 14:28
  • 认证徽章:
个人简介

阿里巴巴是个快乐的青年

文章分类

全部博文(291)

文章存档

2018年(21)

2017年(4)

2016年(5)

2015年(17)

2014年(68)

2013年(174)

2012年(2)

分类: 架构设计与优化

2013-05-13 19:13:49

一、判断一个数字是否是回文
1、原理
       给定一个数字,判断该数字是否回文,比如:1551,15251都是回文,但是1314就不是回文。
        判断一个数字是否回文,可以先将数字转换成字符串,然后根据回文对称的特性判断:查看第i个字符是否等于第n-i+1个字符(i从1开始,n/2结束,n为字符串长度)。
2、实现
        #include    
        #define MAX_LEN 10+1
   
        bool ispalindrome(char *szPalindrome)
        {
            if (NULL == szPalindrome)
            {
                return false;
            }

            int iLen = 0;
            char *szTemp = szPalindrome;
            while (*szTemp++)
            {
                ++iLen;
            }

            if (iLen <= 0)
            {
                return false;
            }

            for (int i=1; i             {
                //if (szPalindrome[i-1] != szPalindrome[iLen-i+1-1])
                if (szPalindrome[i-1] != szPalindrome[iLen-i])
                {
                    return false;
                }
            }

            return true;
        }

        int main()
        {
            int iPalindrome = 1551;
            char szPalindrome[MAX_LEN] = {0};
            sprintf(szPalindrome, "%d", iPalindrome);
            if (ispalindrome(szPalindrome))
            {
                printf("%d is palindrome\n", iPalindrome);
            }
            else
            {
            printf("%d is not palindrome\n", iPalindrome);
            }

            return 0;
    }

二、找出字符串中最长回文
1、原理
        找出字符串中对称的子字符串的最大长度即最长回文。
        用数组来存储整个字符串,假设已经遍历到第i个字符了,要找出以该字符为中新的最长对称子串,可以用两个指针分别向前和向后移动,直到指针到达字符串两端或者两指针所指的字符不相等。
        由于对称子串可能以字符i为中心,完全对称,比如:abcba,也有能i只是对称子串的其中一个中心,比如:abba,因此,需要先分别用这两种方式求得最长回文长度,最后比较这两者大的为最终结果。
2、实现
        (1)第i个字符为中心
        int maxlenmiddle(char *szArray, int iIndex)
        {
            if ((NULL == szArray) || (iIndex < 0))
            {
                return -1;
            }
            int maxlen = 0;
            char *temp = szArray;
            while (*temp++)
            {
                ++maxlen;
            }
            int len = 1;        // 最长子串长度
            int  j = 1;           // 前后移动的指针
            while ((szArray[iIndex-j] == szArray[iIndex+j]) && (((iIndex-j) >=0) && (maxlen >(iIndex+j))))
            {
                len += 2;
                ++j;
            }
            return len;
        }
        (2)第i个字符只是其中一个中心
        int maxlenmirror(char *szArray, int iIndex)
        {
            if ((NULL == szArray) || (iIndex < 0))
            {
                return -1;
            }
            int maxlen = 0;
            char *temp = szArray;
            while (*temp++)
            {
                ++maxlen;
            }
            int len = 0;        // 最长子串长度
            int  j = 0;           // 前后移动的指针
            while ((szArray[iIndex-j] == szArray[iIndex+j+1]) && (((iIndex-j) >=0) && (maxlen >(iIndex+j+1))))
            {
                len += 2;
                ++j;
            }
            return len;
        }  

        // 用前面的两个函数分别遍历字符串中所有字符,比较结果即可找到最长回文长度
        int main()
        {
            char palindrome[] = "12521";
            int maxlen = 0;
            for (int i=0; palindrome[i]!='\0'; i++)
            {
                int temp = -1;
                int len1 = maxlenmiddle(palindrome, i);
                int len2= maxlenmirror(palindrome, i);
                temp = (len1 > len2) ? len1 : len2;
                if (temp > maxlen)
                {
                    maxlen = temp;
                }
            }
            return 0;
        }
 



     
阅读(1616) | 评论(1) | 转发(1) |
1

上一篇:字符串之反转

下一篇:字符串之压缩

给主人留下些什么吧!~~

scq2099yt2013-05-13 19:14:31

文明上网,理性发言...

评论热议
请登录后评论。

登录 注册