天津市建设安全协会网站,找人帮你做ppt的网站吗,百度推广深圳分公司,自建网站分发糖果 文章目录 分发糖果1 题目描述2 题目分析2.1 寻找波峰波谷2.2 从波底往波峰攀爬#xff01;2.2 计算糖果 3 代码附录1 1 题目描述
https://leetcode.cn/problems/candy/
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求…分发糖果 文章目录 分发糖果1 题目描述2 题目分析2.1 寻找波峰波谷2.2 从波底往波峰攀爬2.2 计算糖果 3 代码附录1 1 题目描述
https://leetcode.cn/problems/candy/
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。
示例 1
输入ratings [1,0,2] 输出5 解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2
输入ratings [1,2,2] 输出4 解释你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果这满足题面中的两个条件。
2 题目分析
首先利用实例分析我们假设所有小孩子的评分为[17, 18, 86, 49, 18, 42, 39, 72, 4, 98] 题目让我们返回需要准备的最少糖果最直接的想法就是找到所有的波底分数对应的小孩设置其糖果为1然后朝着两边的波峰逐步1。 我“寻找波峰波谷”、“分发糖果”这些步骤的绘制图像的代码放在了附录1中你可以传入你自定义的评分或者随机生成的评分绘制出每一步的状态然后可以在UUTool这个网站上设置gif。 2.1 寻找波峰波谷
当然如果图像都是像上面那种评分还好我们还有一种特殊情况如果出现连续的相等评分怎么办
如上图出现了连续3个87我们看看“题目描述”中怎么应对这种情况示例2中面对这种情况是直接将第二个得87分的孩子的糖果设为1高分不完全等于完全不高分太残酷了/(ㄒoㄒ)/~~那么从实际来看对于第二个87分这种情况我们视为波谷。
如何判断波峰假设当前索引为i。 i0则不用判断i的左边只考虑i的分数是否大于等于i1的分数。ilen(ratings)-1则不用考虑i的右边只考虑i的分数是否大于等于i-1的分数。
换句话说我们对i是否为波峰的判断分为i与i-1的rating相比以及和i1的rating相比。如果i0不考虑左边如果ilen(ratings)-1不考虑右边。
如何判断波谷其实也是同样的方式。
is_t_left (i 0) or (ratings[i - 1] ratings[i])
is_t_right (i len(ratings) - 1) or (ratings[i] ratings[i 1])
is_top is_t_left and is_t_rightis_b_left (i 0) or (ratings[i - 1] ratings[i])
is_b_right (i len(ratings) - 1) or (ratings[i] ratings[i 1])
is_bottom is_b_left and is_b_rightif is_top:tops.append(i)
if is_bottom:bottoms.append(i)这里有一个疑问为什么是“大于等于”而不是“大于”
很简单我们看第一个87其和右边相等但是还是满足是一个波峰。 但是这样的判断方式有一个问题假设ratings[i]ratings[i-1]ratings[i1]i既满足对于波峰的判断条件也满足对于波谷的判断条件也就是说i这个点即是波峰也是波谷。
没事只要我们能判断出来这个i是波谷就行叠加一个波峰的标志对后面没有影响看后续代码就行。 2.2 从波底往波峰攀爬
已经到达谷底了往哪走都是上升————不是鲁迅说的 接下来我们对所有的bottom进行遍历先将bottom位置设为1然后往左往右分别1。
这里需要注意了有些点既是top也是bottom假设我们从i开始向左向右只要碰到bottom不管是不是top都要停下来。
然后我们看上面那张图从i0向右到达2从i4向左到达2到达top的时候都会对应一个值这里恰好都是3那么我再举一个例子 这张图中从不同的方向到达top一个对应2一个对应3我们取最大值。这样就可以满足candy[2]candy[1]也满足candy[2]candy[3]。
for b in bottoms:res[b] 1 # 谷底设为1if b 0: # 可以往左走left b - 1while (left 0) and (left not in bottoms): # left not in bottoms 注意不要碰到波峰波谷结合体if left in tops: # 遇到波峰先更新成最大值再breakres[left] max(res[left 1] 1, res[left])breakelse:res[left] res[left 1] 1 # 没有异常直接1left left - 1if b len(ratings) - 1:right b 1while (right len(ratings)) and (right not in bottoms):res[right] res[right - 1] 1 # 包括top也一起更新if right in tops:break # 这里为什么直接break呢因为此时的top还没有被除了b小孩外的其他小孩到达过。right right 12.2 计算糖果
candy 0
for c in res:candy candy c3 代码
class Solution(object):def candy(self, ratings)::type ratings: List[int]:rtype: intbottoms []tops []res [0 for _ in range(len(ratings))]for i in range(len(ratings)):is_b_left (i 0) or (ratings[i - 1] ratings[i])is_b_right (i len(ratings) - 1) or (ratings[i] ratings[i 1])is_bottom is_b_left and is_b_rightif is_bottom:bottoms.append(i)is_t_left (i 0) or (ratings[i - 1] ratings[i])is_t_right (i len(ratings) - 1) or (ratings[i] ratings[i 1])is_top is_t_left and is_t_rightif is_top:tops.append(i)for b in bottoms:res[b] 1if b 0:left b - 1while (left 0) and (left not in bottoms):if left in tops:res[left] max(res[left 1] 1, res[left])breakelse:res[left] res[left 1] 1left left - 1if b len(ratings) - 1:right b 1while (right len(ratings)) and (right not in bottoms):res[right] res[right - 1] 1if right in tops:breakright right 1candy 0for c in res:candy candy creturn candy此时我们注意到(left not in bottoms)和(right not in bottoms)可能会增加耗时那么我考虑可以增加一个set来代替遍历查询
# 将bottoms变成set方便查找
bottoms_set set(bottoms)
(left not in bottoms_set)
(right not in bottoms_set)即
class Solution(object):def candy(self, ratings)::type ratings: List[int]:rtype: intbottoms []tops []res [0 for _ in range(len(ratings))]for i in range(len(ratings)):is_b_left (i 0) or (ratings[i - 1] ratings[i])is_b_right (i len(ratings) - 1) or (ratings[i] ratings[i 1])is_bottom is_b_left and is_b_rightif is_bottom:bottoms.append(i)is_t_left (i 0) or (ratings[i - 1] ratings[i])is_t_right (i len(ratings) - 1) or (ratings[i] ratings[i 1])is_top is_t_left and is_t_rightif is_top:tops.append(i)# 将bottoms变成set方便查找bottoms_set set(bottoms)for b in bottoms:res[b] 1if b 0:left b - 1while (left 0) and (left not in bottoms_set):if left in tops:res[left] max(res[left 1] 1, res[left])breakelse:res[left] res[left 1] 1left left - 1if b len(ratings) - 1:right b 1while (right len(ratings)) and (right not in bottoms_set):res[right] res[right - 1] 1if right in tops:breakright right 1candy 0for c in res:candy candy creturn candy但是好像并没有什么卵用大家可以尽情优化。
附录1
def candy(ratings)::type ratings: List[int]:rtype: intbottoms []tops []bots []res [0 for _ in range(len(ratings))]for i in range(len(ratings)):is_b_left (i 0) or (ratings[i - 1] ratings[i])is_b_right (i len(ratings) - 1) or (ratings[i] ratings[i 1])is_bottom is_b_left and is_b_rightif is_bottom:bottoms.append(i)bots.append(i)is_t_left (i 0) or (ratings[i - 1] ratings[i])is_t_right (i len(ratings) - 1) or (ratings[i] ratings[i 1])is_top is_t_left and is_t_rightif is_top:tops.append(i)draw_pic(ratings, bottoms, tops, res)for b in bottoms:res[b] 1draw_pic(ratings, bottoms, tops, res)if b 0:left b - 1while (left 0) and (left not in bots):if left in tops:res[left] max(res[left 1] 1, res[left])draw_pic(ratings, bottoms, tops, res)breakelse:res[left] res[left 1] 1draw_pic(ratings, bottoms, tops, res)left left - 1if b len(ratings) - 1:right b 1while (right len(ratings)) and (right not in bots):res[right] res[right - 1] 1draw_pic(ratings, bottoms, tops, res)if right in tops:breakright right 1candy 0for c in res:candy candy cdraw_pic(ratings, bottoms, tops, res)return candy
def draw_pic(ratings, bottoms, tops, res):import matplotlib.pyplot as pltimport numpy as np# 绘制柱状图ratings为红色res为蓝色(透明度为0.5)绘制在同一个图中plt.plot(range(len(ratings)), ratings, colorr, zorder1)plt.scatter(range(len(ratings)), ratings, colorr, zorder100)# 将bottoms标记出来plt.scatter(bottoms, [ratings[i] for i in bottoms], colorg, zorder100)# 将这些点添加文字bottom并且放置在点的下方for i in bottoms:plt.text(i, ratings[i] - 0.5, bottom, hacenter, vatop, fontsize10)# 将tops标记出来plt.scatter(tops, [ratings[i] for i in tops], colory, zorder100)# 将这些点添加文字top并且放置在点的上方for i in tops:plt.text(i, ratings[i] 0.5, top, hacenter, vabottom, fontsize10)plt.bar(range(len(ratings)), res, colorb, alpha0.5)# 将数值绘制在柱状图上for x, y in enumerate(res):plt.text(x, y 0.1, %s % y, hacenter, vabottom)# 设置 x 轴刻度及标签plt.xticks(np.arange(len(ratings)), range(len(ratings)))# showplt.show()# 随机生成ratings
import random
ratings [random.randint(0, 100) for _ in range(10)]
# 绘制折线图
import matplotlib.pyplot as plt
import numpy as np
plt.plot(range(len(ratings)), ratings)
plt.scatter(range(len(ratings)), ratings)
# 设置 x 轴刻度及标签
plt.xticks(np.arange(len(ratings)), range(len(ratings)))
# 绘制y值
for x, y in enumerate(ratings):plt.text(x, y 1, %s % y, hacenter, vabottom)
plt.show()candy(ratings)
