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

贪心算法(一)

一、概念

贪心算法的核心思想是,在处理一个大问题时,划分为多个局部并在每个局部选择最优解,并且认为在每个局部选择最优解,那么最后全局的问题得到的就是最优解。

贪心算法可以解决一些问题,但是不适用于所有问题,也不保证使用贪心算法得出的就是最优解。

维基百科更详细的解释:

 二、分配问题

先来看一道简单的分配问题:

力扣icon-default.png?t=N176https://leetcode.cn/problems/assign-cookies/解题思路:

孩子的胃口值需要小于等于饼干大小,根据贪心算法的局部最优解的思想,就是给每个孩子分配能满足她胃口的最小的饼干,且应该优先处理胃口小的孩子。

C++代码:

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int i = 0, j = 0;while(i<g.size()&&j<s.size()){if(g[i]<=s[j]){i++;}j++;}return i;}
};

下面这题难度略大一些,同样也是分配问题:

力扣icon-default.png?t=N176https://leetcode.cn/problems/candy/

解题思路:

每个孩子需要与左右两边的孩子比较评分,贪心算法的运用在于从左到右遍历一次评分数组,每个元素只考虑是否比左边的元素大,再从右到左遍历一次评分数组,每个元素只考虑是否比右边的元素大。这样两次遍历后,就能得到同时满足左右限制的糖果数量了。

C++代码:

class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();vector<int> c(n,1);for(int i=1;i<n;i++){if(ratings[i]>ratings[i-1]){c[i] = c[i-1] + 1;}}for(int i=n-2;i>=0;i--){if(ratings[i]>ratings[i+1]){c[i] = max(c[i], c[i+1] + 1);}}return accumulate(c.begin(), c.end(), 0);}
};

相关文章:

贪心算法(一)

一、概念 贪心算法的核心思想是&#xff0c;在处理一个大问题时&#xff0c;划分为多个局部并在每个局部选择最优解&#xff0c;并且认为在每个局部选择最优解&#xff0c;那么最后全局的问题得到的就是最优解。 贪心算法可以解决一些问题&#xff0c;但是不适用于所有问题&a…...

【栈和队列OJ题】有效的括号用队列实现栈用栈实现队列设计循环队列

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录OJ题1.有效的括号1.1…...

kuernetes 资源对象分析报错

文章目录1. pod 状态1.1 容器启动错误类型1.2 ImagePullBackOff 错误1.3 CrashLoopBackOff1.4 Pending2. Service 连接状态3. Ingress 连接状态1. pod 状态 创建一个 pod-status.yaml apiVersion: v1 kind: Pod metadata:name: runninglabels:app: nginx spec:containers:- na…...

动态内存的开辟

&#x1f436;博主主页&#xff1a;ᰔᩚ. 一怀明月ꦿ ❤️‍&#x1f525;专栏系列&#xff1a;线性代数&#xff0c;C初学者入门训练&#xff0c;题解C&#xff0c;C的使用文章&#xff0c;「初学」C &#x1f525;座右铭&#xff1a;“不要等到什么都没有了&#xff0c;才下…...

【蓝桥杯-筑基篇】搜索

&#x1f353;系列专栏:蓝桥杯 &#x1f349;个人主页:个人主页 目录 递归树 1.递归构建二进制串 2.全排列的 DFS 解法 3.全排列的 BFS 解法 4.数的划分法 5.图书推荐 递归树 递归树是一种用于分析递归算法时间复杂度的工具。它可以将递归算法的执行过程可视化&#xf…...

week5-质数-最大公约数-快速幂-组合计数-博弈论

蓝桥 等差数列——欧几里得算法质数质数的判定——试除法分解质因数——试除法筛质数——埃氏筛法筛质数——线性筛法质数问题质数距离约数试除法求约数约数个数约数之和最大公约数-欧几里得算法(辗转相除法)扩展欧几里得算法裴蜀定理应用——线性同余方程消灭老鼠Hankson的趣…...

CloudCompare 二次开发(6)——插件中拖拽添加Qt窗口(区域生长算法为例)

目录 一、概述二、插件制作三、Cmake编译四、插件代码五、结果展示一、概述 手动拖拽的方式搭建Qt对话框界面的制作流程,以PCL中的点云区域生长算法为例进行制作。 二、插件制作 1、将....\plugins\example路径下的ExamplePlugin复制一份并修改名字为CCPointCloudProcess。 …...

2023值得推荐的高颜值Vue3.0 Web PC端UI框架,赶紧收藏学习!

Hello&#xff0c;我是前端胡说&#xff0c;本期给大家带来2023值得推荐的Vue3.0 UI组件库&#xff0c;希望大家喜欢&#xff01; Vue3 正式发布已经有一段时间了&#xff0c;2022年2月也正式变成 Vue 项目的默认版本。在过去一年多的时间里&#xff0c;各大组件库、框架也紧跟…...

Springboot项目Aop、拦截器、过滤器横向对比

