【算法 - 动态规划】京东面试题 - 洗咖啡杯问题

2024-02-24 10:52

本文主要是介绍【算法 - 动态规划】京东面试题 - 洗咖啡杯问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

通过前面多篇文章的学习,相信小伙伴们对动态规划的 分类 以及做题 套路 已经有了清晰的认识。包括从左到右模型、范围尝试模型、样本对应模型。

本文我们继续学习一种新的模型 —— 业务限制模型

咖啡杯变干净

给定数组 arr 和整数 N。 arr[i]的长度代表有几个咖啡机,arr[i] 代表第 i 号咖啡机泡一杯咖啡所需要的时间,N 表示有多少个人正在等待着泡咖啡,每台咖啡机只能轮流泡咖啡。喝完咖啡的杯子有两种方式变干净:用 咖啡机洗 或者 自己挥发 干净。

洗咖啡杯机器只有一台,每次 耗时 a 洗干净 一个咖啡杯,洗完才能洗下一个杯子(串行);每个咖啡杯也可以 耗时 b 自己挥发干净 ,咖啡杯可以并行挥发。

假设所有人拿到咖啡后立刻喝完,求出从开始等待到所有咖啡杯都变干净的最短时间

思路分析

本道题先逆向思考一下,因为洗咖啡杯的时间和咖啡杯自己挥发干净所需要的时间都是固定的,因此,要想求出所有咖啡杯变干净的最短时间。就需要让咖啡杯尽可能的早点空出来等待清洗,也就是,让更多的人尽快喝到咖啡。

因此,就可以将本题划分为两道题目。

  • 问题 1: 如何安排每个人在哪个咖啡机前等咖啡(影响到了什么时候能喝到咖啡并等待清洗)。
  • 问题 2: 当杯子等待清洗时如何选择清理方式:机洗 还是 挥发

我们一个一个的破解。

问题 1 思路

影响每个人什么时候喝到咖啡的因素有两个:咖啡机空闲的时间点做一杯咖啡需要的时间(arr[i])

想象一下,如果你来到咖啡机前喝咖啡想要早点结束,你会去哪个咖啡机呢?很简单,当然是去以上 两个因素相加最小的咖啡机前

因此,对于如何安排人到哪台咖啡机前等待,可以使用小根堆进行计算。

代码

public static class Machine {public int timePoint;public int workTime;public Machine(int t, int w) {timePoint = t;workTime = w;}
}public static class MachineComparator implements Comparator<Machine> {@Override// 小根堆// 两者总和小的排在前面public int compare(Machine o1, Machine o2) {return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);}
}public static int[] minTime(int[] arr, int n, int a, int b) {PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());for (int i = 0; i < arr.length; i++) {heap.add(new Machine(0, arr[i]));}int[] drinks = new int[n];// 计算出每个顾客的最佳喝咖啡时间// 即每个咖啡杯最早空出等待清洗的时间for (int i = 0; i < n; i++) {Machine cur = heap.poll();cur.timePoint += cur.workTime;drinks[i] = cur.timePoint;heap.add(cur);}return drinks;// 调用问题 2 的暴力递归// return bestTime(drinks, a, b, 0, 0);// 调用问题 2 的动态规划// return bestTimeDp(drinks, a, b);
}

代码解释

当每个顾客来到后,弹出小根堆的堆顶,此时就是最佳的喝咖啡方案,即最早喝完咖啡。做完咖啡后,该咖啡机的工作时间更新为当前时间,即 cur.timePoint += cur.workTime ,也就是该顾客喝完咖啡释放杯子的时间,记录在 drinks[i] 数组中。然后将更新后的咖啡机加入小根堆中,继续为后面的顾客服务,直到所有的 N 个人结束。返回 drinks 数组,表示需要清洗的杯子的到来时间。

问题 2 思路

对于问题 2 ,这就是最熟悉的 从左往右的选择模型 ,对于每个咖啡杯来说,有两种可能的选择,要么选择使用咖啡清洗机清洗要么选择挥发干净。我们按照套路先写出递归版本:

递归的准备

注意是 从左到右 的模型哦!

定义递归函数的功能: 返回 drinks 中 [index...] 范围上咖啡杯都变干净的最早结束时间。

思考递归需要的参数: drinks 数组,清洗杯子的时间 a,挥发干净的时间 b,此时来到的下标 index 以及清洗机器什么时候是空闲的可以使用 free。

明确递归的边界条件:index == drinks.length 时说明已经没有杯子要洗了,根据函数功能可知,返回 0 。

思路

从左到右的尝试模型 ,因此,递归就可以按照 当前位置如何选择 的思路来划分情况:

  • 第 index 号杯子选择 使用机器清洗;
  • 第 index 号杯子选择 挥发干净。

因为要求 最短 时间,因此要返回这两种情况当中的最小值。

代码

// free : 清洗咖啡的机器空闲的时间
public static int bestTime(int[] drinks, int a, int b, int index, int free) {if (index == drinks.length) {return 0;}// index 号杯子 选择清洗int selfCleanA = Math.max(drinks[index], free) + a;int restCleanA = bestTime(drinks, a, b, index + 1, selfCleanA);int p1 = Math.max(selfCleanA, restCleanA);// index 号杯子 选择挥发int selfCleanB = drinks[index] + b;int restCleanB = bestTime(drinks, a, b, index + 1, free);int p2 = Math.max(selfCleanB, restCleanB);return Math.min(p1, p2);
}

