[LeetCode] 788. Rotated Digits_Easy tag: **Dynamic Programming

基本思路建一个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
上一篇:Java和.net对比分析


下一篇:Axure8.0从入门到精通