贪心策略:请你最最小的金条分割代价

2023-11-11 06:10

本文主要是介绍贪心策略:请你最最小的金条分割代价,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

贪心策略:请你最最小的金条分割代价

提示:从本文开始,咱们来说贪心策略系列文章!!

贪心策略在互联网大厂的招聘笔试和面试中的地位!!!在笔试中考贪心,而面试不考贪心。

(1)贪心在笔试中:75%的考题都是贪心策略,为啥呢,一方面考你的聪明程度,另一方面,考你的代码编写能力;所以我参加过的笔试证明了这一点,往往大厂给你三个算法题,第1道题一定是贪心,排序结合的算法题,你需要懂点脑子,了解一下排序和堆啥的数据结构,还得会点贪心技巧,才能设计出来;
(2)面试不怎么考贪心策略,为什么?因为面试考你的是算法的优化能力,所以如果给你贪心的话,你一下子想到了解决方案,也不谈什么优化的事情,没意义,所以不考贪心。
(3)你必须要认识到:最简单的是国内的面试过程(嘴说的事情,都好办),难度中上等的是国外的笔试面试,最难的国内的算法笔试。 那么,你一定要明白,最难的还是国内的算法笔试题!!!因此要多练,多学,多见题,多思考,多总结,才能拿下。

以下是贪心策略基础题目系列文章:
(1)贪心策略:请你计算i×arr[i]的累加和最大值
(2)贪心策略:请你设计最优的安排会议日程表,以使得举行的会议数最多
(3)贪心策略:求一条街上最少应该放多少盏灯,才能照亮整条街的商户
(4)贪心策略:请你将字符串拼接,最终拼接好的字符串字典序最小


文章目录

  • 贪心策略:请你最最小的金条分割代价
    • @[TOC](文章目录)
  • 题目
  • 一、审题
  • 二、贪心策略:哈夫曼树
  • 总结

题目

给你一个数组arr,里面都是黄金的部分价值,整个arr是一条黄金
每次你切一刀,将金条一分为2,代价是两遍黄金总和
最后每一块都只能切到只剩一个部分
请你最最小的金条分割代价


一、审题

示例:arr= 10 20 30
有几种切法:
第一种:
第一刀切为10/ 20 30代价是10+20+30=60
第二刀切为10/20/30代价是20+30=50
总代价为110

第二种:
第一刀切为:10 20 / 30代价为30+30=60
第二刀切为:10/20 / 30代价为10+20=30
故总得代价为90

显然90更小


二、贪心策略:哈夫曼树

其实我们希望左右每次都是尽量相等而且尽量小
否则,你留一遍太大,切下去代价很费力

那就用哈夫曼树解决:
比如:
arr= 3,9,6,4,1
怎么切呢?要总代价最小,最后一刀尽量让小的两部分
也就是最后一刀应该切1 3,这样他们总的和最小为4
把4放入arr,继续选择最小的两部分作为最后一刀……
在这里插入图片描述

用小根堆来模拟:
sum=0,结果
(1)将arr全部放入小根堆,让小根堆堆顶2个连续弹出,求和为cur,sum+=cur。
(2)将cur再次放入小根堆,回到(1),不断玩
(3)找到小根堆仅剩下最后的结果cur了,它也就是sum,返回结果
这样相当于每次都把数组中最小的俩数,拿出来做和,这样代价最小
这就是哈夫曼树!!【大厂的笔试中亲眼见过的哦】

手撕代码:

//复习:哈夫曼树,小根堆实现public static int minCostReview(int[] arr){int N = arr.length;PriorityQueue<Integer> heap = new PriorityQueue<>();for (int i = 0; i < N; i++) {heap.add(arr[i]);}//然后模拟哈夫曼树int sum = 0;//结果while (heap.size() != 1){//当最后一次结果加入后,就停止int cur = heap.poll() +heap.poll();//2个连续弹出最小值heap.add(cur);//再次加入heapsum += cur;}return sum;}public static void test(){int[] arr = {10,20,30};//int cost = lessMoeny(arr);System.out.println(cost);cost = minCostReview(arr);System.out.println(cost);}public static void main(String[] args) {test();}

结果:

90
90

总结

提示:重要经验:

1)贪心策略就是多见题,多思考,多总结,培养敏感度!
2)本题的关键在于切一刀要代价最小,那么我们考虑切刀两遍的量尽量平衡,而且越小越好,用哈夫曼树解决,用小根堆模拟。
3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。

这篇关于贪心策略:请你最最小的金条分割代价的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/388081

相关文章

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Deepseek使用指南与提问优化策略方式

《Deepseek使用指南与提问优化策略方式》本文介绍了DeepSeek语义搜索引擎的核心功能、集成方法及优化提问策略,通过自然语言处理和机器学习提供精准搜索结果,适用于智能客服、知识库检索等领域... 目录序言1. DeepSeek 概述2. DeepSeek 的集成与使用2.1 DeepSeek API

Redis的数据过期策略和数据淘汰策略

《Redis的数据过期策略和数据淘汰策略》本文主要介绍了Redis的数据过期策略和数据淘汰策略,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录一、数据过期策略1、惰性删除2、定期删除二、数据淘汰策略1、数据淘汰策略概念2、8种数据淘汰策略

SpringBoot中的404错误:原因、影响及解决策略

《SpringBoot中的404错误:原因、影响及解决策略》本文详细介绍了SpringBoot中404错误的出现原因、影响以及处理策略,404错误常见于URL路径错误、控制器配置问题、静态资源配置错误... 目录Spring Boot中的404错误:原因、影响及处理策略404错误的出现原因1. URL路径错

使用Python实现批量分割PDF文件

《使用Python实现批量分割PDF文件》这篇文章主要为大家详细介绍了如何使用Python进行批量分割PDF文件功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、架构设计二、代码实现三、批量分割PDF文件四、总结本文将介绍如何使用python进js行批量分割PDF文件的方法

Redis多种内存淘汰策略及配置技巧分享

《Redis多种内存淘汰策略及配置技巧分享》本文介绍了Redis内存满时的淘汰机制,包括内存淘汰机制的概念,Redis提供的8种淘汰策略(如noeviction、volatile-lru等)及其适用场... 目录前言一、什么是 Redis 的内存淘汰机制?二、Redis 内存淘汰策略1. pythonnoe

使用Python将长图片分割为若干张小图片

《使用Python将长图片分割为若干张小图片》这篇文章主要为大家详细介绍了如何使用Python将长图片分割为若干张小图片,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. python需求的任务2. Python代码的实现3. 代码修改的位置4. 运行结果1. Python需求

Python 中 requests 与 aiohttp 在实际项目中的选择策略详解

《Python中requests与aiohttp在实际项目中的选择策略详解》本文主要介绍了Python爬虫开发中常用的两个库requests和aiohttp的使用方法及其区别,通过实际项目案... 目录一、requests 库二、aiohttp 库三、requests 和 aiohttp 的比较四、requ