Hackerrank购买演出门票优化
几天前我在一家公司的在线筛选测试中遇到了这个问题.问题陈述如下:
有n个人排队购买演出门票.由于需求量大,场地按照以下规则出售门票:
- 该行的负责人可以购买一张票,然后必须退出该行.
- 如果一个人需要购买额外的票,他们必须重新进入该行的末尾并等待出售他们的下一张票(假设退出并重新进入需要零秒).
- 每张门票仅需一秒钟.
我们将n个人的初始行表示为数组,ticket = [tickets0,tickets1 ... ticketsN-1],其中ticketi表示我想要购买的票的人数.如果杰西站在这条线的位置p,找出他需要花多少时间购买所有门票.在下面的编辑器中完成等待时间功能.它有两个参数:
- n个正整数的数组,票据,描述了排队的人的初始顺序.每个故障单描述了一个人在初始位置等待的票数.
整数p,表示Jesse在门票中的位置.
样品输入5 2 6 3 4 5 2样品输出12样品输入4 5 5 2 3 3样品输出11
在测试期间,我想出了这个简单的方法,它通过了大多数测试用例,但是在一些测试用例上超时了:
long waitingTime(vector<int> tickets, int p) {
// bool flag indicates whether it's Jesse or not
queue<pair<int, bool> > aQueue;
for(int i = 0; i < tickets.size(); i++) {
aQueue.push(make_pair(tickets[i], i == p));
}
long long nTime = 1;
while(!aQueue.empty()) {
pair<int, bool> aItem = aQueue.front();
aQueue.pop();
nTime++;
if(aItem.first == 1 && aItem.second == true)
break;
else if(aItem.first > 1) {
aQueue.push(make_pair(aItem.first-1, aItem.second));
}
}
return nTime-1;
}
但是我无法找到解决这个问题的不同方法.我认为还有其他方法,无需模拟整个队列流.如果有人能为我提供正确的解决方法,我将非常感激.提前致谢!
Abh*_*rni 11
HackerRank上的所有测试用例都通过了.最简单的解决方案是 -
def waitingTime(tickets, p):
total_steps = tickets[p]
first_half = tickets[:p]
second_half = tickets[p+1:]
for num in first_half:
if num < tickets[p]:
total_steps += num
else:
total_steps += tickets[p]
for num in second_half:
if num < tickets[p]:
total_steps += num
else:
total_steps += tickets[p] - 1
return total_steps
说明 -
- 将列表分成两半.人们站在杰西和站在杰西身后的人之前.
- 检查两个人中的每个人 - 该人想要购买多少张票.
- 让我们考虑上半年
- 如果这个人想买的票数少于杰西的票数 - 那么这个人就会在售票窗前看到他在杰西之前买票.因此,将他的票数添加到总单位时间
- 如果该人想要购买比Jesse更多或相同的门票,那么他将在Jesse之前访问售票窗口,这与Jesse访问售票窗口的次数完全相同.因此,将Jesse的门票数量添加到总单位时间 - 这相当于他在Jesse之前购买的门票数量
- 现在考虑下半场 -
- 如果站在Jesse后面的人想要购买比Jesse更多或更多的门票,他将比Jesse更少的时间访问售票窗口.所以将(Jesse的票数 - 1)添加到总单位时间
- 如果站在Jesse身后的人想要购买比Jesse更少的门票,那么该人将访问售票窗口,直到他买完所有门票.因此,将总票数计入总单位时间.
- 最后,将Jesse的票数添加到总单位时间,因为Jesse也会访问售票窗口,直到他购买了他想要的所有票
例如,有五个人站在队列中.他们的票数在下面的列表中给出.Jesse站在第3位(列表索引= 2)
[2,6,3,4,5]
上半场= [2,6]下半场= [4,5]
现在考虑上半年 -
#1号人想买2张票.Jesse的数量(3)大于2.所以这个人肯定会在Jesse之前两次访问售票窗口.因此total_unit_time = 2
#2号人想买6张票.Jesse的数量(3)小于6.所以这个人将在Jesse之前3次访问售票窗口.所以total_unit_time = 2+ 3
现在考虑下半场 - 1.人#1想买4张票.Jesse的数量(3)小于4.现在,Jesse将购买他的第一张票,然后该人将有机会购买他的第一张票.但是杰西将不得不等待2个回合才能购买剩余的2张门票.所以total_unit_time = 2 + 3 + (3-1)
- #2号人想买5张票.Jesse将再次购买他的第一张票,并等待他剩下的两个回合,直到这个人买了两张票.所以total_unit_time = 2 + 3 + 2 + (3-1)
Sch*_*eff 10
两次看问题,我认为分析解决方案应该是可行的.
我的想法是:
- 人们我杰西前将留在他的面前分钟{门票我,门票杰西 }倍.
- 杰西本人将使用杰西时代的门票.
- 人们我杰西后会留在杰西面前分钟{门票我,门票杰西 - 1}次.
因此,应该可以简单地在一个循环中总结数字.这将意味着O(n)而不是O(n 2).
我意识到,结果也取决于杰西的位置.但是,我的结果看起来与样本输出有所不同.因此,我也实施了一个天真的解决方案(类似于OP).来源waiting-queue.cc:
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
// naive approach
int waitingTimeSim(const std::vector<int> &tickets, int p)
{
// setup sim. model
std::queue<std::pair<int, bool> > people;
for (int i = 0, n = (int)tickets.size(); i < n; ++i) {
people.push(std::make_pair(tickets[i], i == p));
}
// simulation
int tP = 0;
for (;;) {
std::pair<int, bool> person = people.front();
people.pop();
--person.first; ++tP; // buy ticket
if (!person.first) { // if person is done
if (person.second) return tP; // It's Jesse -> terminate
} else people.push(person);
}
}
// analytical approach
int waitingTime(const std::vector<int> &tickets, int p)
{
int tP = 0, ticketsP = tickets[p];
for (int i = 0, n = (int)tickets.size(); i < n; ++i) {
tP += std::min(tickets[i], ticketsP - (i > p));
// i > p -> people after jesse -> decr. by 1
}
return tP;
}
int main()
{
{ std::vector<int> tickets{ 2, 6, 3, 4, 5 };
for (int p = 0, n = tickets.size(); p < n; ++p) {
std::cout << "tickets{ 2, 6, 3, 4, 5 }, p = " << p << std::endl;
int tS = waitingTimeSim(tickets, p);
std::cout << "simulated t: " << tS << std::endl;
int t = waitingTime(tickets, p);
std::cout << "computed t: " << t << std::endl;
}
}
{ std::vector<int> tickets{ 5, 5, 2, 3 };
for (int p = 0, n = tickets.size(); p < n; ++p) {
std::cout << "tickets{ 5, 5, 2, 3 }, p = " << p << std::endl;
int tS = waitingTimeSim(tickets, p);
std::cout << "simulated t: " << tS << std::endl;
int t = waitingTime(tickets, p);
std::cout << "computed t: " << t << std::endl;
}
}
return 0;
}
我将源代码上传到ideone.com.
我的测试会话(g ++,cygwin,Windows 10):
$ g++ -std=c++11 -o waiting-queue waiting-queue.cc
$ ./waiting-queue.exe
tickets{ 2, 6, 3, 4, 5 }, p = 0
simulated t: 6
computed t: 6
tickets{ 2, 6, 3, 4, 5 }, p = 1
simulated t: 20
computed t: 20
tickets{ 2, 6, 3, 4, 5 }, p = 2
simulated t: 12
computed t: 12
tickets{ 2, 6, 3, 4, 5 }, p = 3
simulated t: 16
computed t: 16
tickets{ 2, 6, 3, 4, 5 }, p = 4
simulated t: 19
computed t: 19
tickets{ 5, 5, 2, 3 }, p = 0
simulated t: 14
computed t: 14
tickets{ 5, 5, 2, 3 }, p = 1
simulated t: 15
computed t: 15
tickets{ 5, 5, 2, 3 }, p = 2
simulated t: 7
computed t: 7
tickets{ 5, 5, 2, 3 }, p = 3
simulated t: 11
computed t: 11
$
注意:
恕我直言,这个名字waitingTime()有点误导,因为作业明确表示你必须这样做
了解他购买所有门票需要多长时间.
因此,我的实施计算了等待时间+杰西需要购买他的最后一张票的时间.
更新:
一个经常使用的德语短语说:谁能读懂显然是有利的.(听起来不像德语那么好用,也很方便:"Wer lesen kann,ist klar im Vorteil.")然而,在再次阅读Rohan Kumar对我的评论问题的评论答案后,我调整了我的样本输入OP,突然得到预期的输出.但是,算法没有改变.
这是我解决这个问题的想法,先来看看这一行.我们将人分为两组:
1 /那些站在第p个人之前.
2 /那些站在pth perosn 后面.
让我们把时间 -这一举动的数量PTH人必须采取买sufficent门票.
现在,考虑到第一组[ tickets0,tickets1,...,ticketsP-1 ],如果有一个人我谁需要买票比小的数目PTH的人,则只是简单地添加< 票我 >以倍(工期PTH人有等待的人我,直到他得到了该行的).否则,万一买的人的票量我比人更大的PTH,添加< 票p >以倍.
其次,对于那些站在第p个人身后的人也有同样的想法[ ticketsP + 1,ticketsP + 2,...,ticketsN ].考虑到人t(t> p),如果ticketT < ticketP,我们将< ticket t > 添加到时间.除非人们购买的票数少于人票p,否则跳过最后一轮,只需将< 票数p - 1>添加到时间
在迭代这些线条的同时,不要忘记每次遇到人物p时都要将票证p添加到时间.
public static long times( int[] tickets, int p) {
long times = 0;
int[] temp = Arrays.copyOf(tickets, tickets.length); //creating this array to check whether the *person i* buy tickets less than *person p*
for(int i = 0; i < tickets.length; i++ ) {
temp[i] = tickets[i] - tickets[p];
}
for(int i = 0; i < tickets.length; i++ ) {
if(temp[i] < 0) times += tickets[i];
else {
if(i <= p) times += tickets[p];
else times += tickets[p] - 1;
}
}
return times;
}
说明:
样品输入 4 5 5 2 3 3 样品输出 14
p = 4,14 = 3 + 3 + 2 + 3 + 3
| 归档时间： |
|
| 查看次数： |
17421 次 |
| 最近记录： |