日記20220503

LeetCode Algorithem Assign Cookie C++

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int child = 0, cookie = 0;
        while (child < g.size() && cookie < s.size()){
            if (g[child] <= s[cookie]) ++child;
            ++cookie;
        }
     return child;   
    }
};

Python

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        children = len(g)
        cookies = len(s)
        i = j = 0
        while i < children and j < cookies:
            if g[i] <= s[j]:  # cookie j is big enough for child i
                i += 1
            j += 1
        return i
        

Candy C++

class Solution {
public:
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        if (size<2) {
            return size;
        }
        vector<int> num(size,1);
        for (int i = 1; i < size; ++i){
            if (ratings[i] > ratings[i-1]){
                num[i] = num[i-1] +1;
            }
        }
        for (int i = size - 1; i >0; --i) {
            if (ratings[i] < ratings[i-1]){
                num[i-1] = max(num[i-1], num[i] + 1);
            }
        }
        return accumulate(num.begin(), num.end(), 0);
    }
};

Python

class Solution:
    def candy(self, ratings: List[int]) -> int:
        size = len(ratings)
        if size <2:
            return size
        num = [1]*size
        for i in range(1,size):
            if ratings[i] > ratings[i-1]:
                num[i] = num[i-1] + 1
        for i in range(len(ratings)-1, 0, -1):
            if ratings[i-1] > ratings[i]:
                num[i-1] = max(num[i] + 1,num[i-1])
        return sum(num)

435. Non-overlapping Intervals C++

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return 0;
        }
        int n = intervals.size();
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){
            return a[1] < b[1];
        });
        int removed = 0, prev = intervals[0][1];
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] < prev) {
                ++removed;
            } else {
                prev = intervals[i][1];
            }
        }
        return removed;
    }
};

Python

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 0:
            return 0
        n = len(intervals)
        intervals.sort()
        removed = 0
        prev = intervals[0][1]
        for i in range(1,n):
            if intervals[i][0] < prev:
                removed+=1
                prev = min(prev,intervals[i][1])
            else:
                prev = intervals[i][1]
        return removed
        

Can Place Flowers C++

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        if (n == 0) return true;
        for (int i = 0; i < flowerbed.size(); i ++) {
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.size() - 1 || flowerbed[i + 1] == 0)) { // can place?
                -- n;
                if (n == 0) return true;
                flowerbed[i] = 1; // place!
            }
        }
        return false;
    }
};

Python

class Solution:
     def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count, prev = 0, 0

        for cur in flowerbed:
            if cur == 1:
                if prev == 1: # violation!
                    count -= 1
                prev = 1
            else:
                if prev == 1: # can't plant
                    prev = 0 
                else:
                    count += 1
                    prev = 1 # the cur plot gets taken
            
        return count >= n

452. Minimum Number of Arrows to Burst Balloons C++

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end());
        
        int mini = points[0][1];
        int arrow = 1;
        for(int i=1; i<points.size(); i++)
        {   
            mini = min(points[i][1], mini);
            if(mini < points[i][0])
            {
                mini = points[i][1];
                arrow++;
            }
        }
        
        return arrow;
    }
};

Python

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort()
        cur_end = -math.inf
        res = 0
        
        for start, end in points:
            if cur_end >= start:
                cur_end = min(cur_end, end)
            else:
                res += 1
                cur_end = end
        
        return res