[LeetCode] #70. Climbing Stairs
題目
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
參考 Solution 區的 java 解
Approach 1: Brute Force
python 3 實作（失敗）：
class Solution:
def climbStairs(self, n: int) -> int:
return self.climb(0, n)
def climb(self, current_position, n):
if current_position > n:
return 0
elif current_position == n:
return 1
return self.climb(current_position + 1, n) + self.climb(current_position + 2, n)
執行結果：
Time Limit Exceeded
Last executed input: 38
Approach 2: Recursion with Memoization
自己的 python 3 實作：
class Solution:
def __init__(self):
self.cache = {1: 1, 2: 2, 3: 3}
def climbStairs(self, n, current_position=0):
if current_position > n:
return 0
elif current_position == n:
return 1
elif self.cache.get(n - current_position) is not None:
return self.cache[n - current_position]
self.cache[n - current_position] = self.climbStairs(n, current_position + 1) + self.climbStairs(n, current_position + 2)
return self.cache[n - current_position]
效能：
Runtime: 28 ms, faster than 81.22% of Python3 online submissions for Climbing Stairs.
Memory Usage: 14.2 MB, less than 42.66% of Python3 online submissions for Climbing Stairs.
Approach 3: Dynamic Programming
自己的 python 3 實作：
class Solution:
def __init__(self):
self.cache = {1: 1, 2: 2, 3: 3}
def climbStairs(self, n):
for i in range(4, n + 1):
self.cache[i] = self.cache[i-1] + self.cache[i-2]
return self.cache[n]
效能：
Runtime: 24 ms, faster than 94.73% of Python3 online submissions for Climbing Stairs.
Memory Usage: 14 MB, less than 97.76% of Python3 online submissions for Climbing Stairs.
Approach 4: Fibonacci Number
自己的 python 3 實作：
class Solution:
def climbStairs(self, n):
if n < 3:
return n
first = 1
second = 2
for i in range(3, n + 1):
second = first + second
first = second - first
return second
效能：
Runtime: 24 ms, faster than 94.73% of Python3 online submissions for Climbing Stairs.
Memory Usage: 14.3 MB, less than 42.66% of Python3 online submissions for Climbing Stairs.
Approach 5: Binets Method
參考資料：Binet's Formula using Linear Algebra | Fibonacci Matrix
自己的 python 3 實作（時間 O(n)）：
import copy
class Solution:
def climbStairs(self, n):
return self.exponential_of_q(n)[0][0]
def exponential_of_q(self, n):
q = [[1, 1], [1, 0]]
temp = copy.deepcopy(q)
result = copy.deepcopy(q)
for _ in range(n-1):
for i in range(2):
for j in range(2):
result[i][j] = q[i][0] * temp[0][j] + q[i][1] * temp[1][j]
temp = copy.deepcopy(result)
return result
效能：
Runtime: 40 ms, faster than 13.43% of Python3 online submissions for Climbing Stairs.
Memory Usage: 14.3 MB, less than 11.00% of Python3 online submissions for Climbing Stairs.
自己的 python 3 實作（時間 O(log n)）：
class Solution:
def climbStairs(self, n):
return self.pow_of_q(n)[0][0]
def pow_of_q(self, n):
q = [[1, 1], [1, 0]]
result = [[1, 0], [0, 1]]
while n > 0:
if n % 2 == 1:
result = self.multiply(result, q)
n = n // 2
q = self.multiply(q, q)
return result
def multiply(self, a, b):
result = [[None, None], [None, None]]
for i in range(2):
for j in range(2):
result[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
return result
效能：
RRuntime: 32 ms, faster than 53.92% of Python3 online submissions for Climbing Stairs.
Memory Usage: 14.3 MB, less than 42.66% of Python3 online submissions for Climbing Stairs.
Approach 6: Fibonacci Formula
自己的 python 3 實作：
import math
class Solution:
def climbStairs(self, n):
sqrt5 = math.sqrt(5)
numerator = pow((1 + sqrt5) / 2, n+1) - pow((1 - sqrt5) / 2, n+1)
return math.floor(numerator / sqrt5)
目前還不確定小數點的地方到底是怎麼處理的，覺得有點害怕⋯⋯
效能：
Runtime: 28 ms, faster than 81.22% of Python3 online submissions for Climbing Stairs.
Memory Usage: 14.2 MB, less than 71.85% of Python3 online submissions for Climbing Stairs.
Comments
Post a Comment