Re: [問卦] 演算法DFS看得懂 但寫不出來 問題在哪?
本巨巨推薦DFS從binary tree開始寫 並且要用遞迴的方式
用stack可以 但是全局視野比較沒有解子問題的感覺
類似這一題
98. Validate Binary Search Tree
這題就是要你驗證 這是不是一個Binary Search Tree
其實就是不斷解以下這個子問題
1. 左子樹是不是BST
如果不是 那此Binary Tree不是BST
2. 如果左子樹是BST 那根節點的值是不是比左子樹最大的還大
如果不是 那此Binary Tree也不是BST
3. 右子樹是不是BST 並且裡頭所有的值都大於根節點的值
那我們來看一個例子
按照上面的邏輯
5
/ \
3 7
/ \ /
1 4 6
1. 左子樹是不是BST 那我們就要看 3
/ \
1 4
喔喔 還有左子樹 再來看 那 1 是不是BST? 是
那同時用一個變量來存1的值 prev = 1
那再來就是
2. 如果左子樹是BST 那根節點的值是不是比左子樹最大的還大
3 是不是比1大 是 並且更新prev = 3
再來
3. 右子樹是不是BST 並且裡頭所有的值都大於根節點的值
4 是不是 BST? 是 那4是不是比3大? 是
再來更新prev = 4
我們解完 3
/ \
1 4
再來就要看 5
\
7
/
6
解完 5的左子樹了 那就回到
2.如果左子樹是BST 那根節點的值是不是比左子樹最大的還大
剛剛的prev = 4 那5有沒有比4大? 有 更新prev=5
再來就是
3. 右子樹是不是BST 並且裡頭所有的值都大於根節點的值
又是一個子問題
我們要來看 7 的 1. 左子樹是BST
/
6
6是不是BST? 是 有沒有大於5? 有 更新prev=6
2. 如果左子樹是BST 那根節點的值是不是比左子樹最大的還大
7有沒有比6大? 有 更新prev=7
過完整棵樹 發現所有問題的1. 2. 3. 都是true 那我們就可以說這個二元樹是一顆BST
本巨巨覺得DFS的精神就是要你站在子問題的視野來解題 忘掉你從哪裡來
然後從子子子子子子子問題開始解回去
用stack結構來解這題也行 也是DFS 也比較理想
變成一個用stack做inorder traversal
不會讓你stack overflow 也比較快 不用caller callee一直跳
但就少了解子問題的味道 我覺得拉
※ 引述《cosmite (焼き団子)》之銘言:
: 最近開始Leetcode
: 發現字串處理和系統設計的的題目較DFS容易寫
: DFS的題目看解答看得懂
: 但是要自己從無到有寫一次
: 包括邊界條件和遞迴判斷式怎麼寫 卻寫不出來
: (中等難度)
: 到底是哪裡出問題?
: 我是不是題目寫太少了
: 應該從最簡單的DFS題目 反覆不同寫
: 寫到建函示變反射動作嗎?
: 有沒有人能救我==
: 卦
: -----
: Sent from JPTT on my iPhone
--
阿肥你很懂哦
怎辦到看dfs反射動作就是用stack
很正常啊 因為你會用stack啊 對會寫code的人你要他用遞迴還是stack都行
不用stack用什麼?
你可以自己刻出stack啊 用雙queue模擬stack 怎麼樣 沒規定時間我也能脫褲子放屁
喔 我多打一個到
遞迴就是stack
解完給offer
考完就還給老師啊
嗯嗯 這樣說我就懂了
謝謝 待會來試
問就是Morris traversal 空間複雜度O(1)
爆
Re: [外絮] 龜龜被懷疑眼睛和手是不是有問題這也太怪 先撇除Westbrook有沒有刷的問題 他這季最後15場的場均是這樣 場均20.3分6.3助攻,投籃命中率50.3%,連他這季很不擅長的3分球每場出手3.7次投籃命 中率都有37.5% 他幾乎就是湖人最後關頭表現算很正常的球員之一了,因為他是季末狂拉尾盤的爆
[求助] 是我的問題嗎?是不是該離開?背景說明: 結婚6年,2個小孩,3歲跟4個月,都是男寶 無後援,雙薪家庭 我跟先生是第一代移民,除了我們跟兩個小孩外,所有家人都在台灣。 我是職業婦女,固定一到五上班,每天接送小孩再加回家大概1-1.5小時車程。(8點出門89
[閒聊] 你行你上的導師是不是跟國小導師一樣?要他們認錯都很難 雖然賽制問題已經討論到爛了,而且風潮感覺也已經過了 但想趁節目還沒完結時再來討論一下賽制 這幾天才看花絮果實能力者小熊的VOD(搭檔章) 那天來DC討論的湯米、ZOD跟PO11都覺得賽制沒問題93
[無言] 你會寫慎重的慎嗎?板工提醒:內容少於二十字 或 少於三行,會立刻砍文,並視情況劣退! 想發集氣文或問卷文的,請將板規八每一個字都看清楚,再有違反就劣退+水桶了! ========================================================================== 我老婆的名字有個慎字,慎重的慎,認識他之後才知道原來這個字是冷門字,很多人都不 會寫,看過各種寫法「愼」「禛」「槇」31
[討論] 跟有對象的人告白是不是人品有問題是說,大家覺得明明知道一個人有對象,還去跟那個人告白,是不是品格有問題呢? 不過翻了一下相關的文,這些人似乎都會說表白不等於示愛,大概就是說我只是想要表達 我的心意,沒有想要介入你們的意思。 不過我也很懷疑,如果那個人答應了是不是告白的人就衝了,沒成功的話就用前面那個理 由當擋箭牌呢?3
[問卦] 會C的人學Java要注意什麼如題 我已經精通C了 指針 指針的指針 linked list, queue, stack binary tree, dfs都難不倒我了X
[問卦] 先有演算法 還是先有資料結構常見的資料結構有 堆疊(Stack)佇列(Queue)陣列(Array)連結串列(Linked List) 樹(Tree)圖(Graph)堆積(Heap)雜湊表(Hash table) 在一段程式的設計 先有考慮演算法? 還是先考慮資料結構?1
Re: [問卦] leetcode medium看完答案還是寫不出來千萬不要背的 原則上科技巨頭會避開網路上找得到的題目 之前被問的問題隔了五個月後才出現在leetcode 上面 要先熟悉基本的資料結構 hash map, stack, tree, trie,
爆
[問卦] 青鳥現場瀕臨完全沒人了 怎麼辦爆
[問卦] 青鳥吹著中國製水冷扇?爆
[問卦] 青島自助餐爆
[問卦] 今日青鳥證明 716真的不簡單吧?爆
[問卦] 現場大概2000人了 你各位再酸啊爆
[問卦] 如果當初核四如期完工使用會怎樣93
[問卦] 健康檢查完 接到醫院的電話 該怎麼辦87
[問卦] 驚! 館長扮九世惡人也太像82
Re: [問卦] 為什麼三立直播不拍人群只拍舞台?72
[問卦] 職業拳手可以KO 3個以上的廟會8+9嗎69
Re: [問卦] 為什麼三立直播不拍人群只拍舞台?56
Re: [新聞] 唐治平突現身下跪 不爽被逼認屍:說了80068
[問卦] 江南七怪的武功到底是什麼等級?50
[問卦] 為什麼青鳥會淪為笑柄?58
Re: [問卦] 青鳥現場瀕臨完全沒人了 怎麼辦57
[問卦] 為什麼三立直播不拍人群只拍舞台?48
[問卦] 企鵝妹登上長城了,超級壯觀50
[問卦] 這兩天是不是在蹲等星期五大會師?46
[問卦] 法國博愛座有優先順序: 75歲老人排最後?爆
[問卦] 新青安五年後哭的會是誰?45
[問卦] 熱搜第1:尹錫悅稱再不生娃韓國會走向滅絕46
[問卦] 明天立院18:00前就表決完 那小鳥們要幹嘛41
[問卦] 孫安佐在台灣還能交到正妹女友嗎?45
Re: [新聞] 快訊/郭智輝宣布每個月公告用電數據 「42
[問卦] 外匯交易者是什麼新產業嗎?39
[問卦] 什麼飼料可以讓大家願意成為青鳥?38
[問卦] 今日青鳥人數,是不是可以樂觀看台灣?38
[問卦] 四叉貓這次怎麼沒有去算人數?29
[問卦]步入40歲大叔 中午吃415,PR多少?38
Re: [新聞] 台中兒掛急診返家遭輾!母目睹死亡過程