文档章节

判断是否为回文数 Palindrome Number

叶枫啦啦
 叶枫啦啦
发布于 2017/06/27 15:00
字数 480
阅读 1
收藏 0

问题:

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

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

【注】问题要求O(1)空间复杂度,负数不是回文数

解决:

①每次提取头部和尾部的两个数,判断它们是否相等,判断后去掉头尾继续。采用除数和取余实现。暂时不能查看提交信息!耗时337ms。

public class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0) return false;
        int len = 1;
        while(x / len >=10) len *= 10;
        while(x > 0){
            int head = x / len;//获取头部
            int tail = x % 10;//获取尾部

            if (head != tail) {
                return false;
            }else{//去掉头部和尾部
                x = (x % len) / 10;
                len /= 100;

            }
        }
        return true;
    }
}

进化版:

public class Solution { //206ms
    public boolean isPalindrome(int x) {
        if(x < 0) return false;
        int div = 1;
        while(x / div >= 10) div = div * 10;  //位数
        while(x > 0) {
            if(x / div != x % 10) return false;
            x = x % div;  //去除头部
            x = x / 10;  //去除尾部
            div = div / 100;  //位数减2位
        }
        return true;
    }
}

③ 用tempx保存数字x的头部,用reverse保存除头部之外x位数的翻转,对比整个x的头尾两位,以及中间所有位reverse以后是否与不reverse时一致,即可得到结果。

public class Solution { //207ms
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int tempX = x;
        int reverse = 0;        
        while (tempX >= 10) { //// 当tempX剩下一位数的时候停下来
            reverse = reverse * 10 + tempX % 10; //将除了最高位之外的位数翻转
            tempX /= 10; //取得最高位
        }    
   
        return tempX == x % 10 && reverse == x / 10; ////对比整个x的头尾两位,以及中间所有位reverse以后是否与不reverse时一致
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 12
博文 569
码字总数 354997
作品 0
海淀
私信 提问
LeetCode:Palindrome Number - 回文数

1、题目名称 Palindrome Number(回文数) 2、题目地址 https://leetcode.com/problems/palindrome-number 3、题目内容 英文:Determine whether an integer is a palindrome. Do this witho......

北风其凉
2015/09/24
109
0
LeetCode 9. Number(回文数)

原题: IDetermine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. 判断一个整数是否是回文数。回文数是指正序(从左向右)......

dby_freedom
09/04
0
0
由两个n位数相乘得到的最大回文 Largest Palindrome Product

问题: Find the largest palindrome made from the product of two n-digit numbers. Since the result could be very large, you should return the largest palindrome mod 1337. Example......

叶枫啦啦
01/06
0
0
LeetCode:Valid Palindrome - 回文字符串

1、题目名称 Valid Palindrome(回文字符串) 2、题目地址 https://leetcode.com/problems/valid-palindrome/ 3、题目内容 英文:Given a string, determine if it is a palindrome, consid......

北风其凉
2015/08/05
0
0
UVa 401 - Palindromes 解题报告 - C语言

1.题目大意 输入字符串,判断其是否为回文串或镜像串。其中,输入的字符串中不含0,且全为合法字符。以下为所有的合法字符及其镜像: 2.思路 (1)考虑使用常量数组而不是if或switch来实现对镜...

rgvb178
2016/10/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

myeclipse 启动到10分之一左右就挂了

删掉 {workspace}/.metadata/.plugins/org.eclipse.e4.workbench/workbench.xmi

夜醒者
11分钟前
0
0
Hive on Spark 伪分布式环境搭建过程记录

进入hive cli是,会有如下提示: Hive-on-MR is deprecated in Hive 2 and may not be available in the future versions. Consider using a different execution engine (i.e. spark, tez) ......

PeakFang-BOK
18分钟前
0
0
用户输入和while 循环

# 用户输入和while循环# 7.1函数input() 的工作原理# 函数input() 让程序暂停运行,等待用户输入一些文本。获取用户输入后,Python将其存储在一个变量中,以方便你使用。message = inp...

吕湘颖
18分钟前
0
0
开发函数计算的正确姿势 —— 排查超时问题

写不尽的 code,查不完的 bug 通常我们写 bug,哦,不对,写代码时总不会一帆风顺,往往各种 bug 充斥其中,即使测试有较高的代码覆盖率往往也会有漏网之鱼。能写出一些比较隐蔽或者看起来像...

阿里云云栖社区
23分钟前
1
0
Python3新特性

一、类型注解 例子: def add(x:int, y:int) -> int: return x + y 解释: 类型`的形式指定函数的**参数类型**,用`-> 类型`的形式指定函数的**返回值类型 然后特别要强调的是,Pyt...

_Change_
37分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部