程序员算法基础——贪心算法

贪心是人类自带的能力，贪心算法是在贪心决策上进行统筹规划的统称。

比如一道常见的算法笔试题---- 跳一跳 ：

我们自然而然能产生一种解法：尽可能的往右跳，看最后是否能到达。

本文即是对这种贪心决策的介绍。

狭义的贪心算法指的是解最优化问题的一种特殊方法，解决过程中总是做出当下最好的选纤启择，因为具有最优子结构的特点，局部最优解可以得到全局最优解；这种贪心算法是动态规划的一种特例。 能用贪心解决的问题，也可以用动态规划解决。

而广义的贪心指的是一种通用的贪心策略，基于当前局面而进行贪心决策。以 跳一跳 的题目为例：

我们发现的题目的核心在于 向右能到达的最远距离 ，我们用maxRight来表示；

此时有一种贪心的策略：从第1个盒子开始向右遍历，对于每个经过的盒子，不断更新maxRight的值。

贪毁局如心的思考过程类似动态规划，依旧是两步： 大事化小 ， 小事化了 。

大事化小：

一个较大的腊山问题，通过找到与子问题的重叠，把复杂的问题划分为多个小问题；

小事化了：

从小问题找到决策的核心，确定一种得到最优解的策略，比如跳一跳中的 向右能到达的最远距离 ；

在证明局部的最优解是否可以推出全局最优解的时候，常会用到数学的证明方式。

如果是动态规划：

要凑出m元，必须先凑出m-1、m-2、m-5、m-10元，我们用dp[i]表示凑出i元的最少纸币数；

有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1

容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；

根据以上递推方程和初始化信息，可以容易推出dp[1~m]的所有值。

似乎有些不对？ 平时我们找零钱有这么复杂吗？

从贪心算法角度出发，当m>10且我们有10元纸币，我们优先使用10元纸币，然后再是5元、2元、1元纸币。

从日常生活的经验知道，这么做是正确的，但是为什么？

假如我们把题目变成这样，原来的策略还能生效吗？

接下来我们来分析这种策略：

已知对于m元纸币，1，2，5元纸币使用了a，b，c张，我们有a+2b+5c=m；

假设存在一种情况，1、2、5元纸币使用数是x，y，z张，使用了更少的5元纸币（z<c），且纸币张数更少（x+y+z<a+b+c），即是用更少5元纸币得到最优解。

我们令k=5*(c-z)，k元纸币需要floor(k/2)张2元纸币，k%2张1元纸币；（因为如果有2张1元纸币，可以使用1张2元纸币来替代，故而1元纸币只能是0张或者1张）

容易知道，减少(c-z)张5元纸币，需要增加floor(5*(c-z)/2)张2元纸币和(5*(c-z))%2张纸币，而这使得x+y+z必然大于a+b+c。

由此我们知道不可能存在使用更少5元纸币的更优解。

所以优先使用大额纸币是一种正确的贪心选择。

对于1、5、7元纸币，比如说要凑出10元，如果优先使用7元纸币，则张数是4；（1+1+1+7）

但如果只使用5元纸币，则张数是2；（5+5）

在这种情况下，优先使用大额纸币是不正确的贪心选择。（但用动态规划仍能得到最优解）

如果是动态规划：

前i秒的完成的任务数，可以由前面1~i-1秒的任务完成数推过来。

我们用 dp[i]表示前i秒能完成的任务数 ；

在计算前i秒能完成的任务数时，对于第j个任务，我们有两种决策：

1、不执行这个任务，那么dp[i]没有变化；

2、执行这个任务，那么必须腾出来(Sj, Tj)这段时间，那么 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；

比如说对于任务j如果是第5秒开始第10秒结束，如果i>=10，那么有 dp[i]=max(dp[i], dp[5] + 1)； （相当于把第5秒到第i秒的时间分配给任务j）

再考虑贪心的策略，现实生活中人们是如何安排这种多任务的事情？我换一种描述方式：

我们自然而然会想到一个策略： 先把结束时间早的兼职给做了！

为什么？

因为先做完这个结束时间早的，能留出更多的时间做其他兼职。

我们天生具备了这种优化决策的能力。

这是一道 LeetCode题目 。

