滴滴笔试题

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

总揽

两题都是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.

感谢您的阅读。 🙏 关于转载请看这里