资讯专栏INFORMATION COLUMN

2019年京东面试题-洗咖啡杯问题【贪心和动态规划】

kamushin233 / 2737人阅读

摘要:京东年面试题冲咖啡和洗咖啡杯问题题目描述首先,给你几个数据数组表示几个咖啡机,这几个咖啡机生产一杯咖啡所需要的时间就是数组中的值,例如就表示第一台咖啡机生产一杯咖啡需要单位时间,第二台需要单位时间,第三台需要单位时间。

京东2019年面试题—冲咖啡和洗咖啡杯问题

题目描述

首先,给你几个数据:

  • 数组arr:表示几个咖啡机,这几个咖啡机生产一杯咖啡所需要的时间就是数组中的值,例如arr=[2,3,7]就表示第一台咖啡机生产一杯咖啡需要2单位时间,第二台需要3单位时间,第三台需要7单位时间。

  • int N:表示有N个人需要用咖啡机制作咖啡,每人一杯,同时,假设制作完咖啡后,喝咖啡时间为0,一口闷。

  • int a:表示用洗碗机洗一个咖啡杯需要的时间,串行运行。

  • int b:表示咖啡杯也可以不洗,自然晾干的时间。咖啡杯要么洗,要么晾干。

    现在,请你求出这N个人从开始用咖啡杯制作咖啡到杯子洗好或者晾干的最少时间?

分析:题目的意思就是,从第一个人开始冲咖啡计时,到最后一个人喝完咖啡,并把杯子全部洗干净,最少需要多少时间???

整体大致分为两个部分:

  • 需要计算出每个人冲好咖啡的时间点。
  • 根据每个人冲好咖啡的时间点,开始洗杯子。(因为咖啡是一口喝完的,冲好咖啡的时间点,也就是洗杯子的时间点)

