LeetCode刷题day48

简介: LeetCode刷题day48

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.


思路分析


方法一


这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。


先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组,用大饼干优先满足胃口大的,并统计满足小孩数量。直至小孩遍历完毕或者饼干分发完毕.


5c65659c24a026388a640d0bfe221990.png

方法二


局部最优是:小饼干先喂饱小胃口. 全局最优就是尽可能的把饼干分发给每个小孩.


先将饼干数组和小孩数组排序。然后从前往后遍历饼干数组,小饼干优先满足小胃口的,如果小孩胃口比饼干大,则进行下一块饼干。直至饼干分发完毕或者小孩尽可能的得到饼干。


9b673f8b65682c03ae7fa62c65cf626e.png


参考代码


方法一

int findContentChildren(vector<int>& g, vector<int>& s) {//g:小孩  s:饼干 
  //从后往前 
  int result = 0;
  sort(g.begin(),g.end());
  sort(s.begin(),s.end());
  int index = s.size() - 1;
  //大孩子吃大饼干 
  for(int i = g.size() - 1; i >= 0;i--){
    if(index>=0 && g[i] <= s[index]){//饼干 > 小孩胃口,匹配成功. 否则换更小胃口的小孩来尝试该饼干. 
      index--;
      result++;
    }
  } 
  return result;
}

方法二

int findContentChildren(vector<int>& g, vector<int>& s) {//g:小孩  s:饼干 
  //从前往后
  int result = 0;
  sort(g.begin(),g.end());
  sort(s.begin(),s.end());
  int index = 0;
  //小饼干给小孩子 
  for(int i = 0; i < s.size();i++){
    if(index < g.size() && s[i] >= g[index]){
      index++;//饼干 > 小孩胃口,匹配成功,进行为下一个小孩匹配.否则 饼干应该更大一点
      result++; 
    }
  } 
  return result;
}

376. 摆动序列


题目描述


如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 **摆动序列 。**第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。


例如, [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


思路分析


本题要求通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。


来分析一下,要求删除元素使其达到最大摆动序列,应该删除什么元素呢?


用示例二来举例,如图所示:


7bc72fb1b4a664ac31676249608eab45.png

局部最优:删除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值


整体最优:整个序列有最多的局部峰值,从而达到最长摆动序列


局部最优推出全局最优,并举不出反例,那么试试贪心!


实际操作上,其实连删除的操作都不用做,因为题目要求的是最长摆动子序列的长度,所以只需要统计数组的峰值数量就可以了


本题代码实现中,还有一些技巧,例如统计峰值的时候,数组最左面和最右面是最不好统计的(因为可能出现相等情况[2,2,5,1])


例如序列[2,5],它的峰值数量是2,如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。


所以可以针对序列[2,5],可以假设为[2,2,5],这样它就有坡度了即preDiff = 0,如图:


37a61547438a8385e0bbaebb741aa9e5.png


result初始为1(默认最右面有一个峰值),此时curDiff > 0 && preDiff <= 0,那么result++(计算了左面的峰值),最后得到的result就是2(峰值个数为2即摆动序列长度为2)


参考代码

int wiggleMaxLength(vector<int>& nums) {
  if(nums.size()<=1){
    return nums.size();
  }
  int curDiff = 0;
  int preDiff = 0;
  int result = 1;
  for(int i = 0;i < nums.size();i++){
    curDiff = nums[i+1]-num[i];
    if( (curDiff  > 0 && preDiff <= 0) || (preDiff >=0 &&curDiff < 0)){
      result++;
      preDiff = curDiff;//这个不可以放在if外边,写在这里和删除坡度上的结点达到是一样的结果.
    }
  }
  return result;
}


53. 最大子数组和


题目描述


给你一个整数数组 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


思路分析


方法一:暴力法


第一层for 就是设置起始位置,第二层for循环遍历数组寻找最大值


方法二:贪心法


如果 -2 1 在一起,计算起点的时候,一定是从1开始计算,因为负数只会拉低总和,这就是贪心贪的地方!


局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。


全局最优: 局部最优的情况下,并记录最大的“连续和”,可以推出全局最优。


image.gif


红色的起始位置就是贪心每次取count为正数的时候,开始一个区间的统计。


参考代码


暴力法代码

//暴力法 TCL
int maxSubArray(vector<int>& nums) {
  int count  = 0;
  int result = INT_MIN;//初始化
  for(int i = 0;i < nums.size(); i++){//起始位置 
    count = 0;
    for(int j = i;j < nums.size(); j++){
      count+=nums[j];
      result = count > result ?  count: result ;
    }
  }
  return result;
}

贪心法代码

//贪心法
int maxSubArray(vector<int>& nums) {
  int count  = 0;
  int result = INT_MIN;//初始化
  for(int i = 0; i < nums.size(); i++) {
    count+=nums[i];
    if(count>result) { //如果比result大,则更新result  (即使都是负数也没有关系,根据代码,最后保存的将是最大的负数)
      result = count;
    }
    if(count < 0) { //子数组 + 负数,会导致结果更小.所以只要count <0,则下次直接重新开始构成新的数组
      count = 0;
    }
  }
  return result;
}

122. 买卖股票的最佳时机 II


题目描述


给定一个数组 prices ,其中 prices[i] 表示股票第 i 天的价格。

在每一天,你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它,然后在 同一天 出售。


返回 你能获得的 最大 利润


示例 1:

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:


输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。


思路分析


看到这个题,我们会想,选一个低的买入,在选个高的卖,在选一个低的买入…循环反复。最终利润是可以分解的 ,这样想这个题就很容易解决了.


如何分解呢?


假如第0天买入,第3天卖出,那么利润为:prices[3] - prices[0]。


相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。


根据prices可以得到每天的利润序列:(prices[i] - prices[i - 1]).....(prices[1] - prices[0]).


这样我们可以得到利润的序列. 我们要做的是收取利润为正的序列数


如图:


601fc3940a4f09dea52d38e698c9e8b6.png


第一天当然没有利润,至少要第二天才会有利润,所以利润的序列比股票序列少一天!


从图中可以发现,其实我们需要收集每天的正利润就可以,收集正利润的区间,就是股票买卖的区间,而我们只需要关注最终利润,不需要记录区间。


局部最优:收集每天的正利润,全局最优:求得最大利润。


局部最优可以推出全局最优,可以使用贪心!


参考代码


int maxProfit(vector<int>& prices) {
  int result = 0;
  for(int i = 1;i < prices.size();i++){
    result += max(prices[i]-prices[i-1],0) ;
  }
  return result;
}
相关文章
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
54 6
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
46 4
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
107 2
|
9天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
10 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
3月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
54 7
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
25 4
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
50 5
|
3月前
|
算法 Python
【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
本文介绍了LeetCode 2038题的解法,题目要求在一个由'A'和'B'组成的字符串中,按照特定规则轮流删除颜色片段,判断Alice是否能够获胜,并提供了Python的实现代码。
50 3