欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Palindrome Number

程序员文章站 2024-03-22 14:35:10
...

一 问题描述

Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:
Coud you solve it without converting the integer to a string?
翻译:
判定一个整数是不是回文串。一个是否是回文串取决于正着读或反着读是否一样。

二 解法

1. 第一解法(个人,转换字符串)

分析:
将数字转换成字符串数组之后,从两端往中间比较,很容易得出结论。
代码:

var isPalindrome = function(x) {
    
    let str = x.toString().split("");
    
    let len = str.length - 1;
    let mid = str.length / 2;
    
    for (let i = 0; i <= mid; i++) {
        if (str[i] !== str[len - i])
            return false
    }
    return true;
};

2. 第二解法(个人,非转字符串)

分析:
将数字通过数学计算生成一个相反排列的数字,与原数字比较即可。这时候,需要先判断是否是负数。并且,js中整数除法可以除出来小数,因此需要使用Math.floor()方法向下取整。
代码:

var isPalindrome = function(x) {
    
    let num = x;
    let arc = 0;
    
    if (x < 0)
        return false;
    
    while (num >= 10) {
        arc *= 10;
        arc += num % 10;
        num = Math.floor(num /10);
    }
    
    arc = arc * 10 + num;
    return arc === x;
    
};

3. 第三解法(个人,最优,非转字符串)

分析:
上述的通过数学计算,从头到尾完全反转,但实际上,是不需要这样的。回文串判断只需要前后半段比较。因此,通过新设置一个arc变量存储后半段数字,然后比较x是否大于arc,只要大于arc,就和前面的逻辑一样,一直生成后半段反转数字。
之后,判断有两个标准:

  1. 是否相等,如果相等, 必定是回文串
  2. 前半段此时已经小于后半段,说明,如果前半段乘10加上后半段的个位数如果和后半段相等,也可以判定为回文串。

注:这种判断方法不能正确处理0的问题。例如x = 10,x = 100。因为0 * 10 = 0。会干扰判断。因此在一开始需要排除掉这种情况。这种情况有两个特征,首先是x % 10 === 0,其次是x !== 0。

代码:

    var isPalindrome = function(x) {
        
        let num = x;
        let arc = 0;
        
        if (x < 0 || x % 10 === 0 && x !== 0)
            return false;
        
        while (num > arc) {
            arc *= 10;
            arc += num % 10;
            num = Math.floor(num /10);
        }
    
        if(arc === num || num * 10 + arc % 10 === arc)
            return true;
    
        return false;  
    };

结果:

11509 / 11509 test cases passed.
Status: Accepted
Runtime: 164 ms
Memory Usage: 45.3 MB
Runtime:faster than 98%

By DoubleJan
2019.7.7

相关标签: leetcode 算法