LeetCode 248. 中心对称数 III（DFS/BFS）

文章目录

1. 题目

中心对称数是指一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。

写一个函数来计算范围在 [low, high] 之间中心对称数的个数。

示例:输入: low = "50", high = "100"输出: 3 解释: 69，88 和 96 是三个在该范围内的中心对称数注意:由于范围可能很大，所以 low 和 high 都用字符串表示。

来源：力扣（LeetCode）

链接：https://leetcode-/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./

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

如果觉得《LeetCode 248. 中心对称数 III（DFS/BFS）》对你有帮助，请点赞、收藏，并留下你的观点哦！