购物网站产品做促销能赚钱吗,wordpress提示ftp,外贸平台有哪些电商,南宁关键词排名优化外包455. 分发饼干 假设你是一位很棒的家长#xff0c;想要给你的孩子们一些小饼干。但是#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i#xff0c;都有一个胃口值 g[i]#xff0c;这是能让孩子们满足胃口的饼干的最小尺寸#xff1b;并且每块饼干 j#xff0c;都有… 455. 分发饼干 假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。 对每个孩子 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。 示例 2: 输入: g [1,2], s [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2. 提示 1 g.length 3 * 10(4) 0 s.length 3 * 10(4) 1 g[i], s[j] 2(31) - 1 class Solution {
public:int findContentChildren(vectorint children, vectorint 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;}
}; 问题的核心是尽可能满足更多孩子的胃口每个孩子最多能得到一块饼干每块饼干也只能分给一个孩子给定一个孩子数组children代表每个孩子的胃口值一个饼干数组cookies代表每块饼干的大小求最多有多少孩子能得到饼干满足胃口。
sort(children.begin(), children.end());这行代码将children数组按胃口值从小到大排序。
sort(cookies.begin(), cookies.end());这行代码将cookies数组按饼干大小从小到大排序。
int child 0, cookie 0;初始化两个变量child和cookie分别表示当前考虑到的孩子和饼干的索引。
while (child children.size() cookie cookies.size()) {这个循环继续执行直到所有孩子都被考虑过或所有饼干都被尝试分配。
if (children[child] cookies[cookie]) child;如果当前饼干的大小能满足当前孩子的胃口那么这个孩子被满足移动到下一个孩子。
cookie;无论当前的饼干是否能满足当前的孩子都将考虑下一块饼干。
时间复杂度和空间复杂度
时间复杂度O(nlogn)。主要时间开销来自于排序children和cookies数组假设children和cookies的长度分别为m和n那么时间复杂度为O(mlogm nlogn)。遍历数组的过程时间复杂度为O(mn)所以总体时间复杂度为O(nlogn)这里n是两个数组中较长的那个的长度。
空间复杂度O(1)。除了输入的数组外我们只使用了常数空间。
135. 分发糖果 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求给这些孩子分发糖果 每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。 示例 1 输入ratings [1,0,2] 输出5 解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。 示例 2 输入ratings [1,2,2] 输出4 解释你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果这满足题面中的两个条件。 提示 n ratings.length 1 n 2 * 10(4) 0 ratings[i] 2 * 10(4) class Solution {
public:int candy(vectorint ratings) {int size ratings.size();if (size 2) {return size;}vectorint 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 可以很方便地求和}
}; 定义变量 size 为评分数组 ratings 的长度。
如果 size 小于 2直接返回 size。因为如果只有一个孩子那他就是唯一的获得糖果的人直接返回1如果没有孩子返回0。
初始化一个大小与 ratings 相同值全为1的数组 num。这一步确保了每个孩子至少得到一颗糖果。
第一次遍历从左到右遍历 ratings。
如果当前孩子i对应孩子的评分高于左边的孩子ratings[i] ratings[i - 1]则当前孩子得到的糖果数应该比左边的孩子多一颗num[i] num[i - 1] 1。
第二次遍历从右到左遍历 ratings。
如果当前孩子i-1对应孩子的评分高于右边的孩子ratings[i] ratings[i - 1]则左边的孩子得到的糖果数应该是其原本的数目和右边孩子的糖果数加一中的较大值num[i - 1] max(num[i - 1], num[i] 1)。
最后使用 accumulate 函数对 num 数组进行求和得到总共需要的糖果数并返回这个值。accumulate 函数起始值为0意味着从0开始累加 num 数组中所有元素的值。
accumulate函数
accumulate 函数是 C 标准库中 numeric 头文件提供的一个非常实用的数值累加函数。它用于计算一个给定范围内所有元素的累加和或者在提供了自定义操作时按照该操作进行累加。accumulate 的基本用法是计算序列的总和但通过自定义加法操作它也可以用于更复杂的累加操作如累乘。
基本用法
基础版本的 accumulate 接受三个参数序列的开始迭代器、结束迭代器和累加的初始值。如果不指定操作则默认进行加法操作。下面是一个简单的例子 #include numeric // 引入accumulate的头文件
#include vectorstd::vectorint v {1, 2, 3, 4, 5};
int sum std::accumulate(v.begin(), v.end(), 0); // 计算总和
在这个例子中accumulate 从 0 开始将 v 中的每个元素相加计算出总和为 15。
使用自定义操作
accumulate 还允许你指定一个自定义的二元操作函数来代替默认的加法操作。这个二元操作接受两个参数累加值到当前为止的结果和序列中的当前元素。这使得 accumulate 变得非常灵活可以实现各种复杂的累加逻辑。
例如使用 accumulate 来计算一个数列的乘积 #include numeric
#include vectorstd::vectorint v {1, 2, 3, 4, 5};
int product std::accumulate(v.begin(), v.end(), 1, [](int a, int b) {return a * b;
});
这里初始值设为 1乘法的单位元并通过一个 lambda 表达式指定乘法为累加操作。最终product 的值为 120即 1*2*3*4*5 的结果。
注意事项
accumulate 默认使用加法操作时累加初始值的类型决定了整个操作的类型。例如如果初始值为整数那么即使数组是浮点数累加结果也会被截断为整数。因此选择合适的初始值类型是非常重要的。
435. 无重叠区间 给定一个区间的集合 intervals 其中 intervals[i] [start(i), end(i)] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。 示例 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 解释: 你不需要移除任何区间因为它们已经是无重叠的了。 提示: 1 intervals.length 10(5) intervals[i].length 2 -5 * 10(4) start(i) end(i) 5 * 10(4) int eraseOverlapIntervals(vectorvectorint intervals) {if (intervals.empty()) {return 0;}int n intervals.size();sort(intervals.begin(), intervals.end(), [](vectorint a, vectorint 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;} 检查区间数组是否为空
if (intervals.empty()) { return 0; }如果区间数组为空则没有需要移除的区间直接返回0。
获取区间数组的大小
int n intervals.size();这里定义了一个变量 n 来存储区间数组的长度。
按区间结束时间排序
sort(intervals.begin(), intervals.end(), [](vectorint a, vectorint b) { return a[1] b[1]; });使用标准库函数 sort通过自定义的比较函数将区间按照结束时间升序排序。这样做的目的是尽可能让区间不重叠因为结束得早的区间留给后面的区间的空间就越多。
初始化计数器和前一个区间的结束右端点
int total 0, prev intervals[0][1];初始化需要移除的区间数量 total 为0并将 prev 设置为第一个区间的结束时间。prev 用于记录当前不重叠区间的最后一个区间的结束时间。
遍历区间数组确定需要移除的区间数量
for (int i 1; i n; i) { if (intervals[i][0] prev) { total; } else { prev intervals[i][1]; } }从第二个区间开始遍历如果当前区间的开始时间小于前一个区间的结束时间 prev说明这两个区间重叠需要移除一个区间因此 total 自增1。如果不重叠更新 prev 为当前区间的结束时间继续向后比较。
标准库函数sort
C 标准库中的 sort 函数是一个非常强大且灵活的排序算法主要用于对数组或容器内的元素进行排序。它位于 algorithm 头文件中。sort 函数可以对一个序列进行默认的升序排序也可以通过自定义比较函数来指定排序规则。
基本用法
默认情况下sort 对序列进行升序排序。如果你想对一个数组或者 vector 排序可以这样使用 #include algorithm // 引入算法库
#include vectorstd::vectorint v {4, 2, 5, 3, 1};
std::sort(v.begin(), v.end());
在上述代码中v.begin() 和 v.end() 分别是容器 v 的起始迭代器和终止迭代器sort 函数会将 v 中的元素从小到大排序。
自定义比较函数
sort 函数允许你通过自定义比较函数来指定排序规则这让你能够实现复杂的排序逻辑比如降序排序或者根据对象的某个属性排序。
自定义比较函数可以是一个普通函数也可以是一个lambda表达式。比较函数需要接受两个参数被比较的元素并返回一个布尔值指示第一个参数是否应该位于第二个参数之前。
使用普通函数作为比较函数 bool compare(int a, int b) {return a b; // 降序排序
}std::vectorint v {4, 2, 5, 3, 1};
std::sort(v.begin(), v.end(), compare);
使用 Lambda 表达式
Lambda 表达式提供了一种便捷的方式来定义临时的比较函数这在实现简单的自定义排序规则时非常有用 std::vectorint v {4, 2, 5, 3, 1};
std::sort(v.begin(), v.end(), [](int a, int b) {return a b; // 降序排序
});
对象排序
如果你想根据对象的某个属性排序可以这样做 struct Person {std::string name;int age;
};bool compareByAge(const Person a, const Person b) {return a.age b.age; // 按年龄升序排序
}std::vectorPerson people {{Alice, 30}, {Bob, 25}, {Carol, 20}};
std::sort(people.begin(), people.end(), compareByAge);
或者使用 Lambda 表达式 std::sort(people.begin(), people.end(), [](const Person a, const Person b) {return a.age b.age; // 按年龄升序排序
});
结尾
最后感谢您阅读我的文章希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点请随时在评论区留言。 同时不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中我将继续探讨这个话题的不同方面为您呈现更多深度和见解。 谢谢您的支持期待与您在下一篇文章中再次相遇
