本题我们会将数字旋转 180° 来生成一个新的数字。
比如 0、1、6、8、9 旋转 180° 以后,我们得到的新数字分别为 0、1、9、8、6。
2、3、4、5、7 旋转 180° 后,是 无法 得到任何数字的。
易混淆数(Confusing Number)指的是一个数字在整体旋转 180° 以后,能够得到一个和原来 不同 的数,且新数字的每一位都应该是有效的。(请注意,旋转后得到的新数字可能大于原数字)
给出正整数 N,请你返回 1 到 N 之间易混淆数字的数量。
示例 1:
输入:20
输出:6
解释:
易混淆数为 [6,9,10,16,18,19]。
6 转换为 9
9 转换为 6
10 转换为 01 也就是 1
16 转换为 91
18 转换为 81
19 转换为 61
示例 2:
输入:100
输出:19
解释:
易混淆数为 [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100]。
提示:
1 <= N <= 10^9
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/confusing-number-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
vector<int> ch = {0,1,6,8,9};
int sum = 0;
public:
int confusingNumberII(int N) {
vector<int> s = {1,6,8,9};
for(int i = 0; i < s.size(); i++)
dfs(s[i], N);
return sum;
}
void dfs(long long n, int N)
{
if(n > N)
return;
if(isok(n))
sum++;
for(int i = 0; i < ch.size(); i++)
dfs(n*10+ch[i], N);
}
bool isok(long long n)
{
long long num = 0, bit, origin = n;
while(n)
{
bit = n%10;
n /= 10;
if(bit==6) bit = 9;
else if(bit== 9) bit = 6;
num = num * 10 + bit;
}
return num != origin;
}
};
class Solution {
public:
int confusingNumberII(int N) {
queue<long long> q;
vector<int> ch = {0,1,6,8,9};
q.push(1);
q.push(6);
q.push(8);
q.push(9);
int sum = 0;
while(!q.empty())
{
long long n = q.front();
q.pop();
if(isok(n) && n <= N)
sum++;
for(int i = 0; i < ch.size(); i++)
{
if(n*10+ch[i] <= N)
q.push(n*10+ch[i]);
}
}
return sum;
}
bool isok(long long n)
{
long long num = 0, bit, origin = n;
while(n)
{
bit = n%10;
n /= 10;
if(bit==6) bit = 9;
else if(bit== 9) bit = 6;
num = num * 10 + bit;
}
return num != origin;
}
};
468 ms 40.2 MB