模擬 生成區間內連號的數字 Sequential Digits_Leetcode #1291
閱讀時間約 2 分鐘
題目敘述
題目會給定一個區間[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:
86會員
425內容數
由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。
留言0
查看全部
你可能也想看
Google News 追蹤
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
美國總統大選只剩下三天， 我們觀察一整週民調與金融市場的變化（包含賭局）， 到本週五下午3:00前為止， 誰是美國總統幾乎大概可以猜到60-70%的機率， 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
Faker昨天真的太扯了，中國主播王多多點評的話更是精妙，分享給各位
王多多的點評
「Faker是我們的處境，他是LPL永遠繞不開的一個人和話題，所以我們特別渴望在決賽跟他相遇，去直面我們的處境。
我們曾經稱他為最高的山，最長的河，以為山海就是盡頭，可是Faker用他28歲的年齡...
我開始提供協助公務員商調模擬面試的服務，大概兩個月左右了，累積了一些來訪者的反饋以及諮詢過程中的感覺，整理出三個我覺得這樣的面試服務真的很有幫助的地方。
準與不準，除了糾結於軟體本身，演算法，數值方法這些東西以外，其實更重要的是一個問題的複雜度。任何一套軟體，拿去做物理課本例題上面的簡單問題，都沒毛病，而且和實驗一致。但是為什麼模擬軟體能發揮的功能依舊有限?
預測產品行為
預測性的成果，精神上就相當於經驗公式，具體就會像是Intel或AMD所提供的CPU thermal model這種。經過校正後的模型得出的結果在誤差上原則可以小於5%，可以用來預測產品行為，提供廠商開發散熱片的模型。一個模型要準，勢必得投入測量值去校正材料參數或是取得等效參數。
筆者日前受邀參與財團法人資訊工業策進會舉辦的「數位分身與沙盒法制環境建構研析」專家座談會，發現新加坡與英國正在進行這樣的「數據模擬分析」專案計畫，實在很像電玩遊戲「模擬城市」（SimCity），其中衍生國家、城市乃至於個人的元宇宙與數位分身（Digital Twin），可應用於分析風險的高低、測試政
在作模擬的時候，這個準不準這個問題絕對有資格被排在常見問題中的前三名。
當然也是我們首先要問自己的部分。如果人家要拿這份結果去做設計評估，那他的準確性到哪? 如果不能拿來做設計參考，那我們該怎麼解讀?
而準不準的問題，要分成事前諸葛和事後諸葛兩種應用來討論。
事後諸葛的類型
事前諸葛的類型
六月有兩個任務：一是要模擬檢查子宮內膜厚度、二是要照輸卵管攝影。
6/16：愛群開兩週內膜藥，藥物作用是提供雌激素。
6/20：預計月經來，開始用口服，在量多的第二天開始吃。
6/28 +- 2天：已預約6/28 8:30輸卵管攝影，施作前要空腹4小時，避免檢查時吐出來。
8/7：最快植入日
可能包含敏感內容
每每獨處時刻
我都會思考 那晚
我要的是什麼
是那個人 亦或是 排解寂寞的
稱為愛的安全感
不 我就是個骯髒的人
我要的不過是 被用力撞擊的感受
抓緊被單 無法抑制的聲音
一直以來都是書寫著錯誤的答案
現在只不過是改正而已
所有的詭譎 僅僅是 不習慣
諸多錯誤的答案中 你為什麼這麼
一元是意識推理出來的，人有意識，是二元，所以只能模擬一元。
意識是二元，就算最原始的意識也一樣，神佛上帝也是二元，都在 do something，都在創造。
我們說靈修是回去一元，應該不對，一元就不是意識了，應該說是去模擬一元，模擬一元的清靜，靈修是必要的，每個人多多少少都想過修
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
美國總統大選只剩下三天， 我們觀察一整週民調與金融市場的變化（包含賭局）， 到本週五下午3:00前為止， 誰是美國總統幾乎大概可以猜到60-70%的機率， 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
Faker昨天真的太扯了，中國主播王多多點評的話更是精妙，分享給各位
王多多的點評
「Faker是我們的處境，他是LPL永遠繞不開的一個人和話題，所以我們特別渴望在決賽跟他相遇，去直面我們的處境。
我們曾經稱他為最高的山，最長的河，以為山海就是盡頭，可是Faker用他28歲的年齡...
我開始提供協助公務員商調模擬面試的服務，大概兩個月左右了，累積了一些來訪者的反饋以及諮詢過程中的感覺，整理出三個我覺得這樣的面試服務真的很有幫助的地方。
準與不準，除了糾結於軟體本身，演算法，數值方法這些東西以外，其實更重要的是一個問題的複雜度。任何一套軟體，拿去做物理課本例題上面的簡單問題，都沒毛病，而且和實驗一致。但是為什麼模擬軟體能發揮的功能依舊有限?
預測產品行為
預測性的成果，精神上就相當於經驗公式，具體就會像是Intel或AMD所提供的CPU thermal model這種。經過校正後的模型得出的結果在誤差上原則可以小於5%，可以用來預測產品行為，提供廠商開發散熱片的模型。一個模型要準，勢必得投入測量值去校正材料參數或是取得等效參數。
筆者日前受邀參與財團法人資訊工業策進會舉辦的「數位分身與沙盒法制環境建構研析」專家座談會，發現新加坡與英國正在進行這樣的「數據模擬分析」專案計畫，實在很像電玩遊戲「模擬城市」（SimCity），其中衍生國家、城市乃至於個人的元宇宙與數位分身（Digital Twin），可應用於分析風險的高低、測試政
在作模擬的時候，這個準不準這個問題絕對有資格被排在常見問題中的前三名。
當然也是我們首先要問自己的部分。如果人家要拿這份結果去做設計評估，那他的準確性到哪? 如果不能拿來做設計參考，那我們該怎麼解讀?
而準不準的問題，要分成事前諸葛和事後諸葛兩種應用來討論。
事後諸葛的類型
事前諸葛的類型
六月有兩個任務：一是要模擬檢查子宮內膜厚度、二是要照輸卵管攝影。
6/16：愛群開兩週內膜藥，藥物作用是提供雌激素。
6/20：預計月經來，開始用口服，在量多的第二天開始吃。
6/28 +- 2天：已預約6/28 8:30輸卵管攝影，施作前要空腹4小時，避免檢查時吐出來。
8/7：最快植入日
可能包含敏感內容
每每獨處時刻
我都會思考 那晚
我要的是什麼
是那個人 亦或是 排解寂寞的
稱為愛的安全感
不 我就是個骯髒的人
我要的不過是 被用力撞擊的感受
抓緊被單 無法抑制的聲音
一直以來都是書寫著錯誤的答案
現在只不過是改正而已
所有的詭譎 僅僅是 不習慣
諸多錯誤的答案中 你為什麼這麼
一元是意識推理出來的，人有意識，是二元，所以只能模擬一元。
意識是二元，就算最原始的意識也一樣，神佛上帝也是二元，都在 do something，都在創造。
我們說靈修是回去一元，應該不對，一元就不是意識了，應該說是去模擬一元，模擬一元的清靜，靈修是必要的，每個人多多少少都想過修