【刷题笔记】分糖果||数组||暴力通过||符合思维方式||多案例分析

分发糖果

文章目录

  • 分发糖果
    • 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
    • i==0,则不用判断i的左边,只考虑i的分数是否大于等于i+1的分数。
    • i==len(ratings)-1,则不用考虑i的右边,只考虑i的分数是否大于等于i-1的分数。

换句话说,我们对i是否为波峰的判断,分为ii-1的rating相比以及和i+1的rating相比。如果i==0,不考虑左边;如果i==len(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[i+1]i既满足对于波峰的判断条件,也满足对于波谷的判断条件,也就是说,i这个点即是波峰也是波谷。

没事,只要我们能判断出来这个i是波谷就行,叠加一个波峰的标志对后面没有影响,看后续代码就行。

在这里插入图片描述

2.2 从波底往波峰攀爬!

已经到达谷底了,往哪走都是上升!!————不是鲁迅说的

在这里插入图片描述

接下来,我们对所有的bottom进行遍历,先将bottom位置设为1,然后往左往右分别+1。

这里需要注意了,有些点既是top也是bottom,假设我们从i开始向左向右,只要碰到bottom,不管是不是top,都要停下来。

然后,我们看上面那张图,从i=0向右到达2,从i==4向左到达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 + 1

2.2 计算糖果

candy = 0
for c in res:candy = candy + c

3 代码

class Solution(object):def candy(self, ratings):""":type ratings: List[int]:rtype: int"""bottoms = []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: int"""bottoms = []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: int"""bottoms = []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, color='r', zorder=1)plt.scatter(range(len(ratings)), ratings, color='r', zorder=100)# 将bottoms标记出来plt.scatter(bottoms, [ratings[i] for i in bottoms], color='g', zorder=100)# 将这些点添加文字`bottom`,并且放置在点的下方for i in bottoms:plt.text(i, ratings[i] - 0.5, 'bottom', ha='center', va='top', fontsize=10)# 将tops标记出来plt.scatter(tops, [ratings[i] for i in tops], color='y', zorder=100)# 将这些点添加文字`top`,并且放置在点的上方for i in tops:plt.text(i, ratings[i] + 0.5, 'top', ha='center', va='bottom', fontsize=10)plt.bar(range(len(ratings)), res, color='b', alpha=0.5)# 将数值绘制在柱状图上for x, y in enumerate(res):plt.text(x, y + 0.1, '%s' % y, ha='center', va='bottom')# 设置 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, ha='center', va='bottom')
plt.show()candy(ratings)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/206186.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

猜-MISC-bugku-解题步骤

——CTF解题专栏—— 题目信息&#xff1a; 题目&#xff1a;猜 作者&#xff1a;harry 提示&#xff1a; 解题附件&#xff1a;flag格式key{图中人物名字全拼} 解题思路&#xff1a; 这......头都没有&#xff0c;让我guess&#xff1f;&#xff1f;&#xff1f;详细信息看…

Go 从编译到执行

一、Go运行编译简介 Go语言&#xff08;也称为Golang&#xff09;自从2009年由Google发布以来&#xff0c;已成为现代软件开发中不可或缺的一部分。设计者Rob Pike, Ken Thompson和Robert Griesemer致力于解决多核处理器、网络系统和大型代码库所引发的现实世界编程问题。我们…

小程序禁止二次转发分享私密消息动态消息

第一种用法&#xff1a;私密消息 私密消息&#xff1a;运营人员分享小程序到个人或群之后&#xff0c;该消息只能在被分享者或被分享群内打开&#xff0c;不可以二次转发。 用途&#xff1a;主要用于不希望目标客群外的人员看到的分享信息&#xff0c;比如带有较高金额活动的…

ffmpeg下载与配置环境变量

FFmpeg 是一个强大的多媒体框架&#xff0c;可以让用户处理和操纵音频和视频文件。具有易于使用的界面&#xff0c;用户可以在 Windows、Mac 或 Linux Ubuntu 系统上下载 FFmpeg 并将其提取到文件夹中。然后&#xff0c;该软件可以加入 PATH 环境变量中就可以快捷的使用软件了.…

k8s环境排查nginx转发nacos请求失败问题

一、问题背景 k8s部署两个服务,一个nginx&#xff0c;一个nacos, 服务信息如下(nacos有两个端口): 服务 serviceNameservice类型porttargetPort nodePortnginxmonitor-cp-nginxNodePort808031082nacosmonitor-cp-nacosClusterIP88488848-98489848- ng的default.conf配置文件…

轻型载重汽车转向前桥总成系统毕业设计机械设计

wx供重浩&#xff1a;创享日记 对话框发送&#xff1a;前桥 获取完整说明报告工程源文件 绪论 1.1 轻型载重汽车转向桥的设计意义 汽车是现代交通工具中用得最多&#xff0c;最普遍&#xff0c;也是最方便的交通运输工具。汽车转向系是汽车上的一个重要系统,它是汽车转向运动…

SpringCloudAlibaba之Nacos的持久化和高可用——详细讲解

