中心对称数是指一个数字在旋转了 180 度之后看起来依旧相同的数字(或者上下颠倒地看)。
找到所有长度为 n 的中心对称数。
示例 :
输入: n = 2
输出: ["11","69","88","96"]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/strobogrammatic-number-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
add1 = {"0","1","8"}
,add2 = {"00","11","69","88","96"}
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];
}
};
116 ms 24.7 MB