c_788_Rotated_Digits

Posted on | In |

//
// Created by Mr.Hu on 2019/1/17.
//
// 题目定义了good number的概念，对于一个数字，如109，对于数字中的每一个数字旋转180度，规则如下：
// 0，1，8旋转后不变，2旋转后为5，5旋转后为2，6旋转后为9，9旋转后为6，3，4，7不能被旋转。
// good number即为旋转后的数字存在，且和原来的数字不相同。
// 求[1,N]区间中有多少good number存在
//
// 这个题目最直观的方法就是对于每个数字，用一个方法取每一位进行判断，如果满足条件，则count++；
// 但是这种方法过于蛮力，所以想用更加creative的方法的解答，所以就去寻找规律，从1-9，11-19，21-29，…
// 刚开始想的是在1-99，满足条件的good number是有限的，固定的，所以对于一个N，先N/100，看存在多少个这样的值，其实不然，
// 因为当大于100，100-199是满足上述，但是200-299并不满足；其关键在于最高位的数字变成了可旋转且旋转后数字不同的情况。
//
// 于是想另外一种方法，01–>10-19–>100-199->1000->1999…
// 不难发现，根据一位数字，我们可以判断其为十位时所有数字的情况，根据二位数字，可以判断其为百位和十位的情况，依次类推。
// 我们先判断0-10，然后对每一位*10+[0-9]依次判断，以这种递进的关系来不断判断，直到当前数字大于数组的大小。
// 最后判断数组中我们定义能旋转的标志个数，即为所求。
//
// ⚠️：这个题目不仅在思路上让我动了脑筋，还给我扫清了几个只是盲区：
// 1、vector nums(N,0)并不能用来进行动态数组的初始化；
// 2、int[N]并不会默认初始化为0，只会随机初始化
// 这也就是为什么这个题目我一直提交报错的原因，错误的认为会默认初始化为0；
//
// 而且类似于这种统计区间内存在多少满足条件的数，可以往寻找推导关系的方向思考
//

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
using namespace std;

class Solution {
public:
    int rotatedDigits(int N) {
        // 3，4，7 are invalid
        // only 0，1，8 are invalid
        int res = 0;
        int num[N + 1];

        int m;
        for (int i = 0; i <= N / 10; i++) {
            m = i * 10;
            for (int j = 0; j <= 9; j++) {
                if (m + j >= N + 1) {
                    break;
                }
                if (num[i] == 0) {
                    if (j == 0 || j == 1 || j == 8)
                        num[m + j] = 0;
                    else if (j == 2 || j == 5 || j == 6 || j == 9)
                        num[m + j] = 1;
                    else
                        num[m + j] = 2;
                } else if (num[i] == 1) {
                    if (j == 3 || j == 4 || j == 7)
                        num[m + j] = 2;
                    else
                        num[m + j] = 1;
                } else
                    num[m + j] = 2;

            }
        }
        for (int i = 1; i <= N; i++) {
            if (num[i] == 1) {
                res++;
            }
        }
        return res;
    }
};

int main() {
    int N = 1;
    Solution solution;
    int res = solution.rotatedDigits(N);
    cout << res << endl;
    return 0;
}