当前位置: 首页 > news >正文

【135. 分发糖果 困难】

题目:

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求,给这些孩子分发糖果:

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。

示例 1:
输入:ratings = [1,0,2]
输出:5
解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2:
输入:ratings = [1,2,2]
输出:4
解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。

提示:

  • n == ratings.length
  • 1 <= n <= 2 * 104
  • 0 <= ratings[i] <= 2 * 104

思路:

由于每个孩子至少分配到 1 个糖果

先初始化一个vector,里面都填充为1。

代码如下:

vector<int> sumCandy(ratings.size(), 1);    //  每个孩子先分一个

相邻两个孩子评分更高的孩子会获得更多的糖果。

  • 需要先从前往后遍历,如果第i个孩子比第i - 1个孩子评分高,第i个孩子的糖果比第i - 1个多一个。

  • 然后再从后往前遍历,如果如果第i个孩子比第i + 1个孩子评分高,这个时候就有两个选择了,一个是sumCandy[i + 1] + 1(从右边这个加1得到的糖果数量),一个是sumCandy[i](之前比较右孩子大于左孩子得到的糖果数量)。

代码如下:

//  从前向后
for(int i = 1; i < ratings.size(); i++){if(ratings[i] > ratings[i - 1]){sumCandy[i] = sumCandy[i - 1] + 1;}
}
//  从后向前
for(int i = ratings.size() - 2; i >= 0; i--){if(ratings[i] > ratings[i + 1]){sumCandy[i] = max(sumCandy[i + 1] + 1, sumCandy[i]);}
}

统计sumCandy中的糖果总和

代码如下:

//  统计结果
for(auto i : sumCandy){result += i;
}

代码:

