Best Time to Buy and Sell Stock IV
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 k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
----------------------------------------------------------------------------- You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Solution #1, global[i][j] has the max profit at at most j transaction in i days, local[i][j] has the max profit at at most j transaction in i + 1 days and the last transaction must sell at ith day
local[i][j] = max(global[i -1][j - 1] + max(diff,0), local[i - 1][j] + diff)
global[i][j] = max(global[i - 1][j],local[i][j])
local[i - 1][j] + diff推导：
prices[i] - prices[i - 2] = (prices[i - 1] - prices[i - 2]) + (prices[i] - prices[i - 1])
reference: http://blog.csdn.net/linhuanmars/article/details/23236995
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size() == 0 || k == 0) return 0;
if (k > prices.size()) {
return basicSol(prices);
}
vector<vector<int> > local(prices.size(),vector<int>(k + 1,0));
vector<vector<int> > global(prices.size(),vector<int>(k + 1,0));
for (int i = 1; i < prices.size(); i++) {
for (int j = 1; j <= k; j++) {
int diff = prices[i] - prices[i - 1];
local[i][j] = max(global[i -1][j - 1] + max(diff,0), local[i - 1][j] + diff);
global[i][j] = max(global[i - 1][j],local[i][j]);
}
}
return global[prices.size() - 1][k];
}
int basicSol(vector<int>& prices) {
int res = 0;
for (int i = 1; i < prices.size(); i++) {
res += max(0,prices[i] - prices[i - 1]);
}
return res;
}
};
Solution #2, space optimization
'cause of global[j - 1], inner loop goes backwards
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size() == 0 || k == 0) return 0;
if (k > prices.size()) {
return basicSol(prices);
}
vector<int> local(k + 1,0);
vector<int> global(k + 1,0);
for (int i = 1; i < prices.size(); i++) {
int diff = prices[i] - prices[i - 1];
for (int j = k; j > 0; j--) {
local[j] = max(global[j - 1] + max(diff,0), local[j] + diff);
global[j] = max(global[j],local[j]);
}
}
return global[k];
}
int basicSol(vector<int>& prices) {
int res = 0;
for (int i = 1; i < prices.size(); i++) {
res += max(0,prices[i] - prices[i - 1]);
}
return res;
}
};
Count Primes
Description:
Count the number of prime numbers less than a non-negative number, n.
---------------------------------------------------------------------------details is on OJ
class Solution {
public:
int countPrimes(int n) {
vector<bool> isPrime(n, true);
for (int i = 2; i * i < n; i++) {
if (!isPrime[i]) continue;
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
};
Rotate Array
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array
[1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Related problem: Reverse Words in a String II
--------------------------------------------------------------- 三步翻转
class Solution {
public:
void rotateHelper(vector<int>& nums, int start, int end) {
for (int i = 0; i < (end - start + 1) / 2; i++) {
int temp = nums[i + start];
nums[i + start] = nums[end - i];
nums[end - i] = temp;
}
}
void rotate(vector<int>& nums, int k) {
k %= nums.size();
rotateHelper(nums,0,nums.size() - k - 1);
rotateHelper(nums,nums.size() - k, nums.size() - 1);
rotateHelper(nums,0,nums.size() - 1);
}
};
Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).
Follow up:
If this function is called many times, how would you optimize it?
If this function is called many times, how would you optimize it?
Related problem: Reverse Integer
----------------------------------
read: http://articles.leetcode.com/2011/08/reverse-bits.html
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t rt = 0;
for (int i = 0; i < 32; i++) {
rt <<= 1;
if (n & 1) {
rt += 1;
}
n >>= 1;
}
return rt;
}
};
Number of 1 Bits
only count ones, not zeros
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n) {
n = n & n - 1;
count++;
}
return count;
}
};
House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
-------------------------------------------------DP, dp[i] has the max profit [0 : i] and i is robbed
O(n) space
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n + 2,0);
for (int i = n - 1; i >= 0; i--) {
dp[i] = max(nums[i] + dp[i + 2],dp[i + 1]);
}
return dp[0];
}
};
递归：发现重复子问题，所以DP
int rob(vector<int> &houses,int i) {
if (i == houses.size()) return 0;
if (i == houses.size() - 1) {
return houses[i];
}
return max(houses[i] + rob(houses,i + 2),rob(houses,i + 1));
}
Optimized, O(1) space
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
int pre1 = 0,pre2 = 0;
for (int i = n - 1; i >= 0; i--) {
int cur = max(nums[i] + pre2,pre1);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
};
No comments:
Post a Comment