Wiggle SubsequenceIPO-阿南达文事网

Wiggle Subsequence IPO

Wiggle Subsequence & IPO

题目 376 Wiggle Subsequence
解答
题目 502 IPO
解答
分析

题目 376 Wiggle Subsequence

Medium
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

解答

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int size=nums.size(), f=1, d=1;for(int i=1; i<size; ++i){if(nums[i]>nums[i-1]) f=d+1;else if(nums[i]<nums[i-1]) d=f+1;}return min(size, max(f, d));}
};

以上是高票答案，自己写的代码如下

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if(nums.size()<2){return nums.size();}int iMaxPos(1), iMaxNeg(1);     for(int i=1; i<nums.size(); ++i){            if(nums[i]-nums[i-1] < 0) iMaxNeg = iMaxPos+1;if(nums[i]-nums[i-1] > 0) iMaxPos = iMaxNeg+1;}return max(iMaxNeg, iMaxPos);}
};

题目 502 IPO

Hard
Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given several projects. For each project i, it has a pure profit Pi and a minimum capital of Ci is needed to start the corresponding project. Initially, you have W capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.

Example 1:
Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].

Output: 4

Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
Note:
You may assume all numbers in the input are non-negative integers.
The length of Profits array and Capital array will not exceed 50,000.
The answer is guaranteed to fit in a 32-bit signed integer.

解答

class Solution {
public:int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {priority_queue<int> pqLowW;multiset<pair<int,int> > setUpW;for(int i=0; i<Profits.size(); ++i){if(Capital[i]<=W) pqLowW.push(Profits[i]);else setUpW.insert(make_pair(Capital[i],Profits[i]));}while(k-- && pqLowW.size() ){W += pqLowW.top();pqLowW.pop();for(auto i=setUpW.begin(); setUpW.size()&&(i->first <= W); i=setUpW.erase(i))pqLowW.push(i->second);}return W;}
};

附录高票答案：

    int findMaximizedCapital(int k, int W, vector<int>& P, vector<int>& C) {priority_queue<int> low;      // P[i]'s within current Wmultiset<pair<int,int>> high; // (C[i],P[i])'s' outside current Wfor (int i = 0; i < P.size(); ++i) // initialize low and highif(P[i] > 0) if (C[i] <= W) low.push(P[i]); else high.emplace(C[i], P[i]);while (k-- && low.size()) { W += low.top(), low.pop(); // greedy to work on most profitable firstfor (auto i = high.begin(); high.size() && i->first <= W; i = high.erase(i)) low.push(i->second);}return W;}

分析

解答参考了高票答案，路漫漫其修远兮。针对C++新的功能和容器，自己仍然缺乏灵活应用的经验。套路不够多哦。