Authored by Tony Feng
Created on April 19th, 2022
Last Modified on April 19th, 2022
Task 1 - Q10,I. 斐波那契数列
Question
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。
斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), N > 1
答案需要取模 1e9+7（1000000007）
Solution 1
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def fib(self, n: int) -> int:
MOD = 10 ** 9 + 7
if n <= 1 : return n
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = (dp[i-1] + dp[i-2]) % MOD
return dp[n]
|
Solution 2
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def fib(self, n: int) -> int:
MOD = 10 ** 9 + 7
if n <= 1: return n
p, q, r = 0, 0, 1
for i in range(2, n + 1):
p = q
q = r
r = (p + q) % MOD
return r
|
Explanation
- Solution 1 & 2 use the same idea, dynamic programming. However, solution 2 is more spatially-efficient.
- Time Complexity: O(N)
- Space Complexity
- Solution 1: O(N)
- Solution 2: O(1)
Task 2 - Q10,II. 青蛙跳台阶问题
Question
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法?
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution: # Recursion
def numWays(self, n: int) -> int:
if n <= 1: return 1
MOD = 10 ** 9 + 7
buffer = [-1] * (n+1) # Avoid repeated calculation
buffer[0], buffer[1] = 1, 1
def recur(num):
if buffer[num] != -1:
return buffer[num]
else:
res = (recur(num-1) + recur(num-2)) % MOD
buffer[num] = res
return res
return recur(n)
|
Solution 2
1
2
3
4
5
6
7
|
class Solution: # DP
def numWays(self, n: int) -> int:
a, b = 1, 1
MOD = 10 ** 9 + 7
for _ in range(n):
a, b = b, (a + b) % MOD
return a
|
Explanation
- Solution1
- Time Complexity: O(N)
- Space Complexity: O(N)
- Solution2
- Time Complexity: O(N)
- Space Complexity: O(1)
Task 3 - Q63. 股票的最大利润
Question
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
输入: [7,1,5,3,6,4], 输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
Solution 1
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1: return 0
dp = [0] * len(prices)
minP = prices[0]
for i in range(1, len(prices)):
dp[i] = max(dp[i-1], prices[i]-minP)
minP = min(minP, prices[i])
return dp[-1]
|
Solution 2
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1: return 0
minPrice, maxProfit = float("+inf"), 0
for price in prices:
minPrice = min(minPrice, price)
maxProfit = max(maxProfit, price - minPrice)
return maxProfit
|
Explanation
- Time Complexity: O(N)
- Space Complexity
- Solution 1: O(N)
- Solution 2: O(1)