讨论/题目交流/🐱 力扣第 10 场夜喵双周赛/
🐱 力扣第 10 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛
image.png

展开讨论

T3:

纯爆搜

O(2^size(high))

size(high)代表high的位数

high < 2*10^9 => size(high) < 9

...

class Solution {
public:
    set<long long> ans;
    long long l, h;
    void search(long long num, long long k) {
        if (num % 10ll == 9ll) {
            if (num * 10ll + 8ll <= h) {
                if (num * 10ll + 8ll >= l) {
                    ans.insert(num * 10ll + 8ll);
                }
                search(num * 10ll + 8ll, k + 1ll);
            }
        }
        else if (num % 10ll == 0ll) {
            if (num * 10ll + 1ll <= h) {
                if (num * 10ll + 1ll >= l) {
                    ans.insert(num * 10ll + 1ll);
                }
                search(num * 10ll + 1ll, k + 1ll);
            }
        }
        else {
            int ff = num % 10ll;
            if (num * 10ll + ff - 1ll <= h) {
                if (num * 10ll + ff - 1ll >= l) {
                    ans.insert(num * 10ll + ff - 1ll);
                }
                search(num * 10ll + ff - 1ll, k + 1ll);
            }
            if (num * 10ll + ff + 1ll <= h) {
                if (num * 10ll + ff + 1ll >= l) {
                    ans.insert(num * 10ll + ff + 1ll);
                }
                search(num * 10ll + ff + 1ll, k + 1ll);
            }
        }
    }
    vector<int> countSteppingNumbers(int low, int high) {
        this -> l = (long long)low;
        this -> h = (long long)high;
        for (int i = low; i < 10; i++) {
            ans.insert((long long)(i));
        }
        search(1ll, 1ll);
        search(2ll, 1ll);
        search(3ll, 1ll);
        search(4ll, 1ll);
        search(5ll, 1ll);
        search(6ll, 1ll);
        search(7ll, 1ll);
        search(8ll, 1ll);
        search(9ll, 1ll);
        set<long long>::iterator iter;
        vector<int> s;
        for (iter = ans.begin(); iter != ans.end(); ++iter){
            s.push_back(int(*iter));
        }
        return s;
    }
};
展开全部 8 讨论