文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

中心對稱數(shù)是指一個數(shù)字在旋轉(zhuǎn)了 180 度之后看起來依舊相同的數(shù)字（或者上下顛倒地看）。

找到所有長度為 n 的中心對稱數(shù)。

示例 : 輸入: n = 2 輸出: ["11","69","88","96"]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/strobogrammatic-number-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

類似題目：
LeetCode 246. 中心對稱數(shù)（哈希）
LeetCode 248. 中心對稱數(shù) III（DFS/BFS）
LeetCode 1056. 易混淆數(shù)（哈希）

• add1 = {"0","1","8"}，add2 = {"00","11","69","88","96"}
• i 是奇數(shù)，我們在 i-1 偶數(shù)的基礎(chǔ)上每個數(shù)中間位置 add1
• i 是偶數(shù)，我們在 i-2 偶數(shù)的基礎(chǔ)上每個數(shù)中間位置 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)//奇數(shù),我們在i-1偶數(shù)的基礎(chǔ)上每個數(shù)中間位置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是偶數(shù)，我們在i-2偶數(shù)基礎(chǔ)上每個數(shù)中間位置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

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 247. 中心对称数 II（DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。