Re: [閒聊] 每日leetcode
386. Lexicographical Numbers
## 思路
萬用recursion
一開始先1~9, 再對curr*10 + i做recursion
iteration
case1. 乘10: 1 -> 10 -> 100
case2. 末位數<9,直接加1: 1 -> 2
case3. 末位數=9,除10到末位數<9再加1: 199 -> 2
case4. curr >= n時,除10到末位數<9再加1: 13 -> 2, 193 -> 2
2~4合在一起處理
## Code
Recursion
```python
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
res = []
def recur(curr):
if curr > n:
return
res.append(curr)
for i in range(10):
recur(curr*10+i)
for i in range(1, 10):
recur(i)
return res
```
Iteration
```python
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
res = []
curr = 1
for _ in range(n):
res.append(curr)
if curr * 10 <= n:
curr *= 10
else:
while curr % 10 == 9 or curr >= n:
curr //= 10
curr += 1
return res
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.231 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726892410.A.F0A.html
推
09/21 15:46,
1年前
, 1F
09/21 15:46, 1F
討論串 (同標題文章)
完整討論串 (本文為第 888 之 1548 篇)：