「⼩算法」回⽂数与数值合法性检验
原创
⼣⼩瑶
2018-06-12⼣⼩瑶的卖萌屋
喵喵喵,⼩⼣最近准备复习⼀下数学和基础算法,尽量每篇推送下⾯会附带点数学和基础算法的⼩⽂章。说不定哪天就⽤
(考)到了呢( ̄∇ ̄)注意哦,与头条位的⽂章推送不同,「⼩公式」和「⼩算法」⾥的⼩标题之间可能并⽆逻辑关联。
回⽂数
链接:
https://leetcode.com/problems/palindrome-number/description/
判断⼀个整数是否是回⽂数是leetcode上的⼀个简单算法题。回⽂数是指正序(从左向右)和倒序(从右向左)读都是⼀样
的整数。
例1:
输⼊:121
输出:true
例2:
输⼊:-121
输出:false
解释:从右往左读为121-。
例3:
输⼊:10
输出:false
解这个题的话,⼀个很⾃然⽽简单的想法就是将整数转换为字符串,并检查字符串是否为回⽂。但是,这需要额外的⾮常量
空间来创建问题描述中所不允许的字符串。
第⼆个想法是将数字本⾝反转,然后将反转后的数字与原始数字进⾏⽐较,如果它们是相同的,那么这个数字就是回⽂。
但是,如果反转后的数字⼤于 int.MAX,会发⽣数值溢出啦!
不过,按照第⼆个想法,为了避免数字反转可能导致的溢出问题,为什么不考虑只反转 int 数字的⼀半?毕竟如果该数字是
回⽂,其后半部分反转后肯定与原始数字的前半部分相同的呀。
所以直接上代码(原谅我⽤python写\(//∇//)\)
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0 or (x != 0 and x % 10 == 0):
return False
invx = 0
while invx < x:
invx = invx * 10 + x % 10
x //= 10
return invx == x or invx // 10 == x