題目： LeetCode - 1291. Sequential Digits

題目說明

給兩個整數 low, high，求大於等於 low 且小於等於 high 的所有整數，整數需要每一位都比前一位的值大 1，如 123、234、3456 …，且返回的陣列須按大小排列。

解題思路

題目的要求可以想成從 “123456789” 中找在範圍中的連續子串，先找出 low 及 high 的位數，因為在範圍中的數字位數必定會在 low 及 high 的位數中間，接著使用兩個迴圈，第一層代表位數，第二層為起點 ( 從 0 到 9 - i )，這樣做的同時確保了數字會由小到大，接著判斷，若是數字大於 high 則接下來同位數的數都不會在範圍中，最後判斷若是大於等於 low 則存入結果。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> sequentialDigits(int low, int high)
    {
        int ldigits = to_string(low).length(), hdigits = to_string(high).length();
        vector<int> ret;
        string str = "123456789";
        for(int i = ldigits; i <= hdigits; ++i) for(int j{}; j < 10 - i; ++j)
        {
            int tmp = atoi(str.substr(j, i).c_str());
            if(tmp > high) break;
            if(tmp >= low) ret.emplace_back(tmp);
        }
        return ret;
    }
};