算法入门
初识算法
- 算法是最初为了解决数学上的问题，由于计算机编程与数学密切相关，因此算法也被广泛应用于计算机领域中。
- 通过学习算法，可以更好地了解计算机底层的实现原理，对各程序有更加深刻的认识。
- 算法可以帮助我们设计出更好的程序，优化程序的性能，对就职面试也有很大的帮助
算法的意义
- 算法是把人所想的点子（Idea）以编程语言的形式应用到机器或程序设计中
- 人通过写算法表现自己的程序逻辑与设计方式，而通过编程语言作为载体，让计算机理解人们所要表达的设计逻辑
排序算法
冒泡排序
- 冒泡排序（bubble Sort），是一种较简单的排序算法
- 给定一组随机乱序的数组序列，通过比较相邻两个数的大小，按照从小到大的顺序 ，若前者比后者大，则交换位置，否则不需要；当经过一次循环迭代时，出现最大的数在该数组序列的末尾，此时已筛选出最大的数，即“浮出水面”，通过这种比较循环迭代的方式，类似于气泡浮出水面的形式，称为“冒泡”，这种方法也称“冒泡法”。
算法实现
- 详细步骤
- 对于给定的一个乱序的随机数组序列，比较相邻两个数，若前者比后者大，则交换。
- 一轮循环后，出现最大的数，该数则跳出比较循环（根据此规律，每执行完一次循环，就会出现一个排好的数）
- 重复执行步骤一，直到所有数字从小到大排列完成
Java代码实现
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
//初始化需要排序的数组
int array[] = {9,2,11,7,12,5};
//对需要排序的数组进行排序
for (int i=1; i<array.length; i++){
//针对待排序序列中除了已经排序好的元素之外，重复排序工作
for(int j=0;j<array.length-i;j++){
//当相邻两个元素需要交换时，交换相邻的两个元素
if(array[j]>array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
//打印出排序好的序列
System.out.println(Arrays.toString(array));
}
}
插入排序
- 插入排序（Insert Sort），是一种较为简单的排序算法
- 通过构建有序序列，对未排序的序列进行排序，有点类似于打扑克捋顺牌
算法实现
- 详细步骤
- 对于一个未排序的数组序列，选取第一个元素，该元素即被认定为已排序的，将该元素放入一个新的序列中，此序列存放排好数的序列
- 把未排序的数组序列的第二个元素选取出来，对新数列的元素进行大小对比，从大到小排列
- 后面的数重复进行步骤二
- 直到旧数列的数全部被选到新序列中，此时的新序列则为排序好的序列
Java实现
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
//初始化需要排序的数组
int array[] = {9, 2, 11, 7, 12, 5};
//初始化一个与待排序数组大小相同的数组，用来存放排序好的序列
int sortArray[] = new int[array.length];
//步骤1：待排序数组中选择第一个元素作为已经排序好的元素（数组的下标0表示第一个元素）
sortArray[0] = array[0];
//步骤2：依次遍历未排序的元素，将其插入已排序序列中
for (int i = 1; i < array.length; i++) {
//待排序元素
int temp = array[i];
//记录待排序元素需要插入已排序数组中的位置
int index = i;
//从已排序好的数组右边依次遍历数组，直到找到待排序元素需要插入的位置
while( index > 0 && temp < sortArray[index-1] ){
sortArray[index] = sortArray[index-1];
index--;
}
//插入待排序元素
sortArray[index] = temp;
}
//打印出排序好的序列
System.out.println(Arrays.toString(sortArray));
}
}
选择排序
- 选择排序（Select Sort），一种较为直观的排序算法，具有存储空间小的特点
- 通过对一个未排序的序列进行筛选，每次对整个序列进行筛选，筛选出最小的数，直到把所有的数都筛选完，即可得出最终的正确顺序
- 选择排序的==主要优点与数据移动有关==。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多$(n-1)$次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
算法实现
详细步骤
- 一个未排序的序列，对整个序列进行数与数之间的比较，筛选出该序列中最小的数
- 把筛选出的最小数与该序列的第一个元素的位置进行互换，此时序列的最小数就被选择到了序列的最前面
- 每次循环迭代都会选出一个未排序序列中的最小数
- 重复步骤1和2，得出最终的序列即为正确排序的序列（不需要开辟新的地址空间来存储新序列！！！）
选出最小数的关键伪代码
//待排序的序列记为A，寻找最小元素的伪代码如下： min = A[0] for(int i=1;i<A.length;i++){ if(A[i] < min){ min = A[i] } }
Java实现
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
//初始化需要排序的数组
int array[] = {9, 2, 11, 7, 12, 5};
//依次进行选择排序，每次找出最小的元素，放入待排序的序列中
for(int i=0;i<array.length;i++){
//记录最小元素min和最小元素的数组下标索引minIndex
int min = array[i];
int minIndex = i;
//在未排序的序列中找出最小的元素和对应数组中的位置
for(int j=i+1;j<array.length;j++){
if(array[j] < min){
min = array[j];
minIndex = j;
}
}
//交换位置
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
//打印出排序好的序列
System.out.println(Arrays.toString(array));
}
}
希尔排序
- 希尔排序（Shell Sort），也称为“缩小增量排序”，是插入排序的增强版，优先比较较远距离的元素
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
参考资料：https://zhuanlan.zhihu.com/p/87781731
算法基本思想
- 设待排序列有n个元素，取一整数gap（$gap<n$）作为间隔，将全部元素分为gap个子序列，所有距离为gap的元素放在同一个子序列中
- 在每一个子序列中分别采用直接插入排序
- 然后缩小间隔gap，例如取$gap=\frac{gap}{2}$ ,重复上述的子序列划分和排序工作
算法实现
- 详细步骤
- 对于一个未排序的序列，首先对该序列进行“粗略排序”，例如取该序列元素个数的一半作为两个数的跨度（gap），即若元素个数为12，则$gap=6$，每跨越6个数进行两数比较（一号元素与六号元素，二号对七号……），然后两两成组即成了一个个小的子序列，每个子序列进行大小比较，换位后再回到原序列中，此时得到的就是“粗略排序”后的排序序列
- 接着缩小gap的数值，对“粗略排序”好的序列再进行分组，由于已经进行了“粗略排序”，因此即使子序列的数量因gap值的缩小而增加，也不会花费太长的时间；每个子序列排好序后作为一个整体，进行直接插入排序
- 重复步骤2，直到出现正确的序列
- 算法关键点
- 该算法对gap值的取值尤为关键
Java实现
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
//初始化需要排序的数组
int array[] = {9, 2, 11, 7, 12, 5};
//初始化希尔排序的增量为数组长度
int gap = array.length;
//不断地进行插入排序，直至增量为1
while (true) {
//增量每次减半
gap = gap/2;
for (int i = 0; i < gap; i++) {
//内部循环是一个插入排序
for (int j = i + gap; j < array.length; j += gap) {
int temp = array[j];
int k = j - gap;
while (k >= 0 && array[k] > temp) {
array[k + gap] = array[k];
k -= gap;
}
array[k + gap] = temp;
}
}
//增量为1之后，希尔排序结束，退出循环
if (gap == 1)
break;
}
//打印出排序好的序列
System.out.println(Arrays.toString(array));
}
}
快速排序
- 快速排序（Quick Sort），是一种效率比大多数排序算法都要高的排序算法
- 快速排序实现的核心思想就是在待排序序列中选择一个基准值，然后将小于基准值的数字放在基准值左边，大于基准值的数字放在基准值右边，然后左右两边递归排序，整个排序过程中最关键部分就是寻找基准值在待排序序列中的索引位置。
算法实现
- 详细步骤
- 给定一个未排序的序列，选取第一个元素作为基准值$key$，使用双指针$i$、$j$的方式，对第二个元素用$i$指向，对最后一个元素用$j$指向，然后$i++$ 直到指向的数比$key$基准值大，此时$i$停止；$j—$直到指向的数比$key$基准值小，此时$j$停止；$i$指向的数与$j$指向的数位置互换，这样，比$key$小的数就会在序列的左边，比$key$大的数就会在序列的右边
- 在步骤一的$i$与$j$的位置继续进行循环，即$i++$与$j—$，直到出现步骤一的情况，交换两数位置
- 当$i$与$j$两指针指向同一个数时，该数与基准值$key$交换位置，该数的位置即为基准值的位置，此时 以基准值为界限，分离出两个子序列，左边的子序列的数都比基准值$key$要小，右边的子序列的数都比基准值$key$要大。
- 接着两个子序列再按照步骤一和步骤二的方法再每个子序列中在分离出两个子序列，此时整个序列有四个小的子序列，当所有序列都按照从小到大的顺序排列时，排序完成
Java实现
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
//初始化需要排序的数组
int array[] = {9, 2, 11, 7, 12, 5};
//快速排序
quickSort(array,0,array.length-1);
//打印出排序好的序列
System.out.println(Arrays.toString(array));
}
//快速排序
private static void quickSort(int[] array,int low, int high){
if(low < high){
//找到分区的位置，左边右边分别进行快速排序
int index = partition(array,low,high);
quickSort(array,0,index-1);
quickSort(array,index+1,high);
}
}
//快速排序分区操作
private static int partition(int[] array, int low, int high){
//选择基准
int pivot = array[low];
//当左指针小于右指针时，重复操作
while (low < high){
while(low < high && array[high] >= pivot){
high = high - 1;
}
array[low] = array[high];
while (low < high && array[low] <= pivot){
low = low + 1;
}
array[high] = array[low];
}
//最后赋值基准
array[low] = pivot;
//返回基准所在位置，基准位置已经排序好
return low;
}
}
递归算法
什么是递归？
- 在数学和计算机领域中，递归主要是指在函数的定义中使用函数自身的方法。顾名思义，递归主要包含两个意思，==递和归==，这个是递归思想的精华所在。递归就是有去（递去）有回（归来）。“有去” 是指递归问题可以分解成若干个规模较小、与原问题形式相同的子问题，这些子问题可以和原问题用相同的方法来求解。“有回” 是指这些问题的演化过程是一个从大到小，并且最终会有一个明确的终点，一旦达到终点，就可以从终点原路返回，解决原问题。
更为直接的说法就是：递归的基本思想就是把大问题转化为相似的小问题解决。特别是在程序中的函数实现时，大问题的解决方案和小问题是一模一样的，所以就产生==解决一个问题会调用函数本身的情况，这个也是递归的定义。==
递归三要素
- 递归终止条件———防止出现无限递归
- 递归终止条件时的处理方法
- 递归中重复的逻辑提取
recursion(big_problem){
if (end_condition){ //满足递归的终止条件
solve_end_condition; //处理终止条件下的逻辑
end; //递归结束
}else {
recursion(small_problem); //递归中重复的逻辑提取，缩小问题规模，调用自身方法，即为递归的最明显的特点
}
}
参考文档：https://www.cxyxiaowu.com/1135.html
斐波那契数列
- 斐波那契数列（Fibonacci sequence），也称之为黄金分割数列，由意大利数学家列昂纳多・斐波那契（Leonardo Fibonacci）提出。斐波那契数列指的是这样的一个数列：1、1、2、3、5、8、13、21、34、……，这个数列从第 3 项开始，每一项都等于前面两项之和。在数学上，斐波那契数列可以被递推的方法定义如下：
用Java实现斐波那契数列
public class Fibonacci {
public static void main(String[] args){
System.out.println(fibonacci(1));
System.out.println(fibonacci(2));
System.out.println(fibonacci(3));
System.out.println(fibonacci(4));
System.out.println(fibonacci(5));
}
//斐波那契数列数列的计算
private static int fibonacci(int n){
//如果是终止条件，按照要求返回终止条件对应结果
if( n==1 || n==2 ){
return 1;
}else {
//非终止条件，按照要求把大的问题拆分成小问题，调用自身函数递归处理
return fibonacci(n-1)+fibonacci(n-2);
}
}
}
分治算法
- 分治法是建基于多项分支递归的一种很重要的算法范型。字面上的解释是“分而治之”，分（divide）是将一个大的问题分解成一些小的问题分别求解，治 （conquer）则是将分解的问题答案合并在一起；即把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
主要思想
- 对于一个规模较大的问题，将其拆分成一个个小的子问题，再对各个小的问题进行求解，最后将所有小问题的结果合并成大问题的解。
分治算法的可行性
- 该问题是否可以拆分成小的问题
- 每个小的问题能否很容易的解决
实现步骤
- 对待求解的问题进行拆分，拆分成一个个小的，相互独立的子问题，形式与待求解问题形式一致
- 若每个子问题容易求解则直接求解，否则采用递归的方式进行
- 将各个子问题的解合并成该待求解问题的解
- 核心伪代码
divideAndConquer(big_problem){
if (canSolve(big_problem)){ //问题可以直接求解则直接求解返回
solve(big_problem); //求解
return;
}else {
small_problem_A = divide(big_problem); //不能直接求解的问题拆分
small_problem_B = divide(big_problem); //不能直接求解的问题拆分
divideAndConquer(small_problem_A); //递归求解子问题
divideAndConquer(small_problem_B); //递归求解子问题
return merge(); //合并子问题的解
}
}
分治法应用场景
- 二分查找
- 全排列问题
分治算法之最大子数组问题
- 最大子数组问题描述如下：假如我们有一个数组，数组中的元素有正数和负数，如何在数组中找到一段连续的子数组，使得子数组各个元素之和最大。
最大子数组问题在生活中有很多实际情况可以与其对应，比如说我们观察某一股票在一段时间内的走势，请问如何找出在哪一天买入，哪一天卖出可以赚到最大差价（这里假设你已经知道股票的价格走势）？为了实现最大化的股票收益，我们需要考虑的是买进和卖出时候的价格变化幅度，因此从该股票的每日变化幅度来考虑这个问题更加合适。所以，我们可以将这个问题稍作变形：将股票价格走势对应为每日股票价格涨跌，涨记为正值，跌记为负值，然后一段时间就对应一个正负数数组，并试图找到该数组的最大子数组，就可以获得最大收益。
分治算法的实现步骤
- 先找出数组中的中间元素$mid$ ,根据分治策略，把数组分成两个子数组，左边为$[low,mid]$,右边为$[mid+1,high]$
- 判断最大子数组$[i,j]$的位置，即以下三种情况：
- 最大子数组$[i,j]$完全在$[low,mid]$中：即$low\leq i < j \leq mid$
- 最大子数组$[i,j]$完全在$[mid+1,high]$中：即$mid+1\leq i < j \leq high$
- 最大子数组$[i,j]$完全在$[low,high]$中：即$low\leq i \leq mid \leq j \leq high$
- 对三个子问题进行求解
Java实现
package divide_and_conquer;
public class MaxSubarray {
//内部类，用来存储最大子数组的返回结果，
private static class Result {
int low;
int high;
int sum;
public Result(int low, int high, int sum) {
this.low = low;
this.high = high;
this.sum = sum;
}
@Override
public String toString() {
return "Result{" +
"low=" + low +
", high=" + high +
", sum=" + sum +
'}';
}
}
private static Result FindMaxCrossSubarray(int[]A,int low, int mid, int high){
//寻找左边的连续最大值及记录位置
int leftSum = Integer.MIN_VALUE;
int sum = 0;
int maxLeft = mid;
for (int i=mid; i>=low; i--){
sum = sum + A[i];
if(sum > leftSum){
leftSum = sum;
maxLeft = i;
}
}
//寻找右边的连续最大值及记录位置
int rightSum = Integer.MIN_VALUE;
int maxRight = mid+1;
sum = 0;
for ( int j=mid+1; j<=high;j++){
sum = sum + A[j];
if(sum > rightSum){
rightSum = sum;
maxRight = j;
}
}
//返回跨越中间值的最大子数组结果
return new Result(maxLeft,maxRight,leftSum + rightSum);
}
public static Result FindMaxSubarray(int[] A, int low, int high){
//数组只有一个元素时的处理情况
if (high == low){
return new Result(low,high,A[low]);
}else {
//对应思路中步骤1，找到中间元素
int mid = (low + high)/2;
//对应思路中步骤2，分别对应a,b,c三种情况求解最大子数组结果
Result leftResult = FindMaxSubarray(A,low,mid);
Result rightResult = FindMaxSubarray(A,mid+1,high);
Result crossResult = FindMaxCrossSubarray(A,low,mid,high);
//对应步骤3，比较
if(leftResult.sum >= rightResult.sum && leftResult.sum >= crossResult.sum){
return leftResult;
}else if (rightResult.sum >= leftResult.sum && rightResult.sum >= crossResult.sum){
return rightResult;
}else {
return crossResult;
}
}
}
public static void main(String[] args){
int[] A = {12, -3, -16, 20, -19, -3, 18, 20, -7, 12, -9, 7, -10};
System.out.println(FindMaxSubarray(A,0,A.length-1).toString());
}
}
动态规划
动态规划通常用于解决最优化问题，在这类问题中，通过做出一组选择来达到最优解。在做出每个选择的同时，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题时，动态规划技术通常就会很有效，其关键技术就是对每个这样的子问题都保存其解，当其重复出现时即可避免重复求解。
- 动态规划
（Dynamic Programming）在数学上属于运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法，同时也是计算机科学与技术领域中一种常见的算法思想。 - 动态规划算法与我们前面提及的分治算法相似，都是==通过组合子问题的解来求解原问题的解==。但是两者之间也有很大区别：
- 分治法将问题划分为互不相交的子问题，递归的求解子问题，再将他们的解组合起来求解原问题的解；与之相反，动态规划应用于子问题相互重叠的情况，在这种情况下，分治法还是会做很多重复的不必要的工作，他会反复求解那些公共的子问题，而动态规划算法则对相同的每个子问题只会求解一次，将其结果保存起来，避免一些不必要的计算工作。
钢条切割问题
某个钢材公司购买长钢条，将其切割为短钢条出售，其中切割过程本身不考虑成本，公司管理层想知道最赚钱的钢材切割方案。假设我们知道该钢材公司出售一段长度为 i 米的钢条的价格为 $p(i)$ ，对应的价目表如下：
|i |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|
|:—-:|:—-:|:—-:|:—-:|:—-:|:—-:|:—-:|:—-:|:—-:|:—-:|:—-:|
|p(i) |1 |5 |8 |9 |10 |17 |17 |20 |24 |30|所以，钢材切割问题的定义如下：当我们给定一段长度为 $n$ 米的钢条和对应的一个价格表（ $p(i)$, i = 1,2,3,…n)，求一个钢条切割方案，使得最终的销售收益 $r(n)$ 最大。注意：如果长度为 $n$ 英尺的钢条的价格 $p_n$ 足够大，那么最优解就是不需要切割。（在这里，我们要求切割的钢条必须为整米长度）
问题分析 ：考虑 = 4 的情况，那么有以下几种切割方式：
切割为四段，长度为：1，1，1，1；总共卖$4×1=4$元。
切割为三段，长度为：1，1，2；总共卖$2×1+1×5=7$元。
切割为两段，长度为：1，3；总共卖$1×1+1×8=9$元。
切割为两段，长度为：2，2；总共卖$2×5=10$元。
不切割，长度为：4；总共卖$1×9=9$元。
![]()
- 长度为 $n$ 的钢条，总共有 $2^{n-1}$ 种不同的切割方案，因为长度为 $n$ 的钢条，总共有 $n-1$ 个缝隙，每个缝隙都可以选择切或不切，==所以有 $2^{n-1}$ 种不同切割方案。所以随着 $n$ 增大，切割方案总数呈指数级上升，遍历是不现实的==。在这里，很容易想到，当要分析长度为 $n$ 的钢条的最优解时，可以先将钢条切成两段。==将长度为 $n$ 的钢条随意切割的方案是 $2^{n-1}$ 种，但是只切两段的方案只有 $n-1$ 种，这样规避了指数级计算量==。将切成的两段，分别再当作子问题去求解，这就是如下分治策略解法：
自顶向下递归实现
int CutRod(const int *p, int n)
{
if (n == 0)
{
return 0;
}
int q = -1;
for (int i = 1; i <= n; ++i)
{
int tmp = p[i] + CutRod(p, n - i);
if (q < tmp)
{
q = tmp;
}
}
return q;
}
- 自顶向下递归实现的
CutRod效率很差，原因在于CutRod反复地用相同的参数值对自身进行递归调用，即它反复求解相同的子问题。它的运行时间为$T(n)=2^n$。对于长度为n的钢条CutRod考察了所有$2^{n-1}$种可能的切割方案。递归调用树共有$2^{n-1}$个叶结点，每个叶结点对应一种可能的切割方案。
动态规划算法一：带备忘录的自顶向下法
int MemoizedCutRodAux(const int *p, int n, int *r)
{
if (r[n] >= 0)
{
return r[n]; //首先检查所需的值是否存在
}
int q = -1;
if (n == 0)
{
q = 0;
}
else
{
for (int i = 1; i <= n; ++i)
{
int tmp = p[i] + MemoizedCutRodAux(p, n - i, r);
if (q < tmp)
{
q = tmp;
}
}
}
r[n] = q;
return q;
}
int MemoizedCutRod(const int *p, int n)
{
int *r = new int[n + 1];
for (int i = 0; i <= n; ++i)
{
r[i] = -1;
}
return MemoizedCutRodAux(p, n, r);
}
上述代码与分治不同的地方在于初始化了数组
r[n]，将不同长度的最优解数值，储存在了该数组中，所以当不同的 $n$ 传进来时，如果在数组 $r$ 中有当前钢条长度的记录（if r[n] >= 0 : return r[n])，则直接返回结果，不再进行之后的计算，其余的递归思路与分治策略完全一样。此方法的时间复杂度为 $O(n^2)$ ，变为了多项式时间复杂度。可见，==动态规划算法用少量的空间，显著提升了算法效率。==自顶向下的动态规划算法，仍然不是最理想的。例如在计算 $n =4 $时， $n = 0 $的情况被计算了8次，采用了备忘录的形式之后，虽然 $n = 0$ 的情况只需要计算1次，查表有7次操作，但是这7次查表操作，都是在进入了一个相同的函数中，会有频繁的递归函数调用的开销。采用自底向上的动态规划算法，就可以规避这个问题。
动态规划算法二：自底而上法
int BottomUpCutRod(const int *p, int n)
{
int *r = new int[n + 1];
r[0] = 0;
for (int i = 1; i <= n; ++i)
{
int q = -1;
for (int j = 1; j <= i; ++j)
{
int tmp = p[j] + r[i - j];
q = q > tmp ? q : tmp;
}
r[i] = q;
}
return r[n];
}
自底向上法不再使用函数递归调用，而采用子问题的自然顺序。在切割时，先由最小的1开始切割，若 $i<j$ ，则规模为 $j$ 的解中一定包含了规模为 $i$ 的全部解（此时子问题的规模，可以理解为之前递归函数的输入 $n$ ）。
上述代码中，仍然先初始化一个数组 $r$ ，用于记录不同规模子问题的最优解，并且将
r[0]初始化为 0 ；之后对 $j = 1，2，… ，n$进行升序求解。不同于之前算法的是，此时直接访问r[j-i]来获得规模为 $j-i$ 的子问题的解。因为自底向上求解时，若 $i<j$，当在求解规模为 $j$ 的子问题时，r[i]一定有数值，因为之前一定已经计算过。自底向上算法的时间复杂度也为，但是避免了大量的递归函数调用的开销，算法更加稳定。
贪心算法
- 贪心算法（
greedy algorithm）是在对问题求解时，总是做出在当前看来是最好的选择。也就是说，==不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解==。 - 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。————摘自Wikipedia
贪心算法与动态规划算法的最大区别在于：贪心算法每次选择的时候都是按照贪心策略来选择的，满足当前情况的最优解，但是并不一定会是整体最优解；动态规划算法在选择考虑时会考虑所有的子情况，选择最优解，这会是整体的最优解。
关键与实现过程
- 关键
- 创建数学模型来描述问题。
- 把求解的问题分成若干个子问题。
- 对每一子问题求解，得到子问题的局部最优解。
- 把子问题的解局部最优解合成原来解问题的一个解。
- 实现该算法的过程
- 从问题的某一初始解出发；
while能朝给定总目标前进一步do，求出可行解的一个解元素；最后，由所有解元素组合成问题的一个可行解。
- 从问题的某一初始解出发；
贪心算法的可行条件
贪心选择 ： 当某一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次做出的选择可以依赖以前做出的选择，但不需要依赖后面需要做出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须==证明每一步所作的贪心选择最终导致问题的整体最优解==。
最优子结构 ： 如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。问题的最优子结构性质是该问题是否可以用贪心算法求解的关键所在。
贪心算法与动态规划算法求解的问题类似，都需要满足最优子结构的性质。
贪心算法之分饼干
- 题目概述
- 有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。
输入输出样例
- 输入两个数组，分别代表孩子的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数量。
Input: [1,2],[1,2,3] Output: 2- 在这个样例中，我们可以给两个孩子喂
[1,2]、[1,3]、[2,3]这三种组合的任意一种。
- 题解
- 因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。
- 简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对子可以满足条件。
- 排列组合遍历
class Solution { public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); //孩子饥饿度数组 Arrays.sort(s); //饼干大小数组 int numOfChildren = g.length, numOfCookies = s.length; int count = 0; for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) { while (j < numOfCookies && g[i] > s[j]) { j++; } if (j < numOfCookies) { count++; } } return count; } }
- 贪心策略
public int findContentChildren(int[] grid, int[] size) { if (grid == null || size == null) return 0; Arrays.sort(grid); Arrays.sort(size); int gi = 0, si = 0; while (gi < grid.length && si < size.length) { if (grid[gi] <= size[si]) { gi++; } si++; } return gi; }
贪心算法之分糖果
- 题目概述
- 一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所有孩子至少要有一个糖果。求解最少需要多少个糖果。
输入输出样例
- 输入是一个数组，表示孩子的评分。输出是最少糖果的数量。
Input: [1,0,2] Output: 5- 在这个样例中，最少的糖果分法是
[2,1,2]。
题解
- 我们只需要简单的两次遍历即可：把所有孩子的糖果数初始化为 1；先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。通过这两次遍历，分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。
- 在样例中，我们初始化糖果分配为
[1,1,1]，第一次遍历更新后的结果为[1,1,2]，第二次遍历更新后的结果为[2,1,2]。
- 二次遍历代码
class Solution { public int candy(int[] ratings) { int n = ratings.length; int[] left = new int[n]; for (int i = 0; i < n; i++) { if (i > 0 && ratings[i] > ratings[i - 1]) { left[i] = left[i - 1] + 1; } else { left[i] = 1; } } int right = 0, ret = 0; for (int i = n - 1; i >= 0; i--) { if (i < n - 1 && ratings[i] > ratings[i + 1]) { right++; } else { right = 1; } ret += Math.max(left[i], right); } return ret; } }
- 贪心策略代码
class Solution { public int candy(int[] ratings) { int[] left = new int[ratings.length]; int[] right = new int[ratings.length]; Arrays.fill(left, 1); Arrays.fill(right, 1); for(int i = 1; i < ratings.length; i++) if(ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1; int count = left[ratings.length - 1]; for(int i = ratings.length - 2; i >= 0; i--) { if(ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1; count += Math.max(left[i], right[i]); } return count; } }
