最近一直在为准备秋招，一直研究贪心算法，贪心算法的代码看起来简单，但是很考验个人的分析能力，或者就是找规律的能力，所以向大家分享几道贪心方面的习题，都来自于leetcode。如果下文有表达不清，或者说有错误的时候，烦请诸位大佬及时指出。
LeetCode 402:
题目描述：
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 示例 1 :
输入: num = "1432219", k = 3 输出: "1219" 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。 示例 2 :
输入: num = "10200", k = 1 输出: "200" 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。 示例 3 :
输入: num = "10", k = 2 输出: "0" 解释: 从原数字移除所有的数字，剩余为空就是0。
思路分析：关于这里题目考验的就是贪心算法，贪心算法所谓的就是只求当前最优或者就是局部最优
例：1432219，以这个数举例子，加入k是1的话（从头开始遍历）：
从高位开始删除的话：
（1）1432219-->432219(这是删除1的情况)，对于保留1的情况是1432219除过1无论删任何数字，都会比432219小的因为此时在相同的位数下，高位是4的很明显大圩高位是1的
（2）经过这样的分析之后可以大致得到结论：如果高位的数大圩地位的数就应该删除，否则就保留
（3）但是这样的处理结果，无非还有下面几个问题：首先是（12345678）对于这种完全升序的情况，100（删除1位）只留下全0的情况，以及（类似112）的情况，都要左单独的处理
读者先可以考虑考虑第（3）步的情况？
第一种：利用的是栈的思想
class Solution { public String removeKdigits(String num, int k) { Stack<Integer>stack=new Stack<Integer>(); StringBuilder str=new StringBuilder(); char[] nums=num.toCharArray(); for(int i=0;i<nums.length;i++) { int number=nums[i]-'0'; while(!stack.isEmpty()&&stack.peek()>number&&k>0) { stack.pop(); k--; } if(number!=0||stack.size()>0) { stack.push(number); } } while(stack.size()!=0&&k>0) { stack.pop(); k--; } for(int i=0;i<stack.size();i++) { str.append(stack.get(i)); } if(str.toString().equals(""))return "0"; return str.toString(); } }第二种:完全的纯遍历，以及逻辑实现
class Solution { public String removeKdigits(String num, int k) { StringBuilder str=new StringBuilder(new String(num)); if(str.length()<=k)return 0+""; for(int j=0;j<str.length()-1;j++){ while(k>0) { if(str.length()>0&&j>=0&&str.charAt(j)-'0'>str.charAt(j+1)-'0') { str.delete(j,j+1); j--; k--; }else { break; } } } while(k>0) { if(str.charAt(str.length()-2)>str.charAt(str.length()-1)) { str.delete(str.length()-2,str.length()-1); k--; }else { break; } } if(k>0) { str.delete(str.length()-k,str.length()); } //处理前导0的情况 for(int i=0;i<str.length();i++) { if(str.charAt(i)=='0'&&i==0) { str.delete(i,i+1); i--; } } if(str.toString().equals(""))return 0+""; return str.toString(); } }LeetCode 452:
题目描述：
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。
一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
Example:
输入: [[10,16], [2,8], [1,6], [7,12]]
输出:
2
算法思路：我以写的第二种方法的代码来解释，贪心的思维就是先按右边结点给他们拍个序（升序），然后尽最大可能去找重叠的部分，如果有重叠那就说明可以用同一支剑，如果没有一丝重叠，那么就要拿出新的一支箭来射他。
第一种（自己实现排序）：
class Solution { public int findMinArrowShots(int[][] points) { if(points.length<=0)return 0; for(int i=0;i<points.length;i++) {//利用插入排序对这个数组进行排序 for(int j=i;j>0&&points[j-1][0]>points[j][0];j--) { swap(points,j,j-1); } } int num=1;//表示弓箭手 int begin=points[0][0];//表示起始位置 int end=points[0][1];//表示末端位置 for(int i=1;i<points.length;i++) {//遍历数组 if(points[i][0]<=end) {//如果遇到左端结点小于end（末端位置）,更新begin begin=points[i][0]; if(end>points[i][1]) {//如果左端点小于end并且end大于右端点,更新end end=points[i][1]; } } if(points[i][0]>end) {//左端点大于end时表示没有任何重叠,新增射箭手,更新begin,end num++; begin=points[i][0]; end=points[i][1]; } } return num; } public void swap(int[][] arr,int i,int j) {//交换(交换左边的节点的同时也交换右边结点) int temp=arr[i][0]; arr[i][0]=arr[j][0]; arr[j][0]=temp; int sw=arr[i][1]; arr[i][1]=arr[j][1]; arr[j][1]=sw; } }第二种：（利用JDK自带的Arrays.sort()进行排序，效率会更高）
class Solution { public int findMinArrowShots(int[][] points) { if(points.length == 0 || points == null) return 0; // 归约（转化为从小到大排序的数组） //Arrays.sort(points,Comparator.comparingInt(o->o[1])); Arrays.sort(points, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[1] - o2[1]; } }); // 使用的箭数量 int cnt = 1, end = points[0][1]; for (int i = 1; i < points.length; i++) { if (points[i][0] <= end) { continue; } cnt++; end = points[i][1]; } return cnt; } }
