-
第 11 樓 / webdriver
- 時間: 2014-9-29 23:35算法問題推薦解法來了...
1. At the beginning of the ascending order: buy.
At the ending of the ascending order: sell.
2. For ascending order [1,2,4], (4 - 1) == (2 - 1) + (4 - 2).
解法（Python）
代碼: class Solution:
def maxProfit(self, prices):
profit = 0
for i in range(len(prices) - 1):
profit += max(0, prices[i + 1] - prices[i])
return profit -
-
- 時間: 2014-9-29 23:35S算法問題: Best Time to Buy and Sell Stock III
問題描述:
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). -
-
- 時間: 2014-9-29 23:36算法問題推薦解法來了...
dp. max profit = max { l2r[0...i] + r2l[i+1...N-1] }.
0 <= i <= N-1
解法（Python）
代碼: class Solution:
def maxProfit(self, prices):
min_price, max_profit, max_profits = 9223372036854775807, 0, []
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
max_profits.append(max_profit)
max_price, max_profit_after, max_combined_profit = 0, 0, 0
for i in reversed(range(len(prices))):
max_price = max(max_price, prices[i])
max_profit_after = max(max_profit_after, max_price - prices[i])
max_combined_profit = max(max_combined_profit, max_profit_after + max_profits[i])
return max_combined_profit -
- 時間: 2014-9-29 23:36S算法問題: Best Time to Buy and Sell Stock
問題描述:
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock),
design an algorithm to find the maximum profit. -
- 時間: 2014-9-29 23:37算法問題推薦解法來了...
For each element, calculate the max difference with the former elements.
解法（Python）
代碼: class Solution:
def maxProfit(self, prices):
max_profit = 0
min_price = 9223372036854775807
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit -
- 時間: 2014-9-29 23:38
-
- 時間: 2014-9-29 23:39算法問題推薦解法來了...
1. Iterative way (stack). Time: O(n), Space: O(n).
2. Recursive solution. Time: O(n), Space: O(n).
3. Threaded tree (Morris). Time: O(n), Space: O(1).
解法（Python）
代碼: class Solution:
def inorderTraversal(self, root):
res, stack, current = [], [], root
while stack or current:
if current:
stack.append(current)
current = current.left
else:
parent = stack.pop()
res.append(parent.val)
current = parent.right
return res -
- 時間: 2014-9-29 23:41S算法問題: Binary Tree Level Order Traversal II
問題描述:
Given a binary tree, return the bottom-up level order traversal of its nodes' values.
(ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7]
[9,20],
[3],
] -
- 時間: 2014-9-29 23:42算法問題推薦解法來了...
Queue version. On the basis of 'Binary Tree Level Order Traversal', reverse the final vector.
解法（Python）
代碼: class Solution:
def levelOrderBottom(self, root):
if root is None:
return []
res, current = [], [root]
while current:
next, vals = [], []
for node in current:
vals.append(node.val)
if node.left:
next.append(node.left)
if node.right:
next.append(node.right)
current = next
res.insert(0, vals)
return res
# def levelOrderBottom(self, root):
# """ Using a queue is also fine.
# """
# if root is None:
# return []
# current, res = [root], []
# while current:
# vals, length = [], len(current)
# for i in range(length):
# node = current[0]
# vals.append(node.val)
# if node.left:
# current.append(node.left)
# if node.right:
# current.append(node.right)
# current.pop(0)
# res.insert(0, vals)
# return res -
- 時間: 2014-9-29 23:44S算法問題: Binary Tree Level Order Traversal
問題描述:
Given a binary tree, return the level order traversal of its nodes' values.
(ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
Leetcode Hacking Practice -- Solution in Python Part 1
