回文算法

一、回文算法:

回文指从左往右和从由往左读到相同内容的文字。比如: aba，abba，level。
回文具有对称性。
回文算法的目标是把最长的回文从任意长度的文本当中寻找出来。比如：从123levelabc中寻找出level。

回文数C语言（Xcode实现）

#include <stdio.h>
#include <stdlib.h>
int IsHuiWenShu( int );

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
   
    int num = 121;
    int ret = IsHuiWenShu( num );

    if (ret == 0)
    {
        printf( "The number %d is not huiwenshu.\n", num );
    }
    else
    {
        printf( "The number %d is huiwenshu.\n", num );
    }

    return 0;
}

int IsHuiWenShu( int number )
{
    int res = 0;
    int n = number;

    // 小于0和10的倍数的都不是回文数
    if (number < 0 || (number % 10 == 0 && number != 0))
    {
        return 0;
    }

    do
    {
        res = res * 10 + n % 10;
        n = n / 10;
    } while ( n );
    /*
        121
        res = 0+1 = 1
        n = 12
        res = 1*10+2 = 12
        n = 1
        res = 12*10+1=121
        n = 0
     
        n = 0 循环结束
        此时 x = 12 || x = 1
    */
    
    printf("res = %d\n,---number--- = %d\n",res,number);
    
    if ( res == number )
    {
        return 1;
    }

    return 0;
}

参考资料

二、回文串C语言

通过定义一个s字符数组，gets函数控制输入
i、j双指针来回判断字符数组的位置，和对应位置的值的比较，
while循环的条件 i<=j&&s[i]==s[j]
最终判断i、j的关系，如果i<=j说明存在对应位置不等的情况就是不是回文串

#include <stdio.h>
#include <string.h>
#define N 100

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");

char s[N] = "bsfgb";  //改写版本 直接赋值限定大小
        int i=0,j;
        printf("Input a String: \n");
        //输入一个字符串赋值给s
//        gets(s) = ;
//        char strs[N] = "batdb";
        //j的初始值为s字符串最后一个位置
        j=(int)strlen(s)-1;
        //进行while判断i、j的位置和i、j位置的值的关系
        while(i<=j&&s[i]==s[j]){
            //每比较一次就i右移、j左移一位
            i++;j--;
        }
        /*
         0 <= 4 s[0]=b s[4]=b
         1 <= 3 s[1]=b s[3]=b
         2 <= 2 s[2]=d s[2]=d
         3 > 1 结束  是回文最后是i > j
         */
        //判断最终i和j的的位置
        //根据i、j的位置最终是会互相超越的，所以如果i<=j说明存在对应位置不等的情况就是不是回文串
        if (i<=j)
        {
            printf("不是回文字符串\n");
        }
        else{
            printf("是回文字符串\n");
        }
    return 0;
}

Hello, World!
Input a String: 
是回文字符串
Program ended with exit code: 0

参考资料

三、最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

注意看实现思路
参考

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

解题思路：

 中心扩展法：

 每一个位置的字母都有可能是回文串的中心轴， 有三种可能：单轴/双轴左部/双轴右部
 例如：
 aba 此时的 b 就是作为单轴
 cbbc 此时的 bb 就是作为双轴, 对每一个 b 细分， 就是第一个 b 就是双轴左部，第二个 b 就是双轴右部了
 综合考虑一下, 发现双轴左/右只需要考虑到一个就可以
 所以这里只考虑了作为单轴和作为双轴右部 

参考

解题思路：

1.双重for循环+判别回文串
2.单纯for循环+中心扩散法
3.动态规划

参考

大神Leetcode