C语言 171. 最近回文数

题目描述
输入一个整数，找到与它的差的绝对值最小的回文数。当有两个解时，取较小的那一个解。

输入
输入为一行，包括一个整数 N ，整数 N 的长度在 1 到1000 之间（含 1000 ）。

输出
输出只有一个整数，为与输入数字的差的绝对值最小的回文数。

问题分析： 数据较大，应该考虑将输入转为字符串再计算

#include 
#include 

int is_backnum_str(char *n)
{

    int len = strlen(n);
    int left = 0, right = len - 1;
    while (left < right)
    {
        if (n[left] != n[right])
            return 0;
        left++;
        right--;
    }
    return 1;
}

char *get_num_str(char *a)
{
    int len=strlen(a);
    int i=0;
    while(i<len && a[i]=='0'){
        i++;
    }
    char t[1024];
    strcpy(t,a);
    strcpy(a,&t[i]);
    return a;
}

int compare_abstr(char *a, char *b)
{
    //删除前面多余的0再比较大小
    get_num_str(a);
    get_num_str(b);
    int lena = strlen(a), lenb = strlen(b);
    if (lena > lenb)
        return 1;
    if (lena < lenb)
        return -1;
    return strcmp(a, b);
}

void swap(char *a, char *b)
{
    char t[1024] = {0};
    strcpy(t, a);
    strcpy(a, b);
    strcpy(b, t);
}
//传入时，保证a>=b
char *add(char *a, char *b, char *ans)
{
    int lena = strlen(a), lenb = strlen(b), maxlen = strlen(a) + 1;
    memset(ans, '0', maxlen);
    int i = lena - 1, j = lenb - 1, k = maxlen - 1, bit = 0;
    while (j >= 0 || i >= 0)
    {
        bit = j >= 0 ? a[i] - '0' + b[j] - '0' : a[i] - '0';
        ans[k] += bit;
        if (ans[k] > '9')
        {
            ans[k] -= 10;
            ans[k - 1] += 1;
        }
        j--;
        i--;
        k--;
    }
    get_num_str(ans);
    return ans;
}

// a-b，传入时保证a>=b
char *sub(char *a, char *b, char *ans)
{
    int lena = strlen(a), lenb = strlen(b), maxlen = strlen(a);
    memset(ans, '0', maxlen);
    int i = lena - 1, j = lenb - 1, k = maxlen - 1, bit = 0;
    while (j >= 0 || i >= 0)
    {
        bit = j >= 0 ? (a[i] - '0') - (b[j] - '0') : a[i] - '0';
        ans[k] += bit;
        if (ans[k] < '0')
        {
            ans[k] += 10;
            ans[k - 1] -= 1;
        }
        j--;
        i--;
        k--;
    }
    get_num_str(ans);
    return ans;
}

char *reverse(char *src)
{
    //输入的是回文数，则直接返回
    if (is_backnum_str(src))
        return src;
    int len = strlen(src), left = 0, right = len - 1;
    while (left < right)
    {
        src[right--] = src[left++];
    }
    return src;
}

