[討論] 單班 11.1

[suhorng ( )]

很多人滿分了，可是 Scoreboard 上也有一些 9 分的

今天跟一個同學研究的結論是記憶體動態開會比較理想

也就是說，若直接用陣列把資料個數開好的話，需要把空間開足夠

但是這題的測資很大，而且好像挺接近記憶體限制的邊界，

所以稍微開大一點很容易記憶體超過限制當掉，不容易抓到剛好的邊界

一種方法可以是先掃過一次得到正確的記憶體數量，再動態的開陣列

(動態記憶體或是 int a[n]; 之類的, 雖然後者不太正規, 但都可以通過測試)

我個人寫遞迴, 確實可過(Linux 上遞迴可以超深....), 也挺好寫的

另外要注意一下有可能輸入的本來就是空指標... 什麼也不用印

-

另外HW11還滿少人寫的...不過雖然這章教了二元搜尋樹、鏈結串列、...etc,

但是HW11不一定要把二元搜尋樹建出來XD 雖然我不知道老師出這題是希望看到

怎樣的解法...

輸入給的級別可能是個提示吧，舉例來說

                               r
                 ____________／
               ／
              s
           ／   ＼
         ／       ＼
        a           d
      ／ ＼          ＼
     b     c           e
                        ＼
                          f

則 c、f 的級別分別是 4 和 5 (呃....好像一般比較常叫這個東西'深度'? depth)

此外, s 是從 r 走到 c、以及 r 走到 f 的路中最後一個共通的節點, 級別為 1

可以觀察到 c、f 之間的距離是 c 到 s 的距離 + s 到 f 的距離

而 c 到 s 的距離是 c 的級別減去 s 的級別,

   f 到 s 的距離是 f 的級別減去 s 的級別.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.32.126
推 tiefblau:遞迴！
→ suhorng:是唷XD 五行短短的很開心
※ 編輯: suhorng         來自: 61.217.32.126        (12/06 23:56)
→ telgniw:九分通常是爆NULL
→ telgniw:然後書泓你幹麼講出來這題不用建treeQQ
→ suhorng:qq因為輸入實在太奇怪了 一般二元搜尋樹應該會照順序給鍵
→ suhorng:值不給深度 但是這題卻是不照順序給鍵值然後給深度
推 hasheesh:HW11 judegegirl 網站上看不到題目 QQ
推 bemyself:請問有沒有測資沒有深度為1的點? 或是有兩個以上?
→ suhorng:不太懂意思, 根節點不就是唯一的深度為 1 的點嗎 ?