sirve - settitle java

Entrenamiento de codilidad de java Consulta de rango genómico

Question

La tarea es:

Se proporciona una cadena S no indexada a cero no vacía. La cadena S consta de N caracteres del conjunto de letras inglesas en mayúsculas A, C, G, T.

Esta cadena representa en realidad una secuencia de ADN, y las letras mayúsculas representan nucleótidos individuales.

También se le asignan matrices de índice cero no vacías P y Q que consisten en M enteros. Estas matrices representan consultas sobre nucleótidos mínimos. Representamos las letras de la cadena S como números enteros 1, 2, 3, 4 en las matrices P y Q, donde A = 1, C = 2, G = 3, T = 4, y asumimos que A <C <G <T .

La consulta K requiere que encuentre el nucleótido mínimo del rango (P [K], Q [K]), 0 ≤ P [i] ≤ Q [i] <N.

Por ejemplo, considere la cadena S = GACACCATA y las matrices P, Q tales que:

P[0] = 0    Q[0] = 8
P[1] = 0    Q[1] = 2
P[2] = 4    Q[2] = 5
P[3] = 7    Q[3] = 7

Los nucleótidos mínimos de estos rangos son los siguientes:

    (0, 8) is A identified by 1,
    (0, 2) is A identified by 1,
    (4, 5) is C identified by 2,
    (7, 7) is T identified by 4.

Escribe una función:

class Solution { public int[] solution(String S, int[] P, int[] Q); } 

que, dada una cadena S no indexada a cero no vacía que consta de N caracteres y dos matrices P y Q no compuestas de cero indexada que consta de M enteros, devuelve una matriz que consta de M caracteres que especifican las respuestas consecutivas a todas las consultas.

La secuencia debe devolverse como:

    a Results structure (in C), or
    a vector of integers (in C++), or
    a Results record (in Pascal), or
    an array of integers (in any other programming language).

Por ejemplo, dada la cadena S = GACACCATA y las matrices P, Q tales que:

P[0] = 0    Q[0] = 8
P[1] = 0    Q[1] = 2
P[2] = 4    Q[2] = 5
P[3] = 7    Q[3] = 7

la función debe devolver los valores [1, 1, 2, 4], como se explicó anteriormente.

Asumir que:

    N is an integer within the range [1..100,000];
    M is an integer within the range [1..50,000];
    each element of array P, Q is an integer within the range [0..N − 1];
    P[i] ≤ Q[i];
    string S consists only of upper-case English letters A, C, G, T.

Complejidad:

    expected worst-case time complexity is O(N+M);
    expected worst-case space complexity is O(N), 
         beyond input storage 
         (not counting the storage required for input arguments).

Se pueden modificar elementos de matrices de entrada.

Mi solución es:

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        final  char c[] = S.toCharArray();
        final int answer[] = new int[P.length];
        int tempAnswer;
        char tempC;

        for (int iii = 0; iii < P.length; iii++) {
            tempAnswer = 4;
            for (int zzz = P[iii]; zzz <= Q[iii]; zzz++) {
                tempC = c[zzz];
                if (tempC == ''A'') {
                    tempAnswer = 1;
                    break;
                } else if (tempC == ''C'') {
                    if (tempAnswer > 2) {
                        tempAnswer = 2;
                    }
                } else if (tempC == ''G'') {
                    if (tempAnswer > 3) {
                        tempAnswer = 3;
                    }

                }
            }
            answer[iii] = tempAnswer;
        }

        return answer;
    }
}

No es óptimo, creo que se debe hacer dentro de un bucle. ¿Alguna pista de cómo puedo lograrlo?

Puede verificar la calidad de su solución aquí https://codility.com/train/ nombre de la prueba es Genomic-range-query.

Answer 1

¡Este programa tiene un puntaje de 100 y el rendimiento tiene una ventaja sobre los otros códigos Java enumerados anteriormente!

El código se puede encontrar here .

public class GenomicRange {

final int Index_A=0, Index_C=1, Index_G=2, Index_T=3;
final int A=1, C=2, G=3, T=4; 

public static void main(String[] args) {

    GenomicRange gen = new GenomicRange();
    int[] M = gen.solution( "GACACCATA", new int[] { 0,0,4,7 } , new int[] { 8,2,5,7 } );
    System.out.println(Arrays.toString(M));
} 

public int[] solution(String S, int[] P, int[] Q) {

    int[] M = new int[P.length];
    char[] charArr = S.toCharArray();
    int[][] occCount = new int[3][S.length()+1];

    int charInd = getChar(charArr[0]);

    if(charInd!=3) {
        occCount[charInd][1]++;
    }

    for(int sInd=1; sInd<S.length(); sInd++) {

        charInd = getChar(charArr[sInd]);

        if(charInd!=3)
            occCount[charInd][sInd+1]++;

        occCount[Index_A][sInd+1]+=occCount[Index_A][sInd];
        occCount[Index_C][sInd+1]+=occCount[Index_C][sInd];
        occCount[Index_G][sInd+1]+=occCount[Index_G][sInd];
    }

    for(int i=0;i<P.length;i++) {

        int a,c,g;

        if(Q[i]+1>=occCount[0].length) continue;

        a =  occCount[Index_A][Q[i]+1] - occCount[Index_A][P[i]];
        c =  occCount[Index_C][Q[i]+1] - occCount[Index_C][P[i]];
        g =  occCount[Index_G][Q[i]+1] - occCount[Index_G][P[i]];

        M[i] = a>0? A : c>0 ? C : g>0 ? G : T;    
    }

    return M;
}

private int getChar(char c) {

    return ((c==''A'') ? Index_A : ((c==''C'') ? Index_C : ((c==''G'') ? Index_G : Index_T)));  
}
}

Answer 2

¿Qué hay de malo con mi solución en C ++? obtuve [2,1,1] en lugar de [2,4,1]

#include <iostream>
#include <string>

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) 
 { 
  int SumA[S.size()];SumA[0]=0;
  int SumC[S.size()];SumC[0]=0;
  int SumG[S.size()];SumG[0]=0;
  int SumT[S.size()];SumT[0]=0;
  for (int unsigned i=0;i<S.size();i++)
  { 
    if (S[i]==''A'')
    { SumA[i]++;}
      else if (S[i]==''C'')
    { SumC[i]++;}
      else if (S[i]==''G'' )
    { SumG[i]++; }
      else {SumT[i]++;}
    SumA[i+1] = SumA[i];
    SumC[i+1] = SumC[i];
    SumG[i+1] = SumG[i];
    SumT[i+1] = SumT[i];
    } 
   vector<int> answer(P.size());
   for (int unsigned i=0;i<P.size();i++)
   { int Asinrange=SumA[Q[i]+1]-SumA[P[i]];
     int Csinrange=SumC[Q[i]+1]-SumC[P[i]];
     int Gsinrange=SumG[Q[i]+1]-SumG[P[i]];
     int TsInRange =SumT[Q[i]+ 1]- sumT[P[i]]
     if (Asinrange>0)
     { answer[i]=1;}
      else if (Csinrange>0)
     { answer[i]=2;}
      else if (Gsinrange>0)
     { answer[i]=3;}
      else 
     {answer[i]=4;}
  }

   return answer;
}

Answer 3

/ * Solución 100/100 C ++. Usando sumas de prefijo. En primer lugar la conversión de caracteres a un entero en la variable nuc. Luego, en un vector bidimensional, consideramos la ocurrencia en S de cada nucleósido x en su respectivo prefijo_sum [s] [x]. Después, solo tenemos que averiguar el nucluósido inferior que ocurrió en cada intervalo K.

* /. solución vectorial (string & S, vector & P, vector & Q) {

int n=S.size();
int m=P.size();
vector<vector<int> > prefix_sum(n+1,vector<int>(4,0));
int nuc;

//prefix occurrence sum
for (int s=0;s<n; s++) {
    nuc = S.at(s) == ''A'' ? 1 : (S.at(s) == ''C'' ? 2 : (S.at(s) == ''G'' ? 3 : 4) );        
    for (int u=0;u<4;u++) {
        prefix_sum[s+1][u] = prefix_sum[s][u] + ((u+1)==nuc?1:0);
    }
}

//find minimal impact factor in each interval K
int lower_impact_factor;

for (int k=0;k<m;k++) {

    lower_impact_factor=4;
    for (int u=2;u>=0;u--) {
        if (prefix_sum[Q[k]+1][u] - prefix_sum[P[k]][u] != 0)
            lower_impact_factor = u+1;
    }
    P[k]=lower_impact_factor;
}

return P;

}

Answer 4

Aquí está la solución 100% Scala:

def solution(S: String, P: Array[Int], Q: Array[Int]): Array[Int] = {


    val resp = for(ind <- 0 to P.length-1) yield {

      val sub= S.substring(P(ind),Q(ind)+1)


      var factor = 4

      if(sub.contains("A")) {factor=1}
      else{
        if(sub.contains("C")) {factor=2}
        else{
          if(sub.contains("G")) {factor=3}
        }
      }
      factor

    }

    return resp.toArray

  }

Y rendimiento: https://codility.com/demo/results/trainingEUR4XP-425/

Answer 5

Aquí está la solución que obtuvo 100 de 100 en codility.com. Lea acerca de las sumas de prefijos para entender la solución:

public static int[] solveGenomicRange(String S, int[] P, int[] Q) {
        //used jagged array to hold the prefix sums of each A, C and G genoms
        //we don''t need to get prefix sums of T, you will see why.
        int[][] genoms = new int[3][S.length()+1];
        //if the char is found in the index i, then we set it to be 1 else they are 0
        //3 short values are needed for this reason
        short a, c, g;
        for (int i=0; i<S.length(); i++) {
            a = 0; c = 0; g = 0;
            if (''A'' == (S.charAt(i))) {
                a=1;
            }
            if (''C'' == (S.charAt(i))) {
                c=1;
            }
            if (''G'' == (S.charAt(i))) {
                g=1;
            }
            //here we calculate prefix sums. To learn what''s prefix sums look at here https://codility.com/media/train/3-PrefixSums.pdf
            genoms[0][i+1] = genoms[0][i] + a;
            genoms[1][i+1] = genoms[1][i] + c;
            genoms[2][i+1] = genoms[2][i] + g;
        }

        int[] result = new int[P.length];
        //here we go through the provided P[] and Q[] arrays as intervals
        for (int i=0; i<P.length; i++) {
            int fromIndex = P[i];
            //we need to add 1 to Q[i], 
            //because our genoms[0][0], genoms[1][0] and genoms[2][0]
            //have 0 values by default, look above genoms[0][i+1] = genoms[0][i] + a; 
            int toIndex = Q[i]+1;
            if (genoms[0][toIndex] - genoms[0][fromIndex] > 0) {
                result[i] = 1;
            } else if (genoms[1][toIndex] - genoms[1][fromIndex] > 0) {
                result[i] = 2;
            } else if (genoms[2][toIndex] - genoms[2][fromIndex] > 0) {
                result[i] = 3;
            } else {
                result[i] = 4;
            }
        }

        return result;
    }

Answer 6

Aquí está mi solución Java (100/100):

