首页 > 其他分享 >[Leetcode] 0009. 回文数

[Leetcode] 0009. 回文数

时间:2023-06-21 15:25:49浏览次数:54  
标签:10 false 数字 复杂度 0009 121 Leetcode 回文

9. 回文数

点击上方,跳转至Leetcode

题目描述

给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false

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

  • 例如,121 是回文,而 123 不是。

 

示例 1:

输入:x = 121
输出:true

示例 2:

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

示例 3:

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

 

提示:

  • -231 <= x <= 231 - 1

 

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

解法

首先,我们应该处理一些临界情况。所有负数都不可能是回文,例如:-123 不是回文,因为 - 不等于 3。所以我们可以对所有负数返回 false。除了 0 以外,所有个位是 0 的数字不可能是回文,因为最高位不等于 0。所以我们可以对所有大于 0 且个位是 0 的数字返回 false。

现在,让我们来考虑如何反转后半部分的数字。

对于数字 1221,如果执行 1221 % 10,我们将得到最后一位数字 1,要得到倒数第二位数字,我们可以先通过除以 10 把最后一位数字从 1221 中移除,1221 / 10 = 122,再求出上一步结果除以 10 的余数,122 % 10 = 2,就可以得到倒数第二位数字。如果我们把最后一位数字乘以 10,再加上倒数第二位数字,1 * 10 + 2 = 12,就得到了我们想要的反转后的数字。如果继续这个过程,我们将得到更多位数的反转数字。

复杂度分析:

时间复杂度:\(O(\log \textit{n})\),对于每次迭代,我们会将输入除以 10,因此时间复杂度为 \(O(\log \textit{n})\)。
空间复杂度:\(O(1)\)。我们只需要常数空间存放若干变量。

Python3

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        y, t = 0, x
        while t:
            y = y * 10 + t % 10
            t //= 10
        return x == y

C++

class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0)
            return false;
        int t = x;
        long long y = 0;
        while(t){
            y = y * 10 + t % 10;
            t = t / 10;
        }
        return x==y;
    }
};

标签:10,false,数字,复杂度,0009,121,Leetcode,回文
From: https://www.cnblogs.com/yege/p/17496272.html

相关文章

  • [Leetcode] 0013. 罗马数字转整数
    13.罗马数字转整数点击上方,跳转至leetcode题目描述罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。字符数值I1V5X10L50C100D500M1000例如,罗马数字2写......
  • [Leetcode] 0014. 最长公共前缀
    14.最长公共前缀点击上方,跳转至Leetcode题目描述编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。 示例1:输入:strs=["flower","flow","flight"]输出:"fl"示例2:输入:strs=["dog","racecar","car"]输出......
  • [Leetcode] 0020. 有效的括号
    20.有效的括号点击上方,跳转至leetcode题目描述给定一个只包括'(',')','{','}','[',']' 的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例1:输入:s="......
  • [Leetcode] 0724. 寻找数组的中心下标
    724.寻找数组的中心下标点击上方,跳转至leetcode题目描述给你一个整数数组 nums,请计算数组的中心下标。数组中心下标是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。如果中心下标位于数组最左端,那么左侧数之和视为0,因为在下标的左侧不存在元素。......
  • [Leetcode] 0728. 自除数
    728.自除数点击上方,跳转至leetcode题目描述自除数 是指可以被它包含的每一位数整除的数。例如,128是一个自除数,因为 128%1==0,128%2==0,128%8==0。自除数不允许包含0。给定两个整数 left 和 right,返回一个列表,列表的元素是范围 [left,right] 内......
  • [Leetcode] 0733. 图像渲染
    733.图像渲染点击上方,跳转至leetcode题目描述有一幅以 mxn 的二维整数数组表示的图画 image ,其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数sr, sc和newColor。你应该从像素 image[sr][sc] 开始对图像进行上色填充。为了完成上色工作,从......
  • [Leetcode] 0709. 转换成小写字母
    709.转换成小写字母点击上方跳转至Leetcode题目描述给你一个字符串s,将该字符串中的大写字母转换成相同的小写字母,返回新的字符串。 示例1:输入:s="Hello"输出:"hello"示例2:输入:s="here"输出:"here"示例3:输入:s="LOVELY"输出:"lovely" 提示:1<=s.l......
  • [Leetcode] 0717. 1 比特与 2 比特字符
    717.1比特与2比特字符点击上方,跳转至leetcode题目描述有两种特殊字符:第一种字符可以用一比特 0表示第二种字符可以用两比特(10 或 11)表示给你一个以0结尾的二进制数组 bits ,如果最后一个字符必须是一个一比特字符,则返回true。 示例 1:输入:bits=[1,......
  • [Leetcode] 0706. 设计哈希映射
    706.设计哈希映射点击跳转至leetcode题目描述不使用任何内建的哈希表库设计一个哈希映射(HashMap)。实现MyHashMap类:MyHashMap()用空映射初始化对象voidput(intkey,intvalue)向HashMap插入一个键值对(key,value)。如果key已经存在于映射中,则更新其对应的值v......
  • 回文质数(快速求出一个区间内的所有回文数)
    题目链接:回文质数code:#include<bits/stdc++.h>usingnamespacestd;vector<int>constructPalindromes(intstart,intend){vector<int>palindromes;if(start<=1){palindromes.push_back(1);start=2;}intstartLen=......