目录 一、Nacos持久化 1.持久化说明 2.安装mysql数据库5.6.5以上版本(略) 3.修改配置文件 二、nacos高可用 1.集群说明 2.nacos集群架构图 2.集群搭建注意事项 3.集群规划 4.搭建nacos集群 5.安装Nginx 6.配置nginx conf配置文件 7.启动nginx进行测试即可 一、Nacos持久…

【数据中台】开源项目(2)-Davinci可视应用平台

1 平台介绍 Davinci 是一个 DVaaS&#xff08;Data Visualization as a Service&#xff09;平台解决方案&#xff0c;面向业务人员/数据工程师/数据分析师/数据科学家&#xff0c;致力于提供一站式数据可视化解决方案。既可作为公有云/私有云独立部署使用&#xff0c;也可作为…

实现校园网开机自启动部署

❤️博客主页&#xff1a; iknow181&#x1f525;系列专栏&#xff1a; Python、JavaSE、JavaWeb、CCNP&#x1f389;欢迎大家点赞&#x1f44d;收藏⭐评论✍ 目录 一.准备工作 1、IDE安装 2、安装Selenium 1.介绍 2.下载 3、安装pywifi 1.介绍 2.下载 4、下载浏览器驱…

SpringBoot整合MyBatis

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开心好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…

知乎禁止转载的回答怎么复制做笔记?

问题 对于“禁止转载”的回答&#xff0c;右键复制是不行的&#xff0c;ctrl-c也不行&#xff0c;粘贴之后都是当前回答的标题。稍微看了代码&#xff0c;应该是对copy事件进行了处理。不过这样真的有用吗&#xff0c;真是防君子不防小人&#xff0c;只是给收集资料增加了许多…

基于C#实现外排序

一、N 路归并排序 1.1、概序 我们知道算法中有一种叫做分治思想&#xff0c;一个大问题我们可以采取分而治之&#xff0c;各个突破&#xff0c;当子问题解决了&#xff0c;大问题也就 KO 了&#xff0c;还有一点我们知道内排序的归并排序是采用二路归并的&#xff0c;因为分治…

Navicat 技术指引 | 适用于 GaussDB 的自动运行功能

Navicat Premium&#xff08;16.2.8 Windows版或以上&#xff09; 已支持对 GaussDB 主备版的管理和开发功能。它不仅具备轻松、便捷的可视化数据查看和编辑功能&#xff0c;还提供强大的高阶功能&#xff08;如模型、结构同步、协同合作、数据迁移等&#xff09;&#xff0c;这…

a-select:远程搜索——防抖节流处理——基础积累

a-select:远程搜索——防抖节流处理——基础积累 效果图下拉筛选数据&#xff1a;远程搜索功能&#xff1a; 效果图 下拉筛选数据&#xff1a; <a-selectshow-searchv-model"form.jobPositionCode"placeholder"请选择岗位"style"width: 100%"…

Docker安装可视化工具Portainer

目录 Portainer简介 Portainer安装 Portainer简介 Portainer是一款开源的容器管理平台&#xff0c;支持多种容器技术&#xff0c;如Docker、Kubernetes和Swarm等。它提供了一个易于使用的Web UI界面&#xff0c;可用于管理和监控容器和集群。Portainer旨在使容器管理更加简单…

【带头学C++】----- 九、类和对象 ---- 9.1 类和对象的基本概念----(9.1.1---9.1.3)

目录 9.1 类和对象的基本概念 9.1.1 类的封装性 9.1.2 定义类的步骤和方法 9.1.3 设计一个学生类 Student 9.1 类和对象的基本概念 9.1.1 类的封装性 类是一种用户自定义的数据类型&#xff0c;它定义了一组数据成员和成员函数。类可以看作是一个模板或者蓝图&#xff0c;用…

Django之中间件与CSRF_TOKEN

文章目录 一、什么是中间件二、中间件有什么用三、Django自定义中间件中间件中主要方法及作用创建自定义中间件的步骤&#xff1a;process_request与process_response方法process_view方法process_exceptionprocess_template_response&#xff08;不常用&#xff09; 四、CSRF_…

MySQL--慢查询(一)

1. 查看慢查询日志是否开启 show variables like slow_query%; show variables like slow_query_log; 参数说明&#xff1a; 1、slow_query_log&#xff1a;这个参数设置为ON&#xff0c;可以捕获执行时间超过一定数值的SQL语句。 2、long_query_time&#xff1a;当SQL语句执行…

latex中算法的几种模板

latex中算法的几种模板_latex算法模板-CSDN博客文章浏览阅读6.2k次&#xff0c;点赞3次&#xff0c;收藏45次。latex中几种算法模板_latex算法模板https://blog.csdn.net/weixin_50514171/article/details/125136121?spm1001.2014.3001.5506

【开源】基于Vue和SpringBoot的智能教学资源库系统

项目编号&#xff1a; S 050 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S050&#xff0c;文末获取源码。} 项目编号&#xff1a;S050&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 课程档案模块2.3 课…