int main()
{
    char src[1024] = {0};
    scanf("%s", src);
    // 如果是回文数，直接返回
    if (is_backnum_str(src))
    {
        printf("%s\n", src);
        return 0;
    }

    char ans1[1024] = {0}, ans2[1024] = {0}; //存储两个解
    strcpy(ans1, src);
    reverse(ans1); //得到第一个解

    int len = strlen(src), idx = (len - 1) / 2;
    char tmp[1024] = {0}; //存储被+/-的量
    memset(tmp, '0', len);
    tmp[idx] = '1'; //只有第idx为为1，其他全为0；

    char res[1024] = {0}; //存储ans1 +/- tmp的量

    //计算第二个解,如果ans1=src,说明src本身为回文数，此种情况前面已经处理，所以此处两者必不相等
    // 1. ans1>src, 如输入src=91210,ans1=91219,ans2:将ans1-100=91119；
    // 2. ans1
    // 3. 考虑减法退位情况: src=91010,ans1=91019,ans2: 将ans1-100=90919(ans1-tmp=res),再将90919(res)翻转得到ans2=90909；计算tmp时，idx=(5-1)/2；即只有idx为1，其他全为0；
    // 4. 考虑加法进位情况: src=10919,ans1=10901, ans2: 将ans1+100=11001(ans1+tmp=res)，再将11001(res)翻转得到ans2=11011
    // 5. 考虑特殊情况1，减法退位后总位数变化的，如： src=1000, ans1=1001, ans2: 将ans1-100得到901(ans1-tmp=res)，翻转后得到909，909比src少1位，此时将(idx+1)置为9即可，即ans2=999;
    // 6. 考虑特殊情况2，加法进位后总位数变化的，9998>9999>9899>9889。要想加法进位，前面必为99……，得到的ans1>src,所以ans2不可能做加法，即不可能出现加法进位的情况。
    strcpy(ans2, ans1);

    if (compare_abstr(ans1, src) > 0)
        sub(ans2, tmp, res); //情况1，情况3 （在add和sub方法中已经处理了进位/退位的情况）
    else
        add(ans2, tmp, res); // 情况2，情况4
    if (strlen(res) < strlen(ans1))
        res[idx] = '9'; //情况5:1000>1001>991>999

    reverse(res);
    strcpy(ans2, res);
    // printf("the two val:%s,%s\n", ans1, ans2);

    if (compare_abstr(ans1, ans2) > 0)
    {
        swap(ans1, ans2); // ans1}
    char diff1[1024] = {0}, diff2[1024] = {0}; //存储两个解和ans1,ans2的差值
    sub(src, ans1, diff1);
    sub(ans2, src, diff2);
    printf("%s\n", compare_abstr(diff1, diff2) <= 0 ? ans1 : ans2);
    return 0;
}

初学C语言，如果代码写法有什么优化的地方，欢迎指正~

leetcode相同题目

部分优化：如果输入是回文数，则计算±后的回文数

#include 
#include 
#define MAX 20
int is_backnum_str(char *n)
{

    int len = strlen(n);
    int left = 0, right = len - 1;
    while (left < right)
    {
        if (n[left] != n[right])
            return 0;
        left++;
        right--;
    }
    return 1;
}

char *get_num_str(char *a)
{
    int len=strlen(a);
    if(len==1) return a;
    int i=0;
    while(i<len && a[i]=='0'){
        i++;
    }
    char t[MAX];
    strcpy(t,a);
    strcpy(a,&t[i]);
    return a;
}

int compare_abstr(char *a, char *b)
{
    //删除前面多余的0再比较大小
    get_num_str(a);
    get_num_str(b);
    int lena = strlen(a), lenb = strlen(b);
    if (lena > lenb)
        return 1;
    if (lena < lenb)
        return -1;
    return strcmp(a, b);
}

void swap(char *a, char *b)
{
    char t[MAX] = {0};
    strcpy(t, a);
    strcpy(a, b);
    strcpy(b, t);
}
//传入时，保证a>=b
char *add(char *a, char *b, char *ans)
{
    int lena = strlen(a), lenb = strlen(b), maxlen = strlen(a) + 1;
    memset(ans, '0', maxlen);
    int i = lena - 1, j = lenb - 1, k = maxlen - 1, bit = 0;
    while (j >= 0 || i >= 0)
    {
        bit = j >= 0 ? a[i] - '0' + b[j] - '0' : a[i] - '0';
        ans[k] += bit;
        if (ans[k] > '9')
        {
            ans[k] -= 10;
            ans[k - 1] += 1;
        }
        j--;
        i--;
        k--;
    }
    get_num_str(ans);
    return ans;
}

// a-b，传入时保证a>=b
char *sub(char *a, char *b, char *ans)
{
    int lena = strlen(a), lenb = strlen(b), maxlen = strlen(a);
    memset(ans, '0', maxlen);
    int i = lena - 1, j = lenb - 1, k = maxlen - 1, bit = 0;
    while (j >= 0 || i >= 0)
    {
        bit = j >= 0 ? (a[i] - '0') - (b[j] - '0') : a[i] - '0';
        ans[k] += bit;
        if (ans[k] < '0')
        {
            ans[k] += 10;
            ans[k - 1] -= 1;
        }
        j--;
        i--;
        k--;
    }
    get_num_str(ans);
    return ans;
}

char *reverse(char *src)
{
    //输入的是回文数，则直接返回
    if (is_backnum_str(src))
        return src;
    int len = strlen(src), left = 0, right = len - 1;
    while (left < right)
    {
        src[right--] = src[left++];
    }
    return src;
}

char * nearestPalindromic(char * src){
    char ans1[MAX] = {0}, ans2[MAX] = {0}; //存储两个解
    int len = strlen(src), idx = (len - 1) / 2;
    
    char tmp[MAX] = {0}; //存储被+/-的量
    memset(tmp, '0', len);
    tmp[idx] = '1'; //只有第idx为为1，其他全为0；

    char res[MAX] = {0}; //存储ans1 +/- tmp的量

    //输入本身是回文数，src=22,ans1=11,ans2:33（独立计算逻辑，分别-1，+1再反转即可）
    if(is_backnum_str(src)){
        sub(src,tmp,ans1);
        if (strlen(ans1) < len) ans1[idx]='9';
        add(src,tmp,ans2);
        reverse(ans1);
        reverse(ans2);
    }else{
        strcpy(ans1, src);
        reverse(ans1); //得到第一个解
    //计算第二个解
    // 1. ans1>src, 如输入src=91210,ans1=91219,ans2:将ans1-100=91119；
    // 2. ans1
    // 3. 考虑减法退位情况: src=91010,ans1=91019,ans2: 将ans1-100=90919(ans1-tmp=res),再将90919(res)翻转得到ans2=90909；计算tmp时，idx=(5-1)/2；即只有idx为1，其他全为0；
    // 4. 考虑加法进位情况: src=10919,ans1=10901, ans2: 将ans1+100=11001(ans1+tmp=res)，再将11001(res)翻转得到ans2=11011
    // 5. 考虑特殊情况1，减法退位后总位数变化的，如： src=1000, ans1=1001, ans2: 将ans1-100得到901(ans1-tmp=res)，翻转后得到909，909比src少1位，此时将(idx+1)置为9即可，即ans2=999;
    // 6. 考虑特殊情况2，加法进位后总位数变化的，9998>9999>9899>9889。要想加法进位，前面必为99……，得到的ans1>src,所以ans2不可能做加法，即不可能出现加法进位的情况。
        strcpy(ans2, ans1);
        if (compare_abstr(ans1, src) >0){
            sub(ans2, tmp, res); //情况1，情况3 （在add和sub方法中已经处理了进位/退位的情况）
            if (strlen(res) < strlen(ans1))  res[idx] = '9'; //情况5:1000>1001>991>999
        }else{
            add(ans2, tmp, res); // 情况2，情况4
        }
        reverse(res);
        strcpy(ans2, res);        
    } 
    
    
    if (compare_abstr(ans1, ans2) > 0) swap(ans1, ans2); // ans1char diff1[MAX] = {0}, diff2[MAX] = {0}; //存储两个解和ans1,ans2的差值
    sub(src, ans1, diff1);
    sub(ans2, src, diff2);
    src=(char *)malloc(sizeof(char)*MAX);
    strcpy(src,compare_abstr(diff1, diff2) <= 0 ? ans1 : ans2);
    return src;
}