Java 数据结构与算法系列精讲之贪心算法
概述
从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.
贪心算法
贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果.
贪心算法的优缺点:
- 优点: 贪心算法的代码十分简单
- 缺点: 很难确定一个问题是否可以用贪心算法解决
电台覆盖问题
假设存在以下的广播台, 以及广播台可以覆盖的地区:
| 广播台 | 覆盖地区 |
|---|---|
| K1 | 北京, 上海, 天津 |
| K2 | 北京, 广州, 深圳 |
| K3 | 上海, 杭州, 成都 |
| K4 | 上海, 天津 |
| K5 | 杭州, 大连 |
贪心算法的核心思想:
- 把所有需要覆盖的地区取集合
- 从电台中取覆盖集合中地区最多的一个
- 集合中去除已覆盖地区, 继续匹配
代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
public class 贪心算法 {
// 集合, 存放广播台
static HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
// 集合, 存放地区
static HashSet<String> areas = new HashSet<String>();
// 贪心算法
public static ArrayList<String> Greedy() {
// 创建数组存放结果
ArrayList<String> selects = new ArrayList<>();
// 循环直至地区都覆盖
while (areas.size() != 0) {
// 存放交集最大的广播台
String maxKey = null;
// 存放交集最大的值
int maxKeySize = 0;
// 遍历每个剩余电台
for (String key : broadcasts.keySet()) {
// 取出交集个数
int currSize = getRetainSize(key);
// 替换当前最大
if (currSize > 0 && currSize > maxKeySize) {
maxKey = key;
maxKeySize = currSize;
}
}
// 添加广播台到结果
selects.add(maxKey);
// 移除广播台
areas.removeAll(broadcasts.get(maxKey));
}
return selects;
}
// 剩余数量
public static int getRetainSize(String key) {
// 如果为空返回0
if (key == null) return 0;
// 存放key对应的地区集合
HashSet<String> tempSet = new HashSet<>();
// 取key对应的地区
tempSet.addAll(broadcasts.get(key));
// 取交集
tempSet.retainAll(areas);
return tempSet.size();
}
public static void main(String[] args) {
// | K1 | 北京, 上海, 天津 |
// | K2 | 北京, 广州, 深圳 |
// | K3 | 上海, 杭州, 成都 |
// | K4 | 上海, 天津 |
// | K5 | 杭州, 大连 |
// 创建广播台
HashSet<String> K1 = new HashSet<>(Arrays.asList("北京", "上海", "天津"));
HashSet<String> K2 = new HashSet<>(Arrays.asList("北京", "广州", "深圳"));
HashSet<String> K3 = new HashSet<>(Arrays.asList("上海", "杭州", "成都"));
HashSet<String> K4 = new HashSet<>(Arrays.asList("上海", "天津"));
HashSet<String> K5 = new HashSet<>(Arrays.asList("杭州", "大连"));
// 加入map
broadcasts.put("K1", K1);
broadcasts.put("K2", K2);
broadcasts.put("K3", K3);
broadcasts.put("K4", K4);
broadcasts.put("K5", K5);
areas.addAll(K1);
areas.addAll(K2);
areas.addAll(K3);
areas.addAll(K4);
areas.addAll(K5);
// 调试输出
System.out.println(broadcasts);
System.out.println(areas);
ArrayList<String> result = Greedy();
System.out.println(result);
}
}
到此这篇关于Java 数据结构与算法系列精讲之贪心算法的文章就介绍到这了,更多相关Java 贪心算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
Java贪心算法之Prime算法原理与实现方法详解
本文实例讲述了Java贪心算法之Prime算法原理与实现方法.分享给大家供大家参考,具体如下: Prime算法:是一种穷举查找算法来从一个连通图中构造一棵最小生成树.利用始终找到与当前树中节点权重最小的边,找到节点,加到最小生成树的节点集合中,直至所有节点都包括其中,这样就构成了一棵最小生成树.prime在算法中属于贪心算法的一种,贪心算法还有:Kruskal.Dijkstra以及哈夫曼树及编码算法. 下面具体讲一下prime算法: 1.首先需要构造一颗最小生成树,以及两个节点之间的权重数组,在
-
贪心算法原理及在Java中的使用
贪心算法 由于贪心算法本身的特殊性,我们在使用贪心算法之前必须要进行证明,保证算法满足贪心选择性质.具体的证明方法无外乎就是通过数学归纳法来进行证明.但大部分人可能并不喜欢枯燥的公式,因而我这里提供一个使用贪心算法的小技巧.由于贪心算法某种程度上算是动态规划算法的特例,使用条件比较苛刻,因而能够用动态规划解决的问题尽量都是用动态规划来进行先解决,如果在用完动态规划之后,提交时发现问题超时,并且进行状态压缩之后仍然超时,此时我们就可以**考虑使用贪心算法来进行解决.**最后强调一下,我们在使用贪心
-
java贪心算法初学感悟图解及示例分享
算法简介 1)贪心算法是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致是最好或者最优的算法 2)贪心算法所得到的结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果. 应用场景 --> 集合覆盖 public class GreedyAlgorithm { public static void main(String[] args) { // 创建广播电台,放入到Map HashMap<String, HashSet<
-
浅析java贪心算法
贪心算法的基本思路 1.建立数学模型来描述问题. 2.把求解的问题分成若干个子问题. 3.对每一子问题求解,得到子问题的局部最优解. 4.把子问题的解局部最优解合成原来解问题的一个解. 实现该算法的过程: 从问题的某一初始解出发: while 能朝给定总目标前进一步 do 求出可行解的一个解元素: 由所有解元素组合成问题的一个可行解. 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,换句话说,当考虑做何种选择的时候,我们只考虑对当前问题最佳的选择而不考虑子问题
-
Java 数据结构与算法系列精讲之贪心算法
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 贪心算法 贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果. 贪心算法的优缺点: 优点: 贪心算法的代码十分简单 缺点: 很难确定一个问题是否可以用贪心算法解决 电台覆盖问题 假设存在以下的广播台, 以及广播台可以覆盖的地区: 广播台 覆盖地区 K1 北京
-
Java 数据结构与算法系列精讲之排序算法
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 冒泡排序 冒泡排序 (Bubble Sort) 是一种简单的排序算法. 它重复地遍历要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来. 遍历数列的工作是重复地进行直到没有再需要交换, 也就是说该数列已经排序完成. 这个算法的名字由来是因为越小的元素会经由交换慢慢 "浮" 到数列的顶端. 冒泡排序流程: 通过比较相邻的元素, 判断两个元素位置是否需要互换 进行 n-1 次比较,
-
Java 数据结构与算法系列精讲之KMP算法
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. KMP 算法 KMP (Knuth-Morris-Pratt), 是一种改进的字符串匹配算法. KMP 算法解决了暴力匹配需要高频回退的问题, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 从而大大提高效率. 如图: 举个例子 (字符串 "abcabcdef" 匹配字符串 "abcdef"): 次数 暴力匹配 KMP 算法 说明 1 abcabcdef abcdef
-
Java 数据结构与算法系列精讲之字符串暴力匹配
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 字符串匹配 字符串匹配 (String Matching) 指的是判断一个字符串是否包含另一个字符串. 举个例子: 字符串 "Hello World" 包含字符串 "Hello" 字符串 "Hello World" 不包含字符串 "LaLaLa" 暴力匹配 暴力匹配 (Brute-Force) 的思路: 如果charArray1[i] ==
-
Java 数据结构与算法系列精讲之单向链表
目录 概述 链表 单向链表 单向链表实现 Node类 add方法 remove方法 get方法 set方法 contain方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 单向链表 单向链表
-
Java 数据结构与算法系列精讲之环形链表
目录 概述 链表 环形链表 环形链表实现 Node类 insert方法 remove方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 环形链表 环形链表 (Circular Linked Li
-
Java 数据结构与算法系列精讲之栈
目录 概述 栈 栈实现 push方法 pop方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 栈 栈 (Stack) 是一种运算受限的线性表, 遵循先进后出的原则 (Last-In-First-Out). 举个例子, 当我们灌调料的时候, 后灌进去的调料会先被使用. 栈只能在表尾部进行插入和删除的操作. 开口的一端被称为栈顶, 另一端则被称为栈底. 如图: 栈实现 push 方法 栈 (Stack) 的 push 方法, 把项压入栈顶部.
-
Java 数据结构与算法系列精讲之数组
目录 概述 数组 声明数组的两个方法 创建数组的两个方法 索引 自定义数组 泛型 构造函数 元素操作 调用 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 数组 数组 (Array) 是有序数据的集合, 在 Java 中 java.util.Arrays包含用来操作数组的各种方法, 比如排序和搜索等. 其所有方法均为静态方法, 调用起来非常简单. 声明数组的两个方法 方法一: 数据类型[] array; 方法二: 数据类型 array[]; 创建数组的两
-
Java 数据结构与算法系列精讲之二叉堆
目录 概述 优先队列 二叉堆 二叉堆实现 获取索引 添加元素 siftUp 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 优先队列 优先队列 (Priority Queue) 和队列一样, 是一种先进先出的数据结构. 优先队列中的每个元素有各自的优先级, 优先级最高的元素最先得到服务. 如图: 二叉堆 二叉堆 (Binary Heap) 是一种特殊的堆, 二叉堆具有堆的性质和二叉树的性质. 二叉堆中的任意一节点的值总是大于等于其孩子节点值. 如图: 二
-
Java 数据结构与算法系列精讲之时间复杂度与空间复杂度
目录 概述 算法的衡量标准 时间复杂度 最优时间复杂度 平均时间复杂度 最坏时间复杂度 O(1) O(n) O(n^2) O(logN) 空间复杂度 O(1) O(n) 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 算法的衡量标准 当我们需要衡量一个算法的的优越性, 通常会使用时间复杂度 (Time Complexity) 和空间复杂度 (Space Complexity) 来衡量. 时间复杂度 时间复杂度 (Time Complexity) 通常用 O(n)