[Swift]LeetCode1088. 易混淆数 II | Confusing Number II
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/11014408.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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: 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 <= N <= 10^9
本题我们会将数字旋转 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
3976 ms
1 class Solution {
2 var n:Int = 0
3 var cands:[Int] = [0, 1, 6, 8, 9]
4 var ans:Int = 0
5 func confusingNumberII(_ N: Int) -> Int {
6 self.n = N
7 go(1, 0)
8 if n == 1000000000
9 {
10 ans += 1
11 }
12 return ans
13 }
14
15 func conv(_ d:Int) -> Int
16 {
17 if d == 6 {return 9}
18 else if d == 9 {return 6}
19 return d
20 }
21
22 func rot(_ k:Int) -> Int
23 {
24 var k = k
25 var res:Int = 0
26 while(k > 0)
27 {
28 res = 10*res + conv(k%10)
29 k /= 10
30 }
31 return res
32 }
33
34 func go(_ mul:Int,_ k:Int)
35 {
36 if k > n {return}
37 if mul == 1_000_000_000
38 {
39 if rot(k) != k {ans += 1}
40 }
41 else
42 {
43 for c in cands
44 {
45 go(10*mul, k + mul*c)
46 }
47 }
48 }
49 }