关于c:9回文数leetcode-C语言

题目如下：判断一个整数是否是回文数。回文数是斧正序（从左向右）和倒序（从右向左）读都是一样的整数。

思路一、先将数字转换为一个字符串，而后判断字符串是否是回文字符串。代码如下：

/*
** 判断一个整数是不是回文数
**
*/
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

// 将整数转换为数字字符串
void myItoA(int num, char *str)
{
  int i = 0;
  while (num > 0)
  {str[i++] = num % 10 + 48;
    num /= 10;
  }
  str[i] = '\0';
}

// 判断字符串是否是回文字符串
// 双指针法，从首位开始遍历
bool isPalindrome(int x)
{if (x < 0) {return false;}
  if (x == 0) {return true;}
  // 获取数字长度
  int len = 0;
  int temp = x;
  while (temp > 0)
  {
    len++;
    temp /= 10;
  }
  printf("len is %d\n", len);
  // 动态分配存储空间
  char *str = (char *)malloc((len + 1) * sizeof(char));
  myItoA(x, str);
  int k = 0;
  while (str[k] != '\0')
  {printf("%c", str[k++]);
  }
  
  for (int i = 0, j = len - 1; i < j; i++, j--) {if (str[i] != str[j]) {return false;} 
  }
  return true;
}

int main (void) {
  int num = -12321;
  printf("\n%d\n", isPalindrome(num));
}

• 工夫复杂度：O(n)，n 为数字长度
• 空间复杂度：O(n)，n 为数字长度

思路二、先将数字整个逆转，而后判断其和原数字是否相等，不过在逆转过程中可能呈现整数溢出景象，导致逆转停止。

思路三、只逆转一半数字，而后判断逆转后的数字与剩下的一半数字是否相等。

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

bool isPalindrome(int x) 
{
  // 小于 0，必然不是回文
  if (x < 0) {return false;}
  // 等于 0，必然是回文
  if (x == 0) {return true;}
  // 如果一个数大于 0 且个位数为 0，则这个数必然不是回文的
  if (x % 10 == 0)
  {return false;}
  // 上面是 x > 0 的状况，只逆转一半，避免整数溢出
  int reversedNum = 0;
  // 当为奇数时，逆转的一半数字当前，x > reversedNum (12321 -> x == 12  reversedNum == 123)
  // 当 x 的数字个数为偶数时，逆转一半数字当前，x == reversedNum (1221 -> x = 12 reversedNum == 12)
  while (x > reversedNum) {
    // 必须排除个位数为 0 的数，否则这里会出问题，// 因为逆转的数最高位为 0，0 * 10 永远是 0，会导致谬误
    reversedNum = reversedNum * 10 + x % 10;
    x /= 10;
  }
  // 如果不是回文，则不管 x 是奇数还是偶数，x != reversedNum 或 x != reversedNum / 10
  // 如果是回文的，则为 x 偶数时，最终的 x == reversedNum，为奇数时，x == reversedNum / 10
  return x == reversedNum || x == reversedNum / 10;
}
int main (void) {
  int num = -1234321;
  printf("%d\n", isPalindrome(num));
}

工夫复杂度 O(n)，n 为数字长度
空间复杂度 O(1)