这个题目不能直接用动态规划去解，比如用dp[i]表示前i个人需要的最少糖果数。

因为（前i个人的最少糖果数）这种状态表示会收到第i+1个人的影响，如果a[i]>a[i+1]，那么第i个人应该比第i+1个人多。

即是 这种状态表示不具备无后效性。

如果是我们分配糖果，我们应该怎么分配？

答案是： 从分数最低的开始。

按照分数排序，从最低开始分，每次判断是否比左右的分数高。

假设每个人分c[i]个糖果，那么对于第i个人有 c[i]=max(c[i-1],c[c+1])+1 （c[i]默认为0，如果在计算i的时候,c[i-1]为0，表示i-1的分数比i高）

但是，这样解决的时间复杂度为 O(NLogN) ，主要瓶颈是在排序。

如果提交，会得到 Time Limit Exceeded 的提示。

我们需要对贪心的策略进行优化：

我们把左右两种情况分开看。

如果只考虑比左边的人分数高时，容易得到策略：

从左到右遍历，如果a[i]>a[i-1]，则有c[i]=c[i-1]+1；否则c[i]=1。

再考虑比右边的人分数高时，此时我们要从数组的最右边，向左开始遍历：

如果a[i]>a[i+1], 则有c[i]=c[i+1]+1；否则c[i]不变；

这样讲过两次遍历，我们可以得到一个分配方案，并且时间复杂度是 O(N) 。

题目给出关键信息：1、两个人过河，耗时为较长的时间；

还有隐藏的信息：2、两个人过河后，需要有一个人把船开回去；

要保证总时间尽可能小，这里有两个关键原则： 应该使得两个人时间差尽可能小（减少浪费），同时船回去的时间也尽可能小（减少等待）。

先不考虑空船回来的情况，如果有无限多的船，那么应该怎么分配？

答案： 每次从剩下的人选择耗时最长的人，再选择与他耗时最接近的人。

再考虑只有一条船的情况，假设有A/B/C三个人，并且耗时A<B<C。

那么最快的方案是：A+B去, A回；A+C去；总耗时是A+B+C。（因为A是最快的，让其他人来回时间只会更长， 减少等待的原则 ）

如果有A/B/C/D四个人，且耗时A<B<C<D，这时有两种方案：

1、最快的来回送人方式，A+B去；A回；A+C去，A回；A+D去； 总耗时是B+C+D+2A （减少等待原则）

2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；总耗时是 3B+D+A （减少浪费原则）

对比方案1、2的选择，我们发现差别仅在A+C和2B；

为何方案1、2差别里没有D？

因为D最终一定要过河，且耗时一定为D。

如果有A/B/C/D/E 5个人，且耗时A<B<C<D<E，这时如何抉择？

仍是从最慢的E看。（参考我们无限多船的情况）

方案1，减少等待；先送E过去，然后接着考虑四个人的情况；

方案2，减少浪费；先送E/D过去，然后接着考虑A/B/C三个人的情况；（4人的时候的方案2）

到5个人的时候，我们已经明显发了一个特点：问题是重复，且可以由子问题去解决。

根据5个人的情况，我们可以推出状态转移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2])

再根据我们考虑的1、2、3、4个人的情况，我们分别可以算出dp[i]的初始化值：

dp[1] = a[1]

dp[2] = a[2]

dp[3] = a[2]+a[1]+a[3]

dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2])

由上述的状态转移方程和初始化值，我们可以推出dp[n]的值。

贪心的学习过程，就是对自己的思考进行优化。

是把握已有信息，进行最优化决策。

这里还有一些收集的 贪心练习题 ，可以实践练习。

这里 还有在线分享，欢迎报名。

算法一：快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：

1 从数列中挑出一个元素，称为 “基准”（pivot），

2 重新排序知瞎返数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition） *** 作。

3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

算法二：堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤：

1.创建一个搭饥堆H[0..n-1]

2.把堆首（最大值）和堆尾互换

3.把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4.重复步骤2，直到堆的尺寸为1

算法三：归并排序

归并排序（Merge sort，台湾译作：合并排序）是建立在归并 *** 作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤：

算法四：二分查找算法

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜 素过程结束；神携如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组 为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。

算法五：BFPRT(线性查找算法)

BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分 析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂 度，五位算法作者做了精妙的处理。

算法步骤：

终止条件：n=1时，返回的即是i小元素。

算法六：DFS（深度优先搜索）

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分 支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发 现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

算法步骤：

上述描述可能比较抽象，举个实例：

DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

算法七：BFS(广度优先搜索)

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

算法步骤：

算法八：Dijkstra算法

戴克斯特拉算法（Dijkstra’s algorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

该算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目前已知的最快的单源最短路径算法。

算法步骤：

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

算法九：动态规划算法

动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多 子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个 子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

关于动态规划最经典的问题当属背包问题。

算法步骤：

算法十：朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下， 如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。

朴素贝叶斯分类器依靠精确的自然概率模型，在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法，换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。

尽管是带着这些朴素思想和过于简单化的假设，但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。

零基础学习java可按照这份大纲来进行学习

第一阶段：Java专业基础课程

阶段目标：

1. 熟练掌握Java的开发环境与编程核心知识

2. 熟练运用Java面向对象知识进行程序开发

3. 对Java的核心对象和组件有深入理解

4. 熟练应用JavaAPI相关知识

5. 熟练应用JAVA多线程技术

6. 能综合运用所学知识完成一个项目

知识点：

1、基本数据类型，运算符，数组，掌握基本数据类型转换，运算符，冲配流程控制。

2、数组，排序算法，Java常用API，类和对象，了解类与对象，熟悉常用API。

3、面向对象特性，集合框架，熟悉祥判御面向对象三大特性，熟练使用集合框架。

4、IO流，多线程。

5、网络协议，线程运用。

第二阶段：JavaWEB核心课程

阶段目标:

1. 熟练掌握数据库和MySQL核心技术

2. 深入理解JDBC与DAO数据库 *** 作

3. 熟练运用JSP及Servlet技术完成网站后台开发

4. 深入理解缓存，连接池，注解，反射，泛型等知识

5. 能够运用所学知识完成自定义框架

知识点：

1、数据库知识，范式，MySQL配置，命令，建库建表，数据的增删改查，约束，视图，存储过程，函数，触发器，事务，游标，建模工具。

2、深入理解数据库管理系统通用知识及MySQL数据库的使用与管理。为Java后台开发打下坚实基础。Web页面元素，布局，CSS样式，盒模型，JavaScript，jQuery。

3、掌握前端开发技术，掌握jQuery。

4、Servlet，EL表达式，会话跟踪技术，过滤器，FreeMarker。

5、掌握Servlet相关技术，利用Servlet，JSP相关应用技术和DAO完成B/S架构下的应用开发。

6、泛型，反射，注解。

7、掌握JAVA高级应用，利用泛型，注解，枚举完成自己的CRUD框谨岩架开发为后续框架学习做铺垫。

8、单点登录，支付功能，项目整合，分页封装熟练运用JSP及Servlet核心知识完成项目实战。

第三阶段：JavaEE框架课程

阶段目标：

1. 熟练运用Linux *** 作系统常见命令及完成环境部署和Nginx服务器的配置

2. 熟练运用JavaEE三大核心框架：Spring,SpringMVC,MyBatis

3. 熟练运用Maven,并使用SpringBoot进行快速框架搭建

4. 深入理解框架的实现原理，Java底层技术，企业级应用等

5. 使用Shiro,Ztree和Spring,SpringMVC,Mybaits完成企业项目

知识点：

1、Linux安装配置，文件目录 *** 作，VI命令，管理，用户与权限，环境部署，Struts2概述，hiberante概述。

2、Linux作为一个主流的服务器 *** 作系统，是每一个开发工程师必须掌握的重点技术，并且能够熟练运用。

3、SSH的整合,MyBatis,SpringMVC,Maven的使用。

4、了解AOP原理，了解中央控制器原理，掌握MyBatis框架，掌握SSM框架的整合。

5、Shiro,Ztree，项目文档，项目规范，需求分析，原型图设计，数据库设计，工程构建，需求评审，配置管理，BUG修复，项目管理等。

6、独立自主完成一个中小型的企业级综合项目的设计和整体架构的原型和建模。独立自主完成一个大型的企业级综合项目，并具备商业价值

---