@[toc]

Synchronize GitHub here at 👉Github.com/TeFuirnever…

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup
  • Offer (C++ version) series: Offer 05 replace blank
  • Finger Offer (C++ version) series: finger Offer 06 prints linked lists from end to end
  • Sword finger Offer (C++ version) series: sword finger Offer 07 rebuild binary tree
  • Finger Offer (C++ version) series: finger Offer 09 implements queues with two stacks

1, dry

Write a function, input n, to find the NTH term of the Fibonacci sequence (F(n)). The Fibonacci sequence is defined as follows: F(0) = 0, F(1) = 1 F(N) = F(n-1) + F(n-2), where N > 1. The Fibonacci sequence starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers. 1e9+7 (1000000007) is required for the answer. If the initial calculation result is 1000000008, return 1. Example 1: Input: n = 2 Output: 1 Example 2: Input: n = 5 Output: 5 Info: 0 <= n <= 100 Pass count 190,890 Submit count 552,092Copy the code

2. Recursion

Algorithm flow:

  • Transfer equation: that is, the corresponding sequence definition F (n + 1) = F (n) + F (n-1);
  • Initial state: the first two digits are initialized.
  • Return value: the NTH digit of the Fibonacci sequence.
// Interview question 10-I. Fibonacci numbers
// Standard practice
class Solution {
public:
	int fib(int n) {
		int a = 0, b = 1, c = 0;
		for (int i = 0; i < n; ++i)
		{
			a = b, b = c;
			c = (a + b) % 1000000007;
		}
		returnc; }};/ / long long is better
Copy the code

4. Complexity

/* Time complexity O(n), space complexity O(1) */
Copy the code

— — — — — — — — — — — — — — — — — — —

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup
  • Offer (C++ version) series: Offer 05 replace blank
  • Finger Offer (C++ version) series: finger Offer 06 prints linked lists from end to end
  • Sword finger Offer (C++ version) series: sword finger Offer 07 rebuild binary tree
  • Finger Offer (C++ version) series: finger Offer 09 implements queues with two stacks

— — — — — — — — — — — — — — — — — — –

This article is supported by LeetCode, Niuke, the public ha Oh, Zhihu!

Leetcode-cn.com/u/tefuirnev…

blog.nowcoder.net/wsguanxl

Mp.weixin.qq.com/s/bDwxwQfZy…

www.zhihu.com/people/tefu…