Algorithmen, die Frage: spiegeln Spalten

Nehme an, dass wir eine m x n-Gitter von Nullen und Einsen und transformieren möchten Sie das Gitter so, dass die maximale Anzahl von Zeilen bestehen ausschließlich aus Einsen. Die einzige operation, die wir durchführen können, auf dem raster, ist die Kommissionierung einige Spalte und spiegeln all die Nullen und Einsen in dieser Spalte. Wir werden auch einige ganze Zahl k und durchführen müssen genau k Spalten klappt. Angesichts der Startaufstellung und der Wert von k, wie sollen wir bestimmen, welche Spalten flip zu maximieren, die Anzahl der Zeilen, die alle lieben?

Ich denke etwas Dynamik würde getan werden müssen, aber ich bin nicht in der Lage zu erreichen, eine gute Antwort. Kann mir jemand helfen?

  • Ich sollte hinzufügen, dass wir nur flip alle Werte in einer Spalte zusammen.
  • Warten... Mit "kippen" meinst du ersetzt die Nullen mit Einsen und Umgekehrt, oder tatsächlich drehen der Säule upside-down?
  • Nein, ich meinte, dass in der 'flip ein bisschen" Sinn. So ändern Sie die 0EN zu 1en und Umgekehrt.
  • emmm...., pls beziehen sich auf diese leetcode 1072
InformationsquelleAutor efficiencyIsBliss | 2011-08-19
  1. 24

    Lassen Sie uns beginnen, indem wir denken über eine wichtige detail des Problems: wenn Sie zwei Zeilen, eine Spalte enthalten, die sich quer durch die Reihen (zum Beispiel in einer Zeile ist es null, und in einer Zeile ist es eine), dann gibt es keinen möglichen Weg, um die beiden Zeilen alle diejenigen. Um dies zu sehen, nehme an, dass die Zeile x eine null in einige Spalte und Zeile y ist eine ein in dieser Spalte. Dann, wenn wir nicht flip, die Spalte, Zeile x kann nicht alle lieben, und wenn wir tun, spiegeln Sie die Spalte, dann Zeile y kann nicht alle lieben. Wenn wir also einen Blick auf die ursprüngliche matrix und versuchen zu denken, was die Zeilen machen wir alle, wir sind im Grunde nur gehen, wählen Sie eine Reihe von Zeilen, die alle gleich zu einer anderen. Unser Ziel ist dann Holen Sie den Satz von identischen Zeilen, die so groß wie möglich und kann gemacht werden in alle diejenigen, die mit genau k-flips. Lassen Sie uns sagen, dass eine Zeile, die gemacht werden können in alle diejenigen, die mit genau k flips ist ein "Kandidaten-Zeile.". Dann wir müssen Sie nur finden die Kandidaten Zeile in der matrix angezeigt wird, die größte Anzahl von Zeiten.

    Den eigentlichen Algorithmus, dies zu tun, hängt davon ab, ob oder ob nicht, sind wir berechtigt, flip derselben Spalte zweimal. Wenn wir nicht, dann ein Kandidat Reihe ist eine, die genau k Nullen. Wenn wir flip derselben Spalte mehrere Male, dann ist dies ein bisschen verzwickter. Machen Sie die Zeile, in der nur Einsen, würden wir brauchen, um zu konvertieren jede null und eine eins, dann würde halten müssen, um die Ausgaben der restlichen flips, durch die in derselben Spalte zweimal, um zu vermeiden, ändern alle eine auf null. Das ist wahr, wenn der Unterschied zwischen k und der Anzahl der Nullen in der Zeile ist eine positive gerade Zahl.

    Diese verwenden, erhalten wir den folgenden Algorithmus:

    1. Pflegen eine hash-Tabelle Zuordnung von Bewerber-Zeilen an Ihre Häufigkeit.
    2. Für jede Zeile:
      1. Die Anzahl oder die Nullen in der Zeile.
      2. Wenn der Unterschied zwischen k-und diese Zahl ist eine nicht-negative gerade Zahl ist, aktualisieren Sie die hash-Tabelle durch die Erhöhung der Frequenz dieser bestimmten Zeile.
    3. Finden Sie die Kandidaten-Zeile in der hash-Tabelle mit der größten gesamten Frequenzbereich.
    4. Ausgang die Frequenz der Zeile.

    Insgesamt auf eine m x n matrix (m Zeilen, n Spalten), besuchen wir jede Zeile einmal. Während des Besuches machen wir O(n) arbeiten, um die Anzahl der Nullen, dann ist O(1) arbeiten, um zu sehen, ob es gültig ist. Wenn dem so ist, dauert es erwartet O(n) Zeit zum aktualisieren der hash-Tabelle, da die hashing-Schritt in O(n) Zeit, um die hash-Reihe. Dies bedeutet, dass wir verbringen O(mn) Zeit mit dem ausfüllen in der Tabelle. Schließlich ist der Letzte Schritt erfordert Zeit O(m) zu finden, die max-Frequenz der Zeile, für die eine Netto-Laufzeit von O(mn), die linear in der Größe der Eingabe. Außerdem, dies ist asymptotisch optimal, wenn da verbrachten wir weniger Zeit als wir nicht anschauen könnten al die matrix-Elemente!

    Hoffe, das hilft! Dies ist ein cooles problem!

    • Super Antwort, templatetypedef! Wir können flip derselben Spalte mehrere Male, nur zur info. Danke!
    • Tolle Antwort @templatetypedef. Aber, wir sollten nicht update der hash-Tabelle zu, wenn der Unterschied zwischen k und der Anzahl der Nullen in der Zeile IST eine nicht-negative gerade Zahl in Schritt 2.2?
    • Ja, das ist richtig! Ich hatte nicht angeschaut, diese Antwort in fünf Jahren. 🙂
    InformationsquelleAutor templatetypedef
  2. 4

    Dies möglich sein könnte code:

    int candidateRowCount=0;
