-
ZooKeeper的名字空间节点(有关znode的一切)
2016-07-16 20:24:48上一篇有人跟我说比较深奥和抽象,确实,我写这个不是按照循序渐进的写法写的,而是先写那本OREILLY书最不清楚的部分,然后再写次不清楚的……到最后会覆盖zk的绝大多数特性,这时候会再给出一个阅读次序的建议。...上一篇有人跟我说比较深奥和抽象,确实,我写这个不是按照循序渐进的写法写的,而是先写那本OREILLY书最不清楚的部分,然后再写次不清楚的……到最后会覆盖zk的绝大多数特性,这时候会再给出一个阅读次序的建议。这篇来说说有关znode的一切,比较容易理解,也很容易通过zkCli.sh来实验。分层名字空间上图是ZooKeeper的分层名字空间的示意图,可见这种结构很像典型的文件系统结构:以/分割各元素的一种路径,ZooKeeper名字空间的每个节点都是以这样一个路径来标识的。这样的节点统一称为znode。Znode然而,ZooKeeper的名字空间和文件系统仍有着显著的差别。文件系统典型地有目录和文件,目录可包含其他目录或文件,文件则实际存储数据。而znode既可以有其他子znode,又可以存放数据(严格说是必须存放数据,真没有的话得给个“”),因此znode可以看做是目录和文件的合体。znode被用来存储Byte级或KB级的数据,如状态信息、配置信息、位置信息等,因此znode可存放数据量的最大值默认被设为1MB,请注意,该值不仅计算数据的Byte数,所有子节点的名字也要折算成Byte数计入,因此znode的子节点数也不是无限的。改大这个参数可以存储更多数据或包含更多子znode,但我非常不建议这样做,因为这与ZooKeeper的设计目的相悖,只有数据足够小,才能保证ZooKeeper的高读取性能。如果要存储大量数据,有的是其他解决方案。除了数据外,znode还管理了其他一些元数据,存储在stat对象中:- 版本号:znode的数据每次更新时,该版本号递增。当客户端请求该znode时,数据和版本号会一起发回。另外,当znode重建时版本号会被重置,这似乎很自然,但很多时候这是巨坑的来源,比如:客户端执行了’set /test “testdata” 1’,即指定版本1写/test节点,之后该znode被删除重建,数据默认置为“”,版本号还是1,此时客户端请求时虽然该版本号仍然存在,但已经是错误的数据了。
- ACL:即Access Control List,用来限定哪些账号可以操作该znode。ZooKeeper内置了4种ACL模式,第1种是any,即不鉴权;第2种是super,即不受任何ACL约束的管理员模式;第3种是digest,使用用户名和密码进行认证;第4种是SASL,通常使用Kerberos协议来认证,但Kerberos也是个大坑,并且对性能也有一定影响。
- 时间戳:其实就是zxid,存储该znode创建或修改时的时间戳,用于缓存验证或协调更新等。
理解了这些就可以做点操作了,所有zkCli.sh的命令如下,主要掌握ls,get,set,create,delete几个就够玩了(应该明白为何zkCli下没有cd这样的命令):ZooKeeper -server host:port cmd argsconnect host:portget path [watch]ls path [watch]set path data [version]rmr pathdelquota [-n|-b] pathquitprintwatches on|offcreate [-s] [-e] path data aclstat path [watch]closels2 path [watch]historylistquota pathsetAcl path aclgetAcl pathsync pathredo cmdnoaddauth scheme authdelete path [version]setquota -n|-b val pathZnode的四种类型持久节点/临时节点:持久节点只能用delete来删除,通常用来保存应用的持久化数据,比如主从模式下的任务分派情况,这种数据不应该由于主节点的崩溃而丢失。临时节点则顾名思义,除了客户端主动删除该节点时会消失外,创建该znode的客户端断开连接时该节点也会消失,因此它常用来检测会话的有效性,例如主从模式下的主节点注册一个znode,当该主节点崩溃或断开时,该znode会立即消失,于是应用可以检测到该故障并重新选举主节点,这种用法极为常见比如kafka。另外,临时节点不允许有子节点。有序节点:znode还可以被设置为有序节点,当这样的节点被创建时,一个会自动递增的序号会加到路径之后,比如客户端创建一个有序znode并指定路径为/tasks/task,则第一个创建的节点是/tasks/task-0000000001,该节点消亡后再创建这样的节点会产生/tasks/task-0000000002,以此类推。有序znode提供了创建具有唯一命名的znode的方式。这两种类型互相结合后就会产生znode的四种类型:持久的,临时的,持久有序的,临时有序的。监视和通知我们知道,访问ZooKeeper的基本方式是使用API,很多场景我们需要访问一个znode,如果使用轮询的方式,不仅不能实时知晓变更(取决于轮询间隔),更恶劣的是会大大增加ZooKeeper的负载。比较好的方式是,对该znode设置一个监视(watch),当某些事件发生时触发一个通知(notification)。注意监视点是一次性的,如果通知被触发后还需要继续监视该znode,则需要设置一个新的watch。ZooKeeper异步通知设置watch的客户端。但是ZooKeeper能够保证在znode的变更生效之后才会异步地通知客户端,然后客户端才能够看到znode的数据变更。由于网络延迟,多个客户端可能会在不同的时间看到znode数据的变更,但是看到变更的顺序是保证有序的。Znode可以设置两类watch,一个是Data Watches(该znode的数据变更导致触发watch事件),另一个是Child Watches(该znode的孩子节点发生变更导致触发watch事件)。API和watch间的关系如下表:Java APIData WatchesChild WatchesgetData设置exists设置setData触发create触发getChildren设置create某znode的子节点触发delete触发触发如删除的znode有父节点,其父节点上也触发当某个znode的变化可触发监视点时,ZooKeeeper会触发其上可触发的所有监视点,这在某些情况下可能会产生问题,如1000个客户端都在监视某znode的Data时,当该znode的数据发生变化,会触发1000个通知,这会造成性能的波动,比如同一时刻的提交操作可能延迟。解决这一问题,OREILLY书上给出了一个利用有序节点的办法(这块书上写的不错,但翻译依旧很烂,现实中很常用所以整理下):例如n个客户端都抢一把锁。第一种方法是抢到的客户端创建/lock节点,其余客户端便监视该节点的删除事件,当占用锁的客户端完成操作断开时,/lock节点删除,其他客户端获得通知,这种方法就有性能问题。另一种方法是,所有客户端均创建有序节点/lock/lock-xxx,其中xxx为序号,xxx最小的客户端获得锁,其余客户端监视前一个节点,例如有/lock/lock-001,/lock/lock-002,/lock/lock-003三个节点时,001的客户端获得锁,002的客户端监视001的znode,003的客户端监视002的znode,当001的锁释放时,002即获得锁,以此类推,这种方式下每个znode上监视的客户端只有一个,尽管总watches数是一样的,却不会造成性能的波动。监视点也是有存储开销的,一个监视点对应服务端的一个Watcher对象,大约消耗300字节内存,因此管理大量的监视点也有不小的开销,运维人员应该注意连接数和产生的监视点数,以免造成OOM。另外,如果客户端与ZooKeeper断开连接,客户端就无法触发watches,除非再次与ZooKeeper建立连接。关于znode暂时能想到的就这些,如有遗漏会在后续的章节中进行补充。 -
C++编程惯用法(高级程序员常用方法和技巧)/深入C++系列(C++ Strategies and Tactics)
2010-09-24 16:17:294.7 有关继承的细节和陷阶 4.8 小结 4.9 问题 第5章 多重继承 5.1 作为交集的多重继承 5.2 虚基类 5.3 一些有关多重继承的细节问题 5.4 小结 5.5 问题 第6章 考虑继承的设计 6.1 被保护的接口 6.2 我们的设计是否... -
SQL Server 2008数据库设计与实现(关系数据库实现的通关宝典)--随书源代码
2013-02-06 12:04:00对于Louis而言,他全部的职业经验几乎都与微软的SQL Server有关,从早期版本一直到当前最新版本的Beta版。Louis是一本讲数据库设计的书的4个版本的主要作者。Louis主要的兴趣领域是数据库架构和用T-SQL编码,并且,... -
精通Android游戏开发(将本地PC游戏轻松移植到Android的秘技)--详细书签版
2013-02-08 11:30:55曾在IBM担任过4年研究工程师,在此期间积累了有关分布式和网格计算研究的丰富经验。为IBM发表过多篇计算机科学文章。除本书外,他还著有Grid Computing for Developers 和Practical Eclipse RCP Projects。 目录 ... -
车间实习总结.doc
2020-12-27 10:56:56老师指导着我一点一点的填写过序单,让我熟悉这里的员工,以免填错他们的名字。员工们生产的产品的质量直接与他们的工资有关。我的任务就是把这些产品的合格率与缺陷率算出来。当然了,原始数据还是填写的过序单上的... -
React堆样板-源码
2021-02-25 06:27:58项目名称 项目描述的一个段落在这里 安装 您需要什么东西来安装软件以及如何安装它们 Give examples 配置选项 一系列循序渐进的示例,告诉您如何运行开发环境 建于 使用的Web框架 ...你的名字可能在这里 -
C++程序设计语言(特别版)--详细书签版
2012-04-23 07:13:038.2.1 带限定词的名字 151 8.2.2 使用声明 152 8.2.3 使用指令 153 8.2.4 多重界面 154 8.2.5 避免名字冲突 157 8.2.6 名字查找 159 8.2.7 名字空间别名 159 8.2.8 名字空间组合 160 8.2.9 名字空间和老代码... -
C++程序设计语言(特别版)--课后习题源代码
2012-04-23 07:37:348.2.1 带限定词的名字 151 8.2.2 使用声明 152 8.2.3 使用指令 153 8.2.4 多重界面 154 8.2.5 避免名字冲突 157 8.2.6 名字查找 159 8.2.7 名字空间别名 159 8.2.8 名字空间组合 160 8.2.9 名字空间和老代码... -
C++程序设计语言(特别版)--源代码
2012-04-23 07:33:518.2.1 带限定词的名字 151 8.2.2 使用声明 152 8.2.3 使用指令 153 8.2.4 多重界面 154 8.2.5 避免名字冲突 157 8.2.6 名字查找 159 8.2.7 名字空间别名 159 8.2.8 名字空间组合 160 8.2.9 名字空间和老代码... -
C#微软培训教材(高清PDF)
2009-07-30 08:51:1718.2 在 C #代码中调用 C++和 VB 编写的组件 .240 18.3 版 本 控 制 .249 18.4 代 码 优 化 .252 18.5 小 结 .254 第五部分 附 录 .255 附录 A 关 键 字.255 附录 B 错 误 码.256 附录 C .Net 名字空间... -
最权威的C++教程_C++_Primer_Plus中文第五版+C++_Primer中文第四版(都含源码+习题)(共4分卷)分卷1
2010-06-23 17:33:55还要学习有关递归的知识(即函数在什么情况下调用自身)以及如何用它来实现分而治之的策略。最 后将介绍函数指针,它使程序员能够通过函数参数来命令函数使用另一个函数。 第8章:函数探幽 本章将探索C++中函数... -
最权威的C++教程_C++_Primer_Plus中文第五版+C++_Primer中文第四版(都含源码+习题)(共4分卷)分卷2
2010-06-23 17:47:19还要学习有关递归的知识(即函数在什么情况下调用自身)以及如何用它来实现分而治之的策略。最 后将介绍函数指针,它使程序员能够通过函数参数来命令函数使用另一个函数。 第8章:函数探幽 本章将探索C++中函数... -
最权威的C++教程_C++_Primer_Plus中文第五版+C++_Primer中文第四版(都含源码+习题)(共4分卷)分卷3
2010-06-23 18:03:39还要学习有关递归的知识(即函数在什么情况下调用自身)以及如何用它来实现分而治之的策略。最 后将介绍函数指针,它使程序员能够通过函数参数来命令函数使用另一个函数。 第8章:函数探幽 本章将探索C++中函数... -
C#微软培训资料
2014-01-22 14:10:1718.2 在 C #代码中调用 C++和 VB 编写的组件 .240 18.3 版 本 控 制 .249 18.4 代 码 优 化 .252 18.5 小 结 .254 第五部分 附 录 .255 附录 A 关 键 字.255 附录 B 错 误 码.256 附录 C .Net 名字空间... -
antlr4权威指南
2017-09-30 10:47:22免费的在线文档提供了足够多有关基础语法的句法和语义的资料,不过没有详细解释ANTLR的相关概念。在本书中,识别语言的语法模式和将其表述为ANTLR语法的内容是独一无二的。贯穿全书的示例能够在构建语言类应用程序... -
你必须知道的495个C语言问题
2015-08-22 15:18:112.13 怎样在运行时用名字访问结构中的域? . . . . . . . . . . . . . . . 10 2.14 程序运行正确, 但退出时却“core dump”了,怎么回事? . . . . . 10 2.15 可以初始化一个联合吗? . . . . . . . . . . . . . . .... -
初学MVC
2010-01-31 13:58:43MVC(Model-View-Control)在我看来是一种设计思想,能够帮助我们设计出结构清晰的和序。而且,我还认为,既然是一种思想,就还可以应用的更多其它的领域。 MVC从英文名字就能理解其一共划分为三大模块: Model:...MVC(Model-View-Control)在我看来是一种设计思想,能够帮助我们设计出结构清晰的和序。而且,我还认为,既然是一种思想,就还可以应用的更多其它的领域。
MVC从英文名字就能理解其一共划分为三大模块:
Model:模型层,主包数据的处理,即是业务逻辑。所有与数据有关的操作都应当在这个模块中实现.
View:视图层,即展现给用户的,其次就是提交用户的请求。它将模型层处理好的数据通过一定的编排后,以用户易易于接受的方式展示出来,所以这个层面主要是由美工做的。
Control:控制层 控制层就像连接模型层和视图层的管道,负责所有的请求与转发业务。主要由Servlet实现。它既不管具体业务是怎么处理的,也不管用户看到的是什么。它根据用户的请求把事件转发至相应的处理单元,再将处理结果转发给用户。
MVC模型的优点
1. 低耦合性,视图层和业务层的分离,可以使得更改视图层的代码而不用重新编译模型和控制器代码。三层分离,又增加了程序设计的灵活性,当一个应用的业务流程或者业务规则需要改变时只需改动MVC的模型层,而界面表现的改变只需改动MVC的视图层。
2. MVC的三层分离可以让不同的开发者负责不同的模块,就可以分工,分工就可以快速部署,就可以提高效率,相当大的缩短开发时间,按照传统的责任划分来处理软件开发过程,使开发者专心于一个领域,从而极大地提高了软件的开发效率,也因此,MVC模型适合于团队开发。
3. 高重用性和可试性,MVC模式允许使用各种不同样式的视图来访问同一个服务器的代码,包括任何WEB(HTTP)浏览器或者无线浏览器(WAP)。
4. 可维护性,三层的分离使得WEB应用更易于维护和修改。
5. 较低的生命周期成本。
6. 有利于软件工程化管理,不同的层各司其职,每一层不同的应用具有某些相同的特征,有利于工程化、工具化管理程序代码。
7. 模型的部分,因为足够抽象,可以方便地重复利用,另一方面利用单元测试工具对模型进行单元测试,保证工程质量。
MVC模型的缺点
1. 增加了系统结构和实现的复杂性。对于简单的界面,严格遵循MVC,使模型、视图和控制器分离,会增加结构的复杂性,并肯能产生过多的更新操作,降低运行效率。
2. 视图与控制器过于紧密的连接。视图与控制器是相互分离的,但却又是联系紧密的部件,视图没有控制器的存在,其应用是有限的,反之亦然,这就妨碍了他们的独立重用。
3. 视图对模型数据的低效率访问。依据模型操作接口的不同,视图可能需要多次调用才能获得足够的显示数据。对为变化数据的不必要的频繁访问,也将损害操作。
4. MVC模式应用于J2ME上增大了代码体积。据不完全统计,使用了MVC模式后,代码体积约是不是用的1.5倍,这对于存储容量十分有限的移动设备是致命的。
5. MVC的3个定义不是很具体,对于3个部件的具体功能还存在着一些争议,给初学者留下不少陷阱,加大了使用MVC模式的难度。
6. 目前,一般高级的界面工具或构造器不支持MVC模式,改造这些工具一适应MVC需要和建立分离的部件的代价很高,从而也造成了使用MVC的困难。 -
TCP/IP网络互联技术(卷3):客户-服务器编程与应用(Windows套接字版)--详细书签版
2013-06-27 07:31:35重点放在客户—服务器机制上,介绍了客户-服务器机制和应用程序用于网络通信的套接字接口,分析了分布式程序的客户端和服务器两部分的算法,讨论了客户端和服务器的设计及遵循的模式。本书在并发处理上也花费了相当... -
你必须知道的495个C语言问题(PDF)
2009-09-15 10:25:472.13 怎样在运行时用名字访问结构中的域? . . . . . . . . . . . . . . . 10 2.14 程序运行正确, 但退出时却“core dump”了,怎么回事? . . . . . 10 2.15 可以初始化一个联合吗? . . . . . . . . . . . . . . .... -
软著材料样例直接修改就行
2020-11-03 17:35:49申请表要盖你们学校的章; + 说明文档图片一定要清晰; + 名字一定要以什么什么系统结尾等格式,去指南里看,不然会退回重新弄,麻烦;... + 源程序和说明书word文档一定要有页眉和页码编号,页眉是你的系统名称和 -
c++ 程序设计
2019-01-20 22:53:37本书使读者对C++的全貌有基本的认识,用容易理解的方法讲清楚有关的基本概念和基本方法。 (2)全新体系,内容翔实。 本书以面向过程的程序设计为切入点,从编写简单的程序开始,循序渐进,由面向过程、基于对象到... -
中文版Excel.2007公式与函数应用宝典 1/2
2012-04-06 18:29:445.3.9 提取名字的名、中间名和姓 5.3.10 删除名字中的称谓 5.3.11 计算单元格中词的数量 5.4 自定义VBA文本函数 第6章 处理Et期和时间 6.1 Excel如何处理日期和时间 6.1.1 了解日期序列号 6.1.2 输入日期 ... -
中文版Excel.2007公式与函数应用宝典 2/2
2012-04-06 18:37:145.3.9 提取名字的名、中间名和姓 5.3.10 删除名字中的称谓 5.3.11 计算单元格中词的数量 5.4 自定义VBA文本函数 第6章 处理Et期和时间 6.1 Excel如何处理日期和时间 6.1.1 了解日期序列号 6.1.2 输入日期 ... -
左神算法初级班笔记6:前缀树、贪心
2020-09-11 09:47:25前缀树又名字典树,单词查找树,Trie树,多路树形结构,和hash效率有一拼,是一种用于快速检索的多叉树结构。多用于词频搜索或者模糊查询。 查询时只与样本长度有关,而与样本量无关。 如下图所示,将字母写在...01 | 前缀树
-
前缀树又名字典树,单词查找树,Trie树,多路树形结构,和hash效率有一拼,是一种用于快速检索的多叉树结构。多用于词频搜索或者模糊查询。
-
查询时只与样本长度有关,而与样本量无关。
-
如下图所示,将字母写在边上。
-
代码实现:
public class Code_01_TrieTree { public static class TrieNode { public int path; public int end; public TrieNode[] nexts; public TrieNode() { path = 0; //有多少个结点到达过 end = 0; //有多少个字符串以这个结点结尾 nexts = new TrieNode[26]; //通向子节点的路,如果题目所给的范围不确定就用map } } public static class Trie { private TrieNode root; public Trie() { //准备一个头结点 root = new TrieNode(); } //将一个单词插入 public void insert(String word) { if (word == null) { return; } char[] chs = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (node.nexts[index] == null) { node.nexts[index] = new TrieNode(); } node = node.nexts[index]; node.path++; } node.end++; } //在结构中删除这个单词 public void delete(String word) { if (search(word) != 0) { char[] chs = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (--node.nexts[index].path == 0) { //如果某个结点-1之后==0,则说明此节点之后的结点也是-1之后==0,因此直接=null即可。 node.nexts[index] = null; return; } node = node.nexts[index]; } node.end--; } } //查找某个单词插入了几次 public int search(String word) { if (word == null) { return 0; } char[] chs = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } return node.end; } //查某个字符串前缀数量是多少 public int prefixNumber(String pre) { if (pre == null) { return 0; } char[] chs = pre.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } return node.path; } } public static void main(String[] args) { Trie trie = new Trie(); System.out.println(trie.search("zuo")); trie.insert("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuo"); trie.insert("zuo"); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuoa"); trie.insert("zuoac"); trie.insert("zuoab"); trie.insert("zuoad"); trie.delete("zuoa"); System.out.println(trie.search("zuoa")); System.out.println(trie.prefixNumber("zuo")); } }
-
举个栗子:一个字符串类型的数组arr1,另一个字符串类型的数组arr2。
arr2中有哪些字符,是arr1中出现的?请打印
- 对应上述代码中的search(String word)功能。
arr2中有哪些字符,是作为arr1中某个字符串前缀出现的?请 打印
- 对应上述代码中的prefixNumber(String pre)
arr2中有哪些字符,是作为arr1中某个字符串前缀出现的?请打印 arr2中出现次数最大的前缀。
- 对应上述代码中的prefixNumber(String pre)
02 | 贪心算法
不要企图证明贪心的正确性,想几个贪心策略之后,用对数器去证明正确的即可。
- 贪心算法:在对问题求解时,总是做出在当前看来是最好的选择(最小,最大,最优等等)。也就是说,不从整体最优上加以考虑,它所做出的仅是在某种意义上的局部最优解。
- 贪心策略适用的前提是:局部最优策略能导致产生全局最优解。
- 贪心算法的解题思路:把求解的问题分成若干个子问题,对每一子问题求解,得到子问题的局部最优解;把子问题的解局部最优解合成原来解问题的一个解。
- 贪心策略靠经验和积累,没有其他办法。
1.按最低字典序拼接字符串
给定一个字符串类型的数组strs,找到一种拼接方式,使得把所 有字符串拼起来之后形成的字符串具有最低的字典序。
- 字典序:对于字符串,先按首字符排序,如果首字符相同,再按第二个字符排序,以此类推。如aa,ab,ba,bb,bc就是一个字典序。
- 解题思路:str1.str2 <= str2.str1,则 str1 放前面,否则 str2 放前面(根据两个字符串拼接的结果的大小来决定排序),不能直接根据str1和str2的大小比较决定位置排放,比如:b和ba,最小的字典序应该是bab而不是bba。
- 代码实现:
import java.util.Arrays; import java.util.Comparator; public class Code_05_LowestLexicography { public static class MyComparator implements Comparator<String> { @Override public int compare(String a, String b) { return (a + b).compareTo(b + a); } } public static String lowestString(String[] strs) { if (strs == null || strs.length == 0) { return ""; } Arrays.sort(strs, new MyComparator()); String res = ""; for (int i = 0; i < strs.length; i++) { res += strs[i]; } return res; } public static void main(String[] args) { String[] strs1 = { "jibw", "ji", "jp", "bw", "jibw" }; System.out.println(lowestString(strs1)); String[] strs2 = { "ba", "b" }; System.out.println(lowestString(strs2)); } }
2.切分金条总代价最小
一块金条切成两半,是需要花费和长度数值一样的铜板的。比如 长度为20的金条,不管切成长度多大的两半,都要花费20个铜板。一群人想整分整块金 条,怎么分最省铜板?
例如,给定数组{10,20,30},代表一共三个人,整块金条长度为 10+20+30=60. 金条要分成10,20,30三个部分。 如果, 先把长 度60的金条分成10和50,花费60 再把长度50的金条分成20和30, 花费50 一共花费110铜板。 但是如果, 先把长度60的金条分成30和30,花费60 再把长度30 金条分成10和20,花费30 一共花费90铜板。
输入一个数组,返回分割的最小代价。
-
解题思路:
- 典型的哈夫曼编码问题
- 如下图所示:两个叶子节点合并过程中代价就是他们的和,最后只需将所有的非叶子节点值相加即为总代价。
- 贪心步骤如下:
1)将数组中元素加到小根堆中
2)每次从小根堆中弹出两数(最小的两个)进行相加得c,总代价+c,将c放回到小根堆中
3)重复1、2步骤,直至堆中只剩下一个数时结束。
-
当总共的代价是由子代价一种累加累乘或者是一个公式都有可能用哈夫曼编码贪出来。
-
根据自定义的比较器不同来实现不同的堆,比较器就是贪心的标准。
-
代码实现:
public class LowestCost { // 最小堆 public class MyComparator implements Comparator<Integer>{ @Override public int compare(Integer o1, Integer o2) { return o1 - o2; // 谁小把谁放在前面: -表示o1小 } } public int lowestCost(int[] arr){ // 优先级队列是小根堆,谁在前面,就把谁的优先级设置小点 PriorityQueue<Integer> pq = new PriorityQueue<>(new MyComparator()); for (int i : arr) { pq.add(i); } int costTotal = 0; // 总的代价 int costOne = 0; // 两数合并的代价 // 等于1的时候,说明堆里面只有一个元素了,即已经合并完成 while(pq.size() > 1){ costOne = pq.poll() + pq.poll(); // 合并堆里面最小的两个元素 costTotal += costOne; // 两小数合并的结果 pq.add(costOne); // 将两小数合并的结果重新添加到堆里 } return costTotal; } public static void main(String[] args) { LowestCost lc = new LowestCost(); int[] arr = {10, 20, 30, 40}; int res = lc.lowestCost(arr); System.out.println(res); // 190 = 10 + 20 + 30 + 30 + 40 + 60 } }
3.最多做k个项目的最大利润(IPO)
输入: 参数1:代价数组costs; 参数2: 利润数组profits; 参数3:正数k; 参数4:启动资金W 。costs[i]表示i号项目的花费 profits[i]表示i号项目的利润, k表示你不能并行、只能串行的最多做k个项目 。
说明:你每做完一个项目,马上获得的收益,可以支持你去做下 一个 项目。 一次只能做一个项目。
输出: 你最后获得的最大钱数。-
解题思路:
- 准备一个小根堆,这个小根堆是按照花费,谁花费低谁放到小根堆的头部。
- 准备一个大根堆,这个大根堆是按照收益高,谁收益高谁放在大根堆的头部。
- 若小根堆不为空,项目也没做完 K 个,则每次先从小根堆解锁能够做的项目,放入大根堆
- 大根堆不为空,从大根堆弹出堆顶项目来做(即利润最大的项目,每次只弹出堆顶一个项目来做);
- 把 W 加上利润,初始资金增加,再重复3)、4)步骤。
-
举个栗子:
-
代码实现:
public class IPO { // 项目节点 public class Node{ private int profit; // 项目利润 private int cost; // 项目成本 public Node(int profit, int cost){ this.profit = profit; this.cost = cost; } } /** * @param k :最多做k个项目 * @param fund :总的资金 * @param profits :每个项目的利润数组 * @param cost :每个项目的成本数组 * @return */ public int findMaxCapital(int k, int fund, int[] profits, int[] cost){ // 初始化每个项目节点信息 Node[] nodes = new Node[profits.length]; for (int i = 0; i < profits.length; i++) { nodes[i] = new Node(profits[i], cost[i]); } // 优先级队列是谁小谁放在前面,比较器决定谁小 PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator()); // 成本小顶堆 PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator()); // 利润大顶堆 for (int i = 0; i < nodes.length; i++) { minCostQ.add(nodes[i]); // 将所有的项目插入成本堆中 } // 开始解锁项目,赚取利润 for (int i = 0; i < k; i++) { // 解锁项目的前提条件:成本堆中还有项目未被解锁并且该项目的成本小于当前的总资金 while(!minCostQ.isEmpty() && minCostQ.peek().cost <= fund){ maxProfitQ.add(minCostQ.poll()); // 将当前成本最小的项目解锁 } if(maxProfitQ.isEmpty()){ // 如果maxProfitQ为空,则说明没有当前资金能够解锁的新项目了,之前解锁的项目也做完了,即无项目可做了 return fund; // 最后的总金额 } fund += maxProfitQ.poll().profit; // 做利润最大的项目 } return fund; // k个项目都做完了 } // 成本小顶堆:成本最小的在堆顶 public class MinCostComparator implements Comparator<Node>{ @Override public int compare(Node o1, Node o2) { return o1.cost - o2.cost; } } // 利润大顶堆:利润最大的在堆顶 public class MaxProfitComparator implements Comparator<Node>{ @Override public int compare(Node o1, Node o2) { return o2.profit - o1.profit; } } }
4.安排最多的宣讲场次
一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目 的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数 组,里面 是一个个具体的项目),你来安排宣讲的日程,要求会 议室进行 的宣讲的场次最多。
返回这个最多的宣讲场次。- 解题思路:
- 不能按照哪个项目开始的早先安排哪个,因为可能开始早的占用时间非常长,显然不合理;
- 项目持续的时间短优先安排也不合理,因为可能存在时间短的项目时间点正好在其他两个时间长项目中间,这样因为这一个项目就会浪费掉其他两个项目,显然也是不合理的;
- 按照哪个项目先结束来排。先做结束最早的项目,然后淘汰因为这个做这个项目而不能做的项目(时间冲突),依次这样去做。
- 代码实现:
public class BestArrange { public class Program{ public int start; // 项目开始时间 public int end; // 项目结束时间 public Program(int start, int end){ this.start = start; this.end = end; } } /** * @param programs :项目数组 * @param cur :当前时间 * @return :能够安排的最大项目数 */ public int getBestArrange(Program[] programs, int cur){ // 也可以用堆来做,都一样 Arrays.sort(programs, new ProgramComparator()); int res = 0; for (int i = 0; i < programs.length; i++) { // 只有当前时间早于第i个项目的开始时间时,才可以安排 if(cur <= programs[i].start){ res++; // 安排上了 cur = programs[i].end; // 当前时间推移到本次安排项目的结束时间,下个项目的开始时间必须在这个时间之后 } } return res; } // 按照项目的结束时间早来排序,即实现小根堆 public class ProgramComparator implements Comparator<Program>{ @Override public int compare(Program o1, Program o2) { return o1.end - o2.end; } } }
-
-
Reversing:逆向工程揭密
2010-06-21 17:00:47记得第一次做与逆向有关的工作是2000年,当时由于项目的需要,做过一个钩子(hook)程序,用于截获一个第三方控件发出的消息,但是当时还不知道什么是逆向工程。第一次看到“逆向工程”这个词是在2001年的《机械工程... -
UNIX网络编程 第2卷 进程间通信
2013-12-30 13:22:02Stevens博士尽管时间非常宝贵,每天还要花不少时间阅读和回答读者们发给他的有关Unix和TCP/IP的电子邮件,因而颇受尊敬。Stevens博士本人也在与网友们的交往中获益不少,他在本书扉页上写的话就是:“献给Usenet... -
Windows操作系统原理(附书签)
2013-05-01 13:36:297.2.2 网络资源的名字解析 342 7.2.3 协议驱动程序 347 7.2.4 NDIS驱动程序 348 7.3 Windows 2000的层次化网络服务 350 7.3.1 远程访问 351 7.3.2 活动目录 351 7.3.3 网络负载平衡 352 7.3.4 文件... -
MySQL 5权威指南(第3版)--详细书签版
2013-02-05 15:44:0010.2.2 与日期和时间有关的计算 202 10.2.3 UNIX时间戳 204 10.2.4 地理时区 206 10.3 ENUM和SET数据类型 208 10.3.1 ENUM 208 10.3.2 SET 209 10.4 变量与条件表达式(IF、CASE) 209 10.4.1 变量 210 ... -
UNIX高级编程 计算机科学丛书
2010-01-27 18:57:47本书提供了与测试有关的许多时间信息,也说明了用于测试的系统实际系统。 目录 译者序 前言 第1章 UNIX基础知识 1.1 引言 1.2 登录 1.2.1 登录名 1.2.2 shell 1.3 文件和目录 ...