class Solution {
    private ImpactFactorHolder[] mHolder;
    private static final int A=0,C=1,G=2,T=3;

    public int[] solution(String S, int[] P, int[] Q) { 
        mHolder = createImpactHolderArray(S);

        int queriesLength = P.length;
        int[] result = new int[queriesLength];

        for (int i = 0; i < queriesLength; ++i ) {
            int value = 0;
            if( P[i] == Q[i]) {
              value = lookupValueForIndex(S.charAt(P[i])) + 1;
            } else {
             value = calculateMinImpactFactor(P[i], Q[i]);
            }
            result[i] = value;
        }
        return result;    

    }

    public int calculateMinImpactFactor(int P, int Q) {
        int minImpactFactor = 3;

        for (int nucleotide = A; nucleotide <= T; ++nucleotide ) {
            int qValue = mHolder[nucleotide].mOcurrencesSum[Q];
            int pValue = mHolder[nucleotide].mOcurrencesSum[P];
            // handling special cases when the less value is assigned on the P index
            if( P-1 >= 0 ) {
                pValue = mHolder[nucleotide].mOcurrencesSum[P-1] == 0 ? 0 : pValue;
            } else if ( P == 0 ) {
                pValue = mHolder[nucleotide].mOcurrencesSum[P] == 1 ? 0 : pValue;
            }

            if ( qValue - pValue > 0) {
                minImpactFactor = nucleotide;
                break;
            } 
        }        
        return minImpactFactor + 1;
    } 

    public int lookupValueForIndex(char nucleotide) {
        int value = 0;
        switch (nucleotide) {
            case ''A'' :
                    value = A;
                    break;
                case ''C'' :
                    value = C;
                    break;
                case ''G'':
                   value = G;
                    break;
                case ''T'':
                    value = T;
                    break;
                default:                    
                    break;
        }
        return value;
    }

    public ImpactFactorHolder[] createImpactHolderArray(String S) {
        int length = S.length();
        ImpactFactorHolder[] holder = new ImpactFactorHolder[4];
        holder[A] = new ImpactFactorHolder(1,''A'', length);
        holder[C] = new ImpactFactorHolder(2,''C'', length);
        holder[G] = new ImpactFactorHolder(3,''G'', length);
        holder[T] = new ImpactFactorHolder(4,''T'', length);
        int i =0;
        for(char c : S.toCharArray()) {
            int nucleotide = lookupValueForIndex(c);
            ++holder[nucleotide].mAcum;
            holder[nucleotide].mOcurrencesSum[i] = holder[nucleotide].mAcum;  
            holder[A].mOcurrencesSum[i] = holder[A].mAcum;
            holder[C].mOcurrencesSum[i] = holder[C].mAcum;
            holder[G].mOcurrencesSum[i] = holder[G].mAcum;
            holder[T].mOcurrencesSum[i] = holder[T].mAcum;
            ++i;
        }

        return holder;
    }

    private static class ImpactFactorHolder {
        public ImpactFactorHolder(int impactFactor, char nucleotide, int length) {
            mImpactFactor = impactFactor;
            mNucleotide = nucleotide;
            mOcurrencesSum = new int[length];
            mAcum = 0;
        }
        int mImpactFactor;
        char mNucleotide;
        int[] mOcurrencesSum;
        int mAcum;
    }
}

Enlace: https://codility.com/demo/results/demoJFB5EV-EG8/ Estoy deseando implementar un árbol de segmentos similar a la solución @Abhishek Kumar

Answer 7

Aquí está mi solución Usando el árbol de segmentos O (n) + O (log n) + O (M) tiempo

public class DNAseq {


public static void main(String[] args) {
    String S="CAGCCTA";
    int[] P={2, 5, 0};
    int[] Q={4, 5, 6};
    int [] results=solution(S,P,Q);
    System.out.println(results[0]);
}

static class segmentNode{
    int l;
    int r;
    int min;
    segmentNode left;
    segmentNode right;
}



public static segmentNode buildTree(int[] arr,int l,int r){
    if(l==r){
        segmentNode n=new segmentNode();
        n.l=l;
        n.r=r;
        n.min=arr[l];
        return n;
    }
    int mid=l+(r-l)/2;
    segmentNode le=buildTree(arr,l,mid);
    segmentNode re=buildTree(arr,mid+1,r);
    segmentNode root=new segmentNode();
    root.left=le;
    root.right=re;
    root.l=le.l;
    root.r=re.r;

    root.min=Math.min(le.min,re.min);

    return root;
}

public static int getMin(segmentNode root,int l,int r){
    if(root.l>r || root.r<l){
        return Integer.MAX_VALUE;
    }
    if(root.l>=l&& root.r<=r) {
        return root.min;
    }
    return Math.min(getMin(root.left,l,r),getMin(root.right,l,r));
}
public static int[] solution(String S, int[] P, int[] Q) {
    int[] arr=new int[S.length()];
    for(int i=0;i<S.length();i++){
        switch (S.charAt(i)) {
        case ''A'':
            arr[i]=1;
            break;
        case ''C'':
            arr[i]=2;
            break;
        case ''G'':
            arr[i]=3;
            break;
        case ''T'':
            arr[i]=4;
            break;
        default:
            break;
        }
    }

    segmentNode root=buildTree(arr,0,S.length()-1);
    int[] result=new int[P.length];
    for(int i=0;i<P.length;i++){
        result[i]=getMin(root,P[i],Q[i]);
    }
    return result;
} }

Answer 8

Aquí está mi solución. Obtuvo% 100. Por supuesto que primero necesitaba comprobar y estudiar las sumas de prefijo un poco.

public int[] solution(String S, int[] P, int[] Q){

        int[] result = new int[P.length];

        int[] factor1 = new int[S.length()];
        int[] factor2 = new int[S.length()];
        int[] factor3 = new int[S.length()];
        int[] factor4 = new int[S.length()];

        int factor1Sum = 0;
        int factor2Sum = 0;
        int factor3Sum = 0;
        int factor4Sum = 0;

        for(int i=0; i<S.length(); i++){
            switch (S.charAt(i)) {
            case ''A'':
                factor1Sum++;
                break;
            case ''C'':
                factor2Sum++;
                break;
            case ''G'':
                factor3Sum++;
                break;
            case ''T'':
                factor4Sum++;
                break;
            default:
                break;
            }
            factor1[i] = factor1Sum;
            factor2[i] = factor2Sum;
            factor3[i] = factor3Sum;
            factor4[i] = factor4Sum;
        }

        for(int i=0; i<P.length; i++){

            int start = P[i];
            int end = Q[i];

            if(start == 0){
                if(factor1[end] > 0){
                    result[i] = 1;
                }else if(factor2[end] > 0){
                    result[i] = 2;
                }else if(factor3[end] > 0){
                    result[i] = 3;
                }else{
                    result[i] = 4;
                }
            }else{
                if(factor1[end] > factor1[start-1]){
                    result[i] = 1;
                }else if(factor2[end] > factor2[start-1]){
                    result[i] = 2;
                }else if(factor3[end] > factor3[start-1]){
                    result[i] = 3;
                }else{
                    result[i] = 4;
                }
            }

        }

        return result;
    }

Answer 9

Aquí hay una solución de C #, la idea básica es bastante parecida a las otras respuestas, pero puede ser más limpia:

using System;

class Solution
{
    public int[] solution(string S, int[] P, int[] Q)
    {
        int N = S.Length;
        int M = P.Length;
        char[] chars = {''A'',''C'',''G'',''T''};

        //Calculate accumulates
        int[,] accum = new int[3, N+1];
        for (int i = 0; i <= 2; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if(S[j] == chars[i]) accum[i, j+1] = accum[i, j] + 1;
                else accum[i, j+1] = accum[i, j];
            }
        }

        //Get minimal nucleotides for the given ranges
        int diff;
        int[] minimums = new int[M];
        for (int i = 0; i < M; i++)
        {
            minimums[i] = 4;
            for (int j = 0; j <= 2; j++)
            {
                diff = accum[j, Q[i]+1] - accum[j, P[i]];
                if (diff > 0)
                {
                    minimums[i] = j+1;
                    break;
                }
            }
        }

        return minimums;
    }
}

Answer 10

Aquí hay una solución javascript simple que obtuvo el 100%.