void populateHash(int *input, int **hash, int col)
{
    bool found = false;
    for (int i=0; i<candidateRowCount; i++)
    {
        for (int j=0; j<col; j++)
        {
            if(input[j] !=hash[i][j])
                break;
            else
            {
                if (j==(col-1))
                {
                    found = true;
                    hash[i][col] +=1;
                }
            }
        }
    }

    if (!found)
    {   //save current candidate Row  in hash to be used for comparison in else block of above steps of this function 
        for (int i=0; i<col; i++)
        {
            hash[candidateRowCount][i] = input[i];
        }
        hash[candidateRowCount][col] +=1;
        candidateRowCount++;
    }
}

int getMaxCount(int** input, int N , int M, int K)
{
    int **hash= new int *[N];
    //an extra column to save frequency of row i
    for(int i=0; i<M+1; i++)
    {
        hash[i]= new int[M+1];
        hash[i][M] =0;
    }
    for(int i=0; i<N; i++)
        for(int j=0; i<M; j++)
            hash[i][j]=0;

    for(int i=0; i<N; i++)
    {
        int count = 0;
        for (int j=0; j<M; j++)
        {
            if(input[i][j]==0)
                count++;
        }
        if(count<=K)
        {
            int diff= K-count;
            if ((diff >= 0) && ((diff %2)== 0))
            {
                populateHash(input[i], hash, M);
            }
        }
    }

    int maxVal = 0;
    for (int i=0; i<candidateRowCount; i++)
    {
        if(hash[i][M]>maxVal)
            maxVal = hash[i][M];
    }
    return maxVal;
}

int main()
{
    freopen("input.txt", "r", stdin);
    int testcase;
    cin >> testcase;
    for (int t=0; t<testcase; t++)
    {
        int N,M,K;
        cin >> N >>M;
        cin >>K;
        int **input = new int *[N];
        for (int i=0; i<N; i++)
            input[i] = new int [M];
        for (int i=0; i<N; i++)
        {
            for (int j=0; j<M; j++)
            {
                cin >> input[i][j];
            }
        }
        int val= getMaxCount(input, N, M, K);

        cout << "Max Val" <<val << endl;
        candidateRowCount= 0;
    }
    return 0;
}
    InformationsquelleAutor Harry
  3. 3

    Wenn die k Spalten haben, anders zu sein, die Antwort ist einfach: suchen Sie die Zeile, die mit k Nullen, die tritt am häufigsten auf, und drehen Sie die Spalten zu fixieren, diese Zeilen. Wenn Sie sich umdrehen können eine Spalte mehr als einmal, finden Sie die am häufigsten auftretenden Zeile, deren Anzahl von Nullen ist nicht größer als k und hat die gleiche Parität.

    Die erste Lösung funktioniert, da eine andere Methode wird nicht fix, wie viele Zeilen. Die zweite Methode funktioniert, da kann man Sie wegschmeißen jede gerade Anzahl von flips, um sich zu erholen, die Günstigste Art der Reihe, um zu versuchen zu beheben... dies tun, indem Sie spiegeln unbenutzte Spalte eine gerade Anzahl von Zeiten.

    Sorry, wenn dies ist eine grobe Fehlinterpretation Ihres Problems.

    • Nein, Sie interpretiert die Frage richtig.
    InformationsquelleAutor Patrick87
  4. 0

    Wenn Euch jemand sagt, dass die oberste Reihe muss aus vollständig 1s, dann müssen Sie die Reihenfolge aller Spalten die eine 0 an der Spitze. Ebenso für jede Zeile, können Sie sich das Muster der Spalte flips notwendig zu machen, dass eine Zeile alle 1s.

    So klappt, für jede Zeile, die Muster der Spalte flips erforderlich, und finden Sie heraus, welche Muster der Spalte flips tritt Häufig auf, z.B. durch speichern einer Zählung in einer hash-Tabelle oder das ausführen sort/merge-auf die Muster (OK, teurer, aber wenn Sie Planten, die auf der dynamischen Programmierung I rechnen Sie es sich leisten können).

    InformationsquelleAutor mcdowella
Schreibe einen Kommentar