贪心算法---java---黑马

贪心算法

1)Greedy algorithm

称之为贪心算法或者贪婪算法，核心思想是

1. 将寻找最优解的问题分为若干个步骤
2. 每一步骤都采用贪心原则，选取当前最优解
3. 因为未考虑所有可能，局部最优的堆叠不一定得到最终解最优

贪心算法例子

Dijkstra

while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vretex curr = chooseMinDistVertex(list);// 更新当前顶点到相邻顶点距离updateNeighboursDish(curr);// list集合中移除当前顶点list.remove(curr);// 标记当前顶点已被访问curr.visited = true;
}

• 未能找到最短路径：存在负边 情况，得不到正确解；
• 贪心原则会认为本次已找到该顶点的最短路径，使得该顶点赋为已访问 ；
• 与之对比，Bellman-Ford算法并未考虑局部距离最小顶点，而是每次处理所有边 ，不会出错，当然效率不如Dijkstra算法；

prim

while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vretex curr = chooseMinDistVertex(list);// 更新当前顶点到相邻顶点距离updateNeighboursDish(curr);// list集合中移除当前顶点list.remove(curr);// 标记当前顶点已被访问curr.visited = true;
}

prim与Dijkstra的区别在于，根据距离选取最小顶点不同，Dijkstra算法是一个累加距离，而prim算法中距离是跟相邻顶点间的距离 。

KrusKal