冲咖啡和洗杯子,是两码事,分开讨论即可。

  1. 冲咖啡

    • 采用小根堆的形式,进行组织数据。 准备工作:我们先将所有的咖啡机(arr)以Node节点的形式,放入堆中。Node节点如下:
    public class Node {    public int requireTime; //冲一个咖啡花费的时间    public int  freeTime; //当前咖啡机,在什么时间才是空闲    public Node(int freeTime, int requireTime) {        this.requireTime = requireTime;        this.freeTime = freeTime;    }}

    如上,Node节点里只有两个参数,一个是当前咖啡机冲一杯咖啡所花费的时间,另一个就是在什么时间点,当前这台咖啡机才是空闲的状态。堆中组织数据的规则是:将这两个参数加起来,作为参数,来组织成小根堆。

    • 接下来,就是计算每个人冲好咖啡的时间点,流程如下:因为是小根堆组织的数据,当前堆顶的咖啡机就是最佳的选择。 弹出堆顶的咖啡机,将两个参数(requireTime、freeTime)相加,就是当前这台咖啡机冲好一杯咖啡的时间。并用一个数组,记录好当前数据即可。然后将这两个参数的和作为新Node节点freeTime,requireTime时间不变,再次将当前咖啡机放入小根堆。循环这一步骤,有多少个人,就循环几次即可。

      PriorityQueue<Node> minHeap = new PriorityQueue<>((o1, o2) -> o1.freeTime + o1.requireTime - o2.freeTime - o2.requireTime);//将所有咖啡机打包放入堆中for (int i = 0; i < arr.length; i++) {    //刚开始,每台咖啡机都是0点开始    minHeap.add(new Node(0, arr[i]));}int[] drinks = new int[N]; //N是总人数for (int i = 0; i < N; i++) {    Node node = minHeap.poll();    drinks[i] = node.freeTime + node.requireTime;    node.freeTime = drinks[i]; //更新空闲时间    minHeap.add(node); //再次压入堆中}
  2. 洗咖啡杯

    每个人冲好咖啡的时间点,就是需要洗杯子的时间点。则参数就是上面代码计算出来的drinks数组。

    对于每个杯子来说,只有两种选择,要么是机器洗,要么就是自然晾干,我们先用递归的方法来解,然后在递归的基础之上,再改进为动态规划。有如下代码:

    /**drinks是每个人洗杯子的时间点a 是机器洗一个杯子的时间b是自然晾干一个杯子的时间index指向drinks数组washLine表示洗杯子的机器什么时候才是空闲状态*/public static int process(int[] drinks, int a, int b, int index, int washLine) {    if (index == drinks.length - 1) {        //机器洗完这个杯子的时间        int wash = Math.max(drinks[index], washLine) + a;        int autoDry = drinks[index] + b; //自然晾干的时间        return Math.min(wash, autoDry);    }        //机器洗完当前杯子的时间    int wash = Math.max(drinks[index], washLine) + a;    //剩下的杯子去递归,计算出最优结果。传递是刚计算出来的wash    int next = process(drinks, a, b, index + 1, wash);     int p1 = Math.min(wash, next); //机器洗,最优的结果        //自然晾干的时间    int autoDry = drinks[index] + b;    //剩下的杯子去递归,计算出最优结果。传递的还是原washLine    next = process(drinks, a, b, index + 1, washLine);    int p2 = Math.min(autoDry, next); //自然晾干,最优的结果        //机器洗和自然晾干两种结果,取最优返回    return Math.min(p1, p2);}

    以上代码就是递归的解法,整体分为两部分,机器洗和自然晾干,然后分别调用子过程,取最优结果即可。

    看一个代码是否需要改动态规划,我们就得判断当前代码是否存在着大量的重复计算。假设第一个杯子机器洗,则第二个杯子可能是机器洗,也可能是自然晾干;假设第一个杯子是自然晾干,则第二个杯子也可能是机器洗,也可能是自然晾干。在第一个杯子这里,分为两个子过程,且这两个子过程的计算重复了,那么这个代码就是需要改动态规划的。

    本质上,动态规划就是在计算出结果后,存储在另外一个表中,下次还是求这个状态的话,就直接从表中拿数据即可

    根据递归的代码可以看出,整个递归过程,唯一在改变的形参只有两个(index和washLine)。所以我们可以建一张二维表,行就是index,列就是washLine。这样一张表,就能存储下所有的结果。

    index的值就是有多少个人,那么主要问题就在于washLine的值,应该怎么来确定??

    最坏的情况就是,所有的杯子都是用机器洗,那么washLine最大的取值范围就是机器洗完所有杯子的时间。动态规划代码如下:

    //动态规划版本public static int process(int[] drinks, int a, int b) {    int index = drinks.length;    int washLine = 0;    for (int i = 0; i < index; i++) {        int tmp = Math.max(washLine, drinks[i]) + a;        washLine += tmp;    }        int[][] dp = new int[index][washLine];    //根据递归的所有结束条件,来填dp表    //index = drinks,length -1。也就是最后一行    for (int i = 0; i < washLine; i++) {        //机器洗和自然洗,取最优的结果        dp[index -1][i] = Math.min(Math.max(drinks[i], i) + a,                                   drinks[i] + b);    }        //填好最后一行后,剩下的就是普通位置的填写    //i就是index,j就是当前洗杯子的机器的空闲时间    for (int i = N - 2; i >= 0; i--) {        for (int j = 0; j < washLine; j++) {            int wash = Math.max(drinks[i], j) + a;            int next = 0;            if (wash < washLine) {                next = dp[i + 1][wash]; //子过程            }            dp[i][j] = Math.max(wash, next);                        int autoDry = drinks[i] + b;            next = dp[i + 1][j]; //子过程            //机器洗和自然晾干,两种可能性取最优            dp[i][j] = Math.min(dp[i][j], Math.max(autoDry, next));        }    }    return dp[0][0]; //返回左上角的结果即可}

    源码:GitHub

    好啦,以上全部就是这一道题的解析,如若有错误,还望评论区指点!!!我们下期再见吧!!!

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/123463.html

相关文章

  • 大厂算法面试之leetcode精讲3.动态规划

    摘要:动态规划问题一定会具备最优子结构,才能通过子问题的最值得到原问题的最值。另外,虽然动态规划的核心思想就是穷举求最值,但是问题可以千变万化,穷举所有可行解其实并不是一件容易的事,只有列出正确的状态转移方程才能正确地穷举。 大厂算法面试之leetcode精讲3.动态规划视频教程(高效学习):点击学习目录:1.开篇介...

    番茄西红柿 评论0 收藏2637
  • SegmentFault 技术周刊 Vol.31 - 码农也要学算法

    摘要:记作称为算法的渐进时间复杂度,简称时间复杂度。学习数据结构与算法之链表链表一种常见的数据结构,可以存储有序的元素集合。首先在大的分类上,它们都是散列算法。 showImg(https://segmentfault.com/img/bVSDvj?w=900&h=385); 当人工智能、AlphaGo、无人驾驶、智能投顾等词语不断在人们视野中出现的时候,意味着我们正步入一个算法的时代。计算...

    cgspine 评论0 收藏0
  • 前端跳槽面试算法——动态规划

    摘要:我记得大三参加腾讯的校招面试时只准备了几种常见的排序算法就足以应对了,然而今年包括今日头条在内的多家大厂的前端笔试题目中都出现了贪心算法动态规划分治算法等进阶性的算法题目。本篇博客参考今日头条银国徽老师的《js版数据结构与算法》Part1改编自《漫画算法》原作者:程序员小灰前言众所周知,与后台开发人员相比,算法是我们前端开发人员的一个弱项。而近两年随着互联网行业竞争愈发激烈,市场上对前端岗位...

    mushang 评论0 收藏0
  • 2019一线互联网公司最全面试心得汇总

    摘要:做一个靠谱且有责任心的人很多公司在内部的面试细则上面都会注明这一点,如果价值观或是人品问题会直接否决。没有一个面试官不想找一个技术出众又有责任心的人,请相信我,责任心非常重要,更有利于今后的晋升。 关注微信公众号:进击的java程序员K 每日精选BAT技术文章,面试真题,源码资料。 今天分享的BAT等一线互联网公司面试经验: 面试前的心态准备(3点建议)技术硬实力包含的范围(50题目...

    lscho 评论0 收藏0
  • 2019一线互联网公司最全面试心得汇总

    摘要:做一个靠谱且有责任心的人很多公司在内部的面试细则上面都会注明这一点,如果价值观或是人品问题会直接否决。没有一个面试官不想找一个技术出众又有责任心的人,请相信我,责任心非常重要,更有利于今后的晋升。 关注微信公众号:进击的java程序员K 每日精选BAT技术文章,面试真题,源码资料。 今天分享的BAT等一线互联网公司面试经验: 面试前的心态准备(3点建议)技术硬实力包含的范围(50题目...

    snowLu 评论0 收藏0

发表评论

0条评论

kamushin233

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<