→ sixB: 看到一個用trie的好酷 雖然mon可是 09/21 09:07
→ sixB: 字典題用字典樹超有感覺 09/21 09:07
→ dont: 大師 09/21 12:08
386. lexico什麼的number
題目要求T:O(n), M:O(1)
照字典順序擺
就看前綴
原本想說用radix sort試試
可是memory （n）
雖然應該會過==
改用recursive
先來先擺
能*10就*10
再來能+1就+1
不過要確認他不要加到下一個prefix去
class Solution {
public:
vector<int> res;
vector<int> lexicalOrder(int n) {
prefix(1, n);
return res;
}
void prefix(int cur, int& n){
if(cur > n) return;
//put all prefix(cur) into res;
res.push_back(cur);
prefix(cur * 10, n);
if((cur + 1) % 10 != 0) prefix(cur + 1, n);
}
};
-----
Sent from JPTT on my iPad
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726880102.A.5C9.html
※ 編輯: sixB (123.205.121.194 臺灣), 09/21/2024 08:55:36