问题陈述
一所大学只有一个旋转门。它既可以用作出口也可以用作入口。不幸的是，有时很多人想通过旋转栅门，他们的方向可能会有所不同。第i个人在时间[i]到达旋转栅门，并且想要在Direction [i] = 1时退出大学，或者在direciton [i] = 0时进入大学。人们形成2个队列，一个队列退出，一个进入。它们按到达转闸的时间排序，如果时间相等，则按其索引排序。如果某人想同时进入大学而另一人想同时离开大学，则有以下三种情况：
• If in the previous second the turnstile was not used (maybe it was used before, but not at the previous second), then the person who wants to leave goes first.
• If in the previous second the turnstile was used as an exit, then the person who
wants to leave goes first
• If in the previous second the turnstile was used as an entrance, then the person
who wants to enter goes first
经过旋转闸需要1秒
对于每个人，找到他们通过旋转闸门的时间
该函数必须返回由n个整数组成的数组，当第i个人通过旋转闸门时，index [i]处的值相同
该函数具有以下参数：
• time: an array of n integers where the value at index i is the time when the
ith person will came to the turnstile
• direction: an array of n integers where the value at index i is the direction
of the ith person
约束条件
• 1 <= n <= 105
• 0 <= time[i] <= 109 for 0 <= i <= n – 1
• time[i] <= time[i+1] for 0 <= i <= n - 2
• 0 <= direction [i] <= 1 for 0 <= i <= n – 1
例：
n = 4
时间= [0,0,1,5]
方向= [0,1,1,0]
输出= [2,0,1,5]
例子2
n = 5
时间= [0,1,1,3,3]
方向= [0,1,0,0,1]
输出= [0,2,1,4,3]
这是我的实际尝试
def getTimes(time, direction)
persons = time.size - 1
exits = []
(0..persons).each do |person|
if time[person] == time[person + 1]
exits[person + 1] = time[person] if direction[person + 1] == 1 and direction[person] == 0
else
exits[person] = time[person] if direction[person] != direction[person + 1]
end
end
p exits
end
我的回应[nil，0，1，5]
stackoverflow通常不是代码编写服务。但是，事实证明这是一个有趣的问题。
因此，我为您编写了一些代码。这里是：
def calculate_turnstile_times(time, direction)
current_time = 0
dir = direction.map { |d| d.zero? ? :enter : :exit }
enter_queue, exit_queue = time.each_index.map do |i|
{person: i, time: time[i], direction: dir[i]}
end.partition do |h|
h[:direction] == :enter
end.map do |arr|
arr.sort_by { |h| h[:time] }
end
enterer = enter_queue.shift
exiter = exit_queue.shift
time.each_with_object([]) do |_t, to_return|
person_to_go = nil
enterer ||= enter_queue.shift
exiter ||= exit_queue.shift
current_time = [[enterer,exiter].map{|p|p.try(:[],:time)}.compact.min,current_time].max
enterer_arrived = enterer && enterer[:time] <= current_time
exiter_arrived = exiter && exiter[:time] <= current_time
person_to_go = :enterer if enterer_arrived && !exiter_arrived
person_to_go ||= :exiter if exiter_arrived && !enterer_arrived
person_to_go ||= :exiter if exiter_arrived && to_return.empty?
person_to_go ||= :exiter if exiter_arrived && ((to_return.last.try(:[],:time)||-2) != (current_time-1))
person_to_go ||= :enterer if enterer_arrived && to_return.last.try(:[],:direction) == :enter
person_to_go ||= :exiter if exiter_arrived
case person_to_go
when :exiter
person_to_go = exiter
exiter = nil
when :enterer
person_to_go = enterer
enterer = nil
end
person_to_go[:time] = current_time
to_return << person_to_go
current_time += 1
end.sort_by{|p| p[:person]}.map{|p| p[:time]}
end
如果您想尝试一下，这是一个RSpec测试：
require 'rails_helper'
RSpec.describe "Turnstiles" do
it "using calculate_turnstile_times" do
%i(calculate_turnstile_times).each do |method_sym|
test_cases.each do |test_case|
expect(send(method_sym,test_case[0],test_case[1])).to eq(test_case[2])
end
end
end
end
def test_cases
[
[[10],[1],[10]],
[[0,0,0],[0,0,1],[1,2,0]],
[[0,0,1,5],[0,1,1,0],[2,0,1,5]],
[[0,0],[0,1],[1,0]],
[[0,0],[1,1],[0,1]],
[[0,0],[1,0],[0,1]],
[[4,4],[0,1],[5,4]],
[[0,0,0],[0,1,1],[2,0,1]],
[[0,0,0],[0,0,0],[0,1,2]],
[[0,0,0,0],[0,1,1,1],[3,0,1,2]],
[[0,0,0,5],[0,1,1,1],[2,0,1,5]],
[[0,1,1,3,3],[0,1,0,0,1],[0,2,1,4,3]],
[[0,1,1,3,3],[0,1,1,0,1],[0,1,2,4,3]],
[[0,1,1,6,7],[0,1,1,0,1],[0,1,2,6,7]],
[[0,1,1,3,6],[0,1,1,0,1],[0,1,2,3,6]],
[[0,0,1,5],[0,1,1,0],[2,0,1,5]],
[[0,1,1,3,3],[0,1,0,0,1],[0,2,1,4,3]]
]
end
def calculate_turnstile_times(time, direction)
current_time = 0
dir = direction.map { |d| d.zero? ? :enter : :exit }
enter_queue, exit_queue = time.each_index.map do |i|
{person: i, time: time[i], direction: dir[i]}
end.partition do |h|
h[:direction] == :enter
end.map do |arr|
arr.sort_by { |h| h[:time] }
end
enterer = enter_queue.shift
exiter = exit_queue.shift
time.each_with_object([]) do |_t, to_return|
person_to_go = nil
enterer ||= enter_queue.shift
exiter ||= exit_queue.shift
current_time = [[enterer,exiter].map{|p|p.try(:[],:time)}.compact.min,current_time].max
enterer_arrived = enterer && enterer[:time] <= current_time
exiter_arrived = exiter && exiter[:time] <= current_time
person_to_go = :enterer if enterer_arrived && !exiter_arrived
person_to_go ||= :exiter if exiter_arrived && !enterer_arrived
person_to_go ||= :exiter if exiter_arrived && to_return.empty?
person_to_go ||= :exiter if exiter_arrived && ((to_return.last.try(:[],:time)||-2) != (current_time-1))
person_to_go ||= :enterer if enterer_arrived && to_return.last.try(:[],:direction) == :enter
person_to_go ||= :exiter if exiter_arrived
case person_to_go
when :exiter
person_to_go = exiter
exiter = nil
when :enterer
person_to_go = enterer
enterer = nil
end
person_to_go[:time] = current_time
to_return << person_to_go
current_time += 1
end.sort_by{|p| p[:person]}.map{|p| p[:time]}
end
这给了我：
11:44:24 - INFO - Running: spec/so/turnstiles_spec.rb
Turnstiles
using calculate_turnstile_times
Finished in 0.14996 seconds (files took 1.06 seconds to load)
1 example, 0 failures
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句