Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[LeetCode] 1088. Confusing Number II #1088

Open
grandyang opened this issue May 30, 2019 · 0 comments
Open

[LeetCode] 1088. Confusing Number II #1088

grandyang opened this issue May 30, 2019 · 0 comments

Comments

@grandyang
Copy link
Owner

grandyang commented May 30, 2019

We can rotate digits by 180 degrees to form new digits. When 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6 respectively. When 2, 3, 4, 5 and 7 are rotated 180 degrees, they become invalid.

confusing number  is a number that when rotated 180 degrees becomes a different number with each digit valid.(Note that the rotated number can be greater than the original number.)

Given a positive integer N, return the number of confusing numbers between 1 and N inclusive.

Example 1:

Input: 20
Output: 6
Explanation:
The confusing numbers are [6,9,10,16,18,19].
6 converts to 9.
9 converts to 6.
10 converts to 01 which is just 1.
16 converts to 91.
18 converts to 81.
19 converts to 61.

Example 2:

Input: 100
Output: 19
Explanation:
The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].

Note:

  1. 1 <= N <= 10^9

这道题是之前那道 Confusing Number 的拓展,之前那道只是问一个给定的数字是否是迷惑数,而这道题是问给定数字N之内有多少个迷惑数字。这样的话难度就增加了不少,肯定不要想着直接遍历小于N的所有数字,对每个数字都调用之前的判断方法,毫无疑问的会超时。实际上大多数字都不是迷惑数字,所以一个一个的检验非常的不高效。这里需要使用一些技巧,由于组成迷惑数的只有五个数字,那么迷惑数的每个位上只能是这五个数字,于是就可以用递归来遍历所有的情况,假如N是个三位数,那么每一位有五种情况,总共也就 125 个数字要验证,远小于遍历所有的数字。但是由于迷惑数要求翻转后跟原数字不相同,所以还需要一个子函数判断一下是否是真正的迷惑数,这个需要计算出翻转后的数字,然后跟原数字比较一下,不相同才返回 true。当判断了是真正的迷惑数时,结果 res 自增1即可,参见代码如下:

解法一:

class Solution {
public:
    int confusingNumberII(int N) {
    	int res = 0;
        unordered_map<int, int> m{{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}};
        helper(N, 0, m, res);
        return res;
    }
    void helper(int N, long cur, unordered_map<int, int>& m, int& res) {
    	if (isConfusingNum(cur, m)) ++res;
    	for (auto a : m) {
    		if (cur * 10 + a.first <= N && cur * 10 + a.first != 0) {
    			helper(N, cur * 10 + a.first, m, res);
    		}
    	}
    }
    bool isConfusingNum(long num, unordered_map<int, int>& m) {
    	long oldNum = num, res = 0;
    	while (num > 0) {
    		if (m.count(num % 10)) return false;
    		res = res * 10 + m[num % 10];
    		num /= 10;
    	}
    	return res != oldNum;
    }
};

我们还可以使用迭代的写法,思路跟上面的递归写法基本一样,就是写法上有些不同,这里用到一个数组 vec,初始时将0放入,然后进行循环,循环的条件是 found 为 false,这个 found 变量是用来控制当前生成的数字是否在 [1, N] 范围中的。在循环中需要用一个临时数组t,此时生成的方法是,遍历 vec 数组中的每个数字,在其基础上新增一位数字,这个数字要遍历五个候选数字,组成新的数字后首先看是否越界,是的话将found 赋值为 true,然后直接 break 掉内层的 for 循环。因为这种 BFS 的遍历方式是一种层序遍历,之后组成的数字一定会越来越大,所以只要当前超过 N 了,后面的数字一定都会超过N。假如没超过N,若当前数字不为0,则将其加入t数组中,然后再对该数字调用判断迷惑数的子函数,若返回 true,则结果 res 自增1。内层 for 循环结束后,看下 found 值,若为 true,则 break 掉外层 for 循环。外层 for 循环结束后,要将临时数组t赋值给数组 vec,参见代码如下:

解法二:

class Solution {
public:
    int confusingNumberII(int N) {
    	int res = 0;
        map<int, int> m{{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}};
        vector<int> vec{0};
        bool found = false;
        while (!found) {
        	vector<int> t;
        	for (int num : vec) {
        		for (auto a : m) {
        			int cur = num * 10 + a.first;
        			if (cur > N) {
        				found = true; break;
        			}
        			if (cur != 0) t.push_back(cur);
        			if (isConfusingNum(cur, m)) ++res;
        		}
        		if (found) break;
        	}
        	vec = t;
        }
        return res;
    }
    bool isConfusingNum(int num, map<int, int>& m) {
    	int oldNum = num, res = 0;
    	while (num > 0) {
    		if (!m.count(num % 10)) return false;
    		res = res * 10 + m[num % 10];
    		num /= 10;
    	}
    	return res != oldNum;
    }
};

Github 同步地址:

#1088

类似题目:

Confusing Number

参考资料:

https://leetcode.com/problems/confusing-number-ii/

https://leetcode.com/problems/confusing-number-ii/discuss/313407/Backtracking-and-Iterative-Solution-in-Java

https://leetcode.com/problems/confusing-number-ii/discuss/446589/Easy-to-understand-Java-backtracking-solution-covers-edge-case

https://leetcode.com/problems/confusing-number-ii/discuss/392786/Confusing-number-Total-number-Strobogrammatic-number-(Java-1ms)

LeetCode All in One 题目讲解汇总(持续更新中...)

@grandyang grandyang changed the title [LeetCode] 1088. Missing Problem [LeetCode] 1088. Confusing Number II Mar 28, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant