首页 > 其他分享 >leetcode回文数

leetcode回文数

时间:2024-04-19 23:34:33浏览次数:25  
标签:10 数字 int 反转 revertedNumber leetcode 回文

给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。
回文数
是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
例如,121 是回文,而 123 不是。

示例 1:

输入:x = 121
输出:true

示例 2:

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

示例 3:

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

题解有多种思路,但是和我想的都不太一样。我第一种想的是把它变成字符串,然后两个for循环对比,但是我看到这是高阶做法,所以便想着用纯运算方法解题,可惜没解出来。
标准答案 第一种解题思路就是反转数字,但是这个反转数字并不是全部都反转,而是反转一半数字,

如果将数字本身反转,然后将反转后的数字与原始数字进行比较,如果它们是相同的,那么这个数字就是回文。
但是,如果反转后的数字大于 int.MAX\text{int.MAX}int.MAX,我们将遇到整数溢出问题。
按照第二个想法,为了避免数字反转可能导致的溢出问题,为什么不考虑只反转 int\text{int}int 数字的一半?毕竟,如果该数字是回文,其后半部分反转后应该与原始数字的前半部分相同。
例如,输入 1221,我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”,并将其与前半部分 “12” 进行比较,因为二者相同,我们得知数字 1221 是回文。

官方题解如下,说实话这代码太简洁了。

class Solution {
public:
    bool isPalindrome(int x) {
        // 特殊情况:
        // 如上所述,当 x < 0 时,x 不是回文数。
        // 同样地,如果数字的最后一位是 0,为了使该数字为回文,
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        // 当数字长度为奇数时,我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如,当输入为 12321 时,在 while 循环的末尾我们可以得到 x = 12,revertedNumber = 123,
        // 由于处于中位的数字不影响回文(它总是与自己相等),所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }
};

标签:10,数字,int,反转,revertedNumber,leetcode,回文
From: https://www.cnblogs.com/ink-bai/p/18146997

相关文章

  • LeetCode三则
    三道动态规划62.不同路径一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径?输入:m=3,n=7输出:28输入:m=3,n=2输出:3解释:......
  • LeetCode 面试经典150题---008
    ####151.反转字符串中的单词给你一个字符串s,请你反转字符串中单词的顺序。单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。注意:输入字符串s中可能会存在前导空格、尾随空格......
  • LeetCode- 19 删除链表的倒数第N个节点
    题目地址https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/参考实现/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(intval){t......
  • LeetCode三则
    198.打家劫舍你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况......
  • LeetCode两则
    1137.第N个泰波那契数泰波那契序列Tn定义如下:T0=0,T1=1,T2=1,且在n>=0的条件下Tn+3=Tn+Tn+1+Tn+2给你整数n,请返回第n个泰波那契数Tn的值。示例1:输入:n=4输出:4解释:T_3=0+1+1=2T_4=1+1+2=4示例2:输入:n=25输出:1389537提示:0<=n......
  • 马拉车Mananer(求最长回文子序列)
    直接上板子直接输出最长回文子序列的长度#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(0);cin.tie(0);cout.tie(0);usingnamespacestd;chars[32000005],st[32000005];intp[32000005];intchange(){intlen=strlen(st);......
  • Python案例:输出公元后到目前为止全部回文日期
    一、回文日期一个日期,如果顺读和倒读都一样,那么就称之为回文日期,比如今天:20211202,就是一个神奇的回文日期。二、提出任务输出公元后的全部回文日期要求每行输出五个回文日期统计总共有多少个回文日期三、完成任务(一)涉及知识点1、time模块time模块有两个常用函数time()......
  • LeetCode 面试经典150题---007
    ####13.罗马数字转整数罗马数字包含以下七种字符:I,V,X,L,C,D和M。字符数值I1V5X10L50C100D500M1000例如,罗马数字2写做II,即为两个并列的1。12写做X......
  • LeetCode 1315. Sum of Nodes with Even-Valued Grandparent
    原题链接在这里:https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/description/题目:Giventhe root ofabinarytree,return thesumofvaluesofnodeswithan even-valuedgrandparent.Iftherearenonodeswithan even-valuedgrandpar......
  • LeetCode三则
    53.最大子数组和给你一个整数数组nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组是数组中的一个连续部分。示例1:输入:nums=[-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组[4,-1,2,1]的和最大,为6。示例2:输入:nums=[1]输出:1示例3:输......