leetcode/algorithms/ruby/1345-jump-game-iv.rb at main · remy727/leetcode · GitHub

Name: leetcode/algorithms/ruby/1345-jump-game-iv.rb at main · remy727/leetcode · GitHub
Rating: 4.6 (4169 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
# frozen_string_literal: true

# 1345. Jump Game IV
# https://leetcode.com/problems/jump-game-iv

# @param {Integer[]} arr
# @return {Integer}
defmin_jumps(arr)
return0if(t=arr.size - 1) < 1
g=arr.each_index.group_by{arr[_1]}
s,q,v=0,[0],[false] * t
v[0]=true
loopdo
(s += 1;q.size).timesdo
i=q.shift
c=(g[arr[i]] || []) << i + 1
g.deletearr[i]
c << i - 1ifi > 0
c.eachdo | x |
returnsifx == t
nextifv[x]
v[x]=true
q << x
end
end
end
end

defmin_jumps1(arr)
@d=false
last_index=arr.size - 1
return0ifarr.size <= 1
graph={}
arr.each_with_indexdo |value,index|
graph[value] ||= []
graph[value].push(index)
end
layer=[0]
used={}
used[0]=true
step=0
while ! layer.empty?
nxt=[]
layer.eachdo |i|
returnstepiflast_index == i
[i + 1,i - 1].eachdo |j|
ifj.between?(0,last_index) && (!used[j])
used[j]=true
nxt.push(j)
end
end
graph[arr[i]].eachdo |j|
if ! used[j]
used[j]=true
nxt.push(j)
end
end
# Most important line!
graph[arr[i]].clear()
end
step += 1
layer=nxt
end
end

# @param {Integer[]} arr
# @return {Integer}
defmin_jumps2(arr)
arr_count=arr.count

graph=Hash.new{ |h,k| h[k]=[]}
arr_count.timesdo |i|
graph[arr[i]] << i
end

src=0
dest=arr_count - 1

visited=Set.new
visited << src

queue=[]
queue << [src,0]

untilqueue.empty?
node,dist=queue.shift
returndistifnode == dest

([node - 1,node + 1] + graph[arr[node]].reverse).eachdo |child|
if0 <= child &&
child < arr_count &&
child != node &&
 !visited.include?(child)

visited << child
returndist + 1ifchild == dest
queue << [child,dist + 1]
end
end
end

 -1
end

# **************** #
# TEST #
# **************** #

require"test/unit"
classTest_min_jumps < Test::Unit::TestCase
deftest_
assert_equal3,min_jumps([100, -23, -23,404,100,23,23,23,3,404])
assert_equal0,min_jumps([7])
assert_equal1,min_jumps([7,6,9,6,9,6,9,7])

assert_equal3,min_jumps1([100, -23, -23,404,100,23,23,23,3,404])
assert_equal0,min_jumps1([7])
assert_equal1,min_jumps1([7,6,9,6,9,6,9,7])

assert_equal3,min_jumps2([100, -23, -23,404,100,23,23,23,3,404])
assert_equal0,min_jumps2([7])
assert_equal1,min_jumps2([7,6,9,6,9,6,9,7])
end
end

# ********************#
# Benchmark #
# ********************#

require"benchmark"

arr=[100, -23, -23,404,100,23,23,23,3,404]
Benchmark.bmdo |x|
x.report("min_jumps: "){min_jumps(arr)}
x.report("min_jumps1: "){min_jumps1(arr)}
x.report("min_jumps2: "){min_jumps2(arr)}
end

# user system total real
# min_jumps: 0.000029 0.000005 0.000034 ( 0.000029)
# min_jumps1: 0.000040 0.000008 0.000048 ( 0.000048)
# min_jumps2: 0.001512 0.000000 0.001512 ( 0.001514)