9.回文数(leetcode)—— C语言

题目如下:判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

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

/*
** 判断一个整数是不是回文数
**
*/
#include 
#include 
#include 
#include 

// 将整数转换为数字字符串
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 
#include 

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)

你可能感兴趣的