几道回文数案例

回文数

说明：指正序（从左向右）和倒序（从右向左）读是一样的。

例如：abcdcba，abccba，正着读反着读是一样的。

一）判断一个字符串是否属于回文数

题目：给定一个字符串，判断该字符串是否属于一个回文数。

方式一：暴力法

原理：把字符串反转过来，一个一个字符比较。

说明：该方式不推荐使用，当一个字符串非常长时，把字符串反转需耗时，再一个一个字符比较也需耗时，而且此方式比较的时间复杂度是O(n^2)，n代表字符的个数。所以代码就不贴了。

方式二：（对半法）折叠法

原理：用第一个字符和最后一个字符比较，再比较第二个字符和倒数第二个字符，依次类推，一直比较到中心的位置。

例如：

abcdcba，先比较a，比较b，比较c，d不需要比较了，就比较完了。

abccba，先比较a，比较b，比较c，就比较完了。

（对半法）折叠法源码：

/*** 判断一个字符串是否属于回文数*/
public static boolean checkString(String s) {if (s == null) {return false;}// 转换成char数组char[] ch = s.toCharArray();int left = 0; // 第一个字符int right = ch.length-1; // 最后一个字符// 如果是奇数的字符串,最中间一位不需要比较while (left < right) {if (ch[left] == ch[right]) { // 如果第一个字符和最后一个字符相同，继续比较下一个字符left++;right--;} else {return false;}}return true;
}

方式三：中心扩展法（推荐）

原理：先计算字符串的长度是奇数还是偶数，再获取到中位数位置，以中位数的位置，依次向左右两个方向进行比较，和折叠法有点类似。

例如：

abcdcba，是奇数，先获取中位数d的位置，然后依次比较c，b，a字符，向两端扩展。

abccba，是偶数，先获取左中位数c，再获取右中位数c，依次比较c，b，a字符，向两端扩展。

备注：折叠法是从两端往中间方向比较，中心扩展法是从中间往两端方向比较。

中心扩展法源码：

/*** 中心扩展法* @param s* @return*/
public static boolean revertString(String s) {if (s == null) {return false;}// 转换成char数组char[] ch = s.toCharArray();int length = ch.length;int left = 0; // 获取左中位数int right = 0; // 获取右中位数// 如果是奇数的字符串,最中间一位不需要比较if ((ch.length & 1) == 1) {right = (length + 1) >>> 1;left = (length >>> 1) - 1;} else {right = length >>> 1;left = right - 1;}while (left >= 0 && right < length) {// 只要有一个字符不相等, 就不是回文字符串if (ch[left] != ch[right]) {return false;}left--;right++;}return true;
}

二）判断一个数字是否属于回文数

题目：给定一个数字，判断该数字是否属于回文数。

分析：

场景一：数字是不能通过反转来比较的，如果是整数，可能会整型溢出，如：2147483647，把该数字反转之后，会整型溢出，其它数字类型数据都可能存在溢出的情况。

场景二：如果是负数，或者数字最后一位是0，都不会是回文数。

方式一：数字转字符串

原理：把数字转换成字符串，再用字符串的方式判断是否属于回文数，见上面案例。

方式二：前尾去除法

原理：每一次比较前尾两个数字，比较完之后就把前尾两个数字去除，再用剩余的数进行比较。

例如：

1234321

1234321/1000000 = 1234321%10，比较完之后，把前后两个数字去除，剩余23432。

23432/10000 = 23432%10，比较完之后，把前后两个数字去除，剩余343。

343/100 = 343%10，比较完之后，把前后两个数字去除，剩余4。

判断1234321是一个回文数字。

前尾去除法源码：

/*** 判断一个数是否属于回文数*/
public static boolean checkNumber(int x) {// 负数肯定不是回文数，最后一位为0并且x不为0也不是回文数if (x < 0 || (x % 10 == 0 && x != 0)) {return false;}// 先计算出最大的位数int div = 1;while (x / div > 9) {div = div * 10;}while (x > 9) {// 用第一位数和最后一位数进行比较int left = x / div;int right = x % 10;if (left != right) {return false;}// 去除第一位数和最后一位数x = x % div;x = x / 10;// 因为一次性去除了两位数字,所以除以100div = div / 100;}return true;
}

方式三：对半法（折叠法）

例如：int x = 1234321

第一步：每一次都先取最低位，也就是x%10。

第二步：把最低位加在取出数的末尾，revertNum = revertNum * 10 + x % 10。

第三步：再把x/10。

第四步：重复第二步、第三步，当revertNum>x时，跳出循环。

第五步：考虑x有奇偶的情况，如果是偶数，x=revertNum，如果是奇数，x = revertNum/10。

对半法（折叠法）源码：

/*** 折半法(折叠法)*/
public static boolean revertNum(int x) {// 负数肯定不是回文数，最后一位为0并且x不为0也不是回文数if (x < 0 || (x % 10 == 0 && x != 0)) {return false;}int revertNum = 0;while (x > revertNum) {revertNum = revertNum * 10 + x % 10;x = x / 10;}return (x == revertNum) || (x == revertNum / 10);
}

识别二维码关注个人微信公众号

本章完结，待续，欢迎转载！
 
本文说明：该文章属于原创，如需转载，请标明文章转载来源！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！