代码解释

1. 选择机器清洗
  • 当一个杯子选择机器清洗时,drinks[index] 表示自己什么时间可以洗,但此时机器可能还没有空闲。因此,需要选择二者的最大值,也就是既能可以开始洗机器也空闲的时间。洗杯子需要 a 的时间,因此杯子变得干净的时间就等于 Math.max(drinks[index], free) + a
  • 因为要返回的是 index 之后所有的杯子均变干净时间,所以还要考虑剩下的杯子变干净时间。
  • bestTime(drinks, a, b, index + 1, selfCleanA); 继续从下一个杯子开始调用递归函数,此时洗杯子机器空闲的时间正是上一个杯子变干净的时间 selfCleanA
  • 返回当前杯子变干净时间和以后所有杯子变干净时间的最大值,才是所有杯子变干净的最早时间。
2. 选择挥发干净
  • 当一个杯子选择挥发干净(并行)时,不会受到其他因素的影响。因此变干净的时间为 drinks[index] + b
  • 剩下的杯子继续递归调用,此时清洗的机器可用时间不变仍是 free
  • 返回当前杯子变干净时间和以后所有杯子变干净时间的最大值,才是所有杯子变干净的最早时间。

最终返回两种情况中最小的时间,即所有杯子变干净的最早时间。


下面对代码进行优化,改出 动态规划 版本。

思路

首先确定可变参数的范围。

递归函数中,可变的参数有 indexfree 两个。index 的范围很好确定:

    if (index == drinks.length) {return 0;}

由于 index 的值从 0 可以到 drinks.length ,因此设置 dp 表的长度为 drinks.length + 1

麻烦的是 free ,题目中并不能直观的知道清洗机器空闲的最大时间。这就是今天所讲的新模型 —— 业务限制模型不明确的知道一个参数的变化范围,通过业务的限制找到

假设所有的杯子都用机器洗,则能够达到的时间就是 free 能够达到的最大时间,不可能再比这个时间长了!因此,可以先求出这个最大时间,从而设置 dp 数组的大小。

int N = drinks.length;
int maxFree = 0;
for (int i = 0; i < N; i++) {maxFree = Math.max(maxFree, drinks[i]) + a;
}

设置二维 dp 表的大小为 dp[N + 1][maxFree + 1]

代码

public static int bestTimeDp(int[] drinks, int a, int b) {int N = drinks.length;int maxFree = 0;for (int i = 0; i < N; i++) {maxFree = Math.max(maxFree, drinks[i]) + a;}int[][] dp = new int[N + 1][maxFree + 1];// dp[N][...] 都等于 0for (int index = N - 1; index >= 0; index--) {for (int free = 0; free <= maxFree; free++) {int selfCleanA = Math.max(drinks[index], free) + a;// 若超过了最大边界,之后不可能访问到此下标if (selfCleanA > maxFree) {break;}// index 号杯子 选择清洗int restCleanA = dp[index + 1][selfCleanA];int p1 = Math.max(selfCleanA, restCleanA);// index 号杯子 选择挥发int selfCleanB = drinks[index] + b;int restCleanB = dp[index + 1][free];int p2 = Math.max(selfCleanB, restCleanB);dp[index][free] = Math.min(p1, p2);}}return dp[0][0];
}

理解了参数范围的求解方法,修改出动态规划版本的代码就很容易了。

if (index == drinks.length) {return 0;
}

由递归的 base case 可知,dp[N][...] 均为 0 (数组中的值默认为 0 ,无需单独设置了)。index 下标均依赖 index + 1 的值,因此需要倒着遍历数组。

需要注意的是可能越界的情况,这些地方在 dp 表中一定不会被访问到,因此直接跳过。由递归调用含义可知,最终返回 dp[0][0] 即为答案。

总结

本文通过一道面试题目了解了什么是 业务限制模型 。至此,关于如何对递归进行分析的四种基本模型都介绍完了。根据不同模型的套路相信小伙伴也能够轻松应对类似的题目了!再来总结一下:

  1. 从左到右模型arr[index ...]index 之前的不用考虑,只考虑后面的该如何选择
  2. 范围尝试模型 :思考 [L ,R] 两端,即 开头和结尾 处分别该如何取舍。
  3. 样本对应模型 :以 结尾位置 为出发点,思考两个样本的结尾都会产生哪些可能性 。
  4. 业务限制模型 :不能够明确的知道一个参数的变化范围,通过业务的限制找到 最差情况 进行估计。

以上四种模型均能够在往期文章中找到对应的题目哦!

~ 点赞 ~ 关注 ~ 不迷路 ~!!!

------------- 往期回顾 -------------
【算法 - 动态规划】从零开始学动态规划!(总纲)
【算法 - 动态规划】原来写出动态规划如此简单!
【算法 - 动态规划】最长公共子序列问题
【算法 - 动态规划】最长回文子序列
【算法 - 动态规划】力扣 691. 贴纸拼词
【堆 - 专题】“加强堆” 解决 TopK 问题!
AC 此题,链表无敌!!!

这篇关于【算法 - 动态规划】京东面试题 - 洗咖啡杯问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给