The leecode_cplusplus from hujianglang

leecode_cplusplus's People

Contributors

Stargazers

Watchers

leecode_cplusplus's Issues

C++ Leecode

这里是学习笔记，参考LeetCode101:和你一起轻松刷题(C++）
作者：高畅（Chang Gao）
再次表示感谢

贪心算法例子-孩子分饼干问题

算法解释：
贪心算法的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。

int findContentChildren(vector<int>& children, vector<int>& cookies)
{
	sort(children.begin(), children.end());
	sort(cookies.begin(), cookies.end());
	int child = 0, cookie = 0;
	while (child < children.size() && cookie < cookies.size())
	{
		if (children[child] <= cookies[cookie]) ++child;
		cookie++;
	}
	return child;
}

2,分糖果问题
//分糖果问题
int cany(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);//std::accumulate方便求和
}

3,区间问题：Non-overlapping Intervals(Medium)
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 total = 0, prev = intervals[0][1];
	for (int i = 1; i < n; i++) {
		if (intervals[i][0] < prev)
			++total;
		else
			prev = intervals[i][1];
	}
	return total;
}

Recommend Projects