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

【算法自由之路】 贪心算法

贪心算法

  1. 局部最右得到全局最右
  2. 难点在于如何证明局部最优可以得到全局最优
  3. 堆 和 排序 是贪心算法最常用的实现算法

贪心算法作为最符合自然智慧的算法,思路是从小部分取最优从而获得最终的最优,但是难得是怎样获取部分最优才能得到全局最优。

有时候我们会有多个局部最优的想法(或者说局部最贪)但是很多时候这些都是陷阱。

如何验证我们的局部最优想法是对的是贪心算法最复杂的地方:

  1. 数学逻辑推算验证 (太过耗时,费力不讨好)
  2. 对数器验证 (推荐

这里推荐使用对数器来进行验证,即写一个最傻的求解方法(如穷举可能性),与我们贪心算法进行验证。

如何想到贪心算法 这个似乎没有捷径,需要阅历经验和敏捷的思考,即多锻炼吧…………

最后抛两个例子

金条分隔问题

给一根长度为 n 的金条,分隔此金条长度为 x, y 两份(x+y =n) 需要和金条长度数值相同的 n 个铜币。

给定一个数组数组和为 n,问最小代价为多少。

例如:

金条长度为 80
给定数组 [50,20,10]
如果
分隔: 70 , 10 花费 80
分隔: 50 , 20 花费 70 总 150相对平均分割
分隔: 50 , 30 花费 80
分隔: 20 , 10 花费 30  总 110
最优解

贪心思路

每次分隔尽量平均。

如何尽量平均?使用小根堆

在这里插入图片描述

public static int separation(int[] arr, int length) {int sum = 0;if (arr == null) {return 0;}Queue<Integer> queue = new PriorityQueue<>();for (int num : arr) {queue.add(num);}while (queue.size() > 1) {int cur = queue.poll() + queue.poll();sum += cur;queue.add(cur);}return sum;}

字符串拼接字典序最小问题

给定字符数组 [‘sdfsd’,‘wef’,‘sew’,‘a’] ,请给出该数组字典序拼接最小的结果

不想写了,说思路吧,贪心最重要的其实就是思路,思路有了解法很简单,基本上排序 或者 用堆 可以解决大部分问题

贪心解法是进行排序,排序比较是根据 如果 o1 拼接 o2 > o2 拼接 o1 则 o1 放到前面

安排会议问题 ,给道 leetcode 的例题吧

1353.最多可以参加的会议数目

在所有开始时间相同的会议中,尽量选择结束时间最小的会议,因为结束时间更大的会议在后续的日程中可选择天数更多

比如在会议:[[1,1],[1,2],[1,3]] 这三个会议中,如果在第 1 天,应该尽量选择 [1,1] 这个会议,因为后面的两个会议,分别可以在第 2 天和第 3 天选择,选择的范围更广

只有这样选择,才可以得到能参加更多的会议

所以,这里我们需要能快速的选择结束时间最小的会议,而且这个最小的结束时间是动态变化的,因为参加了一个会议,就应该排除这个会议

要高效的维护动态数据的最小值可以使用小根堆。

相关文章:

【算法自由之路】 贪心算法

贪心算法 局部最右得到全局最右难点在于如何证明局部最优可以得到全局最优堆 和 排序 是贪心算法最常用的实现算法 贪心算法作为最符合自然智慧的算法&#xff0c;思路是从小部分取最优从而获得最终的最优&#xff0c;但是难得是怎样获取部分最优才能得到全局最优。 有时候我…...

Scratch少儿编程案例-水果忍者-学生作业

专栏分享 点击跳转=>Unity3D特效百例点击跳转=>案例项目实战源码点击跳转=>游戏脚本-辅助自动化点击跳转=>Android控件全解手册点击跳转=>Scratch编程案例👉关于作者...

7.Docker Compose

Docker Compose 介绍 Docker Compose是Docker官方编排&#xff08;Orchestration&#xff09;项目之一&#xff0c;负责快速的部署分布式应用。其代码目前在https://github.com/docker/compose上开源。Compose 定位是 「定义和运行多个 Docker 容器的应用&#xff08;Definin…...

GitHub访问问题与 Steam++下载及使用(适合小白)

前言 &#x1f4dc; “ 作者 久绊A ” 专注记录自己所整理的Java、web、sql等&#xff0c;IT技术干货、学习经验、面试资料、刷题记录&#xff0c;以及遇到的问题和解决方案&#xff0c;记录自己成长的点滴 ​ 目录 前言 一、Steam的介绍 1、大概介绍 2、详细介绍 二、Ste…...

Oracle对象——视图之简单视图与视图约束

文章目录什么是视图为什么会使用视图视图语法案例简单视图的创建更改数据基表&#xff0c;视图数据会变化么&#xff1f;更改视图数据&#xff0c;基表数据会变更么&#xff1f;带检查约束的视图结论创建只读视图&#xff08;MySQL不支持&#xff09;总结什么是视图 视图是一种…...

SAP模块常用增强总结

MM模块&#xff1a; 采购订单增强&#xff1a; BADI &#xff1a;ME_GUI_PO_CUST ME_PROCESS_PO_CUST 物料凭证增强&#xff1a; BADI&#xff1a;MB_DOCUMENT_BADI USER-EXIT&#xff1a;MBCF0002 实现功能1、当参照预留过帐时&#xff0c;检查填入数量是否小于预留数量 2…...

当make执行遇到 Arguments too long

1. 问题 Ubuntu20.04上make编译生成so的时候报错&#xff1a; make[1]:execvp:/bin/sh:Arguments too long对应makefile中的报错位置&#xff0c;仅仅是生成so的时候报错&#xff0c;伪代码如下 ${build_tool} -shared -fpic -o "$" ${OBJ_FILE} ${LDFLAGS}然而如…...

《手把手教你》系列基础篇(七十三)-java+ selenium自动化测试-框架设计基础-TestNG实现启动不同浏览器(详解教程)

1.简介 上一篇文章中&#xff0c;从TestNg的特点我们知道支持变量&#xff0c;那么我们这一篇就通过变量参数来启动不同的浏览器进行自动化测试。那么如何实现同时启动不同的浏览器对脚本进行测试&#xff0c;且听我娓娓道来。 2.项目实战 2.1创建一个TestNg class 1.首先按…...

Maven基础

Maven简介 传统项目&#xff1a; jar包不统一 不兼容 项目中有部分jar包会升级 没升级的部分会起冲突 管理复杂 Maven本质是一个项目管理工具 pom POM Project Object Model 项目对象模型 把项目以对象形式进行管理 先写 pom.xml 的配置文件 代表一个项目 1个项目对应1个po…...

C++入门:初识类和对象

C入门&#xff1a;类和对象1 本节目录C入门&#xff1a;类和对象11.auto关键字&#xff08;C11)1.1类型别名思考1.2auto简介typeid运算符&#xff1a;获取类型信息1.3 auto的使用细则1.4auto不能推到的场景2.基于范围的for循环(C11)2.1范围for的语法2.2范围for的使用条件3.指针…...

BERT在CNN上也能用?看看这篇ICLR Spotlight论文丨已开源

如何在卷积神经网络上运行 BERT&#xff1f;你可以直接用 SparK —— 字节跳动技术团队提出的提出的稀疏层次化掩码建模 ( Designing BERT for Convolutional Networks: Sparse and Hierarchical Masked Modeling )&#xff0c;近期已被人工智能顶会 ICLR 2023 收录为 Spotligh…...

【MFC】模拟采集系统——界面设计(17)

功能介绍 启动界面 开始采集&#xff1a; PS&#xff1a;不涉及 数据保存&#xff0c;重现等功能 界面设计 界面分为三块&#xff1a;顶部黑条带关闭按钮、左边对话框&#xff0c;右边的主界面 资源&#xff1a; 顶部黑条 top.bmp 2* 29 &#xff08;宽 * 高 像素点&…...

锐捷(十五)mpls vxn跨域optionc场景

一 实验拓扑二 实验需求ce1和ce2为两个分公司&#xff0c;要求两个分公司之间用mpls vxn 进行通信&#xff0c;组网方式是optionc。三 实验分析optionc在转发平面上有点难理解&#xff0c;有一些关键点需要注意&#xff0c;大家点击链接可以参考我上篇发过的一个文章&#xff1…...

2023备战金三银四,Python自动化软件测试面试宝典合集(七)

马上就又到了程序员们躁动不安&#xff0c;蠢蠢欲动的季节~这不&#xff0c;金三银四已然到了家门口&#xff0c;元宵节一过后台就有不少人问我&#xff1a;现在外边大厂面试都问啥想去大厂又怕面试挂面试应该怎么准备测试开发前景如何面试&#xff0c;一个程序员成长之路永恒绕…...

redis 主从复制

在redis的持久化RDB与AOF详解文章中&#xff0c;我们知道如果redis宕机了&#xff0c;我们可以通过AOF 和 RDB 文件的方式恢复数据&#xff0c;从而保证数据的丢失&#xff08;或少量损失&#xff09;从而提高稳定性。但是&#xff0c;如果我们数据只存在一台redis服务器中&…...

如何用Redis实现延迟队列

背景前段时间有个小项目需要使用延迟任务&#xff0c;谈到延迟任务&#xff0c;我脑子第一时间一闪而过的就是使用消息队列来做&#xff0c;比如RabbitMQ的死信队列又或者RocketMQ的延迟队列&#xff0c;但是奈何这是一个小项目&#xff0c;并没有引入MQ&#xff0c;我也不太想…...

项目文件相关总结

风险登记册 风险登记册记录了已识别单个风险的详细信息。其主要内容包括: 已识别的风险清单潜在的风险责任人潜在的风险应对措施清单风险管理计划要求的其他信息供方选择标准 供方选择标准用于确保选出的建议书将提供最佳质量的所需服务,主要内容 包括: 能力和潜力产品成本…...

ZooKeeper集群搭建步骤

一、准备虚拟机准备三台虚拟机&#xff0c;对应ip地址和主机名如下&#xff1a;ip地址Hostname192.168.153.150ant163192.168.153.151ant164192.168.153.152ant165修改hostname&#xff0c;并使之生效[rootlocalhost /]# hostnamectl set-hostname zookeeper1 //修改hostname …...

网际协议IP

网际协议IP 文章目录网际协议IP[toc]虚拟互联网IP地址及其表示方法分类IP地址(两级)无分类编址 CIDR网路前缀地址块地址掩码子网划分&#xff08;三级IP地址&#xff09;IP地址和MAC地址地址解析协议ARPIP数据报的格式IP数据报首部的固定部分中的各字段IP数据报首部的可变部分分…...

Python 语言参考手册、教程、标准库

官方文档&#xff1a;https://docs.python.org/zh-cn/3.11/ Python 语言参考手册 介绍了 Python 句法与“核心语义”。在力求简明扼要的同时&#xff0c;我们也尽量做到准确、完整。有关内置对象类型、内置函数、模块的语义在 Python 标准库 中介绍。有关本语言的非正式介绍&am…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...