数据结构与算法:判断一个整数是否是回文数

您所在的位置:网站首页 判断一个数是否为回文数流程图 数据结构与算法:判断一个整数是否是回文数

数据结构与算法:判断一个整数是否是回文数

2024-02-05 05:20| 来源: 网络整理| 查看: 265

判断一个整数是否是回文数

具体定义不多介绍;

         /*          *  肯定不是回文的负数直接输出false          * 考虑到程序的运行效率以及额外存储空间和溢出等情况,所以采用首尾数字进行比较,即二分查找;          * 首先想到int-->Sting-->char数组,但是因为要逆序存储字符串,造成了额外的存储空间问题, 而且要实现类型转换,过程复杂;          * 其次是直接把int逆序,然后比较是否相等,利用取余和取整运算规则;但是当逆序以后的数字超出整形范围以后,会出现整数溢出问题,即逆序以后的数字不是预期的结果,导致最后输出false;          *  最后是采用二分法,首尾比较,相同就比较下一位,不相同直接false;          */

提供后两种解题思路的代码:

对于拆解整数成分散的个位数,取模和取余运算可以实现。

拆解右边第一个之后,在第二次拆解右边第一个时,把上一次的结果扩大十倍再加本次拆解的结果,最后判断和原来值是否相等。

//整数逆序之后判断是否相等 public static boolean intInverse(int x) { if (x < 0) { return false; } int a = x; int y = 0; while (x != 0) { y = y * 10 + x % 10; x = x / 10; } return a==y; }

 第一步还是拆解整数,此时是拆解前后两位,对这两位进行比较,重复这个步骤;

拆解最高位的方式肯定还是取余运算,重点在于除以多少,两位数除以100,三位数除以1000.根据位数来确定除以多少。定义一个整数用来表示初始值为1的被除数,用这个整数来和被除数取余,每取余一次,被除数乘以10一次,只要取余结果小于10了,被除数大小就确定了。

重点在于:如果前后两位相等时的舍弃以及被除数的变化;首先是被除数的变化,因为去掉了前后两位,数量级变化为2,所以被除数也得缩小两倍;然后是舍弃前后两位,取模可以舍弃最高位,取余可以舍弃最低位,即取余和取模要同时进行:用被除数取余之后的结果再取模;

//采用二分思想,判断前后两位是否相等,相等就舍弃,继续前后两位判断 public static boolean stringInverse(int x) { boolean result = true; if (x < 0) { return false; } int f = 1; while (x / f >= 10) { f = f * 10; } while (x != 0) { int first = x / f; int last = x % 10; if (first != last) { result = false; break; } x = (x % f) / 10; f = f / 100; } return result; }

 

 解题思路二的第二种实现方式:

首先还是负数直接false;其次要考虑的是,当x个位为0时,例如100,也是直接false;

回文整数存在奇位数和偶位数的情况,即2552、252;当x=2552时,只要判断25和52的逆序相等就可;当x=252时,只需要判断2和52%10即可;也就是把整数从中间拆解,两边各一半,对于奇位数把右半部分取模运算再逆序和左半部分比较。对于循环的结束条件,当然是确定拆解的次数是不是到了这个整数的正中间了,即左半部分要大于右半部分的数值。

public static boolean isPalindrome(int x) { if (x == 0) return true; if (x < 0 || x % 10 == 0) return false; int reversed = 0; while (x > reversed) { reversed = reversed * 10 + x % 10; x /= 10; } return x == reversed || x == reversed / 10; }

 



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3