List<String> list = new ArrayList<>();
DisjoinSet set = new DisjoinSet(size);
while (list.size() < size - 1) {// 选取当前【距离最短】的边Edge poll = queue.poll();int i = set.find(poll.start);int j = set.find(poll.end);// 判断两个集合是否相交if (i != j) {// 未相交list.add(poll);set.union(i, j);	// 相交操作}}

其他贪心算法例子

• 选择排序、堆排序
• 拓扑排序
• 并查集和中的union by size 和union by height
• 哈夫曼编码
• 钱币找零
• 任务编排
• 近似算法

零钱兑换ⅡLeetcode518

递归实现

public class Leetcode518 {public int change(int[] coins, int amount) {return coinChange(coins, 0, amount, new LinkedList<>(), true);}public int coinChange(int[] coins, int index, int amount, LinkedList<Integer> stack, boolean first) {if (!first) {stack.push(coins[i]);}int sum = 0;if (amount == 0) {System.out.printlin(stack);sum = 1;} else if (amount < 0) {System.out.println(stack)sum = 0;} else {for(int i = index; i < coins.length; i++) {sum += coinChange(coins, i, amount - coins[i], stack, false);}}if (!stack.isEmpty()) {stack.pop();}return sum;}
}

零钱兑换Leetcode322

递归实现

public class Leetcode322 {static int min = -1;public int change(int[] coins, int amount) {coinChange(coins, 0, amount, new AtomicInteger(-1), new LinkedList<Integer>(), true);return min;}public void coinChange(int[] coins, int index, int amount, AtomicInteger count, LinkedList<Integer> stack, boolean first) {if (!first) {stack.push(coins[i]);}count.incrementAndGet();	// count++;int sum = 0;if (amount == 0) {System.out.println(stack);if (min == -1) {min = min.get();} else {min = Math.min(min, count.get());}} else {for(int i = index; i < coins.length; i++) {sum += coinChange(coins, i, amount - coins[i], count, stack, false);}}count.decrementAndGet();	// count--;	if (!stack.isEmpty()) {stack.pop();}return sum;}public static void main(String[] args) {int[] coins = {5, 2, 1};Leetcode322 leetcode = new Leetcode322();System.out.printlin(leetcode.coinChange(coins, 5));}
}

贪心实现

public class Leetcode322{public int coinChange(int[] coins, int amount) {// 前提是coins是降序排序int reminder = amount;int count;for(int coin : coins) {while (reminder > coin) {reminder -= coin;count++;}if (reminder == coin) {reminder -= coin;count++;break;}}if (reminder > 0) {return -1;} else {return count;}}}

但是这个代码放到Leetcode上跑，有些测试用例是不能通过。

动态规划实现

使用动态规划求解，如下面代码

public class Leetcode322{public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;for(int coin : coins) {for(int j = coin; j < amount + 1; j++) {dp[j] = Math.min(dp[j], dp[j - coin] + 1);}}int r = dp[amount];return r > amount ? -1 : r;}}

哈夫曼编码

Huffman树构建过程

1. 统计出现频次字符，放入优先级队列
2. 每次出对两个频次最低元素(小顶堆)，
3. 当队列中只有一个元素时，构建Huffman树完成

public class Huffman{static class Node{Character ch;int freq;Node left;Node right;String code;public Node(Character ch) {this.ch = ch;}public Node(int freq, Node left, Node right) {this.freq = freq;this.left = left;this.right = right;}int getFreq() {return freq;}boolean isLeaf() {return node.left == null;}@Overridepublic void toString() {return "Node{" +"ch=" + ch + ", freq=" + freq +"}";}}String str;Node root;HashMap<Character, Node> map = new HashMap<>();public Huffman(String str) {this.str = str;char[] chars = str.toCharArray();// 1.统计频次for(char ch : chars) {if (!map.containsKey(ch)) {map.put(ch, new Node(ch));} else {Node node = map.get(ch);node.freq++;}//方法引用// Node node = map.computeIfAbsent(ch, Node :: new);// node.frea++;}for(Node node : map.values()) {System.out.println(node.toString());}2.构造树PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.ComparingInt(Node::getFreq));queue.offerAll(map.values());while (queue.size() >= 2) {Node x = queue.poll();Node y = queue.poll();int f = x.freq + y.freq;queue.offer(new Node(f, x, y));}root = queue.poll();System.out.println(root);// 功能3 计算每个字符编码		//功能4 字符串编码后占几个bitint sum = dfs(root, new StringBuilder());		// 得到字符串编码后占的bitfor(Node node : map.values()) {System.out.printlin(node);}System.out.println(sum);}public int dfs(Node node, StringBuilder sb) {int sum = 0;if (node.isLeaf()) {//编码node.node = sb.toString();sum = sb.length() * node.freq;// System.out.println(sb.toString());   } else {sum += dfs(node.left, sb.append("0"));sum += dfs(node.right, sb.append("1"));}if (sb.length() > 0) {sb.deleteCharAt(sb.length() - 1);}return sum;}public String encode() {char[] chars = str.toCharArray();StringBuilder sb = new StringBuilder();for(char ch : chars) {sb.append(map.get(ch).code);}return sb.toString();}public String decode(String str) {int i = 0;char[] chars = str.toCharArray();StringBuilder sb = new StringBuilder();Node node = root;while (i < chars.length) {if (!node.isLeaf()) {if (chars[i] == '0') {node = node.left;} else if (chars[i] == '1'){node = node.right;}i++;} if (node.isLeaf()) {sb.append(node.ch);node = root;}}return sb.toString();}
}

活动选择问题

要在一个会议室举办n个活动

• 每个活动有它们各自的起始和结束时间
• 找出时间上不冲突的活动组合，能够最充分利用会议室(举办的活动次数最多)

public class ActivitySelectionProblem{static class Activity{int index;int start;int end;public Activity(int index, int start, int end) {this.index = index;this.start = start;this.end = end;}public int getEnd() {return end;}@Overridepublic void tostring() {return "Activity(" + index + ")";}}public static void main(String[] args) {Activity[] activity = new Activity[]{new Activity(0, 1, 3),new Activity(1, 2, 4),new Activity(2, 3, 5)}	Arrays.sort(activity, Comparator.comparingInt(Activity::getEnd))System.out.println(activity);// select(activity, activity.length);}public void select(Activity[] activity, int n) {List<int[]> res = new ArrayList<>();res.add(activity[0]);Activity pre = res;for(int i = 1; i < n; i++) {Activity curr = activity[i];if (curr.start >= pre.end) {res.add(curr);pre =  curr;}}for(Activity a : res) {System.out.println(a);}}
}

Leetcode435

无重叠区间

public class Leetcode435{public int eraseOverlapIntervals(int[][] intervals) {// 根据数组中的第二个元素先升序排序Arrays.sort(intervals, (a, b) -> a[1] - b[1]);List<int[]> res = new ArrayList<>();res.add(intervals[0]);int[] pre = res.get(0);int count = 0;	// 减少个数for(int i = 1; i < intervals.length; i++) {int[] curr = intervals[i];if (curr[0] < pre[1]) {		// 当前的初始值小于前一个的结束值，有冲突count++;} else {	// 只要当前的初始值大于等于前一个的结束值，则不冲突res.add(curr);pre = curr;}}return count;}
}

分数背包问题

1. n个液体物品，有重量和价格属性
2. 现取走10L物品
3. 每次可以不拿，全拿，拿一部分，问最高价值是多少
   

public class FractionalKnapsackProblem{static class Item{int index;int weight;int value;public Item(int index, int weight, int value) {this.index = index;this.weight = weight;this.value = value;}public int perValue() {return value / weight;}@Overridepublic void toString() {return "Item(" + index + ")";}}public static void main(String[] args) {Item[] items = new Item[]{new Item(0, 4, 24),new Item(1, 8, 160),new Item(2, 2, 4000),new Item(3, 6, 108),new Item(4, 1, 4000),}select(items, 10);}public int select(Item[] items, int n) {Arrays.sort(items, Comparator.comparingInt(Item::preValue).reverse());int sum = 0;for(int i = 0; i < items.length; i++) {Item curr = items[i];if (n >= curr.weight) {n -= curr.weight;sum += curr.value;} else {sum += curr.perValue() * n;break;}}return sum;}
}

0-1背包问题

1. n个物体都是固体，有重量和价值
2. 现取走不超过10克物品
3. 每次可以不拿或者全拿，问最高价值是多少

public class FractionalKnapsackProblem{static class Item{int index;int weight;int value;public Item(int index, int weight, int value) {this.index = index;this.weight = weight;this.value = value;}public int perValue() {return value / weight;}@Overridepublic void toString() {return "Item(" + index + ")";}}public static void main(String[] args) {Item[] items = new Item[]{new Item(0, 1, 1000000),new Item(1, 4, 1600),new Item(2, 8, 2400),new Item(3, 5, 30),}select(items, 10);}public int select(Item[] items, int n) {Arrays.sort(items, Comparator.comparingInt(Item::preValue).reverse());int sum = 0;for(int i = 0; i < items.length; i++) {Item curr = items[i];if (n >= curr.weight) {n -= curr.weight;sum += curr.value;}}return sum;}
}

得到的结果，最大价值结果是：1001630 ，实际上选择钻石和红宝石 得到的价值结果 1002400

贪心算法局限性