class Solution {
public:int candy(vector<int>& ratings) {int result = 0;vector<int> sumCandy(ratings.size(), 1);    //  每个孩子先分一个//  从前向后for(int i = 1; i < ratings.size(); i++){if(ratings[i] > ratings[i - 1]){sumCandy[i] = sumCandy[i - 1] + 1;}}//  从后向前for(int i = ratings.size() - 2; i >= 0; i--){if(ratings[i] > ratings[i + 1]){sumCandy[i] = max(sumCandy[i + 1] + 1, sumCandy[i]);}}//  统计结果for(auto i : sumCandy){result += i;}return result;}
};

总结:

时间复杂度: O(n)
空间复杂度: O(n)

这在leetcode上是一道困难的题目,其难点就在于贪心的策略,如果在考虑局部的时候想两边兼顾,就会顾此失彼。

那么本题采用了两次贪心的策略:

一次是从左到右遍历,只比较右边孩子评分比左边大的情况。

一次是从右到左遍历,只比较左边孩子评分比右边大的情况。

这样从局部最优推出了全局最优,即:相邻的孩子中,评分高的孩子获得更多的糖果。


参考:

代码随想录

相关文章:

【135. 分发糖果 困难】

题目&#xff1a; n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求&#xff0c;给这些孩子分发糖果&#xff1a; 每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果&#xff0c;计…...

AAAI2024论文解读|HGPROMPT Bridging Homogeneous and Heterogeneous Graphs

论文标题 HGPROMPT: Bridging Homogeneous and Heterogeneous Graphs for Few-shot Prompt Learning 跨同构异构图的小样本提示学习 论文链接 HGPROMPT: Bridging Homogeneous and Heterogeneous Graphs for Few-shot Prompt Learning论文下载 论文作者 Xingtong Yu, Yuan…...

算法题(49):反转链表II

审题&#xff1a; 需要我们对指定范围的链表进行反转&#xff0c;并返回反转后链表的头结点 思路&#xff1a; 方法一&#xff1a;vector法 我们先遍历一次链表&#xff0c;并把数据对应的存在数组中&#xff0c;然后利用数组的reverse方法进行反转数据&#xff0c;最后再遍历一…...

代码随想录day20

235. 利用二叉搜索树的特性即可 /** lc appleetcode.cn id235 langcpp** [235] 二叉搜索树的最近公共祖先*/// lc codestart /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) :…...

文档智能扫描,提升无纸化办公效率

随着无纸化办公的推广和移动设备的普及&#xff0c;用户迫切需要将纸质文档快速、准确地转换成电子格式&#xff0c;以提高工作效率和信息管理的便捷性。同时&#xff0c;用户将文档扫描成电子版后&#xff0c;可以自行通过加密和访问控制提高电子文档的安全性&#xff0c;以满…...

差分等长的原理

差分等长是指在设计差分信号传输线路时&#xff0c;保证两条差分线的长度尽量一致&#xff0c;长度之差在一个合理的范围内。这是为了确保两个差分信号时刻保持相反极性&#xff0c;减少共模分量&#xff0c;从而提高信号传输的质量。 在差分信号传输中&#xff0c;两条差分线…...

“““【运用 R 语言里的“predict”函数针对 Cox 模型展开新数据的预测以及推理。】“““

主题与背景 本文主要介绍了如何在R语言中使用predict函数对已拟合的Cox比例风险模型进行新数据的预测和推理。Cox模型是一种常用的生存分析方法&#xff0c;用于评估多个因素对事件发生时间的影响。文章通过具体的代码示例展示了如何使用predict函数的不同参数来获取生存概率和…...

真正理解std::move

std::move的作用只有一个&#xff0c;那就是把一个左值强制转换为右值&#xff0c;有了这个右值&#xff0c;右值允许的任何操作就可以实施了。比如&#xff1a;1. 这个右值可以赋给一个左值变量&#xff0c;2. 这个右值可以被一个右值引用来引用。 class A {public:A(int n):…...

Vue3.5 企业级管理系统实战(三):页面布局及样式处理 (Scss UnoCSS )

本章主要是关于整体页面布局及样式处理&#xff0c;在进行这一章代码前&#xff0c;先将前两章中的示例代码部分删除&#xff08;如Home.vue、About.vue、counter.ts、App.vue中引用等&#xff09; 1 整体页面布局 页面整体布局构成了产品的框架基础&#xff0c;通常涵盖主导…...

Python3 【函数】项目实战:5 个新颖的学习案例

Python3 【函数】项目实战&#xff1a;5 个新颖的学习案例 本文包含5编程学习案例&#xff0c;具体项目如下&#xff1a; 简易聊天机器人待办事项提醒器密码生成器简易文本分析工具简易文件加密解密工具 项目 1&#xff1a;简易聊天机器人 功能描述&#xff1a; 实现一个简易…...

17.Word:李楠-学术期刊❗【29】

目录 题目​ NO1.2.3.4.5 NO6.7.8 NO9.10.11 NO12.13.14.15 NO16 题目 NO1.2.3.4.5 另存为手动/F12Fn光标来到开头位置处→插入→封面→选择花丝→根据样例图片&#xff0c;对应位置填入对应文字 (手动调整即可&#xff09;复制样式&#xff1a;开始→样式对话框→管理…...

基于GS(Gaussian Splatting)的机器人Sim2Real2Sim仿真平台

项目地址&#xff1a;RoboGSim 背景简介 已有的数据采集方法中&#xff0c;遥操作&#xff08;下左&#xff09;是数据质量高&#xff0c;但采集成本高、效率低下&#xff1b;传统仿真流程成本低&#xff08;下右&#xff09;&#xff0c;但真实度&#xff08;如纹理、物理&…...

基于Django的豆瓣影视剧推荐系统的设计与实现

【Django】基于Django的豆瓣影视剧推荐系统的设计与实现&#xff08;完整系统源码开发笔记详细部署教程&#xff09;✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统采用了Python作为后端开发语言&#xff0c;采用Django作为后端架构&#xff0c;结…...

提升企业内部协作的在线知识库架构与实施策略

内容概要 在当前快速变化的商业环境中&#xff0c;企业对于提升内部协作效率的需求愈显迫切。在线知识库作为信息存储与共享的平台&#xff0c;成为了推动企业数字化转型的重要工具。本文将深入探讨如何有效打造与实施在线知识库&#xff0c;强调架构设计、知识资产分类管理及…...

Vuex中的getter和mutation有什么区别

在现代前端开发中&#xff0c;状态管理是一个不可忽视的话题&#xff0c;而Vuex作为Vue.js的官方状态管理库&#xff0c;在大型应用中扮演着至关重要的角色。当我们使用Vuex进行状态管理时&#xff0c;getter和mutation是两个重要的概念。虽然它们都是用来处理状态的&#xff0…...

springboot 动态线程池

在Spring Boot中&#xff0c;可以使用ThreadPoolTaskExecutor类来创建动态线程池。以下是一个示例&#xff1a; 首先&#xff0c;需要在配置文件中配置线程池的属性&#xff0c;例如最小线程数、最大线程数、线程存活时间等。可以在application.properties或application.yml中…...

Android - 通过Logcat Manager简单获取Android手机的Log

由于工作需要&#xff0c;经常需要获取Android手机的Log。 平常都是通过adb命令来获取&#xff0c;每次都要写命令。 偶然的一个机会&#xff0c;我从外网发现了一个工具 Logcat Manager&#xff0c;只需要通过简单的双击即可获取Android的Log&#xff0c;这里也分享一下。 目…...

qt-QtQuick笔记之常见项目类简要介绍

qt-QtQuick笔记之常见项目类简要介绍 code review! 文章目录 qt-QtQuick笔记之常见项目类简要介绍1.QQuickItem2.QQuickRectangle3.QQuickImage4.QQuickText5.QQuickBorderImage6.QQuickTextInput7.QQuickButton8.QQuickSwitch9.QQuickListView10.QQuickGridView11.QQuickPopu…...

C语言【基础篇】之流程控制——掌握三大结构的奥秘

流程控制 &#x1f680;前言&#x1f99c;顺序结构&#x1f4af; 定义&#x1f4af;执行规则 &#x1f31f;选择结构&#x1f4af;if语句&#x1f4af;switch语句&#x1f4af;case穿透规则 &#x1f914;循环结构&#x1f4af;for循环&#x1f4af;while循环&#x1f4af;do -…...

LeetCode100之全排列(46)--Java

1.问题描述 给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案 示例1 输入&#xff1a;nums [1,2,3] 输出&#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例2 输入&#xff1a;nums [0,1] 输出&#xf…...

html、js、css实现爱心效果

好的&#xff01;我们可以进一步美化这个爱心效果&#xff0c;增加更多动态和视觉吸引力。以下是改进后的代码&#xff0c;包括以下功能&#xff1a; 1. 背景渐变&#xff1a;添加动态背景渐变效果。 2. 爱心阴影&#xff1a;为爱心添加阴影&#xff0c;使其更具立体感。 3. 随…...

记录 | 基于Docker Desktop的MaxKB安装

目录 前言一、MaxKBStep 1Step2 二、运行MaxKB更新时间 前言 参考文章&#xff1a;如何利用智谱全模态免费模型&#xff0c;生成大家都喜欢的图、文、视并茂的文章&#xff01; MaxKB的Github下载地址 参考视频&#xff1a;【2025最新MaxKB教程】10分钟学会一键部署本地私人专属…...

信息学奥赛一本通 2110:【例5.1】素数环

【题目链接】 ybt 2110&#xff1a;【例5.1】素数环 【题目考点】 1. 深搜回溯 2. 质数 【解题思路】 1~n的数字构成一个环&#xff0c;要求相邻数字加和必须是质数。 该题最终输出的是一个序列&#xff0c;只不过逻辑上序列最后一个数字的下一个数字就是序列的第一个数字…...

5.1.4 软件工具+开发环境

文章目录 软件工具软件开发环境 软件工具 软件工具是辅助软件工程实施的软件&#xff0c;也叫CASE工具。软件工具可分为支持软件开发过程的工具、软件维护工具、软件管理工具3类。 支持软件开发过程的工具 需求分析工具&#xff1a;从需求定义制定出功能规范&#xff0c;描述软…...

嵌入式知识点总结 Linux驱动 (四)-中断-软硬中断-上下半部-中断响应

针对于嵌入式软件杂乱的知识点总结起来&#xff0c;提供给读者学习复习对下述内容的强化。 目录 1.硬中断&#xff0c;软中断是什么&#xff1f;有什么区别&#xff1f; 2.中断为什么要区分上半部和下半部&#xff1f; 3.中断下半部一般如何实现&#xff1f; 4.linux中断的…...

【机器学习】自定义数据集 使用pytorch框架实现逻辑回归并保存模型,然后保存模型后再加载模型进行预测

一、使用pytorch框架实现逻辑回归 1. 数据部分&#xff1a; 首先自定义了一个简单的数据集&#xff0c;特征 X 是 100 个随机样本&#xff0c;每个样本一个特征&#xff0c;目标值 y 基于线性关系并添加了噪声。将 numpy 数组转换为 PyTorch 张量&#xff0c;方便后续在模型中…...

21款炫酷烟花合集

系列专栏 《Python趣味编程》《C/C趣味编程》《HTML趣味编程》《Java趣味编程》 写在前面 Python、C/C、HTML、Java等4种语言实现18款炫酷烟花的代码。 Python Python烟花① 完整代码&#xff1a;Python动漫烟花&#xff08;完整代码&#xff09; ​ Python烟花② 完整…...

【8】思科IOS AP升级操作

1.概述 本文主要针对思科AP的升级操作进行记录,思科的AP目前主要分为IOS和COS AP,IOS AP是我们常见的AP3502/AP1602/AP2702等等型号的AP,而COS AP是AP2802/3802等型号的AP。当然这里所指的都是一些室内AP,如AP1572等室外AP也同样适用。本文先对IOS AP的升级操作进行总结,…...

Continuous Batching 连续批处理

原始论文题目: Continuous Batching — ORCA: a distributed serving system for Transformer-based generative models 关键词: Continuous Batching, iteration-level scheduling, selective batching 1.迭代级调度(iteration-level scheduling) Orca系统又由几个关键…...

如何解决小尺寸图像分割中的样本不均衡问题

1. 生成对抗数据增强&#xff08;Copy-Paste Augmentation&#xff09; 原理&#xff1a;将稀有目标的像素块复制粘贴到其他图像中&#xff0c;低成本生成平衡数据。 适用场景&#xff1a;小目标&#xff08;如车辆、船只&#xff09;或极端稀疏类别&#xff08;如灾害损毁区域…...

obsidian插件——Metadata Hider

原本是要找导出图片时显示属性的插件&#xff0c;奈何还没找到&#xff0c;反而找到了可以隐藏属性的插件。唉&#xff0c;人生不如意&#xff0c;十之八九。 说一下功能&#xff1a; 这个插件可以把obsidian的文档属性放在右侧显示&#xff0c;或者决定只显示具体几项属性&a…...

Ubuntu 20.04 Realtek 8852无线网卡驱动

个人博客地址&#xff1a;Ubuntu 20.04 Realtek 8852无线网卡驱动 | 一张假钞的真实世界 sudo apt-get update sudo apt-get install make gcc linux-headers-$(uname -r) build-essential gitgit clone https://github.com/lwfinger/rtw89.git -b v5 cd rtw89 && mak…...

神经网络|(六)概率论基础知识-全概率公式

【1】引言 在前序学习进程中&#xff0c;我们已经对条件概率做了分析&#xff0c;知晓了古典概型下&#xff0c;求某个条件下某事件发生的概率&#xff0c;应该是计算促成条件发生的事件和要求的某事件都发生的综合概率。 再次回忆一下条件概率的定义&#xff1a; 条件概率就…...

LLM推理优化:数据、模型与系统级策略

标题&#xff1a;“LLM推理优化&#xff1a;数据、模型与系统级策略” 文章信息摘要&#xff1a; 文章探讨了大语言模型&#xff08;LLM&#xff09;推理优化的多层次策略&#xff0c;包括数据级、模型级和系统级优化。数据级优化通过输入压缩和提示工程提升效率&#xff1b;模…...

人工智能在医疗领域的应用有哪些?

人工智能在医疗领域的应用十分广泛&#xff0c;涵盖了诊断、治疗、药物研发等多个环节&#xff0c;以下是一些主要的应用&#xff1a; 医疗影像诊断 疾病识别&#xff1a;通过分析 X 光、CT、MRI 等影像&#xff0c;人工智能算法能够识别出肿瘤、结节、骨折等病变&#xff0c;…...

K8S极简教程(4小时快速学会)

1. K8S 概览 1.1 K8S 是什么 K8S官网文档&#xff1a;https://kubernetes.io/zh/docs/home/ 1.2 K8S核心特性 服务发现与负载均衡&#xff1a;无需修改你的应用程序即可使用陌生的服务发现机制。存储编排&#xff1a;自动挂载所选存储系统&#xff0c;包括本地存储。Secret和…...

大数据学习之SCALA分布式语言三

7.集合类 111.可变set一 112.可变set二 113.不可变MAP集合一 114.不可变MAP集合二 115.不可变MAP集合三 116.可变map一 package com . itbaizhan . chapter07 //TODO 2. 使用 mutable.Map 前导入如下包 import scala . collection . mutable // 可变 Map 集合 object Ma…...

[免费]基于Python的Django博客系统【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的基于Python的Django博客系统&#xff0c;分享下哈。 项目视频演示 【免费】基于Python的Django博客系统 Python毕业设计_哔哩哔哩_bilibili 项目介绍 随着互联网技术的飞速发展&#xff0c;信息的传播与…...

ES设置证书和创建用户,kibana连接es

1、启动好es 2、进入es容器 docker exec -it es /bin/bash 3、生成ca证书 ./bin/elasticsearch-certutil ca 注&#xff1a;两个红方框位置直接回车 4、生成cert证书 ./bin/elasticsearch-certutil cert --ca elastic-stack-ca.p12 注&#xff1a;前两个红框直接回车&am…...

“大模型横扫千军”背后的大数据挖掘--浅谈MapReduce

文章目录 O 背景知识1 数据挖掘2 邦费罗尼原则3 TF.IDF4 哈希函数5 分布式文件系统 一、MapReduce基本介绍1. Map 任务2. 按键分组3. Reduce 任务4. 节点失效处理5.小测验&#xff1a;在一个大型语料库上有100个map任务和若干reduce任务&#xff1a; 二、基于MapReduce的基本运…...

< OS 有关 > 阿里云 几个小时前 使用密钥替换 SSH 密码认证后, 发现主机正在被“攻击” 分析与应对

信息来源&#xff1a; 文件&#xff1a;/var/log/auth.log 因为在 sshd_config 配置文件中&#xff0c;已经定义 LogLevel INFO 部分内容&#xff1a; 2025-01-27T18:18:55.68272708:00 jpn sshd[15891]: Received disconnect from 45.194.37.171 port 58954:11: Bye Bye […...

【C++高并发服务器WebServer】-7:共享内存

本文目录 一、共享内存1.1 shmget函数1.2 shmat1.3 shmdt1.4 shmctl1.5 ftok1.6 共享内存和内存映射的关联1.7 小demo 二、共享内存操作命令 一、共享内存 共享内存允许两个或者多个进程共享物理内存的同一块区域&#xff08;通常被称为段&#xff09;。由于一个共享内存段会称…...

Python中容器类型的数据(下)

集合 集合 (set) 是一种可迭代的、无序的、不能包含重复元素的容器类型的数据。 Python中的集合是一种重要的数据结构&#xff0c;以下为你详细介绍&#xff1a; 定义与特点 无序性&#xff1a;集合中的元素没有固定顺序&#xff0c; {1, 2, 3} 和 {3, 2, 1} 在Python中是同一…...

JavaScript系列(45)--响应式编程实现详解

JavaScript响应式编程实现详解 &#x1f504; 今天&#xff0c;让我们深入探讨JavaScript的响应式编程实现。响应式编程是一种基于数据流和变化传播的编程范式&#xff0c;它使我们能够以声明式的方式处理异步数据流。 响应式编程基础概念 &#x1f31f; &#x1f4a1; 小知识…...

uniapp版本升级

1.样式 登录进到首页&#xff0c;弹出更新提示框&#xff0c;且不可以关闭&#xff0c;侧边返回直接退出&#xff01; 有关代码&#xff1a; <uv-popup ref"popupUpdate" round"8" :close-on-click-overlay"false"><view style"…...

K8s运维管理平台 - KubeSphere 3.x 和4.x 使用分析:功能较强,UI美观

目录标题 Lic使用感受优点&#xff1a;优化点&#xff1a; 实操首页项目 | 应用负载 | 配置 | 定制资源定义存储监控告警集群设置 **KubeSphere 3.x** 和 **4.x**1. **架构变化**&#xff1a;2. **多集群管理**&#xff1a;3. **增强的 DevOps 功能**&#xff1a;4. **监控与日…...

使用Python Dotenv库管理环境变量

使用Python Dotenv库管理环境变量 在开发Python应用程序时&#xff0c;管理配置信息&#xff08;如API密钥、数据库连接字符串等&#xff09;是一个常见的需求。为了确保安全性和灵活性&#xff0c;通常不建议将这些敏感信息硬编码在代码中。这时&#xff0c;dotenv库就派上了…...

HTTP 配置与应用(不同网段)

想做一个自己学习的有关的csdn账号&#xff0c;努力奋斗......会更新我计算机网络实验课程的所有内容&#xff0c;还有其他的学习知识^_^&#xff0c;为自己巩固一下所学知识&#xff0c;下次更新校园网设计。 我是一个萌新小白&#xff0c;有误地方请大家指正&#xff0c;谢谢…...

异或哈希总结

例题 例题1https://codeforces.com/problemset/problem/1175/Fhttps://codeforces.com/problemset/problem/1175/F 例题2https://codeforces.com/contest/2014/problem/Hhttps://codeforces.com/contest/2014/problem/H例题4https://codeforces.com/contest/1418/problem/Ght…...

我的2024年总结

趁着摸鱼赶紧写一下吧 去年目标review 还是将去年的目标完成了一些 【接纳不完美&#xff0c;多拍照片】 这个还是部分做到了&#xff0c;今年和一些朋友们见面时都注意拍照留记录了&#xff0c;不过还可以继续加强&#xff0c;因为外貌上发生了重大变化&#xff0c;下面细说…...