[数据结构与算法]leecode-9. 回文数

一、题目


二、解题思路
例如判断123321是不是回文数，让123321每次余除以10,余数为各位上的值，放到一个数组中，再存数值的过程中，我们可以取得这个数字一共有多少位，作为我们的遍历次数进行铺垫，我定两个指针变量分别从头和尾进行遍历，遍历次数需分情况进行判断:
(1)如果位数长度len为奇数，遍历次数为（len-1）/2，举例12321，头尾遍历1=1,2=2，遍历两次即可，遍历次数：(5-1 )/2
(2)如果位数长度len为偶数，遍历次数为len / 2，举例123321，头尾遍历1=1，2=2，3=3遍历两次即可，遍历次数：6/2

头尾遍历时，两值不相等说明此数不是回文数，反之亦然。

有一些特殊情况：
（1）例如负数：-131,反过来131-，可以排除。
（2）零是回文数，反过来也是零。
（3）除零外，末尾为零的数都不是回文数，例如：120，反过来是21。

以下方便大家理解：
123321 / 10 = 12332 … 1
12332 / 10 = 1233 … 2
1233 / 10 = 123 … 3
123 / 10 = 12 … 3
12 / 10 = 1 … 2
1 / 10 = 0 … 1

三、虚机测试代码

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <math.h>

void main()
{
    bool isPalindrome(int x);

    int num = 123321;

    if(isPalindrome(num))
    {
        printf("%d yes!!!\n",num);
    }
    else
    {
        printf("%d no!!!\n",num);
    }
}

bool isPalindrome(int x)
{
    void PrintfArr(int *arr);

    if(x < 0)
    {
        return false;
    }
    else if(x == 0)
    {
        return true;
    }
    else if(x % 10 == 0)
    {
        return false;
    }

    int remainder = 0;
    //int num = pow(2,31) - 1;
    int num = 10;
    int *arr = malloc(sizeof(int) * num);
    int i = 0;
    
    for(i=0;i<num;i++)
    {
        arr[i] = 0;
    }
    
    i = 0;

    while(x / 10 != 0)
    {
        remainder = x % 10;
        x = x / 10;
        arr[i] = remainder;
        printf("x : %d, remainder : %d\n",x,remainder);
        i++;
    }
    arr[i] = x;
    //printf("num : %d\n",num);
    PrintfArr(arr);

    int q,y,arrsize;
    if((i+1) % 2 == 0)
    {
        arrsize = (i+1) / 2;
    }
    else
    {
        arrsize = i / 2;
    }

    for(q=0,y=i;q<arrsize;q++,y--)
    {
        if(arr[q] != arr[y])
        {
            return false;
        }
    }

    return true;
}

void PrintfArr(int *arr)
{
    int i = 0;
    while(arr[i] != 0)
    {
        printf("index: %3d, val : %3d\n",i,arr[i]);
        i++;
    }
    printf("=============\n");
}

四、虚机测试截图

五、leecode提交代码

bool isPalindrome(int x)
{
    if(x < 0)
    {
        return false;
    }
    else if(x == 0)
    {
        return true;
    }
    else if(x % 10 == 0)
    {
        return false;
    }
    int remainder = 0;
    int num = 10;
    int *arr = malloc(sizeof(int) * num);
    int i = 0;
    for(i=0;i<num;i++)
    {
        arr[i] = 0;
    }
    i = 0;
    while(x / 10 != 0)
    {
        remainder = x % 10;
        x = x / 10;
        arr[i] = remainder;
        i++;
    }
    arr[i] = x;
    int q,y,arrsize;
    if((i+1) % 2 == 0)
    {
        arrsize = (i+1) / 2;
    }
    else
    {
        arrsize = i / 2;
    }
    for(q=0,y=i;q<arrsize;q++,y--)
    {
        if(arr[q] != arr[y])
        {
            return false;
        }
    }
    return true;
}

六、leecode提交截图