CodilityのLessonをやってみる（5-8）
前回の続き。
今回はLesson 5〜8までのeasyをやって行きます。
リポジトリ
Lesson 5 Prefix Sums
最初に合計？
PassingCars
問題
N個の整数で満たされた配列Aがある。配列Aの連続した要素は道路上に連なる車を表している。
配列Aには0か1のみ含まれる。
それぞれが表すのは以下の通り
- 0は東に向かう車
- 1は西に向かう車
求めるのは擦れ違った車の数。0<=P<Q<Nの時、車のペア(P, Q)は、車Pが東に向かう時に西に向かう車Qと擦れ違ったことを表す。
例
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
この時すれ違いは次の5つである。
(0, 1), (0, 3), (0, 4), (2, 3), (2, 4)
考え方
まずは問題の理解から。
右が東、左が西として、配列Aを横に並べて書いてみる。
車の向き -> <- -> <- <-
車 A[0] A[1] A[2] A[3] A[4]
(0, 1), (0, 3), (0, 4)
これはA[0]の東に向かう車がA[1]の西に向かう車、A[3]の西に向かう車、A[4]の西に向かう車とすれ違うことを表す。
(2, 3), (2, 4)
これはA[2]の東に向かう車がA[3]の西に向かう車、A[4]の西に向かう車とすれ違うことを表している。
問題の意味が解ればあとは簡単。
配列を順番に確認して東向きの車が現れたらそれを保存。
西向きの車が現れたらそれまで保存されていた車と必ずすれ違うので、保存されていた車の数だけすれ違った数が増える。
これで全部のすれ違いの数がカウントできる。
最終的にこんな感じ。
def solution(A: [int]) -> int:
east_car = 0
passing = 0
for i in A:
if i == 1:
passing += east_car
else:
east_car += 1
if passing > 1000000000:
passing = -1
return passing
これで100%になる。
計算量 O(N)
感想
最初、問題と例を見ても全然何を言っているのかわからなかった。と言うか、すれ違いの数を求めるのはわかるのだが、例に出てくる5つのタプルの意味がわからなくて困った。
結局わからないから飛ばして先に進んで、Lesson 7 Fishの問題を読んでいて急に理解できた。東西か上流下流か、すれ違うか食べちゃうかの違いだけで似たような問題で、Fishの方が説明が丁寧なのでピンときた。
ところで、Lesson 5はPrefix Sumsなのにそれっぽい解法ではないのだけど…
集合型を使わない場合に最初に合計を求めておく解法になるのか？
Lesson 6 Sorting
ソート
Distinct
問題
配列AにはN個の整数が入っている。配列Aのdistinct valueの数を求めよ。
例
6つの要素が入った配列Aが次のような場合。
A[0] = 2 A[1] = 1 A[2] = 1
A[3] = 2 A[4] = 3 A[5] = 1
答えは3。なぜなら1,2,3の3つのdistinct valueが配列Aには含まれているから。
考え方
まず、distinct valueの訳が思い付かない…
この場合、何種類の数が入っているか？と言い直しても良いかな。
となると、集合型を使えば簡単。
こんな感じになる。
def solution(A: [int]) -> int:
pool = set()
for i in A:
pool.add(i)
return len(pool)
これで100%になる。
計算量 O(N*log(N)) or O(N)
感想
これもLesson 6はソートなのにソートしない解法。
最初にソートして順番に出てくる数を数えるのが意図されている解法なのか？
MaxProductOfThree
問題
配列AにはN個の整数が入っている。0<=P<Q<R<Nのとした場合3つの組み(P,Q,E)の値はA[P]*A[Q]*A[R]となる。最大の3つの組みの値を求める。
例
A[0] = -3
A[1] = 1
A[2] = 2
A[3] = -2
A[4] = 5
A[5] = 6
の場合、下記の3つの組みが含まれる。
- (0,1,2) は -3 * 1 * 2 = -6
- (1,2,4) は 1 * 2 * 5 = 10
- (2,4,5) は 2 * 5 * 6 = 60
最大の3つの組みは(2,4,5)の60なので答えは60。
考え方
配列の中の3つの数字の組み合わせで、それらを掛け算した値が一番大きくなるものを探す問題。
0<=P<Q<R<Nとか難しそうに書いてあるけど単純に同じ要素（例えばA[1]とA[1]）を使うなってこと（と理解した）。
単純に考えればソートして大きいもの3つを掛け算すれば最大の数になる。
が、問題は要素としてマイナスの値も含まれるってこと。
極端な話、下記の例だと大きなもの3つを掛け算した24が最大の数ではない。
[-10, -5, 1, 2, 3, 4]
この場合は -10 * -5 * 4 の 200が答え。
で、ここからスマートな解法が思いつかなかったので結局は場合わけの力技で解決…
- 長さが3ならそれを全部掛け算するしかない。
- 長さが4以上なら
-- まずは答えがプラスになるかどうか。
-- 次にゼロになるか。
-- 最終的にはマイナスの中から選ぶ。
プラスになる場合は
- plus * plus * plus
- plus * minus * minus
の2種類がある。
ゼロになる場合はどれか一つがゼロになればいい。
マイナスになる場合は
- minus * minus * minus
- plus * plus * minus
の2種類。
表にしてみる。
0123
++++ plus A[1]*A[2]*A[3]
0+++ plus A[1]*A[2]*A[3]
-+++ plus A[1]*A[2]*A[3]
-0++ zero A[1]*A[2]*A[3]
--++ plus A[0]*A[1]*A[3]
--0+ plus A[0]*A[1]*A[3]
---+ plus A[0]*A[1]*A[3]
---0 zero A[0]*A[1]*A[3]
---- minus A[1]*A[2]*A[3]
後はこれを力技のif文で実装！
最終的にこんな感じになる。
コード内の変数のpはpositiveでnはnegativeの意味。
def solution(A: [int]) -> int:
if len(A) == 3:
return A[0] * A[1] * A[2]
A.sort()
if A[-3] > 0:
ppp = A[-3] * A[-2] * A[-1]
if A[1] < 0:
pnn = A[-1] * A[0] * A[1]
return ppp if ppp > pnn else pnn
else:
return ppp
elif A[-1] > 0 > A[1]:
pnn = A[-1] * A[0] * A[1]
return pnn
elif A[-1] == 0 or A[-3] == 0:
return 0
else:
return A[-1] * A[-2] * A[-3]
これで一応100%。
計算量 O(N*log(N))
感想
スマートな解法が思い付かない…
数学的というかパズル的にもっと綺麗に書けるのだと思うけど断念。
そろそろやる事がややこしくて面白くなってきた〜
Triangle
問題
配列AにはN個の整数が入っている。
下記の条件を満たす時、3つの組み合わせは三角形？である。
- 0 <= P < Q < R < N
- A[P] + A[Q] > A[R]
- A[Q] + A[R] > A[P]
- A[R] + A[P] > A[Q]
Aに三角形が含まれていれば1を、なければ0を返せ。
例
A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20
この場合、(0, 2, 4)が条件を満たすので三角形。なので1が答え。
A[0] = 10 A[1] = 50 A[2] = 5
A[3] = 1
この場合、条件を満たす組み合わせがないので0が答え。
考え方
- 0<=P<Q<R<N
これは前の問題と同じでバラバラの要素を3つ使うと言う意味。
- A[P] + A[Q] > A[R]
- A[Q] + A[R] > A[P]
- A[R] + A[P] > A[Q]
これはA[P]<A[Q]<A[R]が成り立つ場合、A[P]+A[Q]>A[R]が成り立てば全部成り立つ。
と言うわけで、ソートして順番にA[P]+A[Q]>A[R]が成り立つかどうかを調べれば良い。
因みに、3つの数字のうちどれか一つ以上がマイナスの値になると式は成り立たない。今回Aに含まれる要素にはマイナスの値も入っているので、スピードアップの為に大きい数から調べて行って、マイナスの値が出てきたら処理を切り上げて0を返す。
こんな感じになる。
def solution(A: [int]) -> int:
if len(A) < 3:
return 0
A.sort()
for i in reversed(range(2, len(A))):
pv = A[i-2]
qv = A[i-1]
rv = A[i]
if pv < 0:
return 0
if pv + qv > rv:
return 1
return 0
これで一応100%。
計算量 O(N*log(N))
感想
「A[P]<A[Q]<A[R]が成り立つ場合、A[P]+A[Q]>A[R]が成り立てば全部成り立つ」が肝。
それまでモヤモヤしていたのがシャワーを浴びている時にピコン！とわかった。
シャワー最高！
Lesson 7 Stacks and Queues
スタックとキュー
Brakets
問題
N文字からなる文字列Sは下記の条件を満たす時に、入れ子になっていると考えられる。
- S が空の時
- S が "(U)"もしくは"[U]"もしくは"{U}"でUが入れ子になっている場合
- S が "VW"でVとWが入れ子になっている場合
与えられたSは入れ子になっているかどうか。
例
"{[()()]}"は入れ子になっている。
"([)()]"は入れ子になっていない。
考え方
端から文字列を読んでいって"(", "[", "{"の場合はスタックに積んで、")", "]", "}"の場合はスタックから取ってきたものと対応するかどうかを確認すれば良い。
右側の括弧が来た場合にスタックが空でないかどうかに注意。
空文字の時も入れ子になっているとするので注意。
こんな感じになる。
def solution(S: str) -> int:
right_brackets = [')', ']', '}']
bracket_dict = {'(': ')', '[': ']', '{': '}'}
stack = []
for i in S:
if i in right_brackets:
if len(stack) > 0:
left_bracket = stack.pop()
if bracket_dict[left_bracket] != i:
return 0
else:
return 0
else:
stack.append(i)
return 1 if len(stack) == 0 else 0
これで一応100%。
計算量 O(N)
Fish
問題
あなたはN個の整数が入った配列AとBを渡される。AとBは川にいるN匹のお腹を空かせた魚を川を下る順番にいるのを表している。
魚は0からN-1の番号が振られている。PとQを２匹の魚でP<Qとした場合、最初に魚Pは魚Qの上流に配置されていることになる。初期状態でそれぞれの魚は独立した場所に配置されている。
番号Pの魚はA[P]とB[P]で表される。配列Aは魚の大きさを表す。全ての要素は別々の値になっている。配列Bは魚の進む向きを表している。含まれているのは0と1のみ。
- 0 は上流に昇っている
- 1 は下流に降っている
もし２匹の魚が別々の方向に進みそれぞれの間に他の（生きている）魚がいなかった場合、お互いが出会うことになる。そして大きな魚が小さな魚を食べて大きい魚のみが生き残る。
もっと正確に言うと2匹の魚PとQがP<Qで、さらにB[P]=1でB[Q]=0、さらにそれらの間に生きた魚がいない場合。出会った後は下記のようになる。
- A[P]>A[Q]ならPがQを食べてPが続けて下流へ降っていく
- A[P]<A[Q]ならQがPを食べてQが続けて上流へ昇っていく
全ての魚は同じ速度で泳ぐものとする。これは同じ方向に泳ぐ魚は互いに出会わないことを意味する。
最終的に生き残る魚の数を求めよ。
例
A[0] = 4 B[0] = 0
A[1] = 3 B[1] = 1
A[2] = 2 B[2] = 0
A[3] = 1 B[3] = 0
A[4] = 5 B[4] = 0
上記の配列A, Bが与えられる。
最初、全ての魚は生きていて、番号1の魚を除いて全ての魚は上流へ昇っている。番号1の魚は番号2の魚に出会ってそれを食べる。そして番号3の魚に出会ってまたそれを食べる。が、番号4の魚に出会って食べられてしまう。結果、番号0と4の魚が他の魚に出会わずに生き残る。
下る魚だけ動かして考えると下記の図のようになる。
0が最初の状態。< > < < <が川に配置された魚で左が上流、右が下流。魚の上に書かれた数字4 3 2 1 5がそれぞれの魚の大きさ。
初期状態の次のタイミングで大きさ3の魚が下流の大きさ2の魚を食べて下流に下る。
さらに次のタイミングで大きさ3の魚が下流の大きさ1の魚を食べて下流に下る。
さらに次のタイミングで大きさ3の魚が下流の大きさ5の魚に食べられて大きさ5の魚が残る。
結果、残った魚は最初から他の魚と交わらなかった大きさ4の魚と、最後に大きさ3の魚を食べた大きさ5の魚の2匹。
4 3 2 1 5
0 < > < < <
4 3 1 5
1 < > < <
4 3 5
2 < > <
4 5
3 < <
考え方
上流から下流へ魚を確認していく。
川を下る魚がいればそれを記録しておく。
昇ってくる魚がいたら下る魚達とどちらが生き残るかを確認する。この場合記録していた魚の先頭から順番に確認する。
下る魚が生き残るならどんどん下流の魚と戦わせる。
昇る魚が勝つ場合はどんどん記録されている魚を取り出して戦わせる。
記録した魚がいなければ（下る魚がいなければ）昇っている魚は上流へ泳ぎ切って生き残る。
下る魚の先に昇る魚がいなくなればその時点で記録されている（下流へ降っている）魚は下流へ泳ぎ切って生き残る。
で、記憶しておくのがスタック。上流から下流へ見ていくのに、下る魚を順番に入れると下流の魚が上になる。昇る魚と戦う場合にスタックから取り出すと一番下流にいる魚が出てくる。
かんな感じになる。
def solution(A: [int], B: [int]) -> int:
downstream_fishes = []
alive_fish = 0
for size, direction in zip(A, B):
if direction == 1:
downstream_fishes.append(size)
else:
while len(downstream_fishes) > 0:
if downstream_fishes[-1] > size:
break
else:
downstream_fishes.pop()
if len(downstream_fishes) == 0:
alive_fish += 1
return alive_fish + len(downstream_fishes)
これで一応100%。
計算量 O(N)
感想
思いの外サクっとできたのだけど、Lesson 7がスタックだって情報がなかったらもう少し悩んだと思う。ただwhileの部分はもう少し綺麗に書けないかな？
Nesting
問題
N文字からなる文字列Sは下記の条件を満たす時に、入れ子になっていると考えられる。
- S が空の時
- S が "(U)"でUが入れ子になっている場合
- S が "VW"でVとWが入れ子になっている場合
与えられたSは入れ子になっているかどうか。
例
"(()(())())"は入れ子になっているが、"())"は入れ子になっていない。
考え方
あれ？Bracketsでやってない？
今度は括弧の種類が"()"の一つだけ。
基本は、文字列を順番に見ていって、"("が来たらスタックに積んで、")"が来たらスタックのてっぺんを確認して"("なら取り出す。
他はエラーにする。
こんな感じ。
def solution(S: str) -> int:
stack = []
for i in S:
if i == '(':
stack.append(i)
else:
if len(stack) > 0 and stack[-1] == '(':
stack.pop()
else:
return 0
return 1 if len(stack) == 0 else 0
これで一応100%。
計算量 O(N)
StoneWall
問題
あなたは石の壁を組み上げようとしている。壁は真っ直ぐでNメートルの長さ（幅）。厚さは一定。が、高さはそれぞれの場所でまちまち。壁の高さはN個の整数の配列Hで表される。H[I]は壁の左からIからI+1メートルの部分の高さを表す。H[0]は壁の左端、H[N-1]は壁の右端の高さを表す。
壁は四角形の石のブロックで組み上げられる。求めるのは壁を組み上げるのに必要な最小の四角形の数。
例
配列Hには9つの整数が含まれる。
H[0] = 8 H[1] = 8 H[2] = 5
H[3] = 7 H[4] = 9 H[5] = 8
H[6] = 7 H[7] = 4 H[8] = 8
答えは7になる。
以下の絵がブロックが7つ必要な解の一つ。
考え方
問題が何を言っているのが理解するのに時間がかかった。
与えられた配列Hの意味がわからない。
が、与えられた絵と配列を見比べていてやっと理解した。
与えられた配列が意味するのは以下の絵。
左から8,8,5,7...と、与えられた配列Hに入っている数字の高さの板を並べるだけ。
で、問題はなるべく大きな四角形で構成した場合に四角形の数は幾つになるか？
サンプル？で添付されていた絵はこの問題を解いた場合の答えの一つ。
板は9つ渡されるのだけど四角形を大きくとることで必要な数が7つになる。
なので答えは7。
さて、やっと考え方だけど、絵をパッと見てわかるのは「高さが同じなら一つにまとめられる」と言うこと。
例えば配列Hの最初の2枚。下記の図の青と赤の板は同じ高さなので1枚の大きな青い四角形にまとめられる。結果2枚の板が1つの四角形になった。
次に「間にもっと高い板が挟まれている場合でも、同じ高さの板なら一つにまとめられる」と言うこと。
例えば以下のように3,4,3の高さの板がある場合、3の高さの四角形でまとめられる。結果、3枚の板が2つの四角形になった。
これは間にどれだけの数の板が挟まっていても同じで、下記のように3,4,6,5,3の5枚の板があったら高さ3でまとめられる。結果、5枚の板が4つの四角形になった。
ただし、間に比べる高さよりも低い板が挟まるとまとめられない。
というか下記図の場合、無理に高さ2でまとめても四角形の数は4つのままで減らない。
以上のルールを踏まえて取り出した板をどうするか処理を考えていく。
-
スタックに板がなければ
スタックに積んで使用している板の数を1増やす。 -
前の板と同じ高さの板なら前の板とまとめる
何もしない。（板の数は増やさなくて良い） -
前の板より高い板が来たら
板をスタックに積んで、枚数を1枚増やす -
前の板より低い板が来たら
まとめられるかもしれないので作業開始
スタックを掘っていく- 新しい板と同じ高さの板がある
そこで板を1枚少なくできるので板を1枚減らす
スタックを掘るのは終了 - 新しい板より低い板があれば
スタックに戻して
スタックを掘るのは終了
新しい板をスタックに積んで板を1枚増やす
- 新しい板と同じ高さの板がある
以上を繰り返せば四角形の数（板の数）が求められる。
こんな感じになる。
def solution(H: [int]) -> int:
stack = []
walls = 0
for i in H:
if len(stack) == 0:
stack.append(i)
walls += 1
else:
if i > stack[-1]:
stack.append(i)
walls += 1
elif i < stack[-1]:
while len(stack) > 0:
last_wall = stack.pop()
if last_wall == i:
walls -= 1
break
elif last_wall < i:
stack.append(last_wall)
break
stack.append(i)
walls += 1
return walls
これで一応100%。
計算量 O(N)
感想
表題のところの"Manhattan skyline"はビルの凸凹のことか。
今回の問題はサンプルの画像がなければ解けなかったろう。
ただ、自分の解き方だとサンプルの画像とは違うものになるのだけど…
サンプルはこう。
自分で解いたものはこう考えてる。
自分のは後ろから前にスタックを遡って確認しているけど、サンプルのは毎回前から後方に見に行っている感じ。その割にはテッペンの紫と緑の箱はくっ付いていないんだよな。
Lesson 8 Leader
リーダー
Dominator
問題
N個の整数で満たされた配列A。配列Aの支配者はAの要素の半数以上を占める整数。
例
A[0] = 3 A[1] = 4 A[2] = 3
A[3] = 2 A[4] = 3 A[5] = -1
A[6] = 3 A[7] = 3
この場合支配者は3。なぜなら8この要素のうち5個（0, 2, 4, 6, 7）を占めていて、5はAの要素数8の半数以上だから。
そして返す答えは0, 2, 4, 6, 7のどれか。それがAの中に入っている3の添字だから。
考え方
順に見ていって辞書に登録しながら数を増やして終わったらソートする？と考えたけど、返す答えが支配者の数字ではなくその添字だった。
で、簡単そうなのが添字付きのリストにしてからソートして順番に見ていって支配者を探す。探したら付いている添字をどれでも良いから返す。で、行けそう。
こんな感じになる。
def solution(A: [int]) -> int:
if len(A) == 0:
return -1
a = [(i, v) for i, v in enumerate(A)]
a.sort(key=lambda x: x[1])
max_count = 0
pre_i, pre_v = a[0]
max_value_index = pre_i
count = 0
for i, v in a:
if v == pre_v:
count += 1
else:
if count > max_count:
max_count = count
max_value_index = pre_i
count = 1
pre_i, pre_v = i, v
if count > max_count:
max_count = count
max_value_index = pre_i
return max_value_index if max_count > len(A) / 2 else -1
これで一応100%。
計算量 O(N*log(N)) or O(N)
EquiLeader
問題
N個の整数で満たされた配列A。
配列のリーダーは配列の要素の中で半数以上を占める値。
等しいリーダーは添字S。このSは0<=S<N-1で2つの配列A[0],A[1],...,A[S]とA[S+1],A[S+2],...,A[N-1]のリーダーが同じになるもの。
配列Aの等しいリーダーの数を求める。
例
A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2
この場合2つの等しいリーダーがある。
- 0 なぜなら(4)と(3, 4, 4, 4, 2)はどちらもリーダーが4になる
- 2 なぜなら(4, 3, 4)と(4, 4, 2)はどちらもリーダーが4になる
等しいリーダーの数は2。
考え方
Sで分けた左右両方でリーダーになるにはそれぞれで過半数が必要なので、その値は全体でも過半数を超えるからリーダーになっている。逆に全体でリーダーでなければその値が左右でリーダーになることはできない。
最初に全体のリーダーを求めて要素の添字を調べておく。
あとは左（添字0）から順にSの位置を動かしてそこまでに入っているリーダーの数を計算すれば、左と右とでリーダーになっているかどうかがわかる。
まず、必要なのはリーダーの添字のリスト。
for i, v in enumerate(A):
if v in value_dic.keys():
value_dic[v].append(i)
else:
value_dic[v] = [i]
-> {4: [0, 2, 3, 4], 3: [1], 2: [5]}
ここからmaxでリーダーを探す。
leader_index_array = max(value_dic.values(), key=lambda x: len(x))
leader_count = len(leader_index_array)
リーダーは4の添字は[0, 2, 3, 4]で数は4つ。
あとは左（添字0）から順番にリーダーの添字と合わせて左と右の両方でリーダーになっているかどうかを確認する。
こんな感じになる。
def solution(A: [int]) -> int:
value_dic = {}
for i, v in enumerate(A):
if v in value_dic.keys():
value_dic[v].append(i)
else:
value_dic[v] = [i]
leader_index_array = max(value_dic.values(), key=lambda x: len(x))
leader_count = len(leader_index_array)
equi_leader_count = 0
index = 0
left_leader_count = 0
for leader_index in leader_index_array:
while index <= leader_index:
if index == leader_index:
left_leader_count += 1
left_size = index + 1
right_size = len(A) - left_size
right_leader_count = leader_count - left_leader_count
if left_leader_count > int(left_size / 2) and right_leader_count > int(right_size / 2):
equi_leader_count += 1
index += 1
return equi_leader_count
これで一応100%。
計算量 O(N)
感想
ループの処理がややこしくなっている。もっと綺麗に書けないものか…
元々の考え方に問題があるのか？
最後に
以上、レッスン5から8までのメモ。
英語が辛い…。問題が何を言っているのがすぐに理解できないのは大変。車のすれ違い問題は魚の問題がなければ気付かなかったと思う。
そして事前に処理すると色々とやり易いってことに気付く。一瞬ソートしてしまえば全てOKではないか？と勘違いするほど。
それとループの端の処理が苦手だなと思い知る。判断を先にするのか後にするのか？イコールが付くのかつかないのか？なんとなくで書くと綺麗にするのが大変。
次はレッスン（のeasy）最後まで頑張る予定。
Discussion