首页 > 编程语言 >代码随想录算法训练营第三十一天 | 53. 最大子序和, 376. 摆动序列,455.分发饼干

代码随想录算法训练营第三十一天 | 53. 最大子序和, 376. 摆动序列,455.分发饼干

时间:2024-02-29 16:55:56浏览次数:32  
标签:饼干 nums int res 示例 随想录 455 53 序列

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 * 104
  • 0 <= s.length <= 3 * 104
  • 1 <= g[i], s[j] <= 231 - 1

func findContentChildren(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)
	var res int
	var si int
	for i := 0; i < len(g); i++ {
		for si < len(s) {
			if g[i] > s[si] {
				si++
			} else {
				si++
				res += 1
				break
			}
		}
	}
	return res
}

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

 

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

 

进阶:你能否用 O(n) 时间复杂度完成此题?


func wiggleMaxLength(nums []int) int { if len(nums) < 2 { return len(nums) } res := 1 prevDiff := nums[1] - nums[0] if prevDiff != 0 { res = 2 } for i := 2; i < len(nums); i++ { nowDiff := nums[i] - nums[i-1] if (prevDiff <= 0 && nowDiff > 0) || (prevDiff >= 0 && nowDiff < 0) { res++ prevDiff = nowDiff } } return res }

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

 

提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

 

进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解

 


func maxSubArray(nums []int) int { res, cur := nums[0], nums[0] for i := 1; i < len(nums); i++ { if cur > 0 { cur += nums[i] }else { cur = nums[i] } if cur > res { res = cur } } return res }

标签:饼干,nums,int,res,示例,随想录,455,53,序列
From: https://www.cnblogs.com/suxinmian/p/18044752

相关文章

  • Codeforces 1455E Four Points
    首先确定每个点最后走到的是哪一个点。这部分可以枚举全排列。假设左上角的点为\((x_0,y_0)\),右上角的点为\((x_1,y_1)\),左下角的点为\((x_2,y_2)\),右下角的点为\((x_3,y_3)\)。令最终的点为\((x'_0,y'_0)\),以此类推。那么最终的答案就是\(\sum\limits_{i=0}^3|......
  • CVE-2017-1000353分析
    影响版本Jenkins主版本<=2.56版本)JenkinsLTS<=2.46.1版本)漏洞分析漏洞发生在jenkinscli采用http方式进行通信的时候,处理url为http://127.0.0.1:8080/cli,其处理逻辑在hudson.cli.CLIAction中jenkins采用的是Stapler框架,CLIAction实现了两个接口,分别是UnprotectedRootActio......
  • day50 动态规划part7 代码随想录算法训练营 279. 完全平方数
    题目:279.完全平方数我的感悟:看文字也行理解难点:物品是什么?是i*i<n的集合听课笔记:代码示例:classSolution:defnumSquares(self,n:int)->int:#完全背包问题#顺序没关系,组合把#递推公式难想,dp[j]=min(dp[j],dp[j-i*i]+1)......
  • day50 动态规划part7 代码随想录算法训练营 322. 零钱兑换【什么时候+1】
    题目:322.零钱兑换我的感悟:看着文字版也能做出来了,哈哈哈!!理解难点:这题是最小值dp[j]=min(dp[j],dp[j-coins[i]+1)因为是数量要加一个1,有的加,有的不加,还没太搞清楚。 听课笔记: 代码示例:classSolution:defcoinChange(self,coins:List[int],amount:int......
  • day44 动态规划part7 代码随想录算法训练营 70. 爬楼梯 (进阶)
    题目:爬楼梯(进阶)-在卡尔网我的感悟:昨天最后没怎么听懂的,今日回旋镖来了。理解难点:递推公式,和遍历顺序手写笔记:代码示例:total,m=map(int,input().split())#每次爬m个#dp[i]含义是爬到i有dp[i]种方法#是完全背包问题dp=[0]*(total+1)dp[0]=1fo......
  • 代码随想录算法训练营第六天|242. 有效的字母异位词
    这个题目还是比较简单的,知道是查表的思路之后,很快就写出来了:classSolution:defisAnagram(self,s:str,t:str)->bool:iflen(s)!=len(t):returnFalsealphabet=[]dict_s={}dict_t={}foriinran......
  • 代码随想录算法训练营day08 | leetcode 344. 反转字符串、541. 反转字符串 II、54. 替
    目录题目链接:344.反转字符串-简单题目链接:541.反转字符串II-简单题目链接:[54.替换数字](题目页面(kamacoder.com))题目链接:151.反转字符串中的单词-中等题目链接:[55.右旋字符串](题目页面(kamacoder.com))题目链接:344.反转字符串-简单题目描述:编写一个函数,其作用是将......
  • 苹果取消电动汽车项目;英伟达 CEO 黄仁勋寄语:学习编程价值大幅降低丨 RTE 开发者日报 V
      开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(RealTimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编辑......
  • 代码随想录 day64 柱状图中最大的矩形
    柱状图中最大的矩形本题和接雨水在很多地方都很相似但是不是求凹槽了而是求突起就是相同的思路求不同的柱体对于每一个柱体找左边最矮的柱体这个柱体的右边的柱体和这个柱体围成的矩形就为最大同理找右边的柱体这里注意要用while而不是if因为要找到最矮的而......
  • cf1553f-solution
    CF1553FSolutionlink首先显然地\(\displaystylep_i=p_{i-1}+\sum_{j=1}^{i-1}a_j\bmoda_i+\sum_{j=1}^{i-1}a_i\bmoda_j\)。那么两部分分开来算。\(\displaystyle\sum_{j=1}^{i-1}a_j\bmoda_i\):我们知道\(x\bmody=x-y\lfloor\fracxy\rfloor\),那么我们先把答案加上......