求单调区间与最值（有趣的求区间回文数）

今天通过一道有趣的题目来展示做题时思考的过程是怎样一步步演变的，只讲思路不谈编程和代码，您也可以理解成它就是一个解题过程的笔记，其核心思想也是适用于大多事情的并不专指编程。

为什么用这题？难度适中但想做好需要一定的动脑思考的能力和逻辑推理。

---

开始正文

看题：

给你两个正整数A和B(1<=A<=B<=100000)求A~B(包含A和B)的所有回文数个数。

什么是回文数？请看：

将最高位与最低位、次高位与次低位……进行比较，若彼此相等则为回文数。例如：121,222,456654,45654，这个应该都能懂吧。

一句话：‘‘回文数’’就是不管从左向右还是从右向左读这个数的大小始终保持不变。

答题要求：

A和B之间（包含A和B）的所有回文数个数，没有输出0。

示例：

1.给于两个数A、B分别是2、8 得出的结果是：7

2.给于两个数A、B分别是12、21 得出的结果是：0

解读示例1：

结果为什么是7？首先起始数是“2”，不管从左到右还是从右到左读他还是表示其本身2不变，所以满足“回文数”的定义，同理8也一样所以这两个数本身就是回文数那自然的从2到8的所有数也都是“个位数‘’自然也满足回文数的定义。

计算公式为：8-2 1=7

可以得到简单的计算公式：8-2 1=7

解读示例2：

首先起始数12本身很明显不满足回文数的定义所以不是回文数，下一位13以及直到21也没有一个满足的所以它们之间有0个回文数。

没有回文数

通过这两个示例大家对回文数有了进一步的了解也知道了题目要的计算结果是怎么来的了。

新发现：

个位数全是回文数，并且如果两个回文数都是个位数可以直接相减后 1得到其全部区间的个数。之所以可以是因为正好和自然数是一样从小到大依次排列的所以也可以像自然数一样运算。

计算过程为：C=B-A 1，示例1已验证。

到这自然还会想到是不是其它回文数也能这样用上述的公式进行计算呢？简单的验证下就可以很明显地知道并不是所有情况都可以这样简单地得到结果。

如：8-15之间共有8、9、10、11、12、13、14、15其中是回文数的只有8、9、11这3个那我们明显不能用15-8 1或11-8 1来计算出正确结果。

初入江湖

不能用的话怎么办？有没有其他公式？我们可以先想想看。

大部分没有类似经历的人短暂的思考后可能没有想出来这也很正常，没有经过大量的练习很难能直接想到一个比较理想的方式优雅地计算出来。

既然不能一次想出一个好的办法那我们能不能来点简单粗暴的？

简单粗暴的是什么样？

回想一下刚才举例求8-15之间的回文数个数的时候的情景，虽然不能通过前面的公式得到答案，但你知道不知道答案是3？

怎么知道的？

这应该是人类长期的学习和生活经验的结果，也是以前人工智能进步比较慢的原因，我们可以根据一些信息进行高效的自我学习，然后基于经验快速的推理出结果。

这是很自然地下意识的一个过程快速有效，像呼吸般顺畅自然。

分析一波潜知识下的思考过程。

当我们看到起始数8的时候自然会去看他是不是一个回文数？

如果是我们会在心里默默地给我们设想的一个虚拟计数器 1

然后查看下一个数字9（这9是怎么来的？我们知道自然数8后面的数是9，两个相邻的自然数之间差1）到9的时候我们又会重复上述过程先看是不是回文数？是就给虚拟计数器再 1不是就不加。

此过程往复一直到最后一个15为止，最后大脑中的虚拟计数器已经变成了3

核心逻辑：判断一个数是不是回文数？是就给虚拟计数器 1不是就不

逻辑过程：（非标准流程图只为示意）

上面的逻辑肯定是可以求出A、B之间包含多少回文数的，有了思路编写代码只是技巧和时间问题了略过。

那上面的逻辑过程实际上就是最简单粗暴的一种方式来得到结果。

优点：思路简单很容易想到也符合正常思维方式“简单而有效”。

缺点：实际上需要不停判断A和B之间的N个数是不是回文数，当区间较小的时候还好，如果区间特别大的时候问题就更明显，整个过程需要计算太多次了，不信可以自己计算下1-100000间有多少个回文数

相信没有人真的会去计算吧[笑哭]

我们在使用没那么优雅的方式解决了问题后还要再思考下难道没有更好的办法了吗？

如果实际中就不允许计算这么多次怎么办？

---

拿下首杀

思考下造成我们计算这么多次的原因是什么？

因为我们不知道A和B之间具体有那些回文数，所以只能把从A到B所有的数都试一次。

这其实就是暴力碰撞。