前言伟人曾经说过&#xff0c;没有调查就没有发言权(好像是伟人说的&#xff0c;不管谁说的&#xff0c;这句话是正确的)&#xff0c;有些东西看着简单&#xff0c;张口就来&#xff0c;但很有可能是错的。我个人的经验是&#xff0c;aop、过滤器、拦截器的实现方式很简单&…...

为了之后找工作不被虐,每天刷3道《剑指offer》Day-1

本文已收录于专栏&#x1f33b;《刷题笔记》文章目录前言&#x1f496; 1、二维数组中的查找题目描述思路&#x1f496; 2、替换空格题目描述思路&#x1f496; 3、从尾到头打印链表题目描述思路一&#xff08;反转函数&#xff09;思路二&#xff08;递归&#xff09;思路二&a…...

Linux-磁盘管理介绍

Linux-磁盘管理介绍 计算硬盘介绍 硬盘是计算机主要存储媒介之一&#xff0c;由一个或者多个铝制或者玻璃制的碟片组成&#xff0c;碟片外覆盖有铁磁性材料&#xff0c;硬盘内部由磁道、柱面、扇区、磁头等部件组成; cylinder&#xff1a;柱面sector&#xff1a;扇区 磁道与…...

爬虫架构(一):爬虫中的去重处理

目录一、概要二、去重应用场景以及基本原理2.1 爬虫中什么业务需要使用去重2.2 去重实现的基本原理2.3 根据原始数据进行去重判断2.4 根据原始数据的特征值进行去重判断2.5 临时去重容器与持久化去重容器2.6 常用几种特殊的原始数据特征值计算三、基于信息摘要算法的去重3.1 信…...

算法刷题总结 (二) 回溯与深广搜算法

算法总结2 回溯与深广搜算法一、理解回溯算法1.1、回溯的概念1.2、回溯法的效率1.3、回溯法问题分类1.4、回溯法的做题步骤二、经典问题2.1、组合问题2.1.1、77. 组合 - 值不重复2.1.2、216.组合总和III - 值不重复且等于目标值2.1.3、17. 电话号码的字母组合 - 双层回溯2.1.4、…...

Linux 总结9个最危险的命令,一定要牢记在心!

rm -rf 命令 该命令可能导致不可恢复的系统崩坏。 rm -rf / #强制删除根目录下所有东西。 rm -rf * #强制删除当前目录的所有文件。 rm -rf . #强制删除当前文件夹及其子文件夹。 执行rm -rf 一定要想半天,搞明白自己在干什么. fork 炸弹 &#x1f626;) { &#x1f610;:&am…...

spring cloud

spring cloud 分享 springboot&#xff1a;可以说是spring cloud的基础&#xff0c;是springMVC框架的简化&#xff0c;约定大于配置&#xff08;在使用上、非功能上的简化&#xff09; 可以说每个MPO Digital api就是springboot project(springboot项目) spring cloud&#xf…...

【9】核心易中期刊推荐——图像视觉与图形可视化

🚀🚀🚀NEW!!!核心易中期刊推荐栏目来啦 ~ 📚🍀 核心期刊在国内的应用范围非常广,核心期刊发表论文是国内很多作者晋升的硬性要求,并且在国内属于顶尖论文发表,具有很高的学术价值。在中文核心目录体系中,权威代表有CSSCI、CSCD和北大核心。其中,中文期刊的数…...

0108Bean销毁-Bean生命周期详解-spring

Bean使用阶段&#xff0c;调用getBean()得到bean之后&#xff0c;根据需要&#xff0c;自行使用。 1 销毁Bean的几种方式 调用org.springframework.beans.factory.support.AbstractAutowireCapableBeanFactory#destroyBean调用org.springframework.beans.factory.config.Conf…...

微信小程序可以进行dom操作吗?

小程序不能使用各种浏览器暴露出来的 DOM API&#xff0c;进行 DOM 选中和操作 原因&#xff1a;在小程序中&#xff0c;渲染层和逻辑层是分开的&#xff0c;分别运行在不同的线程中&#xff0c;逻辑层运行在 JSCore 中&#xff0c;并没有一个完整浏览器对象&#xff0c;因而缺…...

昇腾AI深耕沽上:港口辐射力之后,天津再添基础创新辐射力

作者 | 曾响铃 文 | 响铃说 AI计算正在以新基建联动产业集群的方式&#xff0c;加速落地。 不久前&#xff0c;天津市人工智能计算中心正式揭牌&#xff0c;该中心整体规划300P算力&#xff0c;2022年底首批100P算力上线投入运营&#xff0c;并实现上线即满载。 这是昇腾AI…...

基于YOLOv5的疲劳驾驶检测系统(Python+清新界面+数据集)

摘要&#xff1a;基于YOLOv5的疲劳驾驶检测系统使用深度学习技术检测常见驾驶图片、视频和实时视频中的疲劳行为&#xff0c;识别其闭眼、打哈欠等结果并记录和保存&#xff0c;以防止交通事故发生。本文详细介绍疲劳驾驶检测系统实现原理的同时&#xff0c;给出Python的实现代…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...