贪心算法专题(一)
目录
1、贪心算法简介
1.1 什么是贪心算法
1.2 贪心算法的特点
1.3 贪心算法的学习方向
2、算法应用【leetcode】
2.1 题一：柠檬水找零
2.1.1 算法原理
2.1.2 算法代码
2.2 题二：将数组和减半的最少操作次数
2.2.1 算法原理
2.2.2 算法代码
2.3 题三：最大数
2.3.1 算法原理
2.3.2 算法代码
2.4 题四：摆动序列
2.4.1 算法原理
2.4.2 算法代码
2.5 题五：最长递增子序列
2.5.1 算法原理1——记忆化搜索
2.5.2 算法代码1——记忆化搜索
2.5.3 算法原理2——动态规划
2.5.4 算法代码2——动态规划
2.5.5 算法原理3——贪心+二分【最优解】
2.5.6 算法代码3——贪心+二分【最优解】
1、贪心算法简介
1.1 什么是贪心算法
贪心算法（greedy algorithm ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。在每一步选择中都采取当前状态下最优的选择，以期望达到全局最优解的算法策略。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。
贪心算法的核心就是：贪心策略。
而贪心策略就是由：局部最优解 推算出 全局最优解。
- 将解决问题的分为若干步，逐步击破
- 解决每一步时，选择当前步“最优的”解法
- “希望”得到全局最优解
1.2 贪心算法的特点
我们可能是猜的、蒙的、靠直觉想出的贪心策略，所以贪心策略的正确性的不确定的。
贪心策略的提出：
- 贪心算法和我们之前所学到的算法不同，贪心策略的提出是没有任何固定的模版或者标准的
- 每一道题的贪心策略都是不同的
贪心策略的正确性：
- 贪心策略可能是错误的
- 贪心策略需要各种数学方法的证明
1.3 贪心算法的学习方向
由于每一道题的贪心策略都可能不同，所以即使我们做了几十道贪心题后，再面对对于一道新贪心题时，也可能会没有任何的思路。所以遇到不会的贪心题是很正常的，我们要把心态放平。
- 在前期学习时，将每道题的贪心策略当做经验来吸收，扩大对贪心策略的认知。
- 不用纠结别人的贪心策略是怎么想出的，想不出来很正常，我们当做经验把策略吸收即可。
2、算法应用【leetcode】
2.1 题一：柠檬水找零
. - 力扣（LeetCode）
2.1.1 算法原理
对于5元和10元的找零策略是固定的，给20元找零时有两种策略：要么找三张5元；要么找一张5元和一张10元。
经过分析：5元的用处更多(给10元找零时要用)，所以要尽可能的保留5元。
故，贪心策略为：给20元找一张5元和一张10元；当10元不存在时才找三张5元。
2.1.2 算法代码
class Solution {
public boolean lemonadeChange(int[] bills) {
//<金额, 个数>
int five = 0, ten = 0;
if(bills[0] != 5) return false;
for(int i = 0; i < bills.length; i++) {
if(bills[i] == 5) five++;
else if(bills[i] == 10) {
if(five == 0) return false;
five--; ten++;
}else {
if(five == 0) {
return false;
}else if(ten != 0) {
//贪心
ten--;
five--;
}else {
if(five < 3) return false;
five -= 3;
}
}
}
return true;
}
}2.2 题二：将数组和减半的最少操作次数
. - 力扣（LeetCode）
2.2.1 算法原理
策略：贪心+大根堆
- 因为求使数组减半的最小的操作次数，
- 根据贪心策略，每次将数组中最大的元素进行减半操作，这样可使得操作次数最少。
- 循环这个过程，直至将数组和减半。
2.2.2 算法代码
class Solution {
public int halveArray(int[] nums) {
double sum = 0;
//建大堆
PriorityQueue<Double> queue = new PriorityQueue<>((o1,o2) -> o2.compareTo(o1));
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
queue.offer((double)nums[i]);
}
sum /= 2;
int count = 0;
while (sum > 0) {
double peek = queue.poll();
sum -= peek / 2;
queue.offer(peek / 2);
count++;
}
return count;
}
}2.3 题三：最大数
. - 力扣（LeetCode）
2.3.1 算法原理
本质：确定数组中元素的先后顺序（谁在前，谁在后）
核心：修改sort方法的排序规则 -> 进行元素拼接后的比较，将拼接后的较大的元素放在前面。
优化：使用字符串进行拼接
2.3.2 算法代码
class Solution {
public String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++)
strs[i] = nums[i] + "";
Arrays.sort(strs, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
StringBuffer sb = new StringBuffer();
for (String str : strs)
sb.append(str);
if (sb.charAt(0) == '0')
return "0";
return sb.toString();
}
}2.4 题四：摆动序列
. - 力扣（LeetCode）
2.4.1 算法原理
画出数组元素值的折线图，可以发现每次选取极值点可以使摆动序列的长度最大。
- 贪心策略：选取折线图的极值点，计算极值点的个数。
- 为什么该策略为贪心策略呢？——因为选取极大值或极小值，在下次选取元素时(满足摆动序列)会有更多的选择性（贪心策略），不会漏掉数据。
2.4.2 算法代码
class Solution {
int left;//左侧的增减性
int ret;
public int wiggleMaxLength(int[] nums) {
for(int i = 0; i < nums.length - 1; i++) {
//右侧的增减性
int right = nums[i + 1] - nums[i];
//右侧元素与当前元素相同
if(right == 0) continue;
//极值点
if(right * left <= 0) ret++;
left = right;
}
//加上最后一个节点
return ret + 1;
}
}2.5 题五：最长递增子序列
. - 力扣（LeetCode）
2.5.1 算法原理1——记忆化搜索
算法核心：
- dfs当前元素(pos位置)后面位置的元素（要求：nums[pos] < nums[后面序列]），寻找出最长递增子序列的长度，再加一(算上当前节点)，就是以当前位置为起点的最长递增子序列的长度。
备忘录优化（记忆化搜索）：
- 使用memo数组存储以该位置为起点的最长递增子序列的长度。
2.5.2 算法代码1——记忆化搜索
class Solution {
//记忆化搜索
int ret = 1;
int path;
int[] memo;
public int lengthOfLIS(int[] nums) {
memo = new int[nums.length];
int ret = 0;
for(int i = 0; i < nums.length; i++) {
ret = Math.max(ret, dfs(nums, i));
}
return ret;
}
public int dfs(int[] nums, int pos) {
int ret = 1;
if(memo[pos] != 0) return memo[pos];
for(int i = pos + 1; i < nums.length; i++) {
if(nums[i] > nums[pos]) {
ret = Math.max(ret, dfs(nums, i) + 1);
}
}
memo[pos] = ret;
return ret;
}
}2.5.3 算法原理2——动态规划
算法核心：
- 状态表示(dp[i])：以当前位置为结尾的最长递增子序列的长度
- 状态转移方程：dp[i]=max(dp[j] + 1)【要求：(j < i && nums[j] < nums[i])】
2.5.4 算法代码2——动态规划
class Solution {
//动态规划
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for(int i = 0; i < n; i++) {
for(int j = i - 1; j >= 0; j--) {
if(nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int max = 0;
for(int x : dp) max = Math.max(max, x);
return max;
}
}2.5.5 算法原理3——贪心+二分【最优解】
本题最优解为贪心算法。时间复杂度为O(N*logN)
贪心策略的核心，在于以下两点：
- 存什么：每个长度的递增序列中，存的是最后一个元素的最小值（假设x后面可以有一段递增序列，那么比x更小的数后面也一定可以有这个序列）【将数据存入数组hash中】
- 存哪里：存第一个大于等于nums[i]的位置(覆盖删除)
光靠文字也许晦涩难懂，下文已放图。
如果我们仅仅按照以上策略来贪心的话，每个新元素查找插入位置的时间为O(N)，整体的时间复杂度也依然是O(N^2)，但是发现我们存放数据的数组hash满足递增的特性，故我们可以使用二分的方法寻找插入位置——优化为O(logN)，将整体的时间复杂度优化为：O(N*logN)
所以本题的解题原理为：贪心策略 + 二分查找
2.5.6 算法代码3——贪心+二分【最优解】
class Solution {
//贪心 + 二分查找
public int lengthOfLIS(int[] nums) {
int n = nums.length;
List<Integer> hash = new ArrayList<>();
for(int i = 0; i < n; i++) {
int val = nums[i];
int left = 0, right = hash.size() - 1;
//hash为空
//新元素比所有元素都大时，直接插入到最后
if(hash.size() == 0 || val > hash.get(right)) {
hash.add(val);
continue;
}
//二分插入位置（hash为有序数组）
while(left < right) {
int mid = left + (right - left) / 2;
if(hash.get(mid) < val) left = mid + 1;
else right = mid;
}
hash.set(left, val);
}
return hash.size();
}
}END