贪心算法---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

贪心算法局限性

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/463354.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

操作系统——计算机系统概述——1.4操作系统结构

目录 操作系统的体系结构 大内核&#xff08;宏内核/单内核&#xff09;&#xff1a; 微内核&#xff1a; 分层法 模块化 操作系统的体系结构 大内核&#xff08;宏内核/单内核&#xff09;&#xff1a; 将操作系统的主要功能模块都作为系统内核&#xff0c;运行在核心态。…

【MyBatis源码】BoundSql分析

基础 BoundSql是对SQL语句及参数信息的封装&#xff0c;它是SqlSource解析后的结果。Executor组件并不是直接通过StaticSqlSource对象完成数据库操作的&#xff0c;而是与BoundSql交互。BoundSql是对Executor组件执行SQL信息的封装&#xff0c;具体实现代码如下&#xff1a; …

本地部署bert-base-chinese模型交互式问答,gradio

首先下载bert-base-chinese&#xff0c;可以在 Huggingface, modelscope, github下载 pip install gradio torch transformers import gradio as gr import torch from transformers import BertTokenizer, BertForQuestionAnswering# 加载bert-base-chinese模型和分词器 mod…

【题】C#-数组:二维数组

1. 将1~10000赋值给一个二维数组(100行100列) int[,] array new int[100,100]; int index 1; for(int i 0;i < array.GetLength(0);i){for(int j 0;j < array.GetLength(1);j){array[i,j] index;index;} }2. 将二维数组的右上半部分置零 int[,] array new int[4,…

你还在用一串数字访问你的系统吗?

大家还记得第一次启动SpringBoot应用并在浏览器访问是如何进行的吗&#xff1f;在SpringBoot启动后&#xff0c;我们会看到如图所示&#xff1a; SpringBoot内置tomcat以端口8080启动&#xff0c;然后根据指引&#xff0c;我们在浏览器输入&#xff1a; http://127.0.0.1:8080…

ffmpeg视频滤镜:膨胀操作-dilation

滤镜介绍 dilation 官网链接 > FFmpeg Filters Documentation 膨胀滤镜会使图片变的更亮&#xff0c;会让细节别的更明显。膨胀也是形态学中的一种操作&#xff0c;在opencv中也有响应的算子。此外膨胀结合此前腐蚀操作&#xff0c;可以构成开闭操作。 开操作是先腐蚀…

Unity中的屏幕坐标系

获得视口宽高 拖动视口会改变屏幕宽高数值 MousePosition 屏幕坐标系的原点在左下角&#xff0c;MousePosition返回Z为0也就是纵深为0的Vector3 但是如果鼠标超出屏幕范围不会做限制&#xff0c;所以可能出现负数或者大于屏幕宽高的情况&#xff0c;做鼠标拖拽物体时需要注…

基于SpringBoot的学生读书笔记共享的设计与实现

一、项目背景 计算机的普及和互联网时代的到来使信息的发布和传播更加方便快捷。用户可以通过计算机上的浏览器访问多个应用系统&#xff0c;从中获取一些可以满足用户需求的管理系统。网站系统有时更像是一个大型“展示平台”&#xff0c;用户可以选择所需的信息进入系统查看…

【数据结构】二叉树——层序遍历

层序遍历 一、层序遍历二、层序遍历&#xff08;递归&#xff09;三、层序遍历&#xff08;非递归&#xff09;四、总结 一、层序遍历 层序遍历是一种广度优先遍历 以图上二叉树为例&#xff0c;层序遍历就是按照二叉树的深度一层一层进行遍历 遍历顺序&#xff1a; A B C D …

react使用Fullcalendar

前言&#xff1a; 最近在做项目时&#xff0c;遇到了需要用日历的项目。一开始考虑使用antd的日历组件。后来 调研技术库&#xff0c;发现了fullcalendar 库。经过对比 fullcalendar 更强大&#xff0c;更灵活。 其实 antd的日历组件 也不错&#xff0c;简单的需求用他也行。…

Golang--函数、包、defer、系统函数、内置函数

1、何为函数 函数作用&#xff1a;提高代码的复用型&#xff0c;减少代码的冗余&#xff0c;提高代码的维护性 函数定义&#xff1a;为完成某一功能的程序指令(语句)的集合,称为函数。 语法&#xff1a; func 函数名(形参列表)(返回值类型列表){ //执行语句 //…… return …

Chrome和Firefox如何保护用户的浏览数据

在当今数字化时代&#xff0c;保护用户的浏览数据变得尤为重要。浏览器作为我们日常上网的主要工具&#xff0c;其安全性直接关系到个人信息的保密性。本文将详细介绍Chrome和Firefox这两款主流浏览器如何通过一系列功能来保护用户的浏览数据。&#xff08;本文由https://chrom…

如何在Linux系统中使用SSH进行安全连接

如何在Linux系统中使用SSH进行安全连接 SSH简介 安装SSH 在Debian/Ubuntu系统中安装 在CentOS/RHEL系统中安装 启动SSH服务 验证SSH是否安装成功 SSH配置 配置监听端口 配置登录方式 SSH客户端 安装SSH客户端 使用SSH客户端 SSH密钥认证 生成SSH密钥对 复制公钥到远程服务器…

ElasticSearch - Bucket Selector使用指南

文章目录 官方文档Bucket Selector1. 定义2. 工作原理3. 使用场景与示例使用场景官方案例示例2 4. 注意事项5. 总结 官方文档 https://www.elastic.co/guide/en/elasticsearch/reference/current/search-aggregations.html Bucket Selector https://www.elastic.co/guide/en/…

RHCE——笔记

Web服务器 1&#xff0c;web服务器简介 &#xff08;1&#xff09;什么是www 是全球信息广播的意思。通常说的上网就是使用 www 来查询用户 所需要的信息。 www 可以结合文字、图形、影像以及声音等多媒体&#xff0c;并通过可以让鼠标单击超链接的方式将信息以Internet 传递…

Unity XR Interaction Toolkit 开发教程(1):OpenXR 与 XRI 概述【3.0 以上版本】

文章目录 &#x1f4d5;Unity XR 开发架构&#x1f50d;底层插件&#xff08;对接硬件&#xff09;&#x1f50d;高层 SDK&#xff08;面向应用交互层&#xff09; &#x1f4d5;OpenXR&#x1f4d5;XR Interaction Toolkit&#x1f50d;特点&#x1f50d;XRI 能够实现的交互类…

HarmonyOS:@Watch装饰器:状态变量更改通知

Watch应用于对状态变量的监听。如果开发者需要关注某个状态变量的值是否改变&#xff0c;可以使用Watch为状态变量设置回调函数。 说明 从API version 9开始&#xff0c;该装饰器支持在ArkTS卡片中使用。 从API version 11开始&#xff0c;该装饰器支持在元服务中使用。 一、概…

AIGC对传统内容创作行业的冲击

文章目录 引言一、AIGC的概念1.1 AIGC的工作原理 二、AIGC对内容创作行业的影响2.1 提高创作效率2.2 降低创作门槛2.3 改变内容创作的形式 三、AIGC带来的挑战3.1 版权和道德问题3.2 内容质量的参差不齐3.3 人类创作者的角色变化 四、AIGC的应用场景4.1 新闻行业4.2 市场营销4.…

Linux 下执行定时任务之 Systemd Timers

不知道 ECS 因为什么缘故&#xff0c;上面安装的 MySQL 服务老是不定期挂掉&#xff0c;本来想通过 Linux 得 Cron 配置个半小时的定时检测任务&#xff0c;结果一直没有执行&#xff0c;因此又尝试使用了 Systemd Timers 进行了重新配置&#xff0c;简要做个记录。 Systemd Ti…

Java已死,大模型才是未来?

作者&#xff1a;不惑_ 引言 在数字技术的浪潮中&#xff0c;编程语言始终扮演着至关重要的角色。Java&#xff0c;自1995年诞生以来&#xff0c;便以其跨平台的特性和丰富的生态系统&#xff0c;成为了全球范围内开发者们最为青睐的编程语言之一 然而&#xff0c;随着技术的…