算法 LeetCode

9. 回文数

LeetCode 9. 回文数

Posted by Twany on July 16, 2019

题目描述

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

示例 1:

1
2

输入: 121
输出: true

示例 2:

1
2
3

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

示例 3:

1
2
3

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

思路

方案1

我第一想到的就是利用栈和队列相反的特性，分别存入并依次对比。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public boolean isPalindrome(int x) {
        
        
        Queue<Integer> queue = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
          
        int carry = 0;
        
        //不用考虑正负数，因为负数肯定不是回文数
        if( x< 0)
            return false;
        
        if( x == 0 )
            return true;

        while( x!=0 ){
            carry = x%10;   //余数
            x = x/10;   //下一位
            
            //依次存入
            queue.offer(carry);
            stack.push(carry);
        }
        
        while(!stack.empty()){
            if(stack.pop() != queue.poll())
                return false;
        }
        return true;
    }
}

复杂度为 o(2n)，分别是存入和取出的过程

方案二

我发现自己是真的是喜欢用栈… 忘了前面刚做了整数反转，直接将数反转，然后与原数对比不就好了吗？？？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public boolean isPalindrome(int x) {
		if (x < 0) {
			return false;
		}
		if (x == 0) {
			return true;
		}
		final int originX = x;
		int r = 0;
		while (x != 0) {
			int d = x % 10;
			x = x / 10;
			r = r * 10 + d;
		}
		return r == originX;
	}
}

这个方案只需要循环遍历一次原数x就可以，故复杂度仅需 o(n) 果然。。。

CATALOG