788. Rotated Digits

發表於 | 分類於

problem

solution

option 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool check(int k){
        string str = to_string(k);
        bool flag = false;
        for(char c:str){
            if( c=='3' || c=='4' || c=='7') return false;
            if(c=='2' || c=='5' || c=='6' || c=='9') flag = true;
        }
        return flag;
    }
    int rotatedDigits(int n) {
        int count = 0;
        for(int i=1;i<=n;++i) count+=(check(i));
        return count;
        
    }
};

option 2 - dp

analysis

  • time complexity O(nlogn)
  • space complexity O(n)