Lesson 4です。
就活のために始めたCodilityの勉強ですが、そろそろ飽きてきました。
ただ、対策しないと解けそうにないので、もう少し頑張ってみます。
１、FrogRiverOne
また、カエルです。
最初読んだとき問題文を理解できなくて困りました。
留学とか海外インターンとかのために英語は一生懸命勉強してきたつもりですけど、しばらく読んでなったら、全然読めなくなりました。論文読むのも苦痛です。
ちゃっちゃと読んで問題を解きたいですが、問題を読み間違えたら絶対正解できないのでちゃんと読みます。
要は、配列の値が葉っぱの位置で１からXまでのすべての位置に葉っぱがある状態になればいいってことです。
だから、配列を順に読みだして、例えばXが９なら１から９の数字が少なくとも１つ以上読みだされた状態まで、待てばいいんです。
で、こちらが最初に考えたプログラムになります。
def solution(X, A):
# write your code in Python 3.6
all_positions = [x for x in range(1, X+1)]
n_A = len(A)
for i in range(n_A):
try:
all_positions.remove(A[i])
except ValueError:
pass
if all_positions == []:
return i
return -1
removeメソッドで１～Xのリストの要素を消していって、全部消せたらそこで終了。
これで、63%。
実行時間を半減しないとだめといわれました。相変わらず、シビアです。大学生の書くプログラムに実行時間という概念はないんですが、これからは意識しなくちゃならないんですかね。
自分的には進めば進むほどall_positionの中身が減るので、早くなると思ったんですが・・・。
やっぱり、全部読みだして全部確認する走査型？の処理は使っちゃダメ見たです。
他人のコードを参考に書いたのがこちら、ピンポイントで要素を読みだすので無駄がないです。
def solution(X, A):
# write your code in Python 3.6
passable = [False] * X
n_A = len(A)
uncovered = X
for i in range(n_A):
try:
if passable[A[i]-1] == False:
passable[A[i]-1] = True
uncovered -= 1
if uncovered == 0:
return i
except IndexError:
pass
return -1
２、PermCheck
今度はすんなり正解でした。上の問題と比べると随分簡単なような・・・。
まぁ、上の問題で一番苦労したのは英語ですけど。
抜けている数をあてる問題。
ソートしてちゃんと連番になっているか確認すればOKです。
1を抜いてちゃんと連番になっている場合をお忘れなく。
def solution(A):
# write your code in Python 3.6
A.sort()
n_A = len(A)
if A[0] != 1:
return 0
if n_A == 1:
return 1
for i in range(n_A - 1):
if A[i] != A[i+1] -1:
return 0
return 1
３、MissingInteger
def solution(A):
n_A = len(A)
n_List = [False] * n_A
for i in range(n_A):
try:
if A[i] > 0:
n_List[A[i] -1] = True
except IndexError:
pass
for i in range(n_A):
if n_List[i] == False:
return (i+1)
return i + 2
配列のインデックスを負で読み出すと反対から読み出せるんですね知りませんでした。
ついでに、要素数が１だとエラーが出たりして散々でしたね。
一応これで100%になります。
４、MaxCounters
正直これは100%無理だわーって思いました。
いろいろ工夫した結果88%までは行きましたが、それ以上が無理
def solution(N, A):
max_value = 0
counter = [0] * N
n_A = len(A)
for i in range(n_A):
if A[i] <= N:
counter[A[i]-1] += 1
if counter[A[i]-1] > max_value:
max_value = counter[A[i]-1]
elif A[i] == N + 1:
counter = [max_value] * N
return counter
100点取る必要はないんでこれでいいです。それよりも例外の処理を忘れて50点以下をとらないように気を付けたほうが絶対いいと思います。
興味本位でやってますがめっちゃ勉強になります。
研究室ではこんな話しません。わかっている人は分かってるし、知らない人は知らないと思います。
ちょっと面白いと思ってきましたが、時間がかかりすぎるので年末の暇な時でもします。
それでは。
