程序员的算法趣题系列 -Q01- 回文数

前言

此篇为《程序员的算法趣题》中的入门篇第一题"回文数"的相关解题分析博文。

关于该系列的介绍请看：

《程序员的算法趣题》-开坑记录

题目

如果把某个数的各个数字按相反的顺序排列，得到的数和原来的数相同，则这个数就是“回文数”。

譬如 123454321 就是一个回文数。

问题
求用十进制、二进制、八进制表示都是回文数的所有数字中，大于十进制数 10 的最小值

例） 9（十进制数） = 1001（二进制数）= 11（八进制数）

※本例中的十进制数 9 小于 10，因此不符合要求。

表 1

作者思路及代码实现

因为是二进制的回文数，所以如果最低位是 0，那么相应地最高位也是 0。但是，以 0 开头肯定是不恰当的，由此可知最低位为 1。

如果用二进制表示时最低位为 1，那这个数一定是奇数，因此只考虑奇数的情况就可以。接下来可以简单地编写程序，从 10 的下一个数字 11 开始，按顺序搜索。譬如用 Ruby 就可以通过下面的代码找到符合条件的数（代码清单）。

（以下为代码清单 01.01）

# 从11开始搜索
num = 11
while true
	if num.to_s == num.to_s.reverse &&
	   num.to_s(8) == num.to_s(8).reverse  &&
	   num.to_s(2) == num.to_s(2).reverse
	  puts num
	  break
	end
	#只搜索奇数，每次加2
	num += 2
end

作者的小 TIPS：

下面试着用 JavaScript 实现同样的逻辑。JavaScript 里没有内置把字符串逆序的标准函数，因此首先需要封装一个返回逆序字符串的方法，其他流程则和代码清单 01.01 中的一致。JavaScript 版本的实现如代码清单 01.02 所示。

/* 为字符串类型添加返回逆序字符串的方法 */
String.prototype.reverse = function (){
	return this.split("").reverse().join("");
}

/* 从11 开始搜索 */
var num = 11;
while (true){
	if ((num.toString() == num.toString().reverse()) &&
	    (num.toString(8) == num.toString(8).reverse()) &&  
	    (num.toString(2) == num.toString(2).reverse())){  
		console.log(num); 
		break; 
	}  
	/* 只搜索奇数，每次加2 */ 
	num += 2;
}

Point

很多语言都提供了把整数转换成二进制数或者八进制数的方法。表 2 汇总了代表性语言的相关函数或者方法，不过 C 语言并没有提供直接转换的接口。

表 2　各编程语言中进制转换的接口

答案

585（二进制数是 1001001001，八进制数是 1111）

自己做的思路及实现

看到题目，首先对比了以下表 1 中的数，便很容易得出一个规律，就是在 1-100 中，3 种不同进制表示下，十进制能产生的回文数最少，然后是八进制然后是二进制。（这个应该很容易想明白吧，单个位能用的数字越多，碰撞越少）

所以想明白这一点之后，就考虑怎么去查找十进制下大于 10，然后同时满足三种进制表示都为回文数的数字。

我自己是这样想的，既然要看是不是回文数，那我就干脆用相对能产生回文数少的十进制表示数来构造回文数。比如从 1-9999。我可以用 1-99 来构造回文数。因为题目要满足三种进制表示均为回文数，所以我就不去在十进制下一个个往上加着去遍历判断。直接构造出来十进制下的回文数，然后去判断八进制表示是不是，再判断二进制表示是不是。

这里解释下为如何在用 1-99 来构建 1-9999 里面的回文数。

可能大多数人不需要解释就能想到，但这里还是解释下。

1-9 就不说了，分别复制一份就是 11，22，33...88，99。

然后是大于 10 的，这里举例 10，21，99。

10 可以构建两个回文数，一个是 1001，一个是 101。

21 同样是两个，2112 和 212。

99 也是两个，9999 和 999。

基本思路就是这样，下面我们来看看代码如何实现吧。

这里我分别写了四个函数，对应不同的功能。

第一个函数是一个通过传入两个参数，来返回满足条件的回文数的入口方法。两个参数作用分别是，

min 符合要求的数不小于 min
buildStart 构造回文开始的数

该函数代码如下

/*
     * 构造回文，并找出符合要求的数
     * @param min 符合要求的数不小于min
     * @param buildStart 构造回文开始的数
     * @return
     */
    public int findPalindromicNumber(Integer min, Integer buildStart){
        String buildStartStr = buildStart.toString();
        //初始化符合要求的回文数返回值
        Integer resultNum = null;
        //是否进行奇数构造
        Boolean odd = true;
        //遍历中的i的长度
        Integer length_i = buildStart.toString().length();
        //构造数的长度
        Integer length_b = buildStartStr.length();
        for(Integer i = buildStart; length_i <= length_b; i ++){
            length_i = i.toString().length();
            if(odd == true && length_i > length_b){
                //将遍历数还原，开始进行偶数位的回文数构造
                odd = false;
                i = buildStart;
            }
            //进行回文数构造
            Integer palindromicNum = buildPalindromic(i, odd);
            //如果构建出的数既大于传入的最小值，又符合八进制二进制是回文数的要求，则返回该值。
            if(palindromicNum > min && checkResult(palindromicNum)){
                return palindromicNum;
            }
        }
        //遍历结束，仍未找到结果，从新设置buildStart的值，开始递归
        buildStart = (int)Math.pow(10, buildStartStr.length());
        resultNum = findPalindromicNumber(min, buildStart);
        return resultNum;
   }

