久違解題時間，總覺得不練習會生疏阿！
於是從 LeetCode Easy 最後一題開始，沒有理由，只是因為忘記上次做到第幾題，但是我知道一定沒有做到最後一題，所以最後一題先。
LeetCode 題目連結
https://leetcode.com/problems/n-th-tribonacci-number/
題目
The Tribonacci sequence Tn is defined as follows:
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given
n, return the value of Tn.
Example 1:
Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4
Example 2:
Input: n = 25 Output: 1389537
Constraints:
0 <= n <= 37- The answer is guaranteed to fit within a 32-bit integer, ie.
answer <= 2^31 - 1.
題目說明
T0 的時候是 0，T1 的時候是 1，T2 的時候是 1，然而 T3 以後則為 T3 以前的累加結果。
n 的上限是 37 ，則答案小於 2 的 31 次方減 1。
超時作法
第一直覺是認為這題用遞迴解，原本以為是為了考遞迴，後來跑一遍 Test 有到他要的結果，但沒想到超過時間了。總共跑了 八秒。
Kotlin
class Solution {
fun tribonacci(n: Int): Int {
if(n==0)
return 0
if(n == 1 || n == 2)
return 1
return tribonacci(n-2)+tribonacci(n-1)+tribonacci(n-3)
}
}
Accept 作法
後來選擇拿掉遞迴用迴圈去完成，終於通過了。時間複雜度為 O(n) 。
Kotlin
class Solution {
fun tribonacci(n: Int): Int {
var sum = 0
var n1 = 0
var n2 = 1
var n3 = 1
if(n == 0){
return n1
}
if(n == 1 || n == 2)
return n2
for(i in 3..n){
sum = n1 + n2 + n3
n1 = n2
n2 = n3
n3 = sum
}
return sum
}
}
更多 LeetCode 相關資源
複習程式面試書籍
除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。
沒有留言:
張貼留言