博文中会简要介绍Leetcode P0247题目分析及解题思路。
“Strobogrammatic Number II”是一道中等难度的题目，是p0246的衍生题，主要思路和p0246差不多，同样先建立数字和其旋转180度以后的数字之间的映射（如果旋转后能够构成一个数字的话），然后对称地构造需求的数即可。这里需要使用回溯法，对于探索到的位置，填入一个合法数字，接着进入下一层探索，直到对称地填满所有位置后，存储新生成的这个数，然后返回上层填入下一个合法数字。这里的“合法”指的是，数字不仅要在HashTable中，同样也要满足“若数的总位数大于1时，首位不为0”这样的要求。
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Find all strobogrammatic numbers that are of length = n.
Example:
Input: n = 2 Output: ["11","69","88","96"]
以下是Java的题解代码实现。
class Solution {
private Map<Character, Character> ch2CharMap = null;
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 List<String> findStrobogrammatic(int n) {
this.dfs(0, n, new char[n]);
return this.numbers;
}
private List<String> numbers = new ArrayList<>();
private void dfs(int index, int N, char[] num) {
if (index >= (N+1)/2) {
numbers.add(String.valueOf(num));
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);
}
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
Solution() {
ch2ch_['6'] = '9';
ch2ch_['9'] = '6';
ch2ch_['8'] = '8';
ch2ch_['1'] = '1';
ch2ch_['0'] = '0';
}
vector<string> findStrobogrammatic(int n) {
string num(n, ' ');
this->_Dfs(0, n, num);
return numbers_;
}
private:
unordered_map<char, char> ch2ch_;
vector<string> numbers_;
void _Dfs(int index, int N, string &num) {
if (index >= (N+1)/2) {
numbers_.push_back(num);
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;
this->_Dfs(index+1, N, num);
}
}
}
};