基本思路建一个helper function, 然后从1-N依次判断是否为good number, 注意判断条件为没有3,4,7 的数字,并且至少有一个2,5,6,9, 否则的话数字就一样了, 比如88, 18等.
Improve: 利用DP去判断, 时间和空间都能降为O(lgn)
Code T: O(Nlgn) S; O(lgn)
class Solution:
def rotatedDigits(self, N):
## Solution: T: O(Nlgn) S; O(lgn)
def helper(n):
s = str(n)
return all(d not in "" for d in s) and any(d in '' for d in s)
ans = 0
for i in range(1,N + 1):
if helper(i):
ans += 1
return ans