LeetCode 248. 中心对称数 III（DFS/BFS）
LeetCode 248. 中心对称数 III（DFS/BFS）
Michael阿明
发布于 2021-02-19 10:47:35
发布于 2021-02-19 10:47:35
文章被收录于专栏：Michael阿明学习之路
文章目录
1. 题目
中心对称数是指一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。
写一个函数来计算范围在 low, high 之间中心对称数的个数。
示例:
输入: low = "50", high = "100"
输出: 3
解释: 69，88 和 96 是三个在该范围内的中心对称数
注意:
由于范围可能很大，所以 low 和 high 都用字符串表示。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/strobogrammatic-number-iii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 两侧加对称的数，初始从 空字符，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
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/08/03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