就像你要在一个城市统计有多少和你重名的人但你又不知道他们都住在哪里，为了能找到全部的人，你选择了一个最容易想到的方法，就是从这个城市的第一户人家开始问起，一家又一家不停的问下去直到问完全部的为止，虽然有效但不够高效，那怎样才能高效起来？当然是减少去寻找无效的目标啦，也就是我们这里的无效数字判断过程啦。

具体怎么做？

之所以要一个个的判断是因为我们不知道区间有那些数是回文数所以只能假设全部都可能是潜在的目标。

那我们能不能换个思路？

尝试计算出任意回文数的下一个回文数是多少呢？

有人可能会问为什么这样做？

假设从回文数11开始：

如果按之前的办法找到下一个回文数22我们要经过11，12，13，14.....19，20，21，22这么多数的检查判断而有效的其实只有11和22两个。

如果我们直接可以根据11算出下一个回文数是22那是不是就简单了？

稍花点时间仔细观察和思考后发现显然是可以的。

可以类似这样在纸上画画方便观察

最终是可以找到方法计算出下一位回文数的，为了节省篇幅且这部分也不作为重点所以直接略过就不展示推理过程，此处省略三千字[笑哭]

假设现在已掌握了根据一个回文数计算出下一位回文数的方法了，是不是可以这样去思考？

假设己知从A开始的第一位回文数是什么（实际上我们还需要根据A计算出最接近的一个有效回文数，同样不是重点先选择勿略了强行开启外挂获得此技能[666]）那么根据当前回文数又能算出下一位的回文数，这样我们是不是就可以无限算下去直到最后的B为止并且在大小超过B之前每算一位就让计数 1之样最后是不是就得到了总个数？

最后一次推算出的88大于85属于无效

通过上面的示例可以很明显的看到我们从A到B的过程变短了，每次计算的都是一位有效的回文数自然也省去了判断是否是回文的步骤，直接跳过了所有无效目标从而减少了整个过程，当区间越大的时候效果越明显怎么样是不是比之前的方法稍优雅了那么一点了？

核心逻辑：根据一个回文数算出下一个回文数，不大于B时计数器 1，大于停止。

逻辑过程如下：

可以和上次的对比一下逻辑变得更加的简单明了，全部的核心算法都在如何算出下一个回文数这部分，并且还过滤掉了大量的无效计算和判断，同理有了逻辑后写出代码自然也不是太难。

恭喜到这我们已经实现了第一次的逻辑优化过程，我们可以有那么点点成就感了，是不是只要稍加观察和思考也是可以想到更好的方案的，其实思考就是反复观察一些现像，大胆假设推理发现其中可以利用的规律，是不是没有那么难？

大家现在可以稍加休息一会，放松一下大脑，休息时可以在潜意识中问问自己是不是还有更好的办法？

---

推上高地

是否有了新的想法呢？

带着您的想法和疑问我们一起接着思考下去看看是否有共同的发现和奇思妙想。

当没有直接灵光昨現获得新的灵感的话，那这时候我们不妨去思考一下刚才的改进版有哪些优缺点？

优点：确实节省了不少的计算次数，因为过滤了大量无效数，让我们每次到下一位就直接是最理想的那个回文数，自然也不用再去判断是不是回文数了。

缺点：要不停地去计算出每一位有效的回文数，其实这本身也是个不小的计算量，并且我们寻找生成下位回文数的办法这个过程也有点点麻烦，需要我们发现变化规律最终找到一个通用的解，这过程以至于可能又要多掉两根头发[衰]

综合优缺点我们好像看到了一点前进的方向，我们现在需要的是最好又能知道区间有那些回文数又不想去通过太多的计算来实时算出来并且最好还能让逻辑再简单点（要啥自行车）[吐血]

元芳你怎么看？

回大人，应该如此之般......之般一如此。

好了先说下我的思路，大家看看是否和你想法有些相似？

先说个基本都听过或者用过的东西，‘‘字典”不管你是新华字典还是成语字典等等其作用和原理都差不多，就是通过一个关键信息来查询到所对应的另一个相关信息，道理我们都懂，但是和这题有啥关系呢？

是否可以大胆地设想下假如我们捡到了这样的一本字典。

字典的每一页都有一个回文数，并且每页都是按照回文数从小到大的顺序排下去的就像这样‍[机智]

图中每个方框表示为字典中的一页且是从小到大连续排列的，圆中的数字表示是当前页的一个回文数右下角的数表示这个回文数所在的页，也就是该回文数对应的页码。

当有了这样的一本字典那事情就要容易很多了，你问怎么个容易法？

那验证下如果现在有两个数A、B。

A=8，B=44，为了方便先假定A和B就都是回文数。

我们可以去拿着A去翻下字典看下它的页码是多少，对照字典可以知道回文数8对应的页码正好也是8，回文数44对应的页码是13。

