Palindrome Number

题目大意:不使用任何附加空间的情况下判定一个整数是否是回文.

你需要考虑负数是否是回文.

Solution

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
class Solution
{
public:
  bool isPalindrome(int x)
  {
      //负数不是回文
      if(x < 0) return false;
      //最左边,最右边的数位编号
      int left = 1,right = floor(log10(x * 1.0)) + 1;
      //取最左边的数位因子:
      //1==>10^0 2==>10^1 3==>10^2 len==>10^(len-1)
      //int head = pow(10,right - 1);
      int head = 1;
      for(int i = 1; i < right; ++i) head *= 10;
      //回文检测
      while(left <= right)
      {
          int l = x / head;
          int r = x % 10;
          if(l != r) return false;
          ++left;
          --right;
          x = x - l * head;
          x = (x - r) / 10;
          head /= 100;
      }
      return true;
  }
};

//=======================Driver===========================
int main()
{
    Solution sol;
    cout<<sol.isPalindrome(-1)<<endl;
    cout<<sol.isPalindrome(1)<<endl;
    cout<<sol.isPalindrome(10)<<endl;
    cout<<sol.isPalindrome(121)<<endl;
    cout<<sol.isPalindrome(INT_MAX)<<endl;
    return 0;
}


/*
===========makefile=================
all:
    @g++  solve.cpp -o   solve
    @./solve
clean:
    rm -f solve
    reset
===========leetcode accepted========
11507 / 11507 test cases passed.
Status: Accepted
Runtime: 185 ms
Submitted: 0 minutes ago
===========submission date=========
2017-02-03 Fri 10:51 AM
*/

Analysis

这道题Leetcode上给定的等级为Easy级别,判断一个字符串是否是回文是很容易的, 就是拿一个头指针,拿一个尾指针,然后相向而行,逐一判断.同样的道理,也可以应用到本题目.

首先是确定整数的长度,用$\log_pN+1$即为p进制数N的长度.这个我在前面的算法有提到过. 接下来就是取最左边的数字以及最右边的数字,取最右边的数字很简单了,直接对10求余即可.

怎么取最左边的数位呢?也不难.比如12,取1的话只需12/10,再如123,取1的话只需123/100. 类似地,我们可以知道长度为L的整数N,取最左边的数值方法为N/(10^(L-1)).这里记head为N/(10^(L-1)).

分析完了就上代码啦.需要注意的地方就是更新head,由于N每次减少首位两位数字,所以head=head/100, 对于数值N,更新时掐去首位即可.

Supplement

int kth(int x,int k)
{
    int len = floor(log10(x * 1.0)) + 1;
    int m = floor(x / pow(10,len - k));
    int n = 10 * floor(x / pow(10,len - k + 1));
    return  m - n;
}

上面这个函数是使用纯粹数学的方法来求得整数x的第k位数值.整数是从左到右从1开始编号.比如kth(1234,3)返回3. 其中的数学原理,手动模拟一下应该不难理解,在博客上写数学符号确实很麻烦(其实是懒啦~~),此处就从略了.