Re: [閒聊] 每日LeetCode
看板Marginalman作者JerryChungYC (JerryChung)時間4月前 (2024/02/02 13:07)推噓2(2推 0噓 3→)留言5則, 4人參與討論串646/719 (看更多)
※ 引述《Rushia (みけねこ的鼻屎)》之銘言:
: https://leetcode.com/problems/sequential-digits/description
: 1291. Sequential Digits
: 一個Sequential Digits是一個數字滿足所有位數都比前面的位數恰好多出一例如:
: 123 456,給你兩個數字low 和 high,求介於 low~high的所有Sequential Digits
: 並排序之。
: 思路:
: 1.用dfs窮舉所有的可能,不斷的把尾數+1並append到原本的數字直到超出high,
: 因為測資範圍為 10~10^9 所以可以從12開始窮舉,然後排除掉尾數0的case。
Python3 code:
---------------------------------------------------------
class Solution:
def sequentialDigits(self, low: int, high: int) -> List[int]:
lst = [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 [_ for _ in lst if low <= _ <= high]
---------------------------------------------------------
上面是初版 一次就過 穩的
---------------------------------------------------------
class Solution:
def sequentialDigits(self, low: int, high: int) -> List[int]:
text = "123456789"
res = []
low_ = str(low)
high_ = str(high)
for i in range(len(low_), len(high_)+1):
start = int(low_[0]) - 1 if i == len(low_) else 0
word = int(text[start:start+i])
while len(str(word)) == i:
if low <= word <= high:
res.append(word)
start += 1
word = int(text[start:start+i])
return res
---------------------------------------------------------
還是乖乖寫了別的版本
按low的長度判斷 逐步遞增上去
Python3 效能跟 leetcode 的計算就那樣了 看不出明顯的差別
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.251.103 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706850444.A.F92.html
推
02/02 13:10,
4月前
, 1F
02/02 13:10, 1F
推
02/02 13:10,
4月前
, 2F
02/02 13:10, 2F
→
02/02 13:13,
4月前
, 3F
02/02 13:13, 3F
→
02/02 13:13,
4月前
, 4F
02/02 13:13, 4F
→
02/02 13:13,
4月前
, 5F
02/02 13:13, 5F
討論串 (同標題文章)