7/7 算法题详解:Palindromic Decimal Numbers 判断回文数


(mmforever) #1

本视频来自于北美CS刷题神器BitTiger Pro


今天我们来讨论一下回文数。首先我们需要理解一下什么是回文,回文是指一个从前往后读和从后往前读都一模一样的字符串。比方说,“redivider”就是一个回文,而“divider”就不是了,同理可知,7,121,2147447412等就可以说是回文数。

我们今天的目的就是通过完成一个程序,实现输入一个数字后判断该数字是否可以被视为回文数字。比方说输入是100,就需要返回false,输入1441,就需要返回true。那如果是负数呢?一般需要返回false,因为数字前面有一个负号,而尾部没有。但在面试的时候如果你遇到了这个题目,请立即与你的面试官确认和讨论这种情况,这是一个加分项。

解法一:

当你了解了回文以后,你就可以很自然地想到一个方法,先把这个整数转换为字符串,然后通过字符比较得到这个判断结果,字符串判断是否为回文可以参见另外一篇文章【Test palindromicity判断一个字符串是否为回文】,假设传入的数字的长度是n。那么这个方法的时间复杂度是O(n),因为你需要访问所有的字符,空间复杂度是O(n),因为整数需要先转换成字符串。

解法二:

我们能提升一下这个算法吗?我们不能提升时间复杂度上的性能,因为我们需要比对所有的内容才能得出结论,那我们就从空间复杂度下手。考虑到我们在转化成字符串后进行判断的优势就是我们可以随意访问任何位置的内容用以判断最左边的内容和最右边的是否相同,其实我们对整数也可作相同的事情。

我们知道一个整数的最低位=A % 10(取余操作),最高位=A/10n-1整除操作。比如给出一个整数,151751,那么最高位是151751/105=1,最低位是151751%10=1。现在我们可以设计出我们新的算法了。我们比较它们的最高位和最低位,如果一致,就处理掉这两位,然后继续循环匹配,如果不一致,就直接返回false。比方说下图就是步骤举例。

![](data:image/svg+xml;utf8,)

这个方法的时间复杂度是O(n),但空间复杂度降低到了O(1)。

下图就是我们代码实现:

![](data:image/svg+xml;utf8,)

第一步我们需要判断是否小于0,是的话就需要返回false。第二步,计算数字是几位的并初始化掩码(mask)。第三步就是循环判断最高位和最低位是否相等,如果不相等,返回false,否则继续,注意数字最高位和最低位的去除方法以及掩码的处理。

思考题

还有一种方法可以判断,就是通过反转整个数字,然后判断两个数字是否一致来实现。你可以自己动手试试看,然后分析一下时间复杂度和空间复杂度。


本视频来自于北美CS刷题神器BitTiger Pro

每月更新的BitTiger Pro是一个覆盖了CS和数据科学方向最新高频面试题的精讲视频库。订阅后,你可以在Code Evaluation System亲自练习这道题。

![](data:image/svg+xml;utf8,)