-
第 21 樓 / webdriver
- 時間: 2014-9-23 13:00Now comes the solution (in C++) ...
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).
代碼: class Solution {
public:
int maxProfit_1(vector<int> &prices) {
int res = 0;
int buy_i = -1;
for (int i = 1; i < prices.size(); ++i)
{
if (prices[i] > prices[i-1] && buy_i == -1)
{
buy_i = i - 1;
}
else if (prices[i] < prices[i -1] && buy_i != -1)
{
res += prices[i-1] - prices[buy_i];
buy_i = -1;
}
}
if (buy_i != -1)
res += prices[prices.size() - 1] - prices[buy_i];
return res;
}
int maxProfit_2(vector<int> &prices) {
int res = 0;
for (int i = 1; i < prices.size(); ++i)
if (prices[i] > prices[i-1])
res += prices[i] - prices[i-1];
return res;
}
};
-
-
- 時間: 2014-9-23 13:03Problem Name: Best Time to Buy and Sell Stock III
Description:
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-23 13:04Now comes the solution (in C++) ...
dp. max profit = max { l2r[0...i] + r2l[i+1...N-1] }.
0 <= i <= N-1
代碼: class Solution {
public:
int maxProfit(vector<int> &prices) {
int N = prices.size();
if (N <= 1) return 0;
int l2r[N], r2l[N];
l2r[0] = 0;
r2l[N-1] = 0;
int minn = prices[0];
for (int i = 1; i < N; ++i)
{
minn = min(minn, prices[i]);
l2r[i] = max(l2r[i-1], prices[i] - minn);
}
int maxx = prices[N-1];
for (int i = N-2; i >= 0; --i)
{
maxx = max(maxx, prices[i]);
r2l[i] = max(r2l[i+1], maxx - prices[i]);
}
int res = l2r[N-1];
for (int i = 0; i < N-1; ++i)
res = max(res, l2r[i] + r2l[i+1]);
return res;
}
};
-
- 時間: 2014-9-23 13:06
-
- 時間: 2014-9-23 13:07Now comes the solution (in C++) ...
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).
代碼: **
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
return inorderTraversal_1(root);
}
vector<int> inorderTraversal_1(TreeNode *root) {
vector<int> res;
stack<TreeNode *> stk;
TreeNode *cur = root;
while (cur || !stk.empty())
{
if (cur)
{
stk.push(cur);
cur = cur->left;
}
else if (!stk.empty())
{
res.push_back(stk.top()->val);
cur = stk.top()->right;
stk.pop();
}
}
return res;
}
vector<int> inorderTraversal_2(TreeNode *root) {
vector<int> res;
inorderTraversalRe(root, res);
return res;
}
void inorderTraversalRe(TreeNode *node, vector<int> &res) {
if (!node) return;
inorderTraversalRe(node->left, res);
res.push_back(node->val);
inorderTraversalRe(node->right, res);
}
vector<int> inorderTraversal_3(TreeNode *root) {
vector<int> res;
TreeNode *cur = root;
while (cur)
{
if (cur->left)
{
TreeNode *prev = cur->left;
while (prev->right && prev->right != cur)
prev = prev->right;
if (prev->right == cur)
{
res.push_back(cur->val);
cur = cur->right;
prev->right = NULL;
}
else
{
prev->right = cur;
cur = cur->left;
}
}
else
{
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
};
-
- 時間: 2014-9-23 13:10Problem Name: Binary Tree Level Order Traversal
Description:
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]
] -
- 時間: 2014-9-23 13:12Now comes the solution (in C++) ...
1. Use queue. In order to seperate the levels, use 'NULL' as the end indicator of one level.
2. DFS.
代碼: /**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode *root) {
return levelOrder_1(root);
}
vector<vector<int> > levelOrder_1(TreeNode *root) {
vector<vector<int> > res;
if (!root) return res;
queue<TreeNode *> q;
q.push(root);
q.push(NULL);
vector<int> level;
while (true)
{
TreeNode *node = q.front(); q.pop();
if (!node)
{
res.push_back(level);
level.clear();
if (q.empty()) break; // end
q.push(NULL);
}
else
{
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
vector<vector<int>> levelOrder_2(TreeNode *root) {
vector<vector<int>> res;
levelOrderRe(root, 0, res);
return res;
}
void levelOrderRe(TreeNode *node, int level, vector<vector<int>> &res)
{
if (!node) return;
if (res.size() <= level) res.push_back(vector<int>());
res[level].push_back(node->val);
levelOrderRe(node->left, level + 1, res);
levelOrderRe(node->right, level + 1, res);
}
};
-
- 時間: 2014-9-23 13:15Problem Name: Binary Tree Level Order Traversal II
Description:
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-23 13:15Now comes the solution (in C++) ...
Queue version. On the basis of 'Binary Tree Level Order Traversal', reverse the final vector.
代碼: /**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int> > levelOrderBottom(TreeNode *root) {
vector<vector<int>> root2leaf;
queue<TreeNode *> q;
if (!root) return root2leaf;
q.push(root);
q.push(NULL); // end indicator of one level
vector<int> level;
while (true)
{
TreeNode *node = q.front(); q.pop();
if (node)
{
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
else
{
root2leaf.push_back(level);
level.clear();
if (q.empty()) break; // CAUTIOUS! infinite loop
q.push(NULL);
}
}
// reverse
reverse(root2leaf.begin(), root2leaf.end());
return root2leaf;
}
}; -
- 時間: 2014-9-23 13:16
Leetcode Hacking Practice -- Solution in C++ Part 1