因为用一个数来直接构造回文数，当这个数是大于等于 10 的时候，可以构造位数是奇数个的回文数和位数是偶数个的回文数（101 和 1001）。

所以在遍历的时候，需要对 遍历数进行按位区分，n 位数(n>=2)的数进行回文数构造，需要先进行位数是奇数的回文数构造，如果位数为奇数的回文数构造验证完之后仍未有结果，再从头遍历 n 位数，用其构造位数为偶数位的回文数，并验证。

例如，10 -> 101 验证不通过，11 -> 111 验证不通过 .... 99 -> 999(假设此前都没有结果)。返回从 10-99 的遍历，这次生成形如 1001,1111,1221 的位数为偶数的回文数，并依次验证。

然后是入口函数中用到的另外两个函数 buildPalindromic 和 checkResult。直接贴代码，注释里面有解释函数作用。

/**
     * 传入用作构建回文数的数字，以及构建出的回文数位数是奇数偶数为参数，从而构建回文数
     * @param sourceNum 原始数字，用于构建回文数的初始值
     * @param odd 是否构建奇数型回文，默认为true
     * @return
     */
   public int buildPalindromic(Integer sourceNum, Boolean odd){
       //做初始化操作，odd参数不传时设置为真
       if(odd == null){
           odd = true;
       }
       if(sourceNum < 1){
           throw new IllegalArgumentException("参数不正确，sourceNum(用于构建的数)不能小于1");
       }
       //开始构建
       String sourceNumStr = sourceNum.toString();
       StringBuffer rollbackNumStr = new StringBuffer(sourceNumStr).reverse();
       //初始化要返回的回文数StringBuffer型
       StringBuffer palindromiceNum = new StringBuffer();
       //先拼接上原始的构造数
       palindromiceNum.append(sourceNumStr);
       if(odd){
           //构建位数为奇数个的回文数
           palindromiceNum.append(rollbackNumStr.substring(1, sourceNumStr.length()));
       }else{
           //构建位数为偶数个的回文数
           palindromiceNum.append(rollbackNumStr.substring(0, sourceNumStr.length()));
       }
       return Integer.valueOf(palindromiceNum.toString());
   }

/**
     * 验证传入数值是否满足要求,由于传入的数就是由十进制状态构建的回文数，故不验证十进制
     * @param checkNum 需要被检查的数值
     * @return
     */
   public boolean checkResult(Integer checkNum){
       //先转化成八进制，然后反转，进行判断。
       String octalString = Integer.toOctalString(checkNum);
       String rollbackOctalStr = new StringBuffer(octalString).reverse().toString();
       //判断的时候先判断在八进制状态下是否满足，再判断，因为同样从十进制的1到100，八进制的回文数比二进制少
       if(rollbackOctalStr.equals(octalString)){
           //通过八进制判断，在进行二进制转换，并判断
           String binaryString = Integer.toBinaryString(checkNum);
           String rollbackBinaryStr = new StringBuffer(binaryString).reverse().toString();
           if(rollbackBinaryStr.equals(binaryString)){
               return true;
           }
       }
       return false;
   }

然后是写一个测试类，调用我自己编写的入口方法。这里先再说明一个函数，是第一次调取入口方法时，需要传入一个 buildStart 的参数，所以再介绍一下自己实现的另一个方法，就是根据需要查找的回文数允许的最小值，去获得构建大于该值的回文数所需要的构建值。getBuildStart。代码如下

/**
     * 根据最小值，求出一个允许的最小构建回文数的值
     *
     * 思路: 若要求最后获得的回文数不能小于2001，则2001之后的第一个十进制表示的回文数应该是将2001作为字符串看待，从中截取一半，取前半段。
     *       若要求最后获得的回文数不能小于201，则201之后的第一个十进制表示的回文数应该是将201作为字符串看待，从中截取一半，不能完全平分，前半段保留多一个字符，取前半段。
     *       既可以通过字符串操作，也可以如下方法所实现，直接用数字的值进行操作。
     * @param min
     * @return
     */
    public int getBuildStart(Integer min) {
        if(min <= 100){
            return 1;
        }
        int length = min.toString().length();
        return min/(int)Math.pow(10,(length/2));
    }

这里解释下最后一句代码， return min/(int)Math.pow(10,(length/2));

一个简单的例子应该就能明白了，加入传入的 min 是 53128。那么很显然大于 53128 的第一个回文数是 53135。那么用来构建 53135 的数字应该是 531 通过奇数个模式去构建。所以根据中截取一半，不能完全平分，前半段保留多一个字符，取前半段的原则，进行该数字操作就可以实现。

