中心对称数 II
1.题目描述
中心对称数是指一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。
找到所有长度为 n 的中心对称数。
示例 :
输入: n = 2
输出: ["11","69","88","96"]
2.解题思路
（1）如果n == 0，那么返回“” (空字符串)
（2）如果n == 1, 那么返回“0”， “1”， ”8“
（3）如果n == 2， 那么返回 “11” ， “69”， “88”， “96”（这里不包含”00“的情况）
（4）如果n == 3, 那么返回 （这里包含”00“的情况,例如"1001"）
“1” + s + “1”
“6” + s + “9”
“8” + s + “8”
“9" + s + “6”
最外围是对称数，那么s呢，就等于n==1的时候的取值，满足n-2.
add1 = {"0","1","8"}，add2 = {"00","11","69","88","96"}
i 是奇数，我们在 i-1 偶数的基础上每个数中间位置 add1
i 是偶数，我们在 i-2 偶数的基础上每个数中间位置 add2
class Solution {
public:
vector<string> findStrobogrammatic(int n) {
if(n <= 0) return {""};
if(n==1) return {"0","1","8"};
vector<vector<string>> dp(n+1);
dp[1] = {"0","1","8"};
dp[2] = {"11","69","88","96"};
vector<string> add1 = {"0","1","8"};
vector<string> add2 = {"00","11","69","88","96"};
string num;
for(int i = 3, j,k,h; i <= n; ++i)
{
if(i&1)//奇数,我们在i-1偶数的基础上每个数中间位置add1
{
for(j = 0; j < dp[i-1].size(); j++)
{
num = dp[i-1][j];
h = num.size()/2;
for(k = 0; k < 3; k++)
{
dp[i].push_back(num.substr(0,h)+add1[k]+num.substr(h));
}
}
}
else//i是偶数，我们在i-2偶数基础上每个数中间位置add2
{
for(j = 0; j < dp[i-2].size(); j++)
{
num = dp[i-2][j];
h = num.size()/2;
for(k = 0; k < 5; k++)
{
dp[i].push_back(num.substr(0,h)+add2[k]+num.substr(h));
}
}
}
}
return dp[n];
}
};