[Swift]LeetCode788.旋转数字|RotatedDigits

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10545646.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.

Now given a positive number N, how many numbers X from 1 to N are good?

Example:
Input: 10
Output: 4
Explanation: 
There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Note:

N will be in range [1, 10000].

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字，则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

示例:
输入: 10
输出: 4
解释: 
在[1, 10]中有四个好数： 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。

注意:

N 的取值范围是 [1, 10000]。

Runtime: 8 ms

Memory Usage: 18.8 MB

 1 class Solution {
 2     func rotatedDigits(_ N: Int) -> Int {
 3         var res:Int = 0
 4         var dp:[Int] = [Int](repeating:0,count:N + 1)
 5         for i in 0...N
 6         {
 7             if i < 10
 8             {
 9                 if i == 0 || i == 1 || i == 8
10                 {
11                     dp[i] = 1                
12                 }
13                 else if i == 2 || i == 5 || i == 6 || i == 9
14                 {
15                     dp[i] = 2
16                     res += 1
17                 }
18             }
19             else
20             {
21                 var a:Int = dp[i / 10]
22                 var b:Int = dp[i % 10]
23                 if a == 1 && b == 1
24                 {
25                     dp[i] = 1
26                 }
27                 else if a >= 1 && b >= 1
28                 {
29                     dp[i] = 2
30                     res += 1
31                 }                
32             }
33         }
34         return res
35     }
36 }

12ms

 1 class Solution {
 2 
 3     func rotatedDigits(_ N: Int) -> Int {
 4         var count = 0
 5         for n in 1...N {
 6             if good(n, false) { count += 1 }
 7         }
 8         return count
 9     }
10     
11     func good(_ n : Int, _ flag: Bool) -> Bool {
12         if n == 0 { return flag }
13         let d = n%10
14         if d == 3 || d == 4 || d == 7 { return false }
15         if d == 0 || d == 1 || d == 8 { return good(n/10, flag) }
16         return good(n/10, true)   
17     }
18 }

16ms

 1 class Solution {
 2     func rotatedDigits(_ N: Int) -> Int {
 3         var count = 0
 4         
 5         for numRaw in 0...N {
 6             var containDifferent = false
 7             var containInvalid = false
 8             
 9             var num = numRaw
10             while num > 0 {
11                 let dig = num % 10
12                 num = num / 10
13 
14                 switch (dig) {
15                     case 0,1,8:
16                         break
17                     case 2,5,6,9:
18                         containDifferent = true
19                     case 3,4,7:
20                         containInvalid = true
21                     default:
22                         break;
23                 }
24                 
25                 if containInvalid {
26                     break
27                 }
28             }
29 
30             if containDifferent && !containInvalid {
31                 count += 1
32             }
33         }
34 
35         return count
36     }
37 }

24ms

 1 class Solution {
 2   func rotatedDigits(_ N: Int) -> Int {
 3     var dp = Array(repeating: 0, count: N + 1)
 4     var goodNumCount = 0
 5     
 6     for num in 0...N {
 7       if num <= 9 {
 8         if num == 2 || num == 5 || num == 6 || num == 9 {
 9           dp[num] = 2
10           goodNumCount += 1
11         } else if num == 0 || num == 1 || num == 8 {
12           dp[num] = 1
13         }
14       } else {
15         let prevDigits = dp[num / 10]
16         let lastDigit = dp[num % 10]
17         
18         if prevDigits == 1 && lastDigit == 1 {
19           dp[num] = 1
20         } else if prevDigits >= 1 && lastDigit >= 1 {
21           dp[num] = 2
22           goodNumCount += 1
23         }
24       }
25     }
26     
27     return goodNumCount
28   }
29 }

28ms

 1 class Solution {
 2     var rotations = [0, 1, 5, -1, -1, 2, 9, -1, 8, 6]
 3     
 4     func rotatedDigits(_ N: Int) -> Int {
 5         guard N != 0 else { return 0 }
 6         
 7         var count = 0
 8         for i in 1...N {
 9             count += isGood(i) ? 1 : 0
10         }
11         
12         return count
13     }
14     
15     func isGood(_ n: Int) -> Bool {
16         var newNr = 0
17         var multiply = 1
18         var workingN = n
19         var d = 0
20         
21         while workingN != 0 {
22             d = workingN % 10
23             if rotations[d] == -1 { return false }
24             
25             newNr = rotations[d] * multiply + newNr
26             workingN /= 10
27             multiply *= 10
28         }
29         
30         return n != newNr
31     }
32 }

40ms

 1 class Solution {
 2     private let dict: [Int: Int] = [0: 0, 1: 1, 8: 8, 2: 5, 5: 2, 9: 6, 6: 9]
 3     func rotatedDigits(_ N: Int) -> Int {
 4         guard N > 1 else { return 0 }
 5         var curNum = N
 6         var changed: Bool = false
 7         while curNum > 0 {
 8             let digit = curNum % 10
 9             let changedDigit = dict[digit] ?? -1
10             if changedDigit == -1 {
11                 return rotatedDigits(N - 1)
12             } else if digit != changedDigit {
13                 changed = true
14             }
15             curNum /= 10
16         }
17         return (changed ? 1 : 0) + rotatedDigits(N - 1)
18     }
19 }

56ms

 1 class Solution {
 2     func rotatedDigits(_ N: Int) -> Int {
 3         var c : Set<Int> = [2,5,6,9]
 4         var k : Set<Int> = [0,1,8]
 5         var ans = 0
 6         for i in 1 ... N {
 7             var j = i
 8             var cn = 0, kn = 0
 9             var valid = true
10             while j > 0 {
11                 let d = j%10
12                 if c.contains(d) {
13                     cn += 1
14                 } else if k.contains(d) {
15                     kn += 1
16                 } else {
17                     valid = false
18                     break
19                 }
20                 j = j/10
21             }
22             if valid && cn > 0 {
23                 ans += 1
24             }
25         }
26         return ans
27     }
28 }

68ms

 1 class Solution {
 2     func rotatedDigits(_ N: Int) -> Int {
 3         if N == 0 {
 4             return 0
 5         }
 6         var count = 0
 7         for i in 1...N {
 8             if checkIfCanBeRotated(String(i)) {
 9                 count += 1
10             }
11         }
12         return count
13     }
14     
15     func checkIfCanBeRotated(_ str: String) -> Bool {
16         var res = false
17         for s in str {
18             if s == "2" || s == "5" || s == "6" || s == "9" {
19                 res = true
20             } else if s == "3" || s == "4" || s == "7" {
21                 return false
22             }
23         }
24         return res 
25     }
26 }

196ms

 1 class Solution {
 2     func rotatedDigits(_ N: Int) -> Int {
 3         let invalid: Set<Character> = Set(["3", "4", "7"])
 4         let diff: Set<Character> = Set(["2", "5", "6", "9"])
 5         var res = 0
 6 
 7         for i in 1...N {
 8             let lookup = Set(Array(String(i)))
 9             //确定两个集合是否没有共同的值
10             if lookup.isDisjoint(with: invalid) && !lookup.isDisjoint(with: diff) {
11                 res += 1
12             }
13         }
14 
15         return res
16     }
17 }