文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 DFS
    • 2.2 BFS

1. 題目

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

寫一個函數來計算范圍在 [low, high] 之間中心對稱數的個數。

示例: 輸入: low = "50", high = "100" 輸出: 3 解釋: 69，88 和 96 是三個在該范圍內的中心對稱數 注意: 由于范圍可能很大，所以 low 和 high 都用字符串表示。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/strobogrammatic-number-iii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

LeetCode 246. 中心對稱數（哈希）
LeetCode 247. 中心對稱數 II（DP）
LeetCode 1056. 易混淆數（哈希）

• 兩側加對稱的數，初始從 空字符，0，1，8 開始

2.1 DFS

class Solution {vector<string> l = {"0","1","6","8","9"};vector<string> r = {"0","1","9","8","6"};int ans = 0; public:int strobogrammaticInRange(string low, string high) {if(low.size() > high.size() || (low.size()==high.size() && low > high))return 0;vector<string> number = {"", "0","1","8"};for(int i = 0; i < number.size(); ++i){dfs(number[i], low, high);}return ans;}void dfs(string num, string& low, string& high){if(num.size() > high.size())return;if(num.size()>=low.size() && num.size() <= high.size()){if(num.size()==low.size() && num < low) return;if(num.size()==high.size() && num > high)return;if(num.size() == 1 || num[0]!='0')ans++;}for(int i = 0; i < 5; ++i){dfs(l[i]+num+r[i], low, high);}} };

544 ms 44.8 MB

2.2 BFS

class Solution {vector<string> l = {"0","1","6","8","9"};vector<string> r = {"0","1","9","8","6"};int ans = 0; public:int strobogrammaticInRange(string low, string high) {if(low.size() > high.size() || (low.size()==high.size() && low > high))return 0;queue<string> q;q.push("");q.push("0");q.push("1");q.push("8");string num;while(!q.empty()){num = q.front();q.pop();if(num.size() > high.size())continue;if(num.size()>=low.size() && num.size() <= high.size()){if(num.size()==low.size() && num < low) continue;if(num.size()==high.size() && num > high)continue;if(num.size() == 1 || num[0]!='0')ans++;}for(int i = 0; i < 5; ++i)q.push(l[i]+num+r[i]);}return ans;} };

752 ms 92.6 MB

---

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

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 248. 中心对称数 III（DFS/BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。