免费vi模板网站,北京网站案例,千博企业网站管理系统 下载,crm系统开发1) 贪心例子 称之为贪心算法或贪婪算法#xff0c;核心思想是 将寻找最优解的问题分为若干个步骤 每一步骤都采用贪心原则#xff0c;选取当前最优解 因为没有考虑所有可能#xff0c;局部最优的堆叠不一定让最终解最优 v2已经不会更新v3因为v3更新过了 贪心算法是一种在…1) 贪心例子 称之为贪心算法或贪婪算法核心思想是 将寻找最优解的问题分为若干个步骤 每一步骤都采用贪心原则选取当前最优解 因为没有考虑所有可能局部最优的堆叠不一定让最终解最优 v2已经不会更新v3因为v3更新过了 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择从而希望导致结果是最好或最优的算法。这种算法通常用于求解优化问题如最小生成树、背包问题等。 贪心算法的应用 背包问题给定一组物品和一个背包每个物品有一定的重量和价值要求在不超过背包容量的情况下尽可能多地装入物品。 活动选择问题在一个活动集合中每次只能参加一个活动问如何安排时间以最大化所有活动的收益。 编辑距离问题给定两个字符串求它们之间的最小编辑距离(即将一个字符串转换为另一个字符串所需的最少操作次数)。 网络流问题给定一张有向图和一些起点和终点求最大流量。 找零问题给定一定数量的硬币和需要找零的金额求使用最少的硬币数。 常见问题及解答 贪心算法一定会找到最优解吗 答不一定。贪心算法只保证在每一步选择中都是最优的但并不能保证整个问题的最优解。例如背包问题中的贪心算法可能会导致最后一个物品没有被装入背包。 如何判断一个问题是否适合用贪心算法解决 答一个问题如果可以用递归的方式分解成若干个子问题且每个子问题都有明确的最优解(即局部最优),那么这个问题就可以用贪心算法解决。 贪心算法的时间复杂度是多少 答贪心算法的时间复杂度取决于问题的规模和具体实现。一般来说对于规模较小的问题贪心算法的时间复杂度可以达到O(nlogn)或O(n^2);对于规模较大的问题可能需要O(n^3)或更高。 几个贪心的例子
Dijkstra
// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited true;
} 没找到最短路径的例子负边存在时可能得不到正确解 问题出在贪心的原则会认为本次已经找到了该顶点的最短路径下次不会再处理它curr.visited true 与之对比Bellman-Ford 并没有考虑局部距离最小的顶点而是每次都处理所有边所以不会出错当然效率不如 Dijkstra Prim
// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited true;
}
Kruskal
// ...
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 哈夫曼编码 钱币找零英文搜索关键字 change-making problem find Minimum number of Coins 任务编排 求复杂问题的近似解 2) 零钱兑换问题
有几个解零钱兑换 IILeetcode 518
[1,2,5] 5 暴力递归 有解[1, 1, 1, 1, 1] 无解[1, 1, 1, 1, 2] 无解[1, 1, 1, 1, 5] 有解[1, 1, 1, 2] 无解[1, 1, 1, 5] 无解[1, 1, 2, 2] 无解[1, 1, 2, 5] 无解[1, 1, 5] 有解[1, 2, 2] 无解[1, 2, 5] 无解[1, 5] 无解[2, 2, 2] 无解[2, 2, 5] 无解[2, 5] 有解[5] 4 public int rec(int index,int[] coins,int remainder){//1.情况1:剩余金额 0 - 无解//2.情况2:剩余金额 0 - 继续递归//3.情况3:剩余金额 0 - 有解if(remainder 0){return 0;}else if(remainder 0){return 1;}else{int count 0;for(int i index;icoins.length;i){countrec(i,coins,remainder-coins[i]);}return count;}}
那这个递归是怎么运作的呢? /*
//第一次传入 index 01 处理硬币和剩余金额rec(1,5) remainder 0 所以走else逻辑 再循环中的递归是多路递归rec(1,4)rec(1,3)rec(1,2)rec(1,1)rec(1,0) 1rec(2,-1) 0rec(5,-4) 0rec(2,0) 1rec(5,-3) 0rec(2,1)rec(2,-1) 0rec(5,-4) 0rec(5,-2) 0rec(2,2)rec(2,0) 1rec(5,-3) 0rec(5,-1) 0rec(2,5-23)rec(2,1)rec(2,-1) 0rec(5,-4) 0rec(5,-2) 0rec(5,5-50) 1*/import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;/*** 零钱兑换* 可以凑成总金额所需的所有组合可能数*/
public class Leetcode518 {public int coinChange(int[] coins, int amount) {return rec(0, coins, amount, new LinkedList(), true);}/*** 求凑成剩余金额的解的个数** param index 当前硬币索引* param coins 硬币面值数组* param remainder 剩余金额* param stack -* param first -* return 解的个数*/public int rec(int index, int[] coins, int remainder, LinkedListInteger stack, boolean first) {if(!first) {//第一次不压栈stack.push(coins[index]);}// 情况1剩余金额 0 - 无解int count 0;if (remainder 0) {print(无解, stack);
// if(!stack.isEmpty()){
// stack.pop();
// }}// 情况2剩余金额 0 - 有解else if (remainder 0) {print(有解, stack);
// if(!stack.isEmpty()){
// stack.pop();
// }count 1;}// 情况3剩余金额 0 - 继续递归else {for (int i index; i coins.length; i) {count rec(i, coins, remainder - coins[i], stack, false);}}if (!stack.isEmpty()) {stack.pop();}return count;}private static void print(String prompt, LinkedListInteger stack) {ArrayListInteger print new ArrayList();ListIteratorInteger iterator stack.listIterator(stack.size());while (iterator.hasPrevious()) {print.add(iterator.previous());}System.out.println(prompt print);}public static void main(String[] args) {Leetcode518 leetcode new Leetcode518();
// int count leetcode.coinChange(new int[]{1, 5, 10, 25}, 41);
// int count leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
// int count leetcode.coinChange(new int[]{5, 2, 1}, 5);int count leetcode.coinChange(new int[]{1, 2, 5}, 5);
// int count leetcode.change(new int[]{15, 10, 1}, 21);System.out.println(count);}
}
但是这个代码放在leetcode上面跑会超时,因为重复处理了很多次相同的操作
我们可以考虑用记忆法 动态规划来优化
我们也可以考虑顺序优化 规模下降明显 /*
[5,2,1] 5
rec(5,5)rec(5,0) 1rec(2,3) rec(2,1)rec(2,-1) 0rec(1,0) 1rec(1,1)rec(1,0) 1rec(1,4)rec(1,3)rec(1,2)rec(1,1)rec(1,0) 1*/ 但即使是这样写在leetcode上也是会 StackOverflowError
class Solution {public int change(int amount, int[] coins1) {int[] coins sort(coins1);return rec(0,coins,amount);}int rec(int index,int[] coins,int remainder){int count 0;if(remainder 0){return 1;}else if(remainder0){return 0;}else{for(int i index;icoins.length;i){countrec(index,coins,remainder);}return count;}}/***传入一个有序的数组a(从小到大排序),返回一个从大到小的数组*param a 传入的数组(有序)*return 返回一个数组(从大到小)*/int[] sort(int[] a){int[] temp a;if(temp.length % 2 0){//数组里面的个数为偶数for(int i 0;itemp.length/2;i){int temp1 a[i];temp[i] temp[temp.length-1-i];temp[temp.length-1] temp1;}}else{//数组里面的个数为奇数for(int i 0;itemp.length/2;i){int temp1 a[i];temp[i]temp[temp.length-1-i];temp[temp.length-1-i] temp1;}}return temp;}
} import java.util.Arrays;public class Main {public static void main(String[] args) {int[] arr sort(new int[]{1,2,3});System.out.println(Arrays.toString(arr));//为什么我这么选择是因为用Arrays.sort要将数组转化为Integer[]}/***传入一个有序的数组a从小到大排序返回一个从大到小的数组* param a 传入的数组有序* return 返回一个数组从大到小*/public static int[] sort(int[] a){int[] temp a;if(temp.length%20){//数组里面的个数为偶数for (int i 0; i temp.length/ 2; i) {int temp1 a[i];temp[i]temp[temp.length-1-i];temp[temp.length - 1-i] temp1;}}else{//数组里面的个数为奇数for (int i 0; i temp.length / 2; i) {int temp1 a[i];temp[i]temp[temp.length-1-i];temp[temp.length - 1-i] temp1;}}return temp;}
} 动态规划-会在动态规划章节说明 最优解零钱兑换- 穷举法 Leetcode 322
import java.util.LinkedList;
import java.util.concurrent.atomic.AtomicInteger;public class Leetcode322 {static int min -1; // 需要的最少硬币数 2 3public int coinChange(int[] coins, int amount) {rec(0, coins, amount, new AtomicInteger(-1), new LinkedList(), true);return min;}// count 代表某一组合 钱币的总数 可变的整数对象public void rec(int index, int[] coins, int remainder, AtomicInteger count, LinkedListInteger stack, boolean first) {if (!first) {stack.push(coins[index]);}count.incrementAndGet(); // countif (remainder 0) {System.out.println(stack);if (min -1) {min count.get();} else {min Integer.min(min, count.get());}} else if (remainder 0) {for (int i index; i coins.length; i) {rec(i, coins, remainder - coins[i], count, stack, false);}}count.decrementAndGet(); // count--if (!stack.isEmpty()) {stack.pop();}}public static void main(String[] args) {Leetcode322 leetcode new Leetcode322();
// int count leetcode.coinChange(new int[]{5, 2, 1}, 5);int count leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
// int count leetcode.coinChange(new int[]{2}, 3);
// int count leetcode.coinChange(new int[]{15, 10, 1}, 21);System.out.println(count);}
}
最优解零钱兑换- 贪心法 Leetcode 322
自己看看就行因为有些测试样例过不了
假定传过来的数据就是从大到小排序,因为java对int数组从大到小排序比较麻烦
public class Leetcode322 {public int coinChange(int[] coins, int amount) {int remainder amount;int count 0;for (int coin : coins) {while (remainder - coin 0) {remainder - coin;count;}if (remainder - coin 0) {remainder 0;count;break;}}if (remainder 0) {return -1;} else {return count;}}public static void main(String[] args) {Leetcode322 leetcode new Leetcode322();int count leetcode.coinChange(new int[]{5, 2, 1}, 5);
// int count leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
// int count leetcode.coinChange(new int[]{2}, 3);// 问题1 没有回头导致找到更差的解
// int count leetcode.coinChange(new int[]{15, 10, 1}, 21); // 问题2 没有回头导致无解
// int count leetcode.coinChange(new int[]{15, 10}, 20); System.out.println(count);}
}
