"""
day: 2020-09-06
url: https://leetcode-cn.com/problems/rotated-digits/
题目名: 旋转数字
我们称一个数 X 为好数,如果它的每位数字逐个地被旋转180度后,我们仍可以得到一个有效的,且和 X 不同的数.要求每位数字都要被旋转。
如果一个数的每位数字被旋转以后仍然还是一个数字 ,则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己
2 和 5 可以互相旋转成对方,在这种情况下,它们以不同的方向旋转,换句话说，2 和 5 互为镜像,6 和 9 同理,除了这些以外其他的数字旋转以后都不再是有效的数字。
现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
示例:
    输入: 10
    输出: 4
思路:
1. 动态规划
    一个数字可以看做是 x * 10 + y, 如果x是个好数或者y是个好数,且另一个数中不包含 3, 4, 7这三个数字
    那么这个数就是一个好数,自顶向下进行计算,首先个位数的好数是{2, 5, 6, 9},坏数是{3, 4, 7},每次遍历
    我们先判断数字的x//10与x%10是否有一个是坏数,再判断是否有一个是好数.
"""


class Solution:
    def rotatedDigits(self, N: int) -> int:
        dp = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1] + [0 for _ in range(N-9)]
        count = 0
        for i in range(N+1):
            if dp[i // 10] == -1 or dp[i % 10] == -1:
                dp[i] = -1
            elif dp[i // 10] == 1 or dp[i % 10] == 1:
                dp[i] = 1
                count += 1
        return count


if __name__ == "__main__":
    test = 100
    s = Solution()
    print(s.rotatedDigits(test))