不同思路的对比

这里我给出一下我通过 java 代码实现的作者思路。然后写一个测试类去分别使用自己的思路实现的代码和作者的思路实现的代码去运行。对比结果

以下是通过作者的思路实现的代码

/**
     * 作者给出的解法实现
     * @param min
     * @return
     */
    public int findPalindromicNumber(Integer min){
        //开始遍历的数
        int num = 0;
        //进行最开始的遍历数的初始化操作，使之为奇数
        if(min%2 == 0){
            num = min + 1;
        }else{
            num = min + 2;
        }
        //进入循环，直接对这个遍历的数进行3种进制下是否是回文数的判断。
        while (true){
            String numStr = Integer.valueOf(num).toString();
            String numStrRollback = new StringBuffer(numStr).reverse().toString();
            if(numStr.equals(numStrRollback)){
                //此处借用我自己所写的判断八进制和二进制是否是回文数的方法，不影响
                if(checkResult(num)){
                    break;
                }
            }
            num += 2;
        }
        return num;
    }

以下是测试类的代码

/**
 * 查找回文数测试
 *
 * @version V1.0
 * @Package: PACKAGE_NAME
 * @author: 丁奕
 * @date: 2019-06-03 20:55
 **/
public class PalindromicNumberTest {
    //时间格式Format
    private static SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

    public static void main(String[] arg){
        PalindromicNumber palindromicNumber = new PalindromicNumber();
        //一些单个的方法测试
//        System.out.println(palindromicNumber.findPalindromicNumber(10, 1));
//        System.out.println(palindromicNumber.buildPalindromic(5, true));
//        System.out.println(palindromicNumber.checkResult(10001));
//        System.out.println(palindromicNumber.getBuildStart(2001));
        //初始化参数
        int min = 585;
        //使用自己的方法
        System.out.println("***********使用自己的方法************");
        start(min, true);


        //使用作者的方法
        System.out.println("\n\n***********使用作者的方法************");
        start(min, false);
    }

    /**
     * 开始执行主测试方法，查找符合要求的回文数并输出。
     * @param min 不能小于某个数
     * @doMyFunc doMyFunc 使用自己的方法
     */
    private static void start(int min, boolean doMyFunc){
        //记录开始时间，并输出
        Date startTime = new Date();
        System.out.println("查找回文数开始 " + simpleDateFormat.format(startTime));

        PalindromicNumber palindromicNumber = new PalindromicNumber();

        //开始查找符合要求的大于参数min的回文数

        int result = 0;
        if(doMyFunc){
            //使用自己的方法
            int buildStart = palindromicNumber.getBuildStart(min);
            result = palindromicNumber.findPalindromicNumber(min, buildStart);
        }else{
            //使用作者的方法
            result = palindromicNumber.findPalindromicNumber(min);
        }

        System.out.println("得到结果为：" + result + "\n八进制:" + Integer.toOctalString(result) +
                "\n二进制:" + Integer.toBinaryString(result));

        //记录结束时间，并输出
        Date endTime = new Date();
        System.out.println("查找回文数结束 " + simpleDateFormat.format(endTime));
        //计算用时并输出
        Long costTime = endTime.getTime() - startTime.getTime();
        System.out.println("查找回文数用时 " + costTime + "毫秒");

    }
}

通过控制测试方法中的 min 参数，运行该测试类，我们来看下 min 取 10 和 min 取 585 的运行结果。

上图为 min 取 10 的运行结果

这一张是 min 取 585 的运行结果

可以看到在跳过原题的第一个有效答案之后，程序耗时出现了比较大的差异。而形成原因也很清楚。因为原作给出的方法是从 10 进制的数挨个先遍历判断，所以会判断很多十进制下本身就不是回文数的情况。

而我自己的方法，也还可以再做优化，因为我不用去考虑十进制下构造的回文数是偶数的情况，这一点是作者给出的想法里面的优化，而我在实现的时候却未曾想到这一点。

总结

从分析对比代码运行结果，就可以知道，所谓算法去优化性能，其实就是在编写代码的时候，去人为的先考虑好各种情况，然后在代码层面就去规避一些不必要的判断，就可以达到一定程度的代码执行效率的优化。

但是这又带来的另一个问题，就是通过人为的去规避的话，最后到底层的代码实现，可能会出现代码量更大，逻辑比简单粗暴的代码实现更难理顺的现象（因为这个代码是在去年写的，现在来写博客还要去看当初自己的实现思路，代码为何这样写），就一定程度的提高了维护难度。

所以！注释真的很重要。辛亏当初自己在这部分代码的时候，尽可能的去把注释写得详尽，每个方法用来做什么，为啥要这样操作都尽力去写下来。所以时隔一年再回头来看以前的代码，也能很快的理顺思路。

永远不要想着当下写的代码当下明白就行。虽然有个梗叫做，这段代码只有上帝和当时写代码的自己知道其中的含义。但是开开玩笑就好了，千万别去做这样的事啊。🙏