有了上述信息我们就可以去运用个位数回文数的计算公式了。

什么？你问我为什么之前不能现在却可以了？我们现在计算的并不是回文数本身而是它对应的页码哦[机智]

之前的公式是这样的：C=B-A 1

代入数字验证：44-8 1=37 肉眼可见的结果明显不对

变化一下后是这样的：C=B页码-A页码 1

验证：13-8 1=6 结果对不对？数下呗8、9、11、22、33、44正好六个

好像可行啊去偷乐一下吧[舔屏]

可能还有人不放心，很好，那可尝试向我这样自己去画画多验证一下。

怎样？验证完了是不是发现逻辑确实没毛病？

这里的核心原理就是人为的去给本来无法直接建立关系的二者试着去建立他们的关联性从而创造出我们需要的某种规律来适应我们的逻辑。

暂时别高兴太早先冷静下来[奸笑]

刚才所有的前提都是在假设已经有了这样一本字典，并确实可以根据一个回文数查出它对应的页码，但我们真的有吗？好像并没有吧？最少目前编程环境中肯定没有的那问题来了是不是要白高兴了？

既然没有现成的那能不能自己造一个？刚才不就自己动手画了一些吗？

那准备自己打造字典了就要考虑到这个字典我们应该怎么去描述它？它应该有什么样的功能（类似于数据结构的概念先不过多展开）更多精力放在逻辑上。

归纳下创建字典需要解决的问题：

①如何描述这个字典？

先简单认为它是具有一个键值对关系的结构、这个键永远指向他的值，键用来保存回文数，值用来保存这个回文数对应的页码，就像下图这样。

键(key)：可以理解为一个关键字。

值(value)：可以理解为通过这个关键字所能精准找到的内容。

②它的功能是什么？

根据一个键（回文数）精准快速地查出这个键所对应的值（回文数的页码）

有了来描述和保存内容的结构后我们还需要考虑一个关键问题，这些回文数还好说之前我们已经可以根据一个回文数生成下一个回文数了，但每个回文数的页码好像并不知道啊？

再想想之前观察到的一些关键信息（个位数的回文数正好与其自然数排列位置对应的）

我们可以利用这点来做为基准点然后往后连续生成回文数与页码，当回文数如果是连续排序的那他的页码也应该是连续的，只要保证生成的回文数是正确且连续的就行，页码不同于回文数的地方在于只需做简单的自然增长就可以。（每次 1）

准备好这些后实际在理论上已经可以生成一个任意长度的回文字典了[泣不成声]

有了字典就可以按之前的逻辑算出A到B有多少个回文数啦！

不过我们在查A、B对应的页码前还需要再算出A与B各自最接近的有效回文数，因为实际情况中A与B并不一定就正好是回文数所示要确保最终是用回文数去查字典的，此过程中也有点小细节需要注意比如A=12，那他的有效回文数应该是22而不是11，A=21则回文数应是22而不是33或11等一些小的细节要注意。

核心逻辑：生成一个字典，根据一个回文数通过字典查出它对应的页码。

整体逻辑流程：

怎么样逻辑上是不是更简单啦？而且计算量也少了很多，主要部分的计算量也只是在生成字典这一部分，是不是感觉哇原来可以这么简单呀？

到这我们好像终于可以松口气啦！此时低头看了眼地面上的头发虽有些淡淡的忧伤，不过也总算是得到不错的结果，是不是有点小安慰小激动？

此时的你是不是已经在等我的最后总结了？

好吧我们一起来回顾下经过的几次逻辑演变过程。

①先是经过短暂的观察和思考后我们比较容易地想到了一种简单粗暴的方式，不停的一个个去判断计算直到检查完所有可能的目标。

②经过对上述方法的进一步分析其优缺点后我们得到了一个初始的改进方案，尽量减少了不必要的计算过程从而让逻辑和效率都更′‘合理些’’。

③分析前两种本质上还都是从一个目标不停移动到另一个目标的原理只是移动的过程稍高效了一些，那有没有不需要这种方式而能像个位数回文数一样简单的直接得到结果呢？因为很多情况下无法直接做到，我们又转换了思路使用了常见的字典的工作原理来帮助我们实现了这样的目的。

怎么样一路走来是不是感觉没有那么轻松，但也能在经过努力后跟上了节奏？

很多时候只要愿意去观察分析事物的本质与运行规律，都是可以用来大胆假设和推理出一些信息的，这些信息并不一定每条都有用，可能有的成功有的失败了，但在这个过程中也许某些信息产生出新的灵感，这样不断的尝试后肯定是可以找到一条正确的道路的，练习的趆多思考的趆多那么你的思考速度和感觉就会慢慢变得更加高效敏锐！

来到之恭喜聪明的你猜对了事情还没结束，怎么可能就这样收场呢

