ง่าย 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

Tribonacci

Return the nth tribonacci number, where each term is the sum of the three before it.

สิ่งที่คุณจะได้เรียนรู้

  • Compute a sequence iteratively
  • Keep only the last few terms
  • Handle the starting terms directly

โจทย์

ดูฉบับแปล

The tribonacci numbers extend the Fibonacci idea to three terms: T(0) = 0, T(1) = 0, T(2) = 1, and from then on T(n) = T(n − 1) + T(n − 2) + T(n − 3). The sequence goes 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, …

Implement tribonacci(n).

Input

n: The index of the term, starting at 0.

Output

Return T(n). Only the last three terms are needed at any time, so a loop with three variables is enough.

เงื่อนไข

0 ≤ n ≤ 74

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
n = 7

ผลลัพธ์ที่คาดหวัง:
expected = 13
อินพุต:
long long n = 7;

ผลลัพธ์ที่คาดหวัง:
long long expected = 13;
อินพุต:
long n = 7;

ผลลัพธ์ที่คาดหวัง:
long expected = 13;

คำอธิบาย

The terms are 0, 0, 1, 1, 2, 4, 7, 13, so T(7) = 13.

ตัวอย่างที่ 2
อินพุต:
n = 2

ผลลัพธ์ที่คาดหวัง:
expected = 1
อินพุต:
long long n = 2;

ผลลัพธ์ที่คาดหวัง:
long long expected = 1;
อินพุต:
long n = 2;

ผลลัพธ์ที่คาดหวัง:
long expected = 1;

คำอธิบาย

T(2) is the first 1 in the sequence: 1.

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

Return the first three terms directly.

คำใบ้ 2

Keep three variables and shift them along each step.

คำใบ้ 3

A recursive solution without memory repeats work and is far too slow.

ความซับซ้อนที่คาดหวัง

O(n) time, O(1) extra space

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก