[Codility]Lesson5

Task1

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    B=[]
    for i in range(len(A)):
        if A[i]==0:
            B.append(0)
        if A[i]==1:
            B[-1]=B[-1]+1
    N=len(B)
    for i in range(1,N):
        B[N-1-i]=B[N-1-i]+B[N-i]
    sum=0
    for i in range(N):
        sum=sum+B[i]
    return sum

结果得分很低，分析：

1.没看好题目，其中有一句是数据溢出的处理：只要超过10^9就输出-1

2.没有考虑初始就是1的情况

因此 更新后的代码：

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    B=[]
    for i in range(len(A)):
        if A[i]==0:
            B.append(0)
        if A[i]==1:
            if len(B)>0:
                B[-1]=B[-1]+1
    N=len(B)
    for i in range(1,N):
        B[N-1-i]=B[N-1-i]+B[N-i]
    sum=0
    for i in range(N):
        sum=sum+B[i]
        if sum>1000000000:
            return -1
    return sum

满分完成

Task2:

Write a function:

def solution(A, B, K)

that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:

{ i : A ≤ i ≤ B, i mod K = 0 }

For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.

Write an efficient algorithm for the following assumptions:

A and B are integers within the range [0..2,000,000,000];K is an integer within the range [1..2,000,000,000];A ≤ B.

Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B, K):
    # write your code in Python 3.6
    mod1=A//K
    mod2=B//K
    result=mod2-mod1
    if A%K==0:
        result = result+1
    return result

 Task3:

先是复杂度为O(n)的62%得分版本：

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(S, P, Q):
    # write your code in Python 3.6
    result=[]
    for i in range(len(P)):
        result.append(4)
        for j in range(P[i],Q[i]+1):
            temp=4
            if S[j]=='A':
                temp=1
            elif S[j]=='C':
                temp=2
            elif S[j]=='G':
                temp=3
            elif S[j]!='T':
                return -1
            if temp 
实在想不出O(n)或者O(nlogn)的了，想先通过if缩短一下时间：
 
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(S, P, Q):
    # write your code in Python 3.6
    result=[]
    for i in range(len(P)):
        result.append(4)
        for j in range(P[i],Q[i]+1):
            temp=4
            if S[j]=='A':
                result[i]=1
                break
            elif S[j]=='C':
                if 2 
时间复杂度还是O(N*M)，唉继续改……
 
最后想到了一个方法，设置一个N*4的矩阵，每一行存储的是这一列之前所有出现的1234的个数，这样一个区间的个数就可以用列之间的相减获得，一个典型的空间换时间的思路
 
为了减少空间又加了一个专门的转译函数，结果差点在转译函数里面绕糊涂了OTZ
 
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def trans(a):
    if a=='A':
        return 0
    elif a=='C':
        return 1
    elif a=='G':
        return 2
    elif a=='T':
        return 3
    else:
        print("ERROR!")
        return -1
def solution(S, P, Q):
    # write your code in Python 3.6
    rm=[]
    list1=[0,0,0,0]
    list1[trans(S[0])]=1
    rm.append(list1)
    #print("when i=",0,"list=",list1,"rm=",rm)
    result=[]
    for i in range(1,len(S)):
        list2=[]
        for j in range(len(list1)):
            list2.append(list1[j])
        list2[trans(S[i])]=list2[trans(S[i])]+1
        rm.append(list2)
        list1=list2
        #print("when i=",i,"list=",list1,"rm=",rm)
    #print("rm=",rm)
    #rm[i]保存的是从第一个到第S[i]个这些元素中包含ACGT(1234)分别的个数
    for i in range(len(P)):
        list1=rm[P[i]]
        list2=rm[Q[i]]
        listv=[]
        #print("when i=",i,"P[i]=",P[i],"Q[i]=",Q[i],"trans=",trans(S[P[i]]))
        for j in range(len(list1)):
            listv.append(list2[j]-list1[j])#此时listv包含从P[i+1]到Q[i]这个区间内1234分别的个数
        listv[trans(S[P[i]])]=listv[trans(S[P[i]])]+1#把P[i]位置对应的S[P[i]]加回去
        #print("listv=",listv)
        for j in range(len(listv)):
            if listv[j]>0:
                result.append(j+1)
                break
        #print("when i=",i,"result=",result)
    return result
 
Task4
 
 
 
A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).
 
 
For example, array A such that:
 
 
A[0] = 4 A[1] = 2 A[2] = 2 A[3] = 5 A[4] = 1 A[5] = 5 A[6] = 8
 
 
contains the following example slices:
 
 
 
  
slice (1, 2), whose average is (2 + 2) / 2 = 2;slice (3, 4), whose average is (5 + 1) / 2 = 3;slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.
 
 
 
The goal is to find the starting position of a slice whose average is minimal.
 
 
Write a function:
 
 
 
  
def solution(A)
 
 
 
 
that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.
 
 
For example, given array A such that:
 
 
A[0] = 4 A[1] = 2 A[2] = 2 A[3] = 5 A[4] = 1 A[5] = 5 A[6] = 8
 
 
the function should return 1, as explained above.
 
 
Write an efficient algorithm for the following assumptions:
 
 
 
  
N is an integer within the range [2..100,000];each element of array A is an integer within the range [−10,000..10,000].
 
 
 
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
 
 
学乖了，知道O(n^2)的方法不行，苦思冥想只能分割了
 
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    b=(A[0]+A[1])/2
    posi=0
    for i in range(1,len(A)-2):
        tmp=(A[i]+A[i+1])/2
        if tmp