1291. Sequential Digits 解題紀錄

An integer has sequential digits if and only if each digit in the number is one more than the previous digit. Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.   Example 1: Input: low = 100, high = 300 Output: [123,234] Example 2: Input: low = 1000, high = 13000 Output: [1234,2345,3456,4567,5678,6789,12345]   Constraints: 10 <= low <= high <= 10^9 這題給我們兩個變數,low 與 high。 題目需要我們在 low - high 區間裡面找到符合條件的整數, 條件是這個整數必須每一位都比前一位大"1"。 這題如果沒有那個條件,會非常難做, 要考慮 low, high 不同位數。 但如果有遞增"1",可以視為 "123456789" 的模板來做, 另外要注意 substr 的用法是填入起始位元與長度, 這個起始位元需要被計算進來,所以邊界條件要 l + ls <= 9。 C++程式碼:
megapx
假設 RS - LS 為 N。 計算複雜度:O(N) -> 計算 sliding window 其實是 O(N * 10),但 10 是常數所以 O(N) 空間複雜度:O(1) -> 根據 s 與 high 上面是 1e9 推最多只有 36 個,36 是常數所以是 O(1) Github程式碼:
愛心
69
留言
encourage first comment
有些話想說嗎 快分享出來彼此交流吧!