function solution(S, P, Q) {
    var A = [];
    var C = [];
    var G = [];
    var T = [];
    var result = [];
    var i = 0;

    S.split('''').forEach(function(a) {
        if (a === ''A'') {
            A.push(i);
        } else if (a === ''C'') {
            C.push(i);
        } else if (a === ''G'') {
            G.push(i);
        } else {
            T.push(i);
        }

        i++;
    });

    function hasNucl(typeArray, start, end) {
        return typeArray.some(function(a) {
            return a >= P[j] && a <= Q[j];
        });
    }

    for(var j=0; j<P.length; j++) {
        if (hasNucl(A, P[j], P[j])) {
            result.push(1)
        } else if (hasNucl(C, P[j], P[j])) {
            result.push(2);
        } else if (hasNucl(G, P[j], P[j])) {
            result.push(3);
        } else {
            result.push(4);
        }
    }

    return result;
}

Answer 11

En caso de que a alguien le importe C:

#include <string.h>

struct Results solution(char *S, int P[], int Q[], int M) {    
    int i, a, b, N, *pA, *pC, *pG;
    struct Results result;

    result.A = malloc(sizeof(int) * M);
    result.M = M;

    // calculate prefix sums
    N = strlen(S);
    pA = malloc(sizeof(int) * N);
    pC = malloc(sizeof(int) * N);
    pG = malloc(sizeof(int) * N);
    pA[0] = S[0] == ''A'' ? 1 : 0;
    pC[0] = S[0] == ''C'' ? 1 : 0;
    pG[0] = S[0] == ''G'' ? 1 : 0;
    for (i = 1; i < N; i++) {
        pA[i] = pA[i - 1] + (S[i] == ''A'' ? 1 : 0);
        pC[i] = pC[i - 1] + (S[i] == ''C'' ? 1 : 0);
        pG[i] = pG[i - 1] + (S[i] == ''G'' ? 1 : 0);
    }

    for (i = 0; i < M; i++) {
        a = P[i] - 1;
        b = Q[i];

        if ((pA[b] - pA[a]) > 0) {
            result.A[i] = 1;
        } else if ((pC[b] - pC[a]) > 0) {
            result.A[i] = 2;
        } else if ((pG[b] - pG[a]) > 0) {
            result.A[i] = 3;
        } else {
            result.A[i] = 4;
        }
    }


    return result;
}

Answer 12

En rubí (100/100)

def interval_sum x,y,p
    p[y+1] - p[x]
end

def solution(s,p,q)

    #Hash of arrays with prefix sums

    p_sums = {}
    respuesta = []


    %w(A C G T).each do |letter|
        p_sums[letter] = Array.new s.size+1, 0
    end 

    (0...s.size).each do |count|
        %w(A C G T).each do |letter|
            p_sums[letter][count+1] = p_sums[letter][count] 
        end if count > 0

        case s[count]
        when ''A''
            p_sums[''A''][count+1] += 1
        when ''C''
            p_sums[''C''][count+1] += 1
        when ''G''
            p_sums[''G''][count+1] += 1
        when ''T''
            p_sums[''T''][count+1] += 1
        end 

    end




    (0...p.size).each do |count|


        x = p[count]
        y = q[count]


        if interval_sum(x, y, p_sums[''A'']) > 0 then
            respuesta << 1
            next
        end 

        if interval_sum(x, y, p_sums[''C'']) > 0 then
            respuesta << 2
            next
        end 

        if interval_sum(x, y, p_sums[''G'']) > 0 then
            respuesta << 3
            next
        end 

        if interval_sum(x, y, p_sums[''T'']) > 0 then
            respuesta << 4
            next
        end 

    end

    respuesta

end

Answer 13

Espero que esto ayude.

public int[] solution(String S, int[] P, int[] K) {
        // write your code in Java SE 8
        char[] sc = S.toCharArray();
        int[] A = new int[sc.length];
        int[] G = new int[sc.length];
        int[] C = new int[sc.length];

        int prevA =-1,prevG=-1,prevC=-1;

        for(int i=0;i<sc.length;i++){
            if(sc[i]==''A'')
               prevA=i;
            else if(sc[i] == ''G'')
               prevG=i;
            else if(sc[i] ==''C'')
               prevC=i;
            A[i] = prevA;
            G[i] = prevG;
            C[i] = prevC;
            //System.out.println(A[i]+ " "+G[i]+" "+C[i]);

        }
        int[] result = new int[P.length];

        for(int i=0;i<P.length;i++){
            //System.out.println(A[P[i]]+ " "+A[K[i]]+" "+C[P[i]]+" "+C[K[i]]+" "+P[i]+" "+K[i]);

            if(A[K[i]] >=P[i] && A[K[i]] <=K[i]){
                  result[i] =1;
            }
            else if(C[K[i]] >=P[i] && C[K[i]] <=K[i]){
                  result[i] =2;
            }else if(G[K[i]] >=P[i] && G[K[i]] <=K[i]){
                  result[i] =3;
            }
            else{
                result[i]=4;
            }
        }

        return result;
    }

Answer 14

Java 100/100

class Solution {
public int[] solution(String S, int[] P, int[] Q) {
    int     qSize       = Q.length;
    int[]   answers     = new int[qSize];

    char[]  sequence    = S.toCharArray();
    int[][] occCount    = new int[3][sequence.length+1];

    int[] geneImpactMap = new int[''G''+1];
    geneImpactMap[''A''] = 0;
    geneImpactMap[''C''] = 1;
    geneImpactMap[''G''] = 2;

    if(sequence[0] != ''T'') {
        occCount[geneImpactMap[sequence[0]]][0]++;
    }

    for(int i = 0; i < sequence.length; i++) {
        occCount[0][i+1] = occCount[0][i];
        occCount[1][i+1] = occCount[1][i];
        occCount[2][i+1] = occCount[2][i];

        if(sequence[i] != ''T'') {
            occCount[geneImpactMap[sequence[i]]][i+1]++;
        }
    }

    for(int j = 0; j < qSize; j++) {
        for(int k = 0; k < 3; k++) {
            if(occCount[k][Q[j]+1] - occCount[k][P[j]] > 0) {
                answers[j] = k+1;
                break;
            }

            answers[j] = 4;
        }            
    }

    return answers;
}
} 

Answer 15

Java, 100/100, pero sin sumas de prefijo / acumulativas ! Escondí el último índice de ocurrencia de 3 nucleótidos inferiores en una matriz "mapa". Más tarde verifico si el último índice está entre PQ. Si es así, devuelve el nucleótido, si no se encuentra, es el superior (T):

class Solution {

int[][] lastOccurrencesMap;

public int[] solution(String S, int[] P, int[] Q) {
    int N = S.length();
    int M = P.length;

    int[] result = new int[M];
    lastOccurrencesMap = new int[3][N];
    int lastA = -1;
    int lastC = -1;
    int lastG = -1;

    for (int i = 0; i < N; i++) {
        char c = S.charAt(i);

        if (c == ''A'') {
            lastA = i;
        } else if (c == ''C'') {
            lastC = i;
        } else if (c == ''G'') {
            lastG = i;
        }

        lastOccurrencesMap[0][i] = lastA;
        lastOccurrencesMap[1][i] = lastC;
        lastOccurrencesMap[2][i] = lastG;
    }

    for (int i = 0; i < M; i++) {
        int startIndex = P[i];
        int endIndex = Q[i];

        int minimum = 4;
        for (int n = 0; n < 3; n++) {
            int lastOccurence = getLastNucleotideOccurrence(startIndex, endIndex, n);
            if (lastOccurence != 0) {
                minimum = n + 1; 
                break;
            }
        }

        result[i] = minimum;
    }
    return result;
}

int getLastNucleotideOccurrence(int startIndex, int endIndex, int nucleotideIndex) {
    int[] lastOccurrences = lastOccurrencesMap[nucleotideIndex];
    int endValueLastOccurenceIndex = lastOccurrences[endIndex];
    if (endValueLastOccurenceIndex >= startIndex) {
        return nucleotideIndex + 1;
    } else {
        return 0;
    }
}
}

Answer 16

La solución de pshemek se limita a la complejidad del espacio (O (N)), incluso con la matriz 2-d y la matriz de respuesta porque se usa una constante (4) para la matriz 2-d. Esa solución también encaja con la complejidad computacional, mientras que la mía es O (N ^ 2), aunque la complejidad computacional real es mucho menor porque se omite en rangos completos que incluyen valores mínimos.

Lo intenté, pero el mío termina usando más espacio, pero tiene un sentido más intuitivo para mí (C #):

public static int[] solution(String S, int[] P, int[] Q)
{
    const int MinValue = 1;
    Dictionary<char, int> stringValueTable = new Dictionary<char,int>(){ {''A'', 1}, {''C'', 2}, {''G'', 3}, {''T'', 4} };

    char[] inputArray = S.ToCharArray();
    int[,] minRangeTable = new int[S.Length, S.Length]; // The meaning of this table is [x, y] where x is the start index and y is the end index and the value is the min range - if 0 then it is the min range (whatever that is)
    for (int startIndex = 0; startIndex < S.Length; ++startIndex)
    {
        int currentMinValue = 4;
        int minValueIndex = -1;
        for (int endIndex = startIndex; (endIndex < S.Length) && (minValueIndex == -1); ++endIndex)
        {
            int currentValue = stringValueTable[inputArray[endIndex]];
            if (currentValue < currentMinValue)
            {
                currentMinValue = currentValue;
                if (currentMinValue == MinValue) // We can stop iterating - because anything with this index in its range will always be minimal
                    minValueIndex = endIndex;
                else
                    minRangeTable[startIndex, endIndex] = currentValue;
            }
            else
                minRangeTable[startIndex, endIndex] = currentValue;
        }

        if (minValueIndex != -1) // Skip over this index - since it is minimal
            startIndex = minValueIndex; // We would have a "+ 1" here - but the "auto-increment" in the for statement will get us past this index
    }

    int[] result = new int[P.Length];
    for (int outputIndex = 0; outputIndex < result.Length; ++outputIndex)
    {
        result[outputIndex] = minRangeTable[P[outputIndex], Q[outputIndex]];
        if (result[outputIndex] == 0) // We could avoid this if we initialized our 2-d array with 1''s
            result[outputIndex] = 1;
    }

    return result;
}

En la respuesta de pshemek, el "truco" en el segundo bucle es simplemente que una vez que haya determinado que ha encontrado un rango con el valor mínimo, no necesita continuar la iteración. No estoy seguro de si eso ayuda.

Answer 17

La solución php 100/100:

function solution($S, $P, $Q) {
    $S      = str_split($S);
    $len    = count($S);
    $lep    = count($P);
    $arr    = array();
    $result = array();
    $clone  = array_fill(0, 4, 0);
    for($i = 0; $i < $len; $i++){
        $arr[$i] = $clone;
        switch($S[$i]){
            case ''A'':
                $arr[$i][0] = 1;
                break;
            case ''C'':
                $arr[$i][1] = 1;
                break;
            case ''G'':
                $arr[$i][2] = 1;
                break;
            default:
                $arr[$i][3] = 1;
                break;
        }
    }
    for($i = 1; $i < $len; $i++){
        for($j = 0; $j < 4; $j++){
            $arr[$i][$j] += $arr[$i - 1][$j];
        }
    }
    for($i = 0; $i < $lep; $i++){
        $x = $P[$i];
        $y = $Q[$i];
        for($a = 0; $a < 4; $a++){
            $sub = 0;
            if($x - 1 >= 0){
                $sub = $arr[$x - 1][$a];
            }
            if($arr[$y][$a] - $sub > 0){
                $result[$i] = $a + 1;
                break;
            }
        }
    }
    return $result;
}

Answer 18

Mi solución de C ++

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {

    vector<int> impactCount_A(S.size()+1, 0);
    vector<int> impactCount_C(S.size()+1, 0);
    vector<int> impactCount_G(S.size()+1, 0);

    int lastTotal_A = 0;
    int lastTotal_C = 0;
    int lastTotal_G = 0;
    for (int i = (signed)S.size()-1; i >= 0; --i) {
        switch(S[i]) {
            case ''A'':
                ++lastTotal_A;
                break;
            case ''C'':
                ++lastTotal_C;
                break;
            case ''G'':
                ++lastTotal_G;
                break;
        };

        impactCount_A[i] = lastTotal_A;
        impactCount_C[i] = lastTotal_C;
        impactCount_G[i] = lastTotal_G;
    }

    vector<int> results(P.size(), 0);

    for (int i = 0; i < P.size(); ++i) {
        int pIndex = P[i];
        int qIndex = Q[i];

        int numA = impactCount_A[pIndex]-impactCount_A[qIndex+1];
        int numC = impactCount_C[pIndex]-impactCount_C[qIndex+1];
        int numG = impactCount_G[pIndex]-impactCount_G[qIndex+1];

        if (numA > 0) {
            results[i] = 1;
        }
        else if (numC > 0) {
            results[i] = 2;
        }
        else if (numG > 0) {
            results[i] = 3;
        }
        else {
            results[i] = 4;
        }
    }

    return results;
}

Answer 19

Perl 100/100 solución:

sub solution {
    my ($S, $P, $Q)=@_; my @P=@$P; my @Q=@$Q;

    my @_A = (0), @_C = (0), @_G = (0), @ret =();
    foreach (split //, $S)
    {
        push @_A, $_A[-1] + ($_ eq ''A'' ? 1 : 0);
        push @_C, $_C[-1] + ($_ eq ''C'' ? 1 : 0);
        push @_G, $_G[-1] + ($_ eq ''G'' ? 1 : 0);
    }

    foreach my $i (0..$#P)
    {
        my $from_index = $P[$i];
        my $to_index = $Q[$i] + 1;
        if ( $_A[$to_index] - $_A[$from_index] > 0 )
        {
            push @ret, 1;
            next;
        }
        if ( $_C[$to_index] - $_C[$from_index] > 0 )
        {
            push @ret, 2;
            next;
        }
        if ( $_G[$to_index] - $_G[$from_index] > 0 )
        {
            push @ret, 3;
            next;
        }
        push @ret, 4
    }

    return @ret;
}

Answer 20

Sé mucho más por ahí, pero esa es mi respuesta. Obtuvo 100/100. Espero que sea un poco legible.

class GenomeCounter
{

    public char GenomeCode { get; private set; }
    public int Value { get; private set; }
    private List<long> CountFromStart;
    private long currentCount;

    public GenomeCounter(char genomeCode, int value)
    {
        CountFromStart = new List<long>();
        GenomeCode = genomeCode;
        currentCount = 0;
        Value = value;
    }
    public void Touch()
    {
        CountFromStart.Add(currentCount);
    }
    public void Add()
    {
        currentCount++;
        Touch();
    }

    public long GetCountAt(int i)
    {
        return CountFromStart[i];
    }
}

class Solution
{
    static readonly Dictionary<char, int> genomes = new Dictionary<char, int>{
        {  ''A'',1 },
        { ''C'',2 },
        { ''G'',3 },
        {''T'',4}
        };
    public Solution()
    {
        GenomeCounters = new Dictionary<char, GenomeCounter>();

        foreach (var genome in genomes)
        {
            GenomeCounters[genome.Key] = new GenomeCounter(genome.Key, genome.Value);
        }

    }

    Dictionary<char, GenomeCounter> GenomeCounters;
    int GetMinBetween(string S, int First, int Last)
    {
        if (First > Last) throw new Exception("Wrong Input");
        int min = GenomeCounters[S[First]].Value;
        foreach (var genomeCount in GenomeCounters)
        {
            if (genomeCount.Value.GetCountAt(First) < (genomeCount.Value.GetCountAt(Last)))
            {
                if (min > genomeCount.Value.Value) min = genomeCount.Value.Value;
            }
        }
        return min;

    }
    void CalculateTotalCount(string S)
    {

        for (var i = 0; i < S.Length; i++)
        {
            foreach (var genome in GenomeCounters)
            {
                if (genome.Key == S[i]) genome.Value.Add();
                else genome.Value.Touch();
            }
        }

    }
    public int[] solution(string S, int[] P, int[] Q)
    {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int M = P.Length;
        int N = S.Length;
        List<int> Mins = new List<int>();

        CalculateTotalCount(S);
        for (int i = 0; i < M; i++)
        {
            Mins.Add(GetMinBetween(S, P[i], Q[i]));
        }
        return Mins.ToArray();
    }
}

Answer 21

Simple, elegante, dominio específico, solución 100/100 en JS con comentarios!

function solution(S, P, Q) {
    var N = S.length, M = P.length;

    // dictionary to map nucleotide to impact factor
    var impact = {A : 1, C : 2, G : 3, T : 4};

    // nucleotide total count in DNA
    var currCounter = {A : 0, C : 0, G : 0, T : 0};

    // how many times nucleotide repeats at the moment we reach S[i]
    var counters = [];

    // result
    var minImpact = [];

    var i;

    // count nucleotides
    for(i = 0; i <= N; i++) {
        counters.push({A: currCounter.A, C: currCounter.C, G: currCounter.G});
        currCounter[S[i]]++;
    }

    // for every query
    for(i = 0; i < M; i++) {
        var from = P[i], to = Q[i] + 1;

        // compare count of A at the start of query with count at the end of equry
        // if counter was changed then query contains A
        if(counters[to].A - counters[from].A > 0) {
            minImpact.push(impact.A);
        }
        // same things for C and others nucleotides with higher impact factor
        else if(counters[to].C - counters[from].C > 0) {
            minImpact.push(impact.C);
        }
        else if(counters[to].G - counters[from].G > 0) {
            minImpact.push(impact.G);
        }
        else { // one of the counters MUST be changed, so its T
            minImpact.push(impact.T);
        }
    }

    return minImpact;
}

Answer 22

esto funciona para mi

 #include <unordered_map>


 vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {

    vector<int> r;

    unordered_map<char, vector<int>> acum;
    acum.insert(make_pair(''A'', vector<int>(S.length())));
    acum.insert(make_pair(''C'', vector<int>(S.length())));
    acum.insert(make_pair(''G'', vector<int>(S.length())));
    acum.insert(make_pair(''T'', vector<int>(S.length())));

    int a = 0, c = 0, g = 0, t = 0;

    for(unsigned int i=0; i < S.length(); i++){
        char ch = S.at(i);
        if(ch == ''C'') c++;
        else if(ch == ''G'') g++;
        else if(ch == ''T'') t++;
        else if(ch == ''A'') a++;
        acum.at(''C'')[i] = c;
        acum.at(''G'')[i] = g;
        acum.at(''T'')[i] = t;
        acum.at(''A'')[i] = a;
    }

    for(unsigned int i = 0; i < P.size(); i++){
        int init = P[i], end = Q[i];
        if(S.at(init) == ''A'' || acum.at(''A'')[end] - acum.at(''A'')[init] > 0) r.emplace_back(1);
        else if(S.at(init) == ''C'' ||acum.at(''C'')[end] - acum.at(''C'')[init] > 0) r.emplace_back(2);
        else if(S.at(init) == ''G'' || acum.at(''G'')[end] - acum.at(''G'')[init] > 0) r.emplace_back(3);
        else if(S.at(init) == ''T'' || acum.at(''T'')[end] - acum.at(''T'')[init] > 0) r.emplace_back(4);
    }

    return r;

}

Answer 23

php simple solución 100/100

function solution($S, $P, $Q) {
    $result = array();
    for ($i = 0; $i < count($P); $i++) {
        $from = $P[$i];
        $to = $Q[$i];
        $length = $from >= $to ? $from - $to + 1 : $to - $from + 1;
        $new = substr($S, $from, $length);

        if (strpos($new, ''A'') !== false) {
            $result[$i] = 1;
        } else {
            if (strpos($new, ''C'') !== false) {
                $result[$i] = 2;
            } else {
                if (strpos($new, ''G'') !== false) {
                    $result[$i] = 3;
                } else {
                   $result[$i] = 4;
                }
            }
        }
    }
    return $result;
}

Answer 24

Aquí está la solución, suponiendo que alguien todavía esté interesado.

class Solution {
        public int[] solution(String S, int[] P, int[] Q) {
            int[] answer = new int[P.length];
            char[] chars = S.toCharArray();
            int[][] cumulativeAnswers = new int[4][chars.length + 1];

            for (int iii = 0; iii < chars.length; iii++) {
                if (iii > 0) {
                    for (int zzz = 0; zzz < 4; zzz++) {
                        cumulativeAnswers[zzz][iii + 1] = cumulativeAnswers[zzz][iii];
                    }
                }

                switch (chars[iii]) {
                    case ''A'':
                        cumulativeAnswers[0][iii + 1]++;
                        break;
                    case ''C'':
                        cumulativeAnswers[1][iii + 1]++;
                        break;
                    case ''G'':
                        cumulativeAnswers[2][iii + 1]++;
                        break;
                    case ''T'':
                        cumulativeAnswers[3][iii + 1]++;
                        break;
                }
            }

            for (int iii = 0; iii < P.length; iii++) {
                for (int zzz = 0; zzz < 4; zzz++) {

                    if ((cumulativeAnswers[zzz][Q[iii] + 1] - cumulativeAnswers[zzz][P[iii]]) > 0) {
                        answer[iii] = zzz + 1;
                        break;
                    }

                }
            }

            return answer;
        }
    }

Answer 25

solución scala 100/100

import scala.annotation.switch
import scala.collection.mutable

object Solution {
  def solution(s: String, p: Array[Int], q: Array[Int]): Array[Int] = {

    val n = s.length

    def arr = mutable.ArrayBuffer.fill(n + 1)(0L)

    val a = arr
    val c = arr
    val g = arr
    val t = arr

    for (i <- 1 to n) {
      def inc(z: mutable.ArrayBuffer[Long]): Unit = z(i) = z(i - 1) + 1L

      def shift(z: mutable.ArrayBuffer[Long]): Unit = z(i) = z(i - 1)

      val char = s(i - 1)
      (char: @switch) match {
        case ''A'' => inc(a); shift(c); shift(g); shift(t);
        case ''C'' => shift(a); inc(c); shift(g); shift(t);
        case ''G'' => shift(a); shift(c); inc(g); shift(t);
        case ''T'' => shift(a); shift(c); shift(g); inc(t);
      }
    }

    val r = mutable.ArrayBuffer.fill(p.length)(0)

    for (i <- p.indices) {
      val start = p(i)
      val end = q(i) + 1
      r(i) =
        if (a(start) != a(end)) 1
        else if (c(start) != c(end)) 2
        else if (g(start) != g(end)) 3
        else if (t(start) != t(end)) 4
        else 0
    }

    r.toArray
  }
}

Answer 26

   static public int[] solution(String S, int[] P, int[] Q) {
    // write your code in Java SE 8

    int A[] = new int[S.length() + 1], C[] = new int[S.length() + 1], G[] = new int[S.length() + 1];

    int last_a = 0, last_c = 0, last_g = 0;

    int results[] = new int[P.length];
    int p = 0, q = 0;
    for (int i = S.length() - 1; i >= 0; i -= 1) {
        switch (S.charAt(i)) {
            case ''A'': {
                last_a += 1;
                break;
            }
            case ''C'': {
                last_c += 1;
                break;
            }

            case ''G'': {
                last_g += 1;
                break;
            }

        }
        A[i] = last_a;
        G[i] = last_g;
        C[i] = last_c;
    }


    for (int i = 0; i < P.length; i++) {
        p = P[i];
        q = Q[i];

        if (A[p] - A[q + 1] > 0) {
            results[i] = 1;
        } else if (C[p] - C[q + 1] > 0) {
            results[i] = 2;
        } else if (G[p] - G[q + 1] > 0) {
            results[i] = 3;
        } else {
            results[i] = 4;
        }

    }
    return results;
}

Answer 27

import java.util.Arrays;
import java.util.HashMap;
class Solution {

   static HashMap<Character, Integer > characterMapping = new HashMap<Character, Integer>(){{
    put(''A'',1);
    put(''C'',2);
    put(''G'',3);
    put(''T'',4);
  }};

  public static int minimum(int[] arr) {

    if (arr.length ==1) return arr[0];

    int smallestIndex = 0;
    for (int index = 0; index<arr.length; index++) {
      if (arr[index]<arr[smallestIndex]) smallestIndex=index;
    }
    return arr[smallestIndex];
  }

    public int[] solution(String S, int[] P, int[] Q) {
        final char[] characterInput = S.toCharArray();
    final int[] integerInput = new int[characterInput.length];

    for(int counter=0; counter < characterInput.length; counter++) {
      integerInput[counter] = characterMapping.get(characterInput[counter]);
    }

    int[] result = new int[P.length];

    //assuming P and Q have the same length
    for(int index =0; index<P.length; index++) {

      if (P[index]==Q[index]) {
        result[index] = integerInput[P[index]];
        break;
      }
      final int[] subArray = Arrays.copyOfRange(integerInput, P[index], Q[index]+1);
      final int minimumValue = minimum(subArray);
      result[index]= minimumValue;
    }
    return result;
    }
}