ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 7:02 PM
剛剛練習ㄌ N-ary Tree Postorder
不過用 iterative 的方式寫好慢，可是又看不懂那些壓低行數的人 recursive 怎麼寫ㄉ（
oToToT@(>▂<)
@oTo_ToT
Wed, Jul 21, 2021 7:31 PM
那啥? leetcode 590?
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 7:40 PM
oToToT@(>▂<)
: 應該是ㄅ，我忘記題號了，不過找到是 leetcode 就對ㄌ
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 7:42 PM
不過我剛剛跑去解了 ZigZag string ，用比較 naive 的方法解，也是有點慢。但感覺這種鋸齒狀的題目可以寫成一個公式去解
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 7:43 PM
Encode and Decode TinyURL - LeetCode
這個準備工作好長，我先等等看（
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 7:43 PM
我想一下我怎ㄇ貼 code snip
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 7:46 PM
好 Q ㄛ第一次看到這個工具
Mutex<Abby>
@abbychau
Wed, Jul 21, 2021 7:47 PM
590:
Recursive :
優先push 最左邊沒有chilren 的val進入callstack
Iterative :
把最右邊有children 的root 優先放入答案
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 7:50 PM
N-ary tree postorder
我是就很直觀地走過，然後存狀態
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 7:50 PM
Mutex<Abby>
: 為什麼 iterative 是把最右邊有children 的root 優先放入答案
Mutex<Abby>
@abbychau
Wed, Jul 21, 2021 7:54 PM
jennifer7108
: 這樣一直push, 答案就剛好是反過來了
例如:
. 1,5,10,9,13...
oToToT@(>▂<)
@oTo_ToT
Wed, Jul 21, 2021 8:02 PM
這個 python 好 C ww
Mutex<Abby>
@abbychau
Wed, Jul 21, 2021 8:03 PM
Wed, Jul 21, 2021 8:05 PM
jennifer7108
: 你用了array, append 時會不斷變慢的, 這題利用linked list 的特性才會快
linked list prepend 時只要修改第一個pointer 就夠了, pop 時也是, 這樣就令每個存取都是O(1)了
oToToT@(>▂<)
@oTo_ToT
Wed, Jul 21, 2021 8:21 PM
Mutex<Abby>
: 沒吧，python list 的 append 跟 pop 都是 O(1) 的，反正底下基本上就是個 dynamic array
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 8:22 PM
我壓成這幾行ㄌ！！！
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 8:24 PM
oToToT@(>▂<)
: 我一直改不過來wwww 要寫得像 pythoneer 是不是要寫多一點 [::-1] 之類ㄉ操作
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 8:25 PM
不過不知道為什麼更慢ㄌ，我想想
oToToT@(>▂<)
@oTo_ToT
Wed, Jul 21, 2021 8:25 PM
extend的::-1改成reversed應該會比較快ㄅ
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 8:26 PM
oToToT@(>▂<)
: ㄛ對ㄟ，忘記
Mutex<Abby>
@abbychau
Wed, Jul 21, 2021 8:26 PM
oToToT@(>▂<)
: 喔喔真的！
我有聽過越加越慢的說法...
ㄌㄐ@你的水潤餅大使
@raagi
Wed, Jul 21, 2021 8:33 PM
Wed, Jul 21, 2021 8:34 PM
yeah 壓到 44ms ㄌ
oToToT@(>▂<)
@oTo_ToT
Wed, Jul 21, 2021 8:38 PM
Mutex<Abby>
: 我現在想到會變慢的部分可能是因為 O(1) 是 amortized 的，所以他的實際執行時間是偶爾會變特別長，然後越多操作之後特別長的可能會更長 (不確定 python 底下有沒有特別優化)
載入新的回覆
不過用 iterative 的方式寫好慢，可是又看不懂那些壓低行數的人 recursive 怎麼寫ㄉ（
好 Q ㄛ第一次看到這個工具
Recursive :
優先push 最左邊沒有chilren 的val進入callstack
Iterative :
把最右邊有children 的root 優先放入答案
N-ary tree postorder
我是就很直觀地走過，然後存狀態
例如:
. 1,5,10,9,13...
linked list prepend 時只要修改第一個pointer 就夠了, pop 時也是, 這樣就令每個存取都是O(1)了
我壓成這幾行ㄌ！！！