动归数组d，d[i]表示数字i的状态。

d[i]对应有三个值，1是好数，0是普数，-1是坏数。

好数是旋转后不同的数比如(2,5,6,9)，普数是旋转以后相同的数如(0,1,8)，坏数是旋转后不能成立的数如(3,4,7)，这里前十个数的好坏情况通过切片给预处理了。

某数字i末位或末位以外的数字为坏数，数字i就肯定是坏数，例如(897,389,941)等等。

如果数字i不是坏数，那只要末位或末位以外的数字存在好数，那数字i就肯定是好数，如(120,886,509)等等就是好数，如(808,880)就是普数，程序这里计算用了按位或"|"。

如果数字i的结果d[i]是1是好数，那总答案就加1。

主要是末位以外的数字在计算该数字前肯定计算过了，所以可以动归。

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

class Solution:
    def rotatedDigits(self, N: int) -> int:
        ans, d = 0, [0, 0, 1, -1, -1, 1, 1, -1, 0, 1] + [0] * (N - 9)
        for i in range(N + 1):
            d[i] = -1 in (d[i // 10], d[i % 10]) and -1 or d[i // 10] | d[i % 10]
            ans += d[i] == 1
        return ans

func rotatedDigits(N int) int {
    ans, d := 0, make([]int, N + 1)
    copy(d, []int{0, 0, 1, -1, -1, 1, 1, -1, 0, 1})
    for i := 0; i <= N; i++ {
        if d[i / 10] == -1 || d[i % 10] == -1 {
            d[i] = -1
        } else if d[i] = d[i / 10] | d[i % 10]; d[i] == 1 {
            ans++
        }
    }
    return ans
}

impl Solution {
    pub fn rotated_digits(n: i32) -> i32 {
        let mut d: Vec<i32> = vec![0, 0, 1, -1, -1, 1, 1, -1, 0, 1];
        d.extend(vec![0; (n - 9).max(0) as usize]);
        let mut ans = 0;
        for i in 0..=n as usize {
            d[i] = if d[i / 10] == -1 || d[i % 10] == -1 {-1} else {d[i / 10] | d[i % 10]};
            ans += if d[i] == 1 {1} else {0};
        }
        ans
    }
}

var rotatedDigits = function(N) {
    let ans = 0
    const d = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1].concat(Array(Math.max(0, N - 9)).fill(0))
    for (let i = 0; i <= N; ++i) {
        if (d[Math.floor(i / 10)] == -1 || d[i % 10] == -1) {
            d[i] = -1
        } else if (d[Math.floor(i / 10)] == 1 || d[i % 10] == 1) {
            d[i] = 1
            ++ans
        }
    }
    return ans
};

function rotatedDigits(N: number): number {
    let ans: number = 0;
    let d: number[] = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1, ...Array(Math.max(N - 9, 0)).fill(0)];
    for (let i of Array.from({length: N + 1}, (_, k) => k)) {
        let [j, k] = [Math.trunc(i / 10), i % 10];
        d[i] = (d[j] == -1 || d[k] == -1) && -1 || d[j] | d[k];
        ans += Number(d[i] == 1);
    }
    return ans
};

py
go
rs
js
ts