?LeetCode刷題實戰(zhàn)248：中心對稱數(shù)III
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
示例
示例:
輸入: low = “50”, high = “100”
輸出: 3
解釋: 69，88 和 96 是三個在該范圍內的中心對稱數(shù)
解題
class Solution {
public:
//使用深度優(yōu)先構造中心對稱數(shù)
void dfs(string& low,string& high,int& count,string cur){
if(cur.size()>=low.size()&&cur.size()<=high.size()){//若當前的中心對稱數(shù)在有效范圍之內
//三種當前的中心對稱數(shù)是無效的情形
//第一種是當前的中心對稱數(shù)的長度符合要求，但大于最大值
//第二種是當前的中心對稱數(shù)的長度符合要求，但小于最小值
//第三種是當前的中心對稱數(shù)的長度大于1，但最高位是0的情形
//若非這三種情形，則說明當前的中心對稱數(shù)是有效的數(shù)，統(tǒng)計數(shù)量加1
if(!(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;
}
//幾種從當前情形生成新的中心對稱數(shù)的方式
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;//統(tǒng)計中心對稱數(shù)的個數(shù)
//幾種中心對稱數(shù)的可能的初始情形
dfs(low,high,count,"");
dfs(low,high,count,"1");
dfs(low,high,count,"0");
dfs(low,high,count,"8");
return count;
}
};