[LeetCode] 502. IPO

https://leetcode.com/contest/leetcode-weekly-contest-18a/problems/ipo/

Solution:
The profits are the pure profits, which means the costs have already been taken into account. Since this question is looking for the maximum profit, we can first sort the projects based on their costs. In order to keep the information of the corresponding profits, we need a pair structure to connect them. Then for all the projects that are available right now(costs smaller than the capital in hand), we can choose the one with maximum profit. Then we need to update the capital, which will possible make more projects available (that were not previously.) Then we can repeat the above processes starting with find the maximum profit among the projects available, until reaching k projects or no more projects available.

Code:

class Solution {
public:
    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
        int res = W, l = Profits.size();
        vector<pair<int, int>> v;
        for(int i=0; i<l; ++i) v.push_back(make_pair(Capital[i], Profits[i]));
        sort(v.begin(), v.end());
        priority_queue<int> q;//q.top() is the maximum;
        int i = 0;
        for(; i<l; ++i){
            if(v[i].first<=res) q.push(v[i].second);
            else break;
        }
        while(q.size()&&k){
            int t = q.top();
            q.pop();
            res +=t;
            --k;
            for(; i<l; ++i){
                if(v[i].first<=res) q.push(v[i].second);
                else break;
            }
        }
        return res;
    }
};

[LeetCode] 495. Teemo Attacking

https://leetcode.com/contest/leetcode-weekly-contest-17/problems/teemo-attacking/

Solution:
This question should be an easy level question. The only thing need to do is to compare the difference of the adjacent elements in the array with that of the duration time. If larger, then it will take duration time to recover; if smaller, it will take the difference.

Code:

class Solution {
public:
    int findPosisonedDuration(vector<int>& timeSeries, int duration) {
        int res = duration, l = timeSeries.size();
        if(l == 0) res = 0;
        for(int i=1; i<l; ++i){
            int t = timeSeries[i]-timeSeries[i-1];
            res += t>=duration?duration:t;
        }
        return res;
    }
};

486. Max Consecutive Ones II

https://leetcode.com/problems/max-consecutive-ones ii/
This is the following question of 485. If for most one 0 can be flipped to 1, then what is the max consecutive 1s?

Solution:
Nee two variables. One for the previous length of 1s, which may be used when there is only one 0 existing between 1s. The other is the count of 1s after 0.

Code:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, l = nums.size(), c1 = 0, pre = 0;//c1 is the counting of 1s.
        for(int i=0; i<l; ++i){
            ++pre;// the counting for previous 1s.
            ++c1;
            if(nums[i] == 0){
                c1 = pre;
                pre = 0;
            } 
            res = max(res, c1);
        }
        return res;
    }
};

485. Max Consecutive Ones

https://leetcode.com/problems/max-consecutive-ones/

Solution:
It is an easy question. If element is 1, count+1; otherwise, count = 0. Update res for each loop.

Code:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, l = nums.size();
        for(int i=0; i<l; ++i){
            int t = i;
            while(t<l && nums[t] == 1) ++t;
            res = max(res, t-i);
            i = t;
        }
        return res;
    }
};

Another way to code:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, l = nums.size(), c1 = 0;//c1 is the counting of 1;
        for(int i=0; i<l; ++i){
            ++c1;
            if(nums[i] == 0) c1 = 0;
            res = max(res, c1);
        }
        return res;
    }
};