Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork739
Description
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.
A 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: 20Output: 6Explanation: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: 100Output: 19Explanation: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 <= 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 同步地址:
类似题目：
参考资料：