博文中会简要介绍Leetcode P0248题目分析及解题思路。
“Strobogrammatic Number III”是一道相对较难的题目，也是p0246的衍生题，主要思路和p0247差不多，同样先建立数字和其旋转180度以后的数字之间的映射（如果旋转后能够构成一个数字的话），然后对称地构造需求的数即可，而数的长度区间则取决于low和high的长度。
在构造的时候需要使用回溯法，对于探索到的位置，填入一个合法数字，接着进入下一层探索，直到对称地填满所有位置，然后将构造出来的数同low和high比较，同时要满足大于等于low并且小于等于high的条件，若满足条件则计数器加1。然后返回上层填入下一个合法数字。这里的“合法”指的是，数字不仅要在HashTable中，同样也要满足“若数的总位数大于1时，首位不为0”这样的要求。
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.
Example:
Input: low = "50", high = "100" Output: 3 Explanation: 69, 88, and 96 are three strobogrammatic numbers.Note:
Because the range might be a large number, the low and high numbers are represented as string.
以下是Java的题解代码实现。
class Solution {
private Map<Character, Character> ch2CharMap = null;
private int count = 0;
public Solution() {
this.ch2CharMap = new HashMap<>();
this.ch2CharMap.put('6', '9');
this.ch2CharMap.put('9', '6');
this.ch2CharMap.put('1', '1');
this.ch2CharMap.put('0', '0');
this.ch2CharMap.put('8', '8');
}
public int strobogrammaticInRange(String low, String high) {
int left = low.length(), right = high.length();
for (int n=left; n<=right; ++n) {
this.dfs(0, n, new char[n], low, high);
}
return this.count;
}
private void dfs(int index, int N, char[] num, String low, String high) {
if (index >= (N+1)/2) {
String number = String.valueOf(num);
int L = number.length(), LL = low.length(), LH = high.length();
if ((L > LL || (L == LL && number.compareTo(low) >= 0))
&& (L < LH || (L == LH && number.compareTo(high) <= 0))) {
this.count += 1;
}
return;
}
for (char digit: this.ch2CharMap.keySet()) {
if (index == 0 && N > 1 && digit == '0')
continue;
else if (index == N/2 && (digit == '6' || digit =='9'))
continue;
else {
num[index] = digit;
num[N-1-index] = this.ch2CharMap.get(digit);
this.dfs(index+1, N, num, low, high);
}
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
Solution() {
ch2ch_['6'] = '9';
ch2ch_['9'] = '6';
ch2ch_['8'] = '8';
ch2ch_['1'] = '1';
ch2ch_['0'] = '0';
}
int strobogrammaticInRange(string low, string high) {
int left = low.length(), right = high.length();
for (int n=left; n<=right; ++n) {
string num(n, ' ');
_Dfs(0, n, num, low, high);
}
return count_;
}
private:
unordered_map<char, char> ch2ch_;
int count_ = 0;
void _Dfs(int index, int N, string &num, const string &low, const string &high) {
if (index >= (N+1)/2) {
int L = num.length(), LL = low.length(), LH = high.length();
if ((L > LL || (L == LL && num >= low))
&& (L < LH || (L == LH && num <= high))) {
count_ += 1;
}
return;
}
for (auto mapping: ch2ch_) {
char digit = mapping.first;
if (index == 0 && N > 1 && digit == '0')
continue;
else if (index == N/2 && (digit == '6' || digit == '9'))
continue;
else {
num[index] = digit;
num[N-1-index] = mapping.second;
_Dfs(index+1, N, num, low, high);
}
}
}
};