模擬 生成區間內連號的數字 Sequential Digits_Leetcode #1291

Aykut Eke on Unsplash

題目敘述

題目會給定一個區間[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

區間下邊界 >= 10

區間上邊界 <= 10^9

演算法

依照題意，從最小的數字1 ~ 最大的數字8 依照題意進行模擬即可。

1 -> 12 -> 123 ...

2 -> 23 -> 234 ...

3 -> 34 -> 345 ...

中間同理類推...

8 -> 89 停下來。

不會有910 因為91已經違反題目定義的規則。

程式碼

複雜度分析

時間複雜度:

12, 123, ..., 123456789 1開頭的總共 8 條

23, 234, ..., 23456789 2開頭的總共7種

...

67, 678, 6789 6開頭的總共3種

78, 789 7開頭的總共 2 種

89 8開頭的總共1種

全部總計 8 + 7 + 6 + ... + 1 = 8 * 9 / 2 = 36 種

為常數時間 O(36) = O(1)

空間複雜度:

扣掉輸出所指定的空間result，其他所使用到的都是固定尺寸的臨時變數，為常數級別O(1)

關鍵知識點

想到用生成的規律，來枚舉所有符合題意，可能的數字排列情況。

Reference:

[1] Sequential Digits - LeetCode