248 中心对称数 III

题目描述：

中心对称数是指一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。

写一个函数来计算范围在 [low, high] 之间中心对称数的个数。

示例:

输入: low = “50”, high = “100”

输出: 3

解释: 69，88 和 96 是三个在该范围内的中心对称数

注意:

由于范围可能很大，所以 low 和 high 都用字符串表示。

方法1：

主要思路：

（1）仔细观察中心对称数的规律，若中心对称数的位数是偶数，则可以由{0,0}{1,1}{6,9}{9,6}{8,8}从数字的两端对称组成，若中心对称数的位数是奇数，则中心数字只能是0，1,8三种数字；

（2）根据上述的分析，可以从空字符串，或“1”，“0”，“8”开始，在字符串的两端对应的添加数字对，来实现中心对称数的构成；

（3）在构造中心对称数的过程中，和low，high比较，保证生成的中心对称数是有效的；

class Solution {public://使用深度优先构造中心对称数void dfs(string& low,string& high,int& count,string cur){if(cur.size()>=low.size()&&cur.size()<=high.size()){//若当前的中心对称数在有效范围之内//三种当前的中心对称数是无效的情形//第一种是当前的中心对称数的长度符合要求，但大于最大值//第二种是当前的中心对称数的长度符合要求，但小于最小值//第三种是当前的中心对称数的长度大于1，但最高位是0的情形//若非这三种情形，则说明当前的中心对称数是有效的数，统计数量加1if(!(cur.size()==high.size()&&cur>high||cur.size()==low.size()&&cur<low||cur.size()>=2&&cur[0]=='0')){++count;}}//若长度越界，则返回if(cur.size()+2>high.size()){return;}//几种从当前情形生成新的中心对称数的方式dfs(low,high,count,"0"+cur+"0");dfs(low,high,count,"1"+cur+"1");dfs(low,high,count,"6"+cur+"9");dfs(low,high,count,"9"+cur+"6");dfs(low,high,count,"8"+cur+"8");}int strobogrammaticInRange(string low, string high) {int count=0;//统计中心对称数的个数//几种中心对称数的可能的初始情形dfs(low,high,count,"");dfs(low,high,count,"1");dfs(low,high,count,"0");dfs(low,high,count,"8");return count;}};

如果觉得《248 中心对称数 III》对你有帮助，请点赞、收藏，并留下你的观点哦！