Fork me on GitHub

滴滴笔试题

字数统计: 562字   |   阅读时长≈ 1分

总揽

两题都是10行代码不到就写了

第一题

题意

你有一个操作系统，他将要执行n个任务，每个任务有两个阶段，准备阶段和执行阶段，任务必须先完成准备，然后才能执行。

你的操作系统在任意时刻可以执行一个任务，并同时准备多个任务

问你最少花费多少时间可以执行完所有的任务

输入

n表示n个任务

n行，第一个数字为准备时间，第二个数字为执行时间

输入

1
2
3
2
1 5
4 1

输出

1
7

备注

先准备一个时间，然后用5个时间执行第一个任务，然后花一个时间执行第二个任务

题解

按照准备时间从小到大排序，然后依次模拟即可

第二题

描述

给你长度为n个数组（都是正数），你可以花费1的代价来改变一个数的值（改成正数），然后给你一个x，现在你需要用最小的代价把这个数组变长公差为x的等差数列，输出最小的代价。

输入

1
2
5 3
1 3 1 3 5

输出

1
3

备注

改成1 3 5 7 9

问题转化

把数组的下标当作横坐标，把数组的值当作纵坐标，你可以得到二维平面内的n个点。

等差数列的点都在一条直线上，斜率就是公差，首项就是y轴截距

现在问题转化为，给你二维平面内的n个点，找到一条斜率为x点直线经过尽可能多的点，且y轴截距大于0，输出没有经过的点点个数。

问题解决

由于截距为x，我们枚举每个点所在的直线，计算出y=kx+b, 我们对直线进行hash, 由于斜率相同，我们只需要对截距hash，不妨设直线的hash值就是截距的大小

我们对hash值记数，出现次数最多的且hash值大于0的那个条直线，就是我们的答案找到的直线，不妨设这个直线的hash值出现了m次，最终答案就是n-m.

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java后端开发、聚合支付、
公众号开发、开源爱好者、Linux

联系QQ:2434387555

很惭愧

只做了一点微小的工作
谢谢大家