算法练习14：判断一个数是不是回文数（leetcode 9）

判断一个数是不是回文数：

方法1：字符串+中位数+双指针

1. 转成字符串，然后双指针，分别指向最前和最后，比较两指针的值；
2. 如果相等，两指针都向内移一步，继续比较值是否相等；
3. 如此循环此过程，如果中间有哪一步值不相等，则可以判断其不是回文数；而当其移动到中位数之前，都相等，那就代表它是回文数

关于中位数的技巧：
可以使用x.length >> 1来求（相当于除2的结果，向下取整），当为奇数时，刚好为最中间的数的下标；如果是偶数，则为最中间两个数的右边那个数下标
比如：
121，转成字符串str='121'，它的长度是3，3 >> 1 = 1，中位数下标为1，即对应数字2，那就只用比较它前后的值str[0]和str[2]，1和1相等，即循环到i < 中位数(1)，循环一次就好
1221，转成字符串str='1221'，它的长度是4，4 >> 1 = 2，中位数下标为2，即对应第2个2；第1个循环，i =0 , str[0]和str[3]比，1和1相等，继续；第2次循环，i =1, str[1]和str[2]比，相等，下一次循环，i = 中位数，结束
所以由此看出，无论是奇数还是偶数，它们的结束条件都是循环次数小于中位数

当然这个方法，是有边界值，就是2位和1位数时，不适用，所以要对它们做边界处理

var isPalindrome = function(x) {
    // 如果为负责，肯定不是回文
    if(x < 0) return false;
    // 将数字转化为字符串
    let str = String(x)
    let len = str.length;
    // 如果是1位数，肯定就是回文数
    if(len == 1) return true;
    // 如果是2位数，只用比较第1位和第2位是否相等
    if(len === 2) {
        return str[0] === str[1]
    }
    // 如果不是边界值，就用使用中位数作为临界值，循环比较前后的数是否相等
    for(let i = 0; i < len >> 1; i++) {
        if(str[i] !== str[len -1 -i]) return false; 
    }
    return true;
};

这个方法如果忽略将数字转化为字符串的时间，

• 时间复杂度是O(n)，虽然使用了中位数，j时间复杂度O(n/2)，但还是约等于O(n)
• 空间复杂度为O(n)，空间复杂度是因为字符串要占额外空间

方法2：反转一半的数字

使用数字方法：
1221，我们只要取出后半段数21，进行翻转12，判断它跟前半段的数12，判断是否相等，相等则为回文数，否则则不是。
这个解法的关键在于如何判断它已经过半了：通过判断前半断是否小于等于后半断的翻转，如果是则已经过半

实现过程：
1221：

• 第1次，取最后数1，只有1位，不用翻转，前半段122 > 1，继续
• 第2次，取最后数2，和之前1进行翻转得12，前半段12，相等，判断为回文

12331

• 第1次，取最后数1，前半段1233 > 1，继续
• 第2次，取最后数3，翻转13，前半段123 > 13，继续
• 第3次，取最后数3，翻转133，前半段12 < 133，结束，小于，循环结束，这时，因为还有奇偶不同，所以我们还要用判断133 % 10 来判断是否和前面相等，以防止它是个奇数的情况（偶数不用考虑，因为两数折半，如果相等是不需要进行后判断的，如果不等即便再%10也不会改变结果，所以这个操作对偶数没影响），133 / 10 = 13，还是跟前半段不相等，所以它一定不是回文数

var isPalindrome = function(x) {
  if(x < 0) return false;
  // x尾数等于0的情况，只有x自身为0才有可能是回文数
  if(x % 10 == 0) {
    return x === 0
  }
  let backwards = 0
  while(x > backwards) {
      // 最每后半段翻转
      backwards = backwards * 10 + x % 10
      x = Math.floor(x/10)
  }
  return x === backwards || x === Math.floor(backwards/10) 
};

• 时间复杂度：O(logn)
• 空间复杂度：O(1)