Montag, Januar 27, 2020

Was ist falsch mit dieser Lösung für die Max-Zähler codility Herausforderung

Also ich habe gehen durch die tests auf codility und etwas haben, hängt mit dem „Max-Zähler“ (link https://codility.com/demo/take-sample-test/max_counters). Meine erste und naheliegende Lösung war die folgende:

def solution(N, A):

    counters = N * [0];    

    for a in A:
        if 1 <= a <= N:
            counters[a - 1] += 1;
        elif a == N + 1:
            counters = N * [max(counters)];

    return counters

das funktioniert ganz gut, aber zuviel Zeit in Anspruch nimmt, aufgrund der Tatsache, dass jeder Aufruf von max-Zähler füllt eine ganze Palette.

So kam ich auf die folgende Lösung scheint zu funktionieren ok für kleine Eingänge, aber zufällig falsche Ergebnisse liefert für mittlere und große Unternehmen.

def solution(N, A):

    counters = N * [0];
    current_max = 0;
    last_update = 0;

    for a in A:
        if 1 <= a <= N:
            counters[a - 1] += 1;

            if counters[a - 1] < last_update:
                counters[a - 1] = last_update + 1;

            if counters[a - 1] > current_max:
                current_max = counters[a - 1];

        elif a == N + 1:
            last_update = current_max;

    for i in xrange(len(counters)):
        if counters[i] < last_update:
            counters[i] = last_update;           

    return counters

Ich kann nicht scheinen, um herauszufinden, was falsch mit es.

Edit: Ergebnis – http://codility.com/demo/results/demoQA7BVQ-NQT/

  • Unbounded für dein problem, aber in python geben, die Sie nicht brauchen, semi collon.
  • Das ist richtig. Noch nicht verwendet python in eine Weile.
  • Was ist der Zweck der letzten Schleife ?
  • Ich verstehe es nicht. Der einzige Weg, um den gleichen Wert für den Zähler ist A[K]=N+1 . Warum der Vergleich mit der last-update jedes element der counter ?
  • Es ist zu vermeiden, aktualisieren Sie das gesamte array each-Schleife und statt dass man es nur einmal nach der Schleife, für diejenigen Schalter, die nicht vorhanden waren und die in das Eingabe-array. Wenn Sie print A, current_max, last_update each-Schleife werden Sie sehen, was Los ist.
  • E. g. Eingang (3, [3,3,4,3]) wird in (0,0,1) -> (0,0,2) -> (0,0,2) -> (0,0,3). Letzte loop wird es (2,2,3), das ist die korrekte Antwort.

InformationsquelleAutor jaho | 2013-12-10

14 Kommentare

  1. 1

    Ein problem ist hier:

    counters[a - 1] += 1
    if counters[a - 1] < last_update:
        counters[a - 1] = last_update + 1

    was ist, wenn counters[a - 1] war last_update - 1?

    • Natürlich. Verschieben der ersten Zeile nach else – Anweisung löst das problem.
  2. 10

    Überprüfen Sie dieses (python, bekommen 100 score):

    Das Geheimnis ist, nicht auf “ alle aktualisieren der Zähler jedes mal, wenn Sie die Anweisung zu stoßen, Sie alle bis auf einen neuen Minimalwert. Dies erfordert eine operation mit jeder Zähler bei jeder Gelegenheit, und das ist der Unterschied zwischen einem ~60% Punktzahl und eine 100% – score.

    Stattdessen vermeiden diese Treffer durch verfolgen der aktuellen minimum-und maximum-Werte; verwenden und aktualisieren Sie für jeden Zähler die Sie besuchen.

    Dann, nach all den Anweisungen verarbeitet werden, weil es vielleicht Schalter, die noch nicht berührt worden ist, mit Ihren eigenen persönlichen update seit dem letzten update-alle Anweisungen, pass über den Tresen selbst und gewährleisten, dass Sie mindestens Wert.

    def solution(N, A):
        res = [0] * N
        max_val = 0
        last_update = 0
        n1 = N+1
        for i in A:
            if i < n1:
                if res[i-1] < last_update:
                    res[i-1] = last_update
    
                res[i-1]+=1
    
                if res[i-1] > max_val:
                    max_val = res[i-1]
            else:
                last_update = max_val
    
        for i in xrange(len(res)):
            if res[i] < last_update:
                res[i] = last_update
    
        return res

    http://codility.com/demo/results/demoF3AMPT-FVN/

  3. 1

    Können Sie einen Blick auf meine Lösung(in C# geschrieben aber):

    public static int[] solution(int N, int[] A)
        {
            // write your code in C# with .NET 2.0
            var counters = new int[N];
            var defaultValueToInitialize = 0;
            var maxElement = 0;
    
    
            //initializing the counters values, without increasing the N+1 actions
            foreach (var num in A)
            {
                if (num == N + 1)
                {
                    defaultValueToInitialize = maxElement;
                    counters = new int[N];
                }
                else
                {
                    counters[num - 1]++;
                    if (counters[num - 1] + defaultValueToInitialize > maxElement)
                        maxElement = counters[num - 1] + defaultValueToInitialize;
                }
    
            }
    
            //adding the increased default value to each cell
    
            for (int i = 0; i < counters.Length; i++)
            {
                counters[i] += defaultValueToInitialize;
            }
    
            return counters;
        }
    • Vielen Dank für die Veröffentlichung, aber „Counter = new int[N];“ ist nicht notwendig, in der foreach-Schleife ist es? (EDIT: Oh, I get it. Das ist notwendig. Es setzt die Zähler zu Nullen.)
  4. 1

    Betrachten Sie diese 100/100-Lösung in Ruby:

    # Algorithm:
    #
    # * Maintain a maximum value.
    # * For each `increase(X)` command update respective counter.
    # * For each `max_counter` command save the current max as `set_max` for later use.
    # * Once the loop is over, make an adjustment pass to set all values less than `set_max` to `set_max`.
    def solution(n, commands)
      max = set_max = 0
      counters = Array.new(n, 0)
    
      commands.each do |cmd|
        if cmd <= n
          # This is an `increase(X)` command.
          value = [counters[cmd - 1], set_max].max + 1
          counters[cmd - 1] = value
          max = [value, max].max
        else
          # This is a `max_counter` command.
          # Just update `set_max`.
          set_max = max
        end
      end
    
      # Finalize -- set counters less than `set_max` to `set_max`.
      counters.map! {|value| [value, set_max].max}
    
      # Result.
      counters
    end
    
    #--------------------------------------- Tests
    
    def test
      sets = []
      sets << ["1", [1], 1, [1]]
      sets << ["sample", [3, 2, 2, 4, 2], 5, [3, 4, 4, 6, 1, 4, 4]]
    
      sets.each do |name, expected, n, commands|
        out = solution(n, commands)
        raise "FAILURE at test #{name.inspect}: #{out.inspect} != #{expected.inspect}" if out != expected
      end
    
      puts "SUCCESS: All tests passed"
    end
  5. 1

    Javascript 100/100

    function solution(N, A) {
        var max = 0,
            offset = 0,
            counters = Array.apply(null, Array(N)).map(function () {return 0;});
    
        A.forEach(function (d) {
            if (d === N + 1) {
                offset = max;
            }
            else {
                counters[d-1] = Math.max(offset + 1, counters[d-1] + 1);
                max = Math.max(counters[d-1], max);
            }
        });
    
        counters.map(function (d, i) {
            if (d < offset) {
                counters[i] = offset;
            }
        });
    
        return counters;
    }
  6. 0

    Meine python version nur 66 Punkte erzielt, da es ein wenig zu langsam für die späteren tests.

    def solution(N, A):
        counters = [0 for x in range(N)]
        for elem in A:
            if elem > N:
                cmax = max(counters)
                counters = [cmax for x in range(N)]
            else:
                counters[elem-1] += 1
        return counters
  7. 0

    100/100 Lösung in C

    struct Results solution(int N, int A[], int M) {
        struct Results result;
        int *cnts = calloc(N,sizeof(int));
        int i=0,maxcnt=0,j=0,lastcnt=0;
        for (i=0;i<M;i++) {
            if (A[i]<=N && A[i]>=1) {
                if (cnts[A[i]-1] < lastcnt)
                    cnts[A[i]-1] = lastcnt + 1;
                else
                    cnts[A[i]-1] += 1;
                if (cnts[A[i]-1] > maxcnt)
                    maxcnt = cnts[A[i]-1];
            }
            if (A[i] == N+1) {
                    lastcnt = maxcnt;
            }
        }
        for (j=0;j<N;j++) {
                if (cnts[j]<lastcnt)
                    cnts[j] = lastcnt;
        }
        result.C = cnts;
        result.L = N;
        return result;
    }
  8. 0

    Habe ich 77% mit dieser Lösung in java:

    Kann mir jemand empfehlen die 100% Lösung ?

     import java.util.Arrays;
     class Solution {
     public int[] solution(int N, int[] A) {
    
     int maxCounter=0;
     int[] B=new int[N];
    
     for(int i=0;i<A.length;i++){
    
     if(A[i]==N+1){
     setMaximum(B, maxCounter);
     }
     else{
     B[A[i]-1]++;               
     if(maxCounter<B[A[i]-1]){
     maxCounter=B[A[i]-1];
     }
    
     }
     }
     return B;
     }
    
     void setMaximum(int[] B,int maxValue){
     for(int i=0;i<B.length;i++){
     B[i]=maxValue;
     }
    
     }
     }
  9. 0

    MaxCounters Lösung in C

    struct Results solution(int N, int A[], int M) {
        struct Results result;
        // write your code in C90
        int i,k=0,max_v=0;
    
        result.C =(int*)(malloc(N*sizeof(int)));
        result.L = N;   
        memset(result.C, 0, N*sizeof(int));  
    
        for(i=0;i<M;i++)
        {      
            if (A[i] > N)    
                max_v=k;
            else
            {
                if(result.C[A[i]-1] < max_v)
                    result.C[A[i]-1]=max_v;
    
                result.C[A[i]-1]+=1; 
    
                if(result.C[A[i]-1] > k)
                    k=result.C[A[i]-1];
            }   
        }
    
        for(i=0;i<N;i++)
        {
            if(result.C[i] < max_v)
                result.C[i]=max_v;
        }
    
        return result;
    }
  10. 0

    Javascript 100/100

    JS:

    function solution(N, A) {
        
        var j, len = A.length, lastBase = 0, max = 0, 
            counters = [], n1 = N+1;
    
        for(j=0; j<N; j+=1){
            counters[j]=0; //initArray
        }
        
        for(j=0; j < len; j+=1){
            if(A[j]<n1){
                if(counters[A[j]-1] < lastBase) {
                    counters[A[j]-1] = lastBase;
                }
                counters[A[j]-1] += 1;
                if(max < counters[A[j]-1]) {
                    max = counters[A[j]-1];
                }
            } else {
                lastBase = max;
            }
        }
        
        for(j=0; j<N; j+=1){
            if(counters[j] < lastBase) {
                counters[j] = lastBase;
            }
        }
        
        return counters;
        
    }

  11. 0

    Dies ist eine modifizierte version von @jacoor Lösung mit etwas mehr idiomatic python und Namen von Variablen und if-Anweisung Bedingungen genauer widerspiegelt, die Beschreibung des Problems.

    def fast_solution(N, A):
        counters = [0] * N
        max_counter = 0
        last_update = 0
    
        for K,X in enumerate(A): # O(M)
            if 1 <= X <= N:
                counters[X-1] = max(counters[X-1], last_update)
                counters[X-1] += 1
                max_counter = max(counters[X-1], max_counter)
            elif A[K] == (N + 1):
                last_update = max_counter
    
        for i in xrange(N): # O(N)
            counters[i] = max(counters[i], last_update)
    
        return counters

    https://codility.com/demo/results/demo6KPS7K-87N/

  12. 0
    Java solution -->
    
    
        public int[] solution(int N, int[] A) {
            // write your code in Java SE 8
            int[] counter = new int[N];
            int maxCounter = 0;
            int pos;
            int last_max=0;
            for (int i = 0; i < A.length; i++) {
                if (A[i] <= N) {
                    pos = A[i];
    
                    if (counter[pos - 1] < last_max)
                        counter[pos - 1] = last_max;
                    counter[pos - 1] += 1;
    
                    if (maxCounter < counter[pos - 1])
                        maxCounter = counter[pos - 1];
                }
                else{
                    last_max=maxCounter;
                }
            }
    
            for (int i = 0; i < counter.length; i++) {
                if (counter[i] < last_max)
                    counter[i] = last_max;
            }
            return counter;
        }
  13. 0

    C++ 100/100

    Der Schlüssel ist, zu IGNORIEREN, die Probe iteration in das problem, es wird Sie führen zu einem O(m*n) Zeitkomplexität-Lösung.

    vector<int> solution(int N, vector<int> &A) {
    // write your code in C++11
    
    vector<int> counters(N,0);
    
    int last_reset = 0, max_count = 0;
    
    for( unsigned int a=0; a < A.size(); ++a)
    {
         int current_int = A.at (a);
    
         if (current_int == (N+1))
         {
            last_reset = max_count;
         }
         else
         {
            unsigned int counter_index = current_int - 1;
    
            if ( counters.at (counter_index) < last_reset)
                counters.at (counter_index) = last_reset + 1;
            else
                ++counters.at (counter_index);
            if ( counters.at (counter_index) > max_count)
                max_count = counters.at (counter_index);
         }
    
    }
    for( unsigned int n=0; n < counters.size(); ++n)
    {
        if ( counters.at (n) < last_reset)
            counters.at (n) = last_reset;
    }
    return counters;

    }

  14. 0

    C# – a 100/100 Lösung

    public int[] solution(int N, int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int[] counter = new int[N];
        int maxValue = 0;
        int minValue = 0;
        for(int i=0;i<A.Length;i++)
        {
            //less than or equal to length N
            if(A[i] <= N)
            {
                if(counter[A[i] - 1] < minValue)
                {
                    counter[A[i] - 1] = minValue;
                }
                counter[A[i] - 1] += 1;
                if(counter[A[i] - 1] > maxValue)
                {
                    maxValue = counter[A[i] - 1];
                }
            }
            else if(A[i] == N+1)
            {
                minValue = maxValue;
            }
        }
        for(int j=0;j<counter.Length;j++)
        {
            if(counter[j] < minValue)
            {
                counter[j] = minValue;
            }
        }
        return counter;
    }

Kostenlose Online-Tests