本文共 2172 字，大约阅读时间需要 7 分钟。

1. 题目

本题我们会将数字旋转 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 转换为 99 转换为 610 转换为 01 也就是 116 转换为 9118 转换为 8119 转换为 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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

2.1 回溯

class Solution {
   	vector
   
     ch = {
   0,1,6,8,9};	int sum = 0;public:    int confusingNumberII(int N) {
           vector
    
      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;    }};
    
   

2.2 BFS

class Solution {
   public:    int confusingNumberII(int N) {
           queue
   
     q;        vector
    
      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

我的CSDN

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

转载地址：https://michael.blog.csdn.net/article/details/107966008 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！