LeetCode 9. 回文数 Palindrome Numbe

【题目描述】
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

【示例1】

输入: 121
输出: true

【示例1】

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

【示例1】

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

【思路1】
1、转化为字符串，判断字符串相同
2、时间复杂度O(n)

func isPalindrome(_ x: Int) -> Bool {
    var str = String()
    let chas = String(x).reversed()
    for c in chas {
        str.append(c)
    }
    if String(x) == str {
        return true
    }
    return false
}

【思路2】
1、从x的各位到最高位 依次遍历得到一个新数值，判断两个数值是否相等
2、时间复杂度O(log10ºn)，（以十为底n的对数）因为每次都会除以10

func isPalindrome(_ x: Int) -> Bool {
    if x < 0 {
        return false
    }
    var sum = 0
    var tmp = x
    while tmp > 0 {
        sum = sum*10 + tmp%10
        tmp/=10
    }
    return sum == x
}

【思路3】
1、思路2的改进
2、只需要遍历一半就可以，如果这两半相同，那就是回文数，需要判断奇数偶数
3、当halfSum大于x的时候，就遍历一半了，就停止遍历了！（多读几遍😁）
4、时间复杂度O(log10ºn) （以十为底n的对数）

代码实现：

func isPalindrome(_ x: Int) -> Bool {
    if x < 0 || (x%10 == 0 && x != 0) {
        return false
    }
    var halfSum = 0
    var tmp = x
    while tmp > halfSum {//当一半遍历完 halfSum就大于x了
        halfSum = halfSum*10 + tmp%10
        tmp/=10
    }
  //或前是 偶数，或后是奇数
    return tmp == halfSum || tmp == halfSum/10
}