★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★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: 10Output: 4Explanation: 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 == 810 {11 dp[i] = 1 12 }13 else if i == 2 || i == 5 || i == 6 || i == 914 {15 dp[i] = 216 res += 117 }18 }19 else20 {21 var a:Int = dp[i / 10]22 var b:Int = dp[i % 10]23 if a == 1 && b == 124 {25 dp[i] = 126 }27 else if a >= 1 && b >= 128 {29 dp[i] = 230 res += 131 } 32 }33 }34 return res35 }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%1014 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 = numRaw10 while num > 0 {11 let dig = num % 1012 num = num / 1013 14 switch (dig) {15 case 0,1,8:16 break17 case 2,5,6,9:18 containDifferent = true19 case 3,4,7:20 containInvalid = true21 default:22 break;23 }24 25 if containInvalid {26 break27 }28 }29 30 if containDifferent && !containInvalid {31 count += 132 }33 }34 35 return count36 }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] = 210 goodNumCount += 111 } else if num == 0 || num == 1 || num == 8 {12 dp[num] = 113 }14 } else {15 let prevDigits = dp[num / 10]16 let lastDigit = dp[num % 10]17 18 if prevDigits == 1 && lastDigit == 1 {19 dp[num] = 120 } else if prevDigits >= 1 && lastDigit >= 1 {21 dp[num] = 222 goodNumCount += 123 }24 }25 }26 27 return goodNumCount28 }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 : 010 }11 12 return count13 }14 15 func isGood(_ n: Int) -> Bool {16 var newNr = 017 var multiply = 118 var workingN = n19 var d = 020 21 while workingN != 0 {22 d = workingN % 1023 if rotations[d] == -1 { return false }24 25 newNr = rotations[d] * multiply + newNr26 workingN /= 1027 multiply *= 1028 }29 30 return n != newNr31 }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] ?? -110 if changedDigit == -1 {11 return rotatedDigits(N - 1)12 } else if digit != changedDigit {13 changed = true14 }15 curNum /= 1016 }17 return (changed ? 1 : 0) + rotatedDigits(N - 1)18 }19 } 56ms
1 class Solution { 2 func rotatedDigits(_ N: Int) -> Int { 3 var c : Set = [2,5,6,9] 4 var k : Set = [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 = true10 while j > 0 {11 let d = j%1012 if c.contains(d) {13 cn += 114 } else if k.contains(d) {15 kn += 116 } else {17 valid = false18 break19 }20 j = j/1021 }22 if valid && cn > 0 {23 ans += 124 }25 }26 return ans27 }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 += 110 }11 }12 return count13 }14 15 func checkIfCanBeRotated(_ str: String) -> Bool {16 var res = false17 for s in str {18 if s == "2" || s == "5" || s == "6" || s == "9" {19 res = true20 } else if s == "3" || s == "4" || s == "7" {21 return false22 }23 }24 return res 25 }26 } 196ms
1 class Solution { 2 func rotatedDigits(_ N: Int) -> Int { 3 let invalid: Set = Set(["3", "4", "7"]) 4 let diff: Set = 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 += 112 }13 }14 15 return res16 }17 }