跨平台网站开发,做网站排行榜,北京装修公司招聘工长,网站建设用户需求分析455.分发饼干#xff08;easy-自己想得出来并写好#xff09; 假设你是一位很棒的家长#xff0c;想要给你的孩子们一些小饼干。但是#xff0c;每个孩子最多只能给一块饼干。对每个孩子 i#xff0c;都有一个胃口值 g[i]#xff0c;这是能让孩子们满足胃口的饼干的最小尺…455.分发饼干easy-自己想得出来并写好 假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。
示例 1:输入: g [1,2,3], s [1,1] 输出: 1
解释: 你有三个孩子和两块小饼干3个孩子的胃口值分别是1,2,3。 虽然你有两块小饼干由于他们的尺寸都是1你只能让胃口值是1的孩子满足。 所以你应该输出1
思路先将饼干大小和孩子的胃口大小都排序再一一对比...需要注意的是for中的循环条件是饼干不是孩子孩子加一的条件是前一个孩子得到满足之后孩子的下标i才会加一并且一旦这个孩子得到了满足那么饼干的下标j和孩子的下标i均要直接加1进入下一次判断。所以才有了break语句
代码如下
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {int g_len g.size() ;int s_len s.size() ;int i 0 , j 0 ,cnt 0;sort(g.begin(),g.end());sort(s.begin(),s.end());for(j ;js_len ;j){//当饼干满足孩子后孩子才会加一while((ig_len) (s[j]g[i])){i;cnt;break ;//保证一块饼干只给一个孩子}}return cnt ;}
}; 435.无重叠区间hard-自己没什么思路写不了一点 给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。
示例 1:
输入: intervals [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后剩下的区间没有重叠。示例 2:
输入: intervals [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。示例 3:
输入: intervals [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间因为它们已经是无重叠的了。
思路自己想了一下大概只能想到需要排序因为这是一个区间区间怎么排序呢按照边界排序的话排好了之后呢又要怎么做呢后面就不是很明了了。看了一下官方思路结合下面万能网友的评论大概理清楚了直接贴一下评论区的某位网友回答感觉比官方的更容易明白
关于解法二贪心算法的合理性这里作一下补充。其实这里的难点在于理解“为什么是按照右端点排序而不是左端点排序”。官解里对这个描述的非常清楚了这个题其实是预定会议的一个问题给你若干时间的会议然后去预定会议那么能够预定的最大的会议数量是多少核心在于我们要找到最大不重叠区间的个数。 如果我们把本题的区间看成是会议那么按照右端点排序我们一定能够找到一个最先结束的会议而这个会议一定是我们需要添加到最终结果的的首个会议。这个不难贪心得到因为这样能够给后面预留的时间更长。这里补充一下为什么不能按照区间左端点排序。同样地我们把本题的区间看成是会议如果“按照左端点排序我们一定能够找到一个最先开始的会议”但是最先开始的会议不一定最先结束。举个例子 理清楚了算法的思路再进一步完成代码的编写还是不太会这个sort函数的用法搜了一下感觉搜出来的都不太一样有点迷惑反正先整一份正确答案先。 这种情况是使用自定义比较函数对区间进行排序然后自定义的比较函数cmp排序准则是按照区间右端点的升序a[1] b[1]进行排序。因为题目中明确说了区间是一个长度为2的数组所以索引只有0和1索引0指示左端点索引1指示右端点。 这样排序之后就可以按照上面的思路就行进一步操作了排序后的第一个区间肯定是需要保留的遍历后面的区间留下与前面区间没有重合的即可。下面的代码定义的初始右端点是INT_MIN而不是第一个区间的右端点道理是一样的。
class Solution {
public://std::sort 期望一个静态函数或一个函数对象//故作为“自定义比较函数”应该定义为static类型//根据题目intervals是长度为2的数组故索引只有0和1static bool cmp(vectorint a, vectorint b){return a[1] b[1] ;}//vectorvectorint intervals表明intervals是一个二维整数向量int eraseOverlapIntervals(vectorvectorint intervals) {int cnt intervals.size() ;sort(intervals.begin(), intervals.end(), cmp) ;//使用 INT_MIN 宏来表示最小的 32 位整数值int right INT_MIN;for(auto i :intervals){//比较新intervals的左端点与当前intervals的右端点)(right)//若左端点i[0]大于等于right则新的intervals就不需要删除同时更新right值if(i[0]right){right i[1] ;cnt--;}}return cnt ;}}; 看了一下另外的解答方法这里使用的是sort函数的默认排序方法对于一维数组来说就是把数据按照升序排列好但是对于区间来说sort方法的默认排序是按照每个区间的第一个元素起始位置进行升序排序如果起始位置的值是一样的那么就按照第二个位置结束位置进行升序排序。 假设输入的二维数组几个区间为intervals {{1, 3}, {2, 2}, {3, 4}, {1, 2}}那么直接使用下面的sort函数进行排序排列后的结果是intervals{{1, 2}, {1, 3} ,{2, 2}, {3, 4} }。 使用sort函数直接排序之后的进一步处理没有第一种方法那么清晰明了其实思路最后还是一样都是需要不断更新区间的右端点只是上一个右端点是按照升序拍好的只需要看后一个区间和前一个有无重合就可以现在这个需要自己来判断并更新右端点的值【因为排序可能会出现右端点的顺序是上面2324这样交错的】需要理解一下大概讲讲意会一下比如说你使用sort函数排序后得到了这样一组排序好的区间intervals{[1,5],[1,6],[2,3],[3,6],[4,7],[7,8]}按照代码将排序后的第一个区间的右端点初始化为最小右端点也就是right5,然后从第二个区间开始遍历并更新right的值
i1时intervals[1][0]1 right5表明第二个区间是和第一个区间有重合的有重合就需要删除区间所以cntcnt1,那删除哪个区间呢根据上面的思想需要删除右端点大的保留右端点小的区间所以就有了这句”right min(right, intervals[i][1]);“此时right5;
i2时intervals[2][0]2 right5表明第三个区间是和第二个区间有重合的有重合就需要删除区间所以cntcnt2,那删除哪个区间呢根据上面的思想需要删除右端点大的保留右端点小的区间所以此时right3;
i3时intervals[3][0]3 right3表明第四个区间是和第三个区间是没有重合的没有重合就要保留就执行else中的语句更新右端点的值right6此时cnt还是等于2
后面同理不再赘述。最后的结果应该是保留的区间是{[2,3],[3,6],[7,8]},cnt3。画一个上面的那种线段区间图可以看得更清楚。
class Solution {
public:int eraseOverlapIntervals(vectorvectorint intervals) {int cnt 0;//这里排序默认是按照每个区间的第一个元素起始位置进行升序排序//如果起始位置相同则按第二个元素结束位置进行升序排序。sort(intervals.begin(), intervals.end()) ;//将排序后的第一个区间右端点初始化为最小的右端点int right intervals[0][1]; for (int i 1; i intervals.size(); i) {//判断当前区间的左端点是否小于上一个区间的右端点//若小于 则需要删除cnt,同时更新if (intervals[i][0] right) {cnt;right min(right, intervals[i][1]);} else {right intervals[i][1];}}return cnt ;}
};
⭐关于sort函数 std::sort 是 C 标准库中的一个函数用于对指定范围内的元素进行排序。可以通过多种方式使用 std::sort例如按照默认顺序排序或者使用自定义的比较函数来排序。下面是几个使用示例
① 按照默认升序顺序排序该代码的输出是1 2 3 5 7 8
#include iostream
#include vector
#include algorithmint main() {std::vectorint nums {5, 3, 8, 1, 2, 7};std::sort(nums.begin(), nums.end());for(int num : nums) {std::cout num ;}return 0;
}② 按自定义顺序排序降序改代码的输出是8 7 5 3 2 1
#include iostream
#include vector
#include algorithmint main() {std::vectorint nums {5, 3, 8, 1, 2, 7};std::sort(nums.begin(), nums.end(), std::greaterint());for(int num : nums) {std::cout num ;}return 0;
}③ 使用自定义比较函数排序该代码的输出是8 7 5 3 2 1
⭐ 关于这里为什么customCompare函数又不需要定义成静态的不是很明白GPT又说“std::sort 函数并不要求传入的自定义比较函数必须是静态函数”可是第一版本的代码中如果不降传入的cmp函数定义成静态的话运行是会报错的 个人猜测第一版代码中cmp函数是定义在类中的然而这里是一个普通全局函数先这样记一下吧。
#include iostream
#include vector
#include algorithmbool customCompare(int a, int b) {return a b; // 降序排序
}int main() {std::vectorint nums {5, 3, 8, 1, 2, 7};std::sort(nums.begin(), nums.end(), customCompare);for(int num : nums) {std::cout num ;}return 0;
}④ 使用 Lambda 表达式排序该代码的输出是8 7 5 3 2 1
#include iostream
#include vector
#include algorithmint main() {std::vectorint nums {5, 3, 8, 1, 2, 7};std::sort(nums.begin(), nums.end(), [](int a, int b) {return a b; // 降序排序});for(int num : nums) {std::cout num ;}return 0;
}
