あけましておめでとうございます。

年末に投稿しようとしてた記事ですが年末はなんだかんだで忙しくて、年明けちゃいました。

Lesson5になります。ちょっとはまってます。面白いです。

でも、やんなきゃいけないことがたまりにたまっているので、あんまり時間かけないようにします。

１、PassingCars

１と０のペアのカウント。

最初はsumを使っていましたが、やっぱりsumは走査的な処理なので使っちゃダメみたいです。

def solution(A):
    n_A = len(A)
    count = 0
    sum1 = sum(A)
    for i in range(n_A):
        a = A[0]
        del A[0]

        if  a == 0:
            count += abs(a*(n_A-i-1) - sum1)
            print(count)
        else:
            sum1 -= 1
    return count

これで60%。

TIMEOUTとペアが多すぎたときに-1を返す処理を入れてないといわれました。

で、stackoverflowを参考にした、逆から配列を読みだせばsumを使わなくてよいプログラムがこちら。

def solution(A):
    count = 0
    n_A = len(A)
    one = 0
    for i in range(n_A-1, -1, -1):
        if count > 1000000000:
            return -1
        a = A[i]
        if  a == 0:
            count += one
            print(count)
        else:
            one += 1
    return count

これで100%。なるほど～って感じです。

２、GenomicRangeQuery

今度はDNAシークエンサーのお話

A ,C, G, Dの優先度で、ある区間にある塩基の中で一番優先度が高い塩基を配列に保存して返します。

def solution(S, P, Q):
    M = []
    n_Q = len(Q)
    for l in range(n_Q):
        m=4
        for i in range (P[l],Q[l]+1):
            if S[i] == "A":
                m = 1
                break
            elif S[i] == "C":
                m = 2
            elif S[i] == "G"and m == 4 :
                m = 3
        M.append(m)
    return M

これだと62%。

ネットに転がっているのをいくつか試しましたけど同じ62%になりました。

問題は調べる区間数が多くなると、毎回走査的な処理を行わなければならなくなることです。

なんで、与えられた配列の最初から最後まで流して、すべてのタイミングでこれまでどの塩基が何個表れか配列に保存しておきます。

で、調べたい区間のはじめと終わりで各塩基の今までの出現数を引き算すれば、何個塩基があるかわかるという算段です。

で、そのプログラムがこちら

def solution(S, P, Q):
    A_count = [0]
    C_count = [0]
    G_count = [0]
    T_count = [0]
    a = 0
    c = 0
    g = 0
    t = 0
    n_S = len(S)
    n_Q = len(Q)
    impacts = []
    for i in range(n_S):
        if S[i] == "A":
            a += 1
        elif S[i] == "C":
            c += 1
        elif S[i] == "G":
            g += 1
        elif S[i] == "T":
            t += 1
        A_count.append(a)
        C_count.append(c)
        G_count.append(g)
        T_count.append(t)
    for i in range(n_Q):
        if A_count[Q[i]+1] - A_count[P[i]] >0:
            impacts.append(1)
        elif C_count[Q[i]+1] - C_count[P[i]] >0:
            impacts.append(2)
        elif G_count[Q[i]+1] - G_count[P[i]] >0:
            impacts.append(3)
        elif T_count[Q[i]+1] - T_count[P[i]] >0:
            impacts.append(4)
    return impacts

これで100%でした。

なんの処理がたくさん行われるか考えるのがこの問題で得る知見みたいですね。

ふつうにプログラミングの勉強になってる笑。

３、MinAvgTwoSlice

今回のお話は配列のいろいろな枠で平均をとって、一番平均値が小さい枠の最初のインデックスはどこかという問題。

全部の枠組みなんて計算したら、とてもじゃないけど時間がかかってしょうがないじゃんと思ったら、最小になるのは2つの枠組みか３つ枠組みしかないそうです。

なぜかというと、実験とかする人ならわかると思うんですけど、平均ってとればとるほど全体の平均値に近づいていきますよね。平均値が平均された要素よりも尖った値（より小さい値、より大きい値）をとることはないんです。

で、２と３よりも大きい枠組みは、結局２の枠組みの平均値と３の枠組みの平均値を要素として平均をとってるだけなのでそれ以上尖った値にならないということですね。

そんな気はしてたんだよな笑。

def solution(A):
    # write your code in Python 3.6
    min_idx = 0
    min_value = 100
    
    for idx in range(0, len(A)-1):
        if (A[idx] + A[idx+1])/2.0 < min_value:
            min_idx = idx
            min_value = ((A[idx] + A[idx+1])/2.0)
            
        if idx < len(A) -2 and (A[idx] + A[idx+1] + A[idx + 2])/3.0 < min_value:
            min_idx = idx
            min_value = (A[idx] + A[idx+1] + A[idx + 2])/3.0 
    return min_idx

４、CountDiv

ただの植木算と思ったのですが、AがKで割り切れないときの処理がてこずりました。

def solution(A,B,K):
    Dif = B - A
    quotient = Dif /  K
    remainder = 0
    if A % K == 0:
        Answer = (B - A)/K + 1
    else:
        Answer  = (B - (A - A % K))/K
    return int(Answer)

これで100％です。

インターン応募のための勉強としてやっていましたが、ESとかも書かなくちゃいけないような感じになってきたのでcodilityはとりあえずここでやめにしておきます。

ただ、結構勉強になるなって感じましたので、余裕があったらまた再開してもいいかもしれませんね。

勉強してみた感想はコーディング自体はすごく簡単だし、問題も高校入試レベルだけど、機械計算させる前に自分の頭で機械的に優しい計算方法を考えなきゃいけないテストだとわかりました。

あと、自分で計算している気づくけど、コードを書いているとついつい見落としてしまう例外的な事例も対応できるようにするのも大切だと思います。

それでは。

Share this...

Twitter

Facebook

Pinterest

Tumblr