导航页-LeetCode专题-Python实现

相关代码已经上传到github:https://github.com/exploitht/leetcode-python
文中代码为了不动官网提供的初始几行代码内容,有一些不规范的地方,比如函数名大小写问题等等;更合理的代码实现参考我的github repo

1、读题

Determine whether an integer is a palindrome. Do this without extra space.

这一题描述很简单,判断一个数字是否是回文数,不要用额外的空间。其实我觉得逻辑不是那么简答,2个点需要注意,怎样的数字是回文数和怎样算不使用额外空间?

1、先考虑什么数字是回文数?

  • 121是回文数
  • 1221是回文数
  • 1001是回文数
  • 0-9都是回文数
  • 负数都不是回文数

2、怎样理解不占用额外空间?

写代码肯定需要一定的内存空间,一点都不用就表示随意一个操作都可能违规。所以这里我理解的就是空间复杂度是O(1),也就是不管你给什么数字,我的算法占用空间恒定,而且不大。

写python的可能很容易想到把数字12345转换成序列类型然后反转判断反转前后是否相同来判断回文数,但是这样明显多出来了2个字符串对象,字符串和数字可不一样,字符串的基本单位是字符,字符才是和数字一个级别的,通俗讲数字12和1234占用空间一样,字符串12和1234差了约一半。也就是说我们可以操作数字本身,但是不能“投机取巧”空间换时间。

2、解题

怎样操作一个数字呢?判断回文数直接的想法是取首尾然后比较是否相等,相等则去掉首尾,继续比较下一个。
怎样取出最后一位呢?观察如下等式:
1234 % 10 = 4
1234 // 10 = 123
这样就分离出来了123和4

怎样取出第一位呢?
1234 // 1000 = 1
1000是1234的数量级
数量级可以通过1234 // 10 > 10; 1234 // 100 > 10; 1234 // 1000 < 10 来找到1000这个数字

这种算法涉及到寻找位数,更麻烦的是遇到1001这种回文数要做额外判断和处理,不然1001去掉首尾变成0了,虽然1001处理结果还算对的,但是10011这种就躲不过去了,去掉首尾得到1,明显逻辑错误了。鉴于这种实现比较low,这里不贴实现了。

3、第二种思路

题目的提示中说到反转一个整数,然后比较反转前后的数字,也可以判断回文数,只是需要注意反转可能导致溢出。既然反转是一个思路,又要考虑溢出问题,怎么办呢?观察数字:
123456789和123454321,需要处理的数字既然全反转可能会变大导致溢出,那么反转一半会怎样呢?
给定一个数字12344321如果处理成1234 1234,2个数字相等,那么就是回文数。
给定一个数字123454321如果处理成1234 12345,仅末尾不同,那么也是回文数。
需要注意的是0结尾的数字1210这种不单独处理容易被上面算法处理成回文数。

反转的思路和第二部分解题分析的类似,因为1234%10就能拿到最后一位
4 * 10 + 123 % 10就能拿到43,也就是后2位的反转结果,于是有了如下解法:

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
         # 0-9是回文数
        if 0 <= x <= 9:
            return True
        # 负数和0结尾的不是回文数
        if x < 0 or x % 10 == 0:
            return False
        tmp = 0
        while x > tmp:
            tmp = tmp * 10 + x % 10
            x = x / 10
        if x == tmp or x == tmp / 10:
            return True
        else:
            return False

转载于:https://www.cnblogs.com/cloudgeek/p/7601063.html

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