貢獻者: 瑪奇朵 - Macchiato
🧔:interviewer
👶:interviewee
Given the root of a binary tree and an integer targetSum
, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum
. A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
🧔:你好,歡迎來到這場面試。我們蒐集了不同工作情境中會用到的演算法,整理成以下問題,麻煩你依據這些題目描述自己的想法並實作出來。
🧔:第一個問題準備了數狀結構的搜尋問題,探討在一個樹狀的資料結構中,我們要如何找到符合條件的搜尋路徑並獲取路徑上的資料。以這個情境來說,我們想要在給定的樹狀資料中尋找是否存在符合目標總和的路徑。
👶:(重複題目並舉例說明)
👶:初步的想法是用遞迴的方式去做。當我碰到一個節點的時候,我會判斷他是不是葉節點,如果已經是的話,我會去判斷路徑加上當前節點的值是否等於targetSum
。如果不是的話,我會用遞迴的方式去計算他的左右子樹,是否有存在相加後符合targetSum
的路徑。
🧔:好的。想請問樹狀的搜尋除了DFS還有其他的嗎?為甚麼會選用DFS的方式呢?
👶:除了深度優先搜尋之外還有廣度優先搜尋(BFS),BFS會從根節點逐步往外找距離較近的節點。但這裡要計算的是從根節點到葉節點的路徑,所以如果使用BFS會需要存取許多走到一半的路徑總和。DFS的優點就是不用存取這些數值,不須花費額外的記憶體空間。
🧔:好的。可以開始你的實作,樹狀結構可以參考以下的程式碼。
🧔:能不能解釋你的解法是怎麼實現DFS的呢?
👶:我的解法是先判斷左子樹再判斷右子樹,每次會不停的找左子樹,再回到上一層做右子樹的判斷,因此是DFS的實現方式。
🧔:請問上述作法時間複雜度是什麼等級呢?
👶:每個點都會遍歷過一次,因此時間複雜度是 O(n)。
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
🧔:好的,接下來這題是一個關於已排序數列的搜尋問題。在一個非嚴格遞增的數列中,希望找到目標元素的位置。接下來要麻煩你思考這個問題。
👶:(重複題目並舉例說明)
👶:最直接的想法是用一個 for 去遍歷這個非嚴格遞增序列的所有數值,直到找到數值為止。但題目要求是在時間複雜度 O(log n) 之內,所以並不符合題目的要求。
🧔:是的,那你能不能提出其他更好的作法呢?
👶:我再來有想到的方法是使用二分搜尋法的方式,可以讓時間複雜度保持在O(log n) 之內。方法上會先取出中間的索引值,再來會去判斷 target 是否大於索引值,大於的話就會將搜尋範圍集中在索引值之後,反之集中在索引值之前,每次可以減少一半的可能性,所以可以讓時間複雜度保持在 O(log n) 之內。
🧔:沒有其他問題的話,可以請你開始實現這段程式碼
👶:(舉例說明程式碼的運作)
🧔:請描述一下數字重複會如何影響時間複雜度呢?
👶:最差的狀況是當整個數列都等於 target 值的時候,他就必須從中間的索引值往左往右找,時間複雜度會是 O(n)。最佳狀況是每個數值都出現一次,且在 binary search 的第一個搜尋到的位置,也就是中間位置(口誤為midtern),時間複雜度會是 O(1)。對 binary search 來說,最差的狀況是數值出現在,舉例來說最左右兩邊時是最糟,必須要找 log n 次。
🧔:基於你剛才的做法,將題目稍稍修改一下。如果將這段程式碼改成插入目標值的話並回傳應插入的索引值的話,應該怎麼修改呢?(已經出現在裡面的元素,就插入在已有元素的最後面)
👶:(邊修改邊解釋)
👶:(舉例說明程式碼的運作)
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
🧔:There is a final question for you. You have to climb n-step stairs and you can only take one or two steps at a time. How many combinations of steps can you take to get to the top of the stairs?
👶:So, I can only take one or two steps for a time to climb up n-step stairs.
(舉例說明)
👶:Obviously, there is an easy approach using a recursive method. However, the time complexity of the recursive method is O(2 to the power of n) that may result in a runtime error.
🧔:And any other approach?
👶:Sure. The drawback of the recursive method is that it takes so much time to calculate the same question. I would like to use a vector to record the number of distinct ways to climb the stairs from one-step to n-step.
🧔:I see. And what is the time complexity of this approach? How about space complexity?
👶:The time complexity is O(n) and the space complexity is O(n).
🧔:Is there anything you can do to improve your answer?
👶:Ok. Because I only have to get the number of way to climp up n-step stiars, so I can replace it with 3 integers to get the final answer.
🧔:Ok. Thanks for joining the interview. I will contact you when the results are available. Bye.
left+right
不會造成 overflow(),所以 15:24 的地方其實也可以寫 left+right
就好。