域名是建网站之前申请吗,无锡网络公司平台,wordpress缓存方法 张戈,如何下载网站模板文件在哪里文章目录分发饼干思路题解摆动序列题解最大子数组和分发饼干
CategoryDifficultyLikesDislikesContestSlugProblemIndexScorealgorithmsEasy (56.63%)6940--0
TagsCompanies
假设你是一位很棒的家长#xff0c;想要给你的孩子们一些小饼干。但是#xff0c;每个孩子最多只能…
文章目录分发饼干思路题解摆动序列题解最大子数组和分发饼干
CategoryDifficultyLikesDislikesContestSlugProblemIndexScorealgorithmsEasy (56.63%)6940--0
TagsCompanies
假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。
对每个孩子 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 * 1040 s.length 3 * 1041 g[i], s[j] 231 - 1 Discussion | Solution
思路
为了满足更多的小孩就不要造成饼干尺寸的浪费。
大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子那么就应该优先满足胃口大的。
这里的局部最优就是大饼干喂给胃口大的充分利用饼干尺寸喂饱一个全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略先将饼干数组和小孩数组排序。
然后从后向前遍历小孩数组用大饼干优先满足胃口大的并统计满足小孩数量。
题解
// lc codestart
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int index s.size()-1;int result 0;for(int i g.size()-1; i 0; i--) {if(index 0 s[index] g[i]) {result;index--;}} return result;}
};摆动序列
CategoryDifficultyLikesDislikesContestSlugProblemIndexScorealgorithmsMedium (47.07%)9210--0
TagsCompanies
如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 **摆动序列 。**第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如 [1, 7, 4, 9, 2, 5] 是一个 摆动序列 因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。相反[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些也可以不删除元素来获得剩下的元素保持其原始顺序。
给你一个整数数组 nums 返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1
输入nums [1,7,4,9,2,5]
输出6
解释整个序列均为摆动序列各元素之间的差值为 (6, -3, 5, -7, 3) 。示例 2
输入nums [1,17,5,10,13,15,10,5,16,8]
输出7
解释这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] 各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。示例 3
输入nums [1,2,3,4,5,6,7,8,9]
输出2提示
1 nums.length 10000 nums[i] 1000
**进阶**你能否用 O(n) 时间复杂度完成此题? Discussion | Solution
题解
// lc codestart
class Solution {
public:int wiggleMaxLength(vectorint nums) {if(nums.size() 1) return nums.size();int curDiff 0;int preDiff 0;int result 1;for(int i 0; i nums.size() - 1; i) {curDiff nums[i 1] - nums[i];if((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)) {result;preDiff curDiff;}}return result;}
};参考文章代码随想录 (programmercarl.com)
最大子数组和
CategoryDifficultyLikesDislikesContestSlugProblemIndexScorealgorithmsMedium (54.79%)60070--0
TagsCompanies
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。
示例 1
输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6 。示例 2
输入nums [1]
输出1示例 3
输入nums [5,4,-1,7,8]
输出23提示
1 nums.length 105-104 nums[i] 104
**进阶**如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的 分治法 求解。 Discussion | Solution
// lc codestart
class Solution {
public:int maxSubArray(vectorint nums) {int result INT32_MIN;int count 0;for(int i 0; i nums.size(); i) {count nums[i];if(count result) {result count;}if(count 0) count 0;}return result;}
};