不过是真的最后忆次了

点掉水晶

我们把思绪回到最后的“查字典”方案中去，再看忆眼它真的是很完美了吗？

优点：现在可以直接根据字典查出回文数对应的页码了也没有烦杂的移动计数的过程了。

缺点：所有的前提都是要提前准备好一个最少包含了A、B两个回文数区间所有回文数的字典这本身也比较麻烦，且也会出现如果区间很大的话要生成一个比较大的字典，从效率的角度来说明显不太友好不高效。

根据优缺点思考一下接下来该怎么办？

现在是不是很自然向能否不用生成字典而直接知道每个回文数的“页码”这个方向思考了？

看你现在不是也慢慢学会了如何寻找问题的关键来针对性思考了？

那再来最后一次，这次会稍多点细节看是如何最终优化的。

如何才能实现不要字典也能知道每个回文数的页码呢？关键还在字典上。

我们把之前的字典进行平铺式展开后再观察它是否有某种规律

为了方便观察直接跳过了大部分个位数只保留9

为了方便观察直接跳过了大部分个位数只保留一个9做为起始参考，因个位数的特殊性先可以直接先忽略掉方便观察。

请认真观察下字典中的键（K）和值（ⅴ）是否有着某种规律，相信大家隐约感觉到了一些。

如果还没有头绪的话可以进一步缩小观察范围，可以自己在纸上画下。

如果还不能找到一个比较通用的方式的话那可以换个角度看问题，是不是可以先观察更明显的双位数的规律，然后再往后依次解决后面的，如下图。

双位数回文数

相信到这大家或多或少是可以发现他们变化的规律的而且不只是一种。

废话已然太多了[奸笑]所以我就不带大家一步步推算了。

我说其中一个相对简单的方法但不一定是最优的，主要是给大家提供一个思路。

经过观察后我发现双位数的页码就是本身中的一位再加9

如：11就是取任意一位得到1然后1 9=10，66一〉6 9=15，99一〉9 9=18

是不是没毛病？至于为什么 9道理不难理解，不明白的可以把这先想通了会更有帮助。

双位计算过程：任意一位 9=页码

那三位的回文数是否通用呢？我们可以去验证下

如：101一〉1 9=10 明显出现了问题好像不能直接通用那就再接着分析下三位数呗

三位回文数

同样可以观察到不止一种方法，那我还是保持之前的整个逻辑去思考既然你回文数增加了一位那我在取的时候能不能也多取一位？试呗！

如：101一〉前两位（倒着也一样）一〉10 9=19 好像可以？不放心就再来次。

如：989一〉98 9=107确实没问题

那就赶紧再试下4位的回文数是不是可以用？

如：1001一〉10 9不对啊，难道取三位一〉100 9=109？没毛病，再试1111一〉111 9=120 ？？？？

*******什么情况？不管用了啊？

这时候又需要再次思考下了其实和之前的道理差不多，不废话。

依然取前两位 9不过还要再多加个90

如：1001一〉10 9 90=109，1111一〉11 9 90=110，1551一〉15 9 90=114没问题了。

那5位呢？接着试

如：10001一〉有了之前的经验直接取三位一〉110 9 90=199没错，10101一〉101 9 90=200没毛病。（可以自己验证）

由于我们题目中最大数是100000六位数且不是回文数可以直接到此为止了，下面也是类似的情况。

整理下目前观察到的所有规律：

①个位数本身就是页码

②两位数，三位数分别取首位和前两位 9得到页码

③四、五位数分别取其前2、3位 9 90

好了所有的公式都出来了，肯定可以根据一个回文数算出其对应的页码了。

现在主要解题逻辑变成下面这样：

①首先求到A与B最近的有效回文数（注意其特殊情况）

②通过判断回文数是几位数去使用公式算出对应的页码

③C=B-A 1

核心逻辑：根据一个回文数通过字典查出它对应的页码。

整体逻辑流程：

最终逻辑过程

到之从逻辑方面来说已经差不多走到了当前题解的极致，直击问题根本没有什么多余的东西，下面就是根据思路写出代码的问题了。

最后忆点点

一路坚持下来的勇士们是不是有些感触呢？整个过程中并没有使用过多的专业或高深的知识吧，都是一些基本的东西，却能让我们调动更多的精力去以一个相对原始的方式去思考激发更多的潜能。

建议特别是初学着遇到类似这种有点意思的题目时不要急着去想套公式而应该先自己尝试用自己的思路去解决看看，不停的去挑战自己的极限相信经常这样的练习肯定会有不一样的收获。

篇幅问题一些细节没有去讲太多或有遗漏的地方在这表示抱歉，有疑问的也可以根据结论去反推我为什么要这样做？想讲得太多有时会顾此失彼有机会再聊吧。

,