はじめに
みなさんCodility知ってますか？
就職試験なんかでよく使われるコーディングテストのサイトで、Lessonとして練習問題を解くこともできます。
Codilityでは過去の自分の提出を見ることができないので、メモ代わりにPythonで解いた自分の解答を載せていこうと思います。
Lesson1 BinaryGap
def solution(N):
# write your code in Python 3.6
binN = format(N, 'b')
streak = 0
max = 0
for n in binN:
if n=='1':
if(streak > max):
max = streak
streak = 0
else:
streak += 1
return max
Pythonでは組み込みのformatでint→2進数stringの変換ができるのでループとifが分かれば後は楽勝ですね。
中学数学なんかだと2で割っていって余りから2進数に変換とかしていた気がします。
Lesson2 OddOccurrencesInArray
def solution(A):
# write your code in Python 3.6
numSet = set()
for a in A:
if a in numSet:
numSet.remove(a)
else:
numSet.add(a)
for num in numSet:
return num
PythonのSetを使いました。
Aの中の要素aを一つずつ取り出していって、もしnumSetにaがあればremoveして、numSetにaがないならaをaddします。これを続ければ最後には1回しかAの中に登場しない要素が残るのでそれをreturnします。
Lesson2 CyclicRotation
def solution(A, K):
# write your code in Python 3.6
length = len(A)
list = []
for i in range(length):
index = cycleIndex(i,K,length)
list.append(A[index])
return list
def cycleIndex(i,K,length):
if i-K < 0:
return cycleIndex(length + i, K, length)
else:
return i-K
再帰を使って解きました。pythonのlistだと言語機能でA[-1]とかが参照できるので、条件式のところをi-K < -lengthにしたほうが再帰が一回少なくて済みますね(今気づいた)
Lesson3 FrogJmp
def solution(X, Y, D):
# write your code in Python 3.6
dif = Y - X
return -(-dif // D)
切り上げの割り算ができれば一発で解けますね。
C++なんかでよく使われる競技プログラミングのテクニックとしてa/bは(a + (b - 1)) / bとすれば切り上げの結果を求められるそうですがPythonなら-(-a//b)って書く方が綺麗だと思います。（個人的意見）
Lesson3 PermMissingElem
def solution(A):
# write your code in Python 3.6
list = []
for a in A:
list.append(a)
list.sort()
prev = 0
for l in list:
if l-prev!=1:
return l-1
prev = l
return len(A)+1
Lesson3 TapeEquilibrium
def solution(A):
# write your code in Python 3.6
leftSum = 0
rightSum = sum(A)
length = len(A)
min = 2000 * 100000 + 1
for i in range(length-1):
leftSum += A[i]
rightSum -= A[i]
if abs(leftSum - rightSum) < min:
min = abs(leftSum-rightSum)
return min
素直にループ回して最小値を求めました。
関係ないですがpythonってintに最大値がないのでsys.maxsizeより大きな数値もメモリが許せば扱えるらしいですね。
Lesson4 FrogRiverOne
def solution(X, A):
# write your code in Python 3.6
leafPos = set()
count = 0
result = 0
for a in A:
leafPos.add(a)
if len(leafPos) == X:
return count
count += 1
return -1
1~Xまでの数字が現れたかどうかをsetならlen()を使って判定できるのでO(N)で解けました。list使ってforぶん回して判定とかするとO(N**2)扱いでPerformanceが100％出ませんでした。
Lesson4 MaxCounters
https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/
完答できず
Lesson4 MissInteger
def solution(A):
# write your code in Python 3.6
numSet = set()
for a in A:
if a > 0:
numSet.add(a)
for i in range(10000000):
i = i+1
if i in numSet:
continue
else:
return i
0以下の値は問題に全く関係ないので除外して、後はAに含まれない最小値をreturnすればOK
Lesson5 PassingCars
def solution(A):
# write your code in Python 3.6
A.reverse()
sum = 0
suffixSum = 0
for a in A:
if a == 1:
suffixSum += 1
if a == 0:
sum += suffixSum
if sum > 1000000000:
return -1
else:
return sum
Lesson6 MaxProductOfThree
def solution(A):
# write your code in Python 3.6
A.sort()
max1 = A[-1] * A[-2] * A[-3]
max2 = A[0] * A[1] * A[-1]
if max1 > max2:
return max1
else:
return max2
(最小値,2番目に小さい値,最大値)か(最大値,2番目に大きい値,3番目に大きい値)の組み合わせのどちらかが最大値なことに気づけば解ける問題でした。
Lesson6 Distinct
def solution(A):
# write your code in Python 3.6
numSet = set()
for a in A:
numSet.add(a)
return len(numSet)
setは要素の重複を許さないのでsetに要素を追加してsetの要素を数えればOKです。
Lesson6 Triangle
def solution(A):
# write your code in Python 3.6
A.sort()
for i in range(1,len(A)-1):
if A[i] + A[i-1] > A[i+1]:
return 1
return 0
ソート済みなら三角形の判定はO(N)でできます
Lesson7 Brackets
def solution(S):
# write your code in Python 3.6
stack = []
for s in S:
if s == ')':
if len(stack) == 0:
return 0
c = stack.pop()
if c =='(':
continue
else:
return 0
elif s == ']':
if len(stack) == 0:
return 0
c = stack.pop()
if c == '[':
continue
else:
return 0
elif s == '}':
if len(stack) == 0:
return 0
c = stack.pop()
if c == '{':
continue
else:
return 0
else:
stack.append(s)
if len(stack) == 0:
return 1
else:
return 0
スタックをちゃんと理解できているかの問題でした。
Lesson7 Fish
Lesson7 Nesting
Lesson7 StoneWall
Lesson8 Dominator
Lesson8 EquiLeader
Lesson9 MaxProfit
Lesson9 MaxSliceSum
Lesson9 MaxDoubleSliceSum
Lesson10 CountFactors