題目分析

題目

An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

我們定義「順子數」為：每一位上的數字都比前一位上的數字大1的整數。

Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

請你回傳由 [low, high] 範圍內所有順子數組成的有序清單（從小到大排序）。

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

分析

題目所要求的「順子數」(An integer has sequential digits)指：像123 4567 56789這種，相鄰位數均為遞增1的數列所構成的數。

根據測資的範圍(10<=)，個位數不需考慮。

(也就是不限長度的順子啦)

所求為返回一個陣列，其中要包含所有介於[ low, high ]閉區間之內，且屬於「順子數」的整數，超過兩個數時，要以遞增排序。

解題思路

方案一、暴力解(Brute force)

其實在一開始舉例的時候就很容易發覺，題目所要求的順子數並沒有很多，甚至是可以直接快速人工列舉完畢的。

兩位數的「順子數」共有8個：

12 23 34 45 56 67 78 89

三位數的「順子數」共有7個：

123 234 345 456 567 678 789

依此類推，八位數與九位數的「順子數」分別有2和1個：

12345678 23456789

123456789

也就是，在題目測資所求範圍之內(10 <= low <= high <= 10^9)，最多只會有8+7+6+…+2+1 = 36個「順子數」。

如果是在 Contest ，與其花費時間去考慮迴圈的邊界條件等等，直接窮舉所有9位數以內的順子數再用上下邊界去篩選，應該是不錯的選擇。

方案一實作 by Python3：

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        nums = [
            12,23,34,45,56,67,78,89,
            123,234,345,456,567,678,789,
            1234,2345,3456,4567,5678,6789,
            12345,23456,34567,45678,56789,
            123456,234567,345678,456789,
            1234567,2345678,3456789,
            12345678,23456789,
            123456789
        ]
        return filter(lambda x: x>=low and x<=high, nums)

恩對樸實無華(X)

用filter或列表生成式把上下界篩出來就完事了。

方案二、迴圈法

如果是面試的話，或許暴力解無法彰顯我們的智慧(?)，所以即使沒有必要，仍可以用迴圈來自動生成所有順子數。

迴圈的做法一樣有很多種，想炫技(?)的話可以拿牛刀殺雞，看是要遞迴、DP或者backtract都可以。不過這邊展示一下簡單的方法：

因為所有的「順子數」都包含在'123456789’ 這個最長的順子數之間，所以可以用「字串取子字串」的方式，去取得所有長度為2~9的順子數。

123456789
ij        12  從i=1開始
i j       123 讓j從2~9
...
i       j 123456879
---------
 ij       23  然後i=2
 ...          讓j從3~9
 i      j 23456789
---------
...       依此類推
---------
       ij 直到ij = 89

不難發現，具體的範圍是：

i 從 1 ~ 8

j 從 i+1 ~ 9

如此一般，做兩層的迴圈，就能自動化的產生在前述解法一中人工產生的所有「順子數」

需要留意的是，這樣產生的順序並沒有照數字大小排列。因此，在最後要重新排序。

對複雜度敏感的人可能會想到，我呼叫排序算法，時間複雜度會從原本的O(n)變成O(log n)耶。

不過這裡因為n=36，基本上可以不管他。

實際上，透過改變迴圈的寫法，也能讓產生出來的順序就恰為二位數>三位數>…>九位數。不過這並非本題的考點，就暫且省略吧。

方案二實作 by Python3：

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        s = '123456789'
        res = []
        for i in range(8):
            for j in range(i+2,10):
                if int(s[i:j]) in range(low, high+1):
                    res.append(int(s[i:j]))
        res.sort()
        return res

Python3 一行解

如果是希望答案的行數越少越好的python廚(X)，一定喜歡在easy題搞這種一行解：

return sorted(int('123456789'[i:j]) for i in range(8) for j in range(i+2,10) if int('123456789'[i:j])in range(low, high+1))

複雜度分析

假設n為測資範圍內順子數的總數：

方案一：時間、空間複雜度均為O(n)

將所有順子數列出，故空間複雜度O(n)
遍歷所有順子數判斷是否位於low~high區間，故時間複雜度為O(n)

方案二：時間複雜度為O(log n)，空間複雜度為O(n)

遍歷'123456789’的子字串的過程，恰好遍歷所有的順子數各一次，故時間複雜度為O(n)

隨後的排序時間複雜度為O(log n)

O(log n) + O(n) = O(log n)
需要空間存放所有產生出來的順子數，故空間複雜度為O(n)

實際上本題因為n非常小(36)，方案二不見得會比較慢。

不過也因為n很小，標準解的T接近常數時間，下列這種解法，應該就會導致TLE

從low遍歷到high，依序判斷這個數是否為「順子數」

因為測資範圍是10 ~ 10^9，遠大於前述解法的36筆數據。

可知本題的考點在於，並非「判斷是否為順子數」，而是「如何產生所有順子數」。

結語

這題是難度詐欺的 medium，會卡題應該是像最後一段所述，搞錯了題目的基本思路。

感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！

Leetcode 1291. Sequential Digits

目錄