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"]
这道题是之前那道 Strobogrammatic Number 的拓展，那道题让我们判断一个数是否是对称数，而这道题让找出长度为n的所有的对称数，这里肯定不能一个数一个数的来判断，那样太不高效了，而且 OJ 肯定也不会答应。题目中给了提示说可以用递归来做，而且提示了递归调用 n-2，而不是 n-1。先来列举一下n为 0,1,2,3,4 的情况：
n = 0: none
n = 1: 0, 1, 8
n = 2: 11, 69, 88, 96
n = 3: 101, 609, 808, 906, 111, 619, 818, 916, 181, 689, 888, 986
n = 4: 1001, 6009, 8008, 9006, 1111, 6119, 8118, 9116, 1691, 6699, 8698, 9696, 1881, 6889, 8888, 9886, 1961, 6969, 8968, 9966
注意观察 n=0 和 n=2，可以发现后者是在前者的基础上，每个数字的左右增加了 [1 1], [6 9], [8 8], [9 6]，看 n=1 和 n=3 更加明显，在0的左右增加 [1 1]，变成了 101, 在0的左右增加 [6 9]，变成了 609, 在0的左右增加 [8 8]，变成了 808, 在0的左右增加 [9 6]，变成了 906, 然后在分别在1和8的左右两边加那四组数，实际上是从 m=0 层开始，一层一层往上加的，需要注意的是当加到了n层的时候，左右两边不能加 [0 0]，因为0不能出现在两位数及多位数的开头，在中间递归的过程中，需要有在数字左右两边各加上0的那种情况，参见代码如下：
解法一：
class Solution {
public:
vector<string> findStrobogrammatic(int n) {
return find(n, n);
}
vector<string> find(int m, int n) {
if (m == 0) return {""};
if (m == 1) return {"0", "1", "8"};
vector<string> t = find(m - 2, n), res;
for (auto a : t) {
if (m != n) res.push_back("0" + a + "0");
res.push_back("1" + a + "1");
res.push_back("6" + a + "9");
res.push_back("8" + a + "8");
res.push_back("9" + a + "6");
}
return res;
}
};
这道题还有迭代的解法，感觉也相当的巧妙，需要从奇偶来考虑，奇数赋为 0,1,8，偶数赋为空，如果是奇数，就从 i=3 开始搭建，因为计算 i=3 需要 i=1，而已经初始化了 i=1 的情况，如果是偶数，从 i=2 开始搭建，也已经初始化了 i=0 的情况，所以可以用 for 循环来搭建到 i=n 的情况，思路和递归一样，写法不同而已，参见代码如下：
解法二：
class Solution {
public:
vector<string> findStrobogrammatic(int n) {
vector<string> one{"0", "1", "8"}, two{""}, res = two;
if (n % 2 == 1) res = one;
for (int i = (n % 2) + 2; i <= n; i += 2) {
vector<string> t;
for (auto a : res) {
if (i != n) t.push_back("0" + a + "0");
t.push_back("1" + a + "1");
t.push_back("6" + a + "9");
t.push_back("8" + a + "8");
t.push_back("9" + a + "6");
}
res = t;
}
return res;
}
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/247
类似题目：
参考资料：
https://leetcode.com/problems/strobogrammatic-number-ii/
https://leetcode.com/problems/strobogrammatic-number-ii/discuss/67280/AC-clean-Java-solution
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
