788.旋转数字

链接：788.旋转数字
难度：Medium
标签：数学、动态规划
简介：现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？。

题解 1 - cpp

• 编辑时间：2022-09-25
• 执行用时：4ms
• 内存消耗：6.8MB
• 编程语言：cpp
• 解法介绍：动态规划，每次从前面状态推进。

class Solution {
public:
    // 0 -> 无法旋转
    // 1 -> 旋转后是本身
    // 2 -> 旋转后不是本身
    int rotatedDigits(int n) {
        vector<int> list(n + 1, 0);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (i < 10) {
                switch (i) {
                    case 0:
                    case 1:
                    case 8: list[i] = 1; break;
                    case 2:
                    case 5:
                    case 6:
                    case 9: list[i] = 2; break;
                    default: list[i] = 0; break;
                }
            } else {
                int num1 = i / 10, num2 = i % 10;
                if (list[num1] == 0 || num2 == 3 || num2 == 4 || num2 == 7) list[i] = 0;
                else if (list[num1] == 1) list[i] = num2 == 0 || num2 == 1 || num2 == 8 ? 1 : 2;
                else list[i] = 2;
            }
            if (list[i] == 2) ans++;
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-09-25
• 执行用时：4ms
• 内存消耗：5.8MB
• 编程语言：cpp
• 解法介绍：动态规划，每次构造相同位数的数字。

class Solution {
public:
    int rotatedDigits(int n) {
        int len = get_len(n), list[3] = {0}, ans = 0;
        dfs(len, n, list, 0, 0, ans);
        return ans;
    }
    void dfs(int len, int n, int (&list)[3], int num, int cnt, int &ans) {
        if (num > n) return;
        if (cnt == len) {
            if (list[0] == 0 && list[2] > 0) ans++;
            // cout << "len = " << len
            //      << ", list = [" << list[0] << ", " << list[1] << ", " << list[2]
            //      << "], num = " << num << ", cnt = " << cnt << ", ans = " << ans << endl;
            return;
        }
        for (int i = 0; i < 10; i++) {
            list[get_tag(i)]++;
            dfs(len, n, list, num * 10 + i, cnt + 1, ans);
            list[get_tag(i)]--;
        }
    }
    int get_len(int n) {
        int ans = 0;
        while (n) n /= 10, ans++;
        return ans;
    }
    int get_tag(int n) {
        switch (n) {
            case 0:
            case 1:
            case 8: return 1;
            case 2:
            case 5:
            case 6:
            case 9: return 2;
            default: return 0;
        }
    }
};

题解 3 - cpp

• 编辑时间：2022-09-25
• 内存消耗：5.7MB
• 编程语言：cpp
• 解法介绍：同上，优化非倒数。

class Solution {
public:
    int rotatedDigits(int n) {
        int len = get_len(n), list[2] = {0}, ans = 0;
        dfs(len, n, list, 0, 0, ans);
        return ans;
    }
    void dfs(int len, int n, int (&list)[2], int num, int cnt, int &ans) {
        if (num > n) return;
        if (cnt == len) {
            if (list[1] > 0) ans++;
            return;
        }
        for (int i = 0; i < 10; i++) {
            int tag = get_tag(i);
            if (tag == -1) continue;
            list[tag]++;
            dfs(len, n, list, num * 10 + i, cnt + 1, ans);
            list[tag]--;
        }
    }
    int get_len(int n) {
        int ans = 0;
        while (n) n /= 10, ans++;
        return ans;
    }
    int get_tag(int n) {
        switch (n) {
            case 0:
            case 1:
            case 8: return 0;
            case 2:
            case 5:
            case 6:
            case 9: return 1;
            default: return -1;
        }
    }
};