贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都作出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
每次当下选择最好的会不会是全局最优的呢？不一定，有时候可以，有时候不行
很多情况下，可以在某一步用贪心算法，全局再加一个搜索或递归或动态规划之类
贪心:当下做局部最优判断
回溯:能够回退
动态规划:最优判断+回退
贪心法可以解决一些最优化问题，如:求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案。
一单一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
当硬币可选集合固定:Coins = [20,10,5,1],求最少几个硬币可以拼出总数。比如total=36。
36 - 20 = 16 20
16 - 10 = 6 20 10
6 - 5 = 1 20 10 5
1 - 1 = 0 20 10 5 1
前面这些硬币依次是后面硬币的整数倍，可以用贪心法，能得到最优解，
贪心法的反例
非整除关系的硬币，可选集合:Coins = [10,9,1],求拼出总数为18最少需要几个硬币？
最优化算法:9 + 9 = 18 两个9
贪心算法:18 - 10 = 8 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 = 0 八个1
何种情况下可以用到贪心算法
简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解成为最优子结构。
贪心算法与动态规划的不同在于它对每个子问题的最终方案都作出选择，不能回退。
动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
分发饼干(亚马逊)
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
提示：
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
public int findContentChildren(int[] g, int[] s) {
//排序小孩胃口值
Arrays.sort(g);
//排序饼干数量
Arrays.sort(s);
//记录满足条件数量
int res = 0;
int i = 0;
int j = 0;
while (i<g.length && j<s.length){
if (g[i] <= s[j]){
res+=1;
i++;
j++;
}else{
j++;
}
}
return res;
}
买卖股票的最佳时机(亚马逊、字节、微软)
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
public int maxProfit(int[] prices) {
if (prices.length < 2) return 0;
int res = 0;
for(int i = 1;i<prices.length;i++){
if (prices[i] > prices[i-1]){
res += (prices[i] - prices[i-1]);
}
}
return res;
}
跳跃游戏(亚马逊、华为、Facebook)
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
public boolean canJump(int[] nums) {
if (nums == null) return false;
int endReachable = nums.length - 1;
for (int i = nums.length -1; i>=0;i--){
if (nums[i] + i >= endReachable){
endReachable = i;
}
}
return endReachable == 0;
}
跳跃游戏II(亚马逊、华为、字节跳动)
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。
想要达到这样的效果，只要让移动下标，最大只能移动到nums.size - 2的地方就可以了。
因为当移动下标指向nums.size - 2时：
如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：
如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：
public int jump(int[] nums) {
int ans = 0;//记录要跳跃的步数
int curDistance = 0; //当前覆盖的最远距离下标
int nextDistance = 0; //下一步覆盖的最远距离下标
for (int i = 0;i<nums.length - 1;i++){//小于nums.length-1
nextDistance = Math.max(nums[i]+i,nextDistance);//获取下一步能覆盖的最远距离下标
if (curDistance == i){//遇到当前位置的最远距离下标
curDistance = nextDistance;//更新当前覆盖的最远距离下标
ans++;
}
}
return ans;
}
模拟行走机器人
机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：
-2 ：向左转 90 度
-1 ：向右转 90 度
1 <= x <= 9 ：向前移动 x 个单位长度
在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi) 。
机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续尝试进行该路线的其余部分。
返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 5 ，则返回 25 ）
注意：
北表示 +Y 方向。
东表示 +X 方向。
南表示 -Y 方向。
西表示 -X 方向。
示例 1：
输入：commands = [4,-1,3], obstacles = []
输出：25
解释：
机器人开始位于 (0, 0)：
- 向北移动 4 个单位，到达 (0, 4)
- 右转
- 向东移动 3 个单位，到达 (3, 4)
距离原点最远的是 (3, 4) ，距离为 32 + 42 = 25
示例 2：
输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出：65
解释：机器人开始位于 (0, 0)： - 向北移动 4 个单位，到达 (0, 4)
- 右转
- 向东移动 1 个单位，然后被位于 (2, 4) 的障碍物阻挡，机器人停在 (1, 4)
- 左转
- 向北走 4 个单位，到达 (1, 8)
距离原点最远的是 (1, 8) ，距离为 12 + 82 = 65
public int robotSim(int[] commands, int[][] obstacles) {
int result = 0;
int x=0,y=0,direction =0;
int[] directX = new int[]{0,1,0,-1};
int[] directY = new int[]{1,0,-1,0};
Set<String> obstacleSet = new HashSet<>();
for (int[] m: obstacles) {
obstacleSet.add(m[0]+","+m[1]);
}
for (int i : commands) {
if (i == -2){//向左转
direction = (direction + 3)%4;
}
else if (i==-1){//向右转
direction = (direction + 1)%4;
}else{
for (int j = 1;j<=i;j++){
int newX = x + directX[direction];
int newY = y + directY[direction];
if (obstacleSet.contains(newX+","+newY)){
break;
}
x = newX;
y = newY;
result = Math.max(result,x*x+y*y);
}
}
}
return result;
}
柠檬水找零(亚马逊)
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：[5,5,10]
输出：true
示例 3：
输入：[10,10]
输出：false
示例 4：
输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
public boolean lemonadeChange(int[] bills) {
int five = 0,ten = 0,twenty = 0;
for (int bill : bills) {
if (bill == 5){
five++;
}else if(bill == 10){
if (five>0) {
five--;
ten++;
}else return false;
}else if(bill == 20){
if (ten>0 && five > 0){
ten --;
five --;
twenty ++;
}else if(five >=3){
five -= 3;
twenty ++;
}else{
return false;
}
}
}
return true;
}
coin change题目-零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
示例 4：
输入：coins = [1], amount = 1
输出：1
示例 5：
输入：coins = [1], amount = 2
输出：2
int minAns = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount){
if (amount == 0) return 0;
Integer[] coinArray = Arrays.stream(coins).boxed().toArray(Integer[]::new);
Arrays.sort(coinArray,Collections.reverseOrder());
coinChangeBfs(coinArray,amount,0,0);
minAns = (minAns == Integer.MAX_VALUE)?-1:minAns;
return minAns;
}
//coinArray:硬币数组 amount:目标值 index: 有效硬币数组范围 count: 已使用硬币数 miniAns: 当前最小值
public void coinChangeBfs(Integer[] coinArray,int amount,int index,int count){
if (amount == 0) {//遍历到最后有解
minAns = Math.min(minAns,count);
return;
}
if (coinArray.length == index) return;//遍历到最后无解
for (int maxCoinNum = amount/coinArray[index];maxCoinNum>=0 && maxCoinNum+count<minAns;maxCoinNum--){
coinChangeBfs(coinArray,amount-maxCoinNum*coinArray[index],index+1,count+maxCoinNum);
}
}
