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

1つの整数が回文数であるか否かを判断する.回文数とは、正の順序(左から右へ)と逆の順序(右から左へ)が同じ整数です.
考え方1、まず数字を1つの文字列に変換し、文字列が返信文字列であるかどうかを判断する.コードは次のとおりです.

/*
**             
**
*/
#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
", 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("
%d
", isPalindrome(num));
}

時間複雑度:O(n)、nはデジタル長

空間複雑度:O(n)、nはデジタル長

考え方2、まず数字全体を逆転し、元の数字と等しいかどうかを判断するが、逆転過程で整数オーバーフロー現象が発生し、逆転中止を招く可能性がある.
考え方3、半分の数字だけを逆転して、逆転後の数字と残りの半分の数字が等しいかどうかを判断します.

#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
", isPalindrome(num));
}

時間複雑度O(n),nはデジタル長である
空間複雑度O(1)