小白刷力扣之整数反转与回文数

简介: 小白刷力扣之整数反转与回文数

今天我们继续力扣之旅,还是从简单的题目下手,整数反转与回文数

整数反转

题目描述:

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123

输出: 321

示例 2:

输入: -123

输出: -321

示例 3:

输入: 120

输出: 21

注意:

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231,  231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

其实这个题目已经足够简单了,在解题的时候,只需要注意下溢出问题即可。

Way 1

非常容易想到的一种方法就是把给定的整数转换为字符串,然后通过字符串的反转来得到整数的反转,看代码

class Solution:
    def reverse(self, x: int) -> int:
        if x < 0:
            myint = - int(str(-x)[::-1])
            if myint < -2147483648:
                return 0
            return - int(str(-x)[::-1])
        else:
            myint = int(str(x)[::-1])
            if myint > 2147483647:
                return 0
            return int(str(x)[::-1])

这种解法是比较容易想到的,当然最终的成绩虽然是通过,但是却还有比较大的提升空间。

下面我们再来通过数学的方法来优化下

Way 2

对于一个整数,我们可以通过取它与10的模来获得最后一位数字,然后再把该数字乘以10,同时重置该整数为他自己的整除数值,以此类推,直至这个整数整除为0为止。

当然还需要注意整数的符号和溢出问题

class Solution:
    def reverse(self, x: int) -> int:
        reverse = 0
        if x >= 0:
            while x != 0:
                tail = x % 10
                x //= 10
                reverse = reverse * 10 + tail
            if reverse > 2**31 -1:
                return 0
            else:
                return reverse
        else:
            x = abs(x)
            while x != 0:
                tail = x % 10
                x //= 10
                reverse = reverse * 10 + tail
            if - reverse < - 2**31:
                return 0
            else:
                return - reverse

Java 实现

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

回文数

题目描述:

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

示例 1:

输入: 121

输出: true

示例 2:

输入: -121

输出: false

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

示例 3:

输入: 10

输出: false

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

进阶:

你能不将整数转为字符串来解决这个问题吗?

题目里也说了,最好不用字符串的方式来解决,那么我们来看看思路吧。

Way 1

我们可以继续使用上面整数反转的方式来解决

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        elif x == 0:
            return True
        elif x % 10 == 0:
            return False
        else:
            y = x
            reverse = 0
            while (x != 0):
                tail = x % 10
                x //= 10
                reverse = reverse * 10 + tail
            if y == reverse:
                return True
            else:
                return False

不过这种解法效果并不是很好

下面我们可以再进一步,来看看回文数的特点。

Way 2

回文数,必定会是一个前后对称的数字,比如:123321,3223 等等,所以如果我们能够拿出前半部分与后半部分,对比这两部分是否一致也是可以的

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        length = 0
        help = 1
        tmp = x
        while tmp != 0:
            length += 1
            tmp //= 10
        for i in range(1, length):
            help *= 10
        while (x != 0):
            head = x // help
            tail = x % 10
            if head != tail:
                return False
            x = x % help // 10
            help //= 100
        return True

该方法看似只循环了一般的数据,但是实际上结果却并没有提升太多

看来这种回文数问题,在没有限制的前提下,还是使用字符串的方法来解决最好。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        mystr = str(x)
        return mystr == mystr[::-1]

简洁又方便

Java 实现

class Solution {
     public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int help = 1;
        int tmp = x;
        while (tmp >= 10) {
            help *= 10;
            tmp /= 10;
        }
        while (x != 0) {
            if (x % 10 != x / help) {
                return false;
            }
            x = x % help / 10;
            help /= 100;
        }
        return true;
    }
}

今天的两道算法题都属于比较简单的,哈哈哈,从简单的开始,给自己增加信心呀!!

相关文章
|
1月前
|
存储
LeetCode整数反转
解决LeetCode上的整数反转问题的几种方法,包括错误的方法和优化后的解决方案,以及如何避免反转后的整数超出32位有符号整数范围的问题。
35 1
|
1月前
|
算法
LeetCode回文数(暴力解,求更好的思路)
这篇博客讨论了如何判断一个整数是否为回文数,提供了暴力解法的代码,并寻求更优的算法建议。
42 1
LeetCode回文数(暴力解,求更好的思路)
|
1月前
【LeetCode】整数翻转
【LeetCode】整数翻转
15 1
|
1月前
|
存储 C++
Leetcode第十二题(整数转罗马数字)
LeetCode第12题“整数转罗马数字”的解题方法,包括罗马数字的基本规则和特殊规则,以及如何使用C++实现整数到罗马数字的转换。
15 0
|
1月前
|
C++
Leetcode第十三题(罗马数字转整数)
这篇文章介绍了LeetCode第13题“罗马数字转整数”的解题方法,通过一个C++的类`Solution`中的`romanToInt`函数来实现,该函数使用哈希表和遍历字符串的方法,根据罗马数字的规则将输入的罗马数字字符串转换为对应的整数值。
48 0
|
1月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
17 0
|
3月前
|
算法
LeetCode第12题目整数转罗马数字
该文章介绍了 LeetCode 第 12 题整数转罗马数字的解法,通过使用 TreeMap 按照整数从大到小排序,先使用大的罗马数字表示整数,再用小的,核心是先表示完大的罗马数字,想通此点该题较简单。
LeetCode第12题目整数转罗马数字
|
3月前
|
算法
LeetCode第9题回文数
该文章介绍了 LeetCode 第 9 题回文数的解法,通过分析回文数的特征,只需反转一半数字进行比较即可,时间复杂度可降至 O(n/2),并总结了该题与整数反转有关,需根据回文数特征来解决。
LeetCode第9题回文数
|
3月前
|
算法
LeetCode第8题字符串转换整数 (atoi)
该文章介绍了 LeetCode 第 8 题字符串转换整数 (atoi)的解法,需要对字符串进行格式解析与校验,去除前导空格和处理正负号,通过从高位到低位的计算方式将字符串转换为整数,并处理越界情况。同时总结了这几道题都需要对数字的表示有理解。
LeetCode第8题字符串转换整数 (atoi)
|
3月前
|
算法
LeetCode第7题整数反转
该文章介绍了 LeetCode 第 7 题整数反转的解法,通过除 10 取模和乘 10 累加的方式实现整数反转,同时注意边界情况的判断,并总结了通过举例推算发现规律的解题思路。
LeetCode第7题整数反转