本文主要是介绍Greedy 类型题总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Jump Game:思路： Greedy:用maxreach来记录每次可以跳到的最大值，如果某个i > maxreach, 表明这个i我们reach不到，return false，否则 一直更新maxreach
class Solution {public boolean canJump(int[] nums) {if(nums == null || nums.length == 0) {return false;}int maxreach = nums[0];for(int i = 1; i < nums.length; i++) {if(i <= maxreach) {maxreach = Math.max(maxreach, nums[i] + i);} else {// maxreach < i;return false;}}return true;}
}Jump Game II : 思路：贪心，有个概念必须更正，nums[i] 代表的 是可以jump的最大距离，也就是这中间的点也是可以jump到的，所以是一个层级搜索的概念；[curBegin, CurEnd] ,搜集目前的maxReach，如果i走到了CurEnd 代表走完一层，curEnd = maxReach ,step++，搜下一层；注意只用搜到倒数第二个，因为目标是最后一个position，always reach last position;
class Solution {public int jump(int[] nums) {if(nums == null || nums.length == 0) {return 0;}int step = 0, curEnd = 0, maxReach = 0;for(int i = 0; i < nums.length - 1; i++) {maxReach = Math.max(maxReach, nums[i] + i);if(i == curEnd) {curEnd = maxReach;step++;}}return step;}
}Minimum Cost to Connect Sticks PriorityQueue 来做，每次poll出来最小的两个，然后相加，累加到cost里面；
class Solution {public int connectSticks(int[] sticks) {PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> (a - b));for(Integer stick: sticks) {pq.offer(stick);}int cost = 0;while(!pq.isEmpty() && pq.size() > 1) {Integer node1 = pq.poll();Integer node2 = pq.poll();int curcost = node1 + node2;cost += curcost;pq.offer(curcost);}return cost;}
}Reorganize String 用priorityqueue， O(nlog(26)) => O(N); 思想就是每次用最高的c交替进行填充，如何交替就是把c填了以后，不加入pq，然后用第二大的frequency的c去填，然后加入，再继续，具体实现是用中间变量pre来保存上一个频率最大的，不加入queue，然后再加入queue的方法；
class Solution {public class Node {public char c;public int fre;public Node(char c, int fre) {this.c = c;this.fre = fre;}}public String reorganizeString(String s) {HashMap<Character, Integer> hashmap = new HashMap<>();for(int i = 0; i < s.length(); i++) {char c = s.charAt(i);hashmap.put(c, hashmap.getOrDefault(c, 0) + 1);}PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) -> (b.fre - a.fre));for(Character key: hashmap.keySet()) {pq.add(new Node(key, hashmap.get(key)));}StringBuilder sb = new StringBuilder();Node pre = null;while(!pq.isEmpty()) {Node node = pq.poll();sb.append(node.c);node.fre--;if(pre != null && pre.fre > 0) {pq.offer(pre);}pre = node;}return sb.length() == s.length() ? sb.toString() : "";}
}Gas Station
If car starts at A and can not reach B. Any station between A and B
can not reach B.(B is the first station that A can not reach.)
If the total number of gas is bigger than the total number of cost. There must be a solution.
首先判断是否有solution，如果有solution，判断起点在哪里，如果是负数，那么start就是下一个。整个循环是有解的；
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {// find if we can has solution;int overall = 0;for(int i = 0; i < gas.length; i++) {overall += gas[i] - cost[i];}if(overall < 0) {return -1;}// find where to start;int tank = 0; int start = 0;for(int i = 0; i < gas.length; i++) {tank += gas[i] - cost[i];if(tank < 0) {start = i + 1;tank = 0;}}return start;}
}Task Scheduler 就是模拟整个pop的过程，pop n + 1 次，然后把频率全部减去1，看下一阶段的pq是否为空，如果不为空，那么当前的step就是n + 1,里面可能存在idle的step也可以，如果为空，那么当前就是queue.size；
class Solution {public int leastInterval(char[] tasks, int n) {if(tasks == null || tasks.length == 0) {return 0;}HashMap<Character, Integer> hashmap = new HashMap<>();for(int i = 0; i < tasks.length; i++) {char c = tasks[i];hashmap.put(c, hashmap.getOrDefault(c, 0) + 1);}PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> (b - a));pq.addAll(hashmap.values());int step = 0;while(!pq.isEmpty()) {int k = n + 1;Queue<Integer> queue = new LinkedList<>();while(k > 0 && !pq.isEmpty()) {queue.offer(pq.poll());k--;}int queuesize = queue.size();while(!queue.isEmpty()) {int num = queue.poll();if(--num > 0) {pq.offer(num);}}//如果下一阶段还有元素，就是加 n + 1，也就是目前的step可能存在idle，组成n + 1;step += pq.isEmpty() ? queuesize : n + 1;}return step;}
}这篇关于Greedy 类型题总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
