胖達-Panda
🐶:interviewer
🐼:interviewee
🐶:題目會給你一組數值,希望你把所有的組合找出來,組合有都是三個數值所組成,三個數值的總和為 。請注意你的答案不能有重複的組合。
🐶:輸入最少有 個數值,最多有 個。數值的值大小最小為,最大為。
🐶:請問你對題目有疑問嗎?
🐼:有,我想請問輸入的數值有經過排序嗎?
🐶:沒有,題目預設輸入的數值沒有經過排序。
🐼:好的,爲了確認我對題目的理解,我想用一個例子説明
🐼:請問我有理解錯題目嗎?
🐶:沒有,你可以開始寫你的程式了。
🐼:在寫程式之前,我想先講一下我的想法。
🐼:最直觀的解法是用三個迴圈,把所有組合列舉出來,然後用一判斷式判斷三個數值的總和是否為。
🐼:至於重複的組合,我們可以先把輸入的數值進行排序,然後用 把答案存起來,防止加入重複組合。
🐶:你用三個迴圈把所有組合列舉出來是可以解決我們的題目。但以實務層面來説,輸入資料十分大時,程式的效能會很差。請問你有辦法解決嗎?
🐼:的確,用三個迴圈的時間複雜度是 。我的想法是用排序過的數值所提供給我們的資訊,先用一個迴圈把第一個數值選出來,然後用雙指標把第二,三個數值給找出來。
🐼:這樣時間複雜度是 。
🐶:很好,那如果我們今天不能對輸入的數值做排序,你有辦法解決問題嗎?
🐼:那我們可以用Hash Table來做,但空間複雜度也會增加。
針對 interviewer 的檢討:
針對 interviewee 的檢討:
針對 interviewer 的檢討
針對 interviewee 的檢討
vector
延伸閱讀: 3sum|4sum|ksum
🐶:題目會給你一個二元樹的根節點 和 目標數 。希望你可以找出根節點到葉節點的路徑,葉節點為沒有子節點的節點。
🐶:請注意路徑的所通過的節點值總和為 時回傳 ,否則回傳 。
🐶:二元樹的節點定義你可以參考這裏。
🐶:請問你對題目有疑問嗎?
🐼:目前沒有,那我想用這裏的例子來驗證我對題目的理解。
🐼:我另外再自己舉例説明。
🐼:請問我有理解錯題目嗎?
🐶:沒有,你可以開始寫你的程式。
🐼:在寫程式之前,我想先講一下我的想法。
🐼:我會先判斷節點是否為葉節點,如果不是的話就把目標數減掉節點的值,把減完的數值和子節點的值存到佇列。遇到葉節點時會比對減完的數值和子節點的值是否相同。佇列爲空時演算法結束。
🐶:你這邊使用了迭代的做法,請問你可以用遞迴的方式處理嗎?
🐼:可以,其實用遞迴和迭代的慨念差不多,但程式碼會簡潔很多。
針對 interviewer 的檢討:
針對 interviewee 的檢討:
程式碼的調整:
針對 interviewee 的檢討:
延伸閲讀:
模擬面試連結: 9. Palindrome Number(英)
🐶:In this question, you are given an integer x, return true if x is a palindrome integer.
🐶:An integer is a palindrome when it reads the same backward as forward.
🐶:For example, 121 is a palindrome while 123 is not.
🐶:Do you have any questions about this question?
🐼:I think no. I want to use one example to check my understanding about this question
🐼:Am I correct about this quetion?
🐶:Yeah, I think you are right. You can start codding now.
🐼:Before I start my coding, I want to explain my appoach to this problem.
🐼:I will first change the input number into string format.Then, I will reverse the string and check if it is same.
🐶:So your first appoach is to change the integer to string format. Can you solve the problem by not changing it to string?
🐼:Yes, we can check the number digit by digit.
🐼:Seems that I fail to deal with negative numbers.
針對 interviewer 的檢討:
針對 interviewee 的檢討:
相關閲讀材料: