LeetCode - Weekly Contest 213 - Kth Smallest Instructions

Question

Salve, ho partecipato al concorso settimanale Leetcode 213 e sto riscontrando problemi con l'invio della domanda di seguito Kth Smallest Instructions

Bob si trova nella cella (0, 0) e vuole raggiungere la destinazione: (riga, colonna). Può solo viaggiare a destra e in basso. Aiuterai Bob fornendogli istruzioni per raggiungere la destinazione.

Le istruzioni sono rappresentate come una stringa, dove ogni carattere è:

"H", che significa spostarsi orizzontalmente (andare a destra), o "V", che significa spostare verticalmente (andare in basso). Molteplici istruzioni porteranno Bob a destinazione. Ad esempio, se la destinazione è (2, 3), sia "HHHVV" che "HVHVH" sono istruzioni valide.

Tuttavia, Bob è molto esigente. Bob ha un numero fortunato k, e vuole le k-esime istruzioni lessicograficamente più piccole che lo porteranno a destinazione. k è indicizzato 1.

Data una destinazione array intero e un intero k, restituisce la k-esima istruzione lessicograficamente più piccola che porterà Bob a destinazione.

Esempio 1 :
Input : destination = [2,3], k = 1
Output : "HHHVV"
Spiegazione : Tutte le istruzioni che raggiungono (2, 3) in ordine lessicografico sono le seguenti: ["HHHVV", "HHVHV", " HHVVH "," HVHHV "," HVHVH "," HVVHH "," VHHHV "," VHHVH "," VHVHH "," VVHHH "].

Vincoli :
destination.length == 2
1 <= riga, colonna <= 15
1 <= k <= nCr (riga + colonna, riga), dove nCr (a, b) denota una scelta b.

Ho provato a creare lessicograficamente tutti i percorsi possibili e fermarmi quando il conteggio ha raggiunto k, ma mi ha dato TLE.

Di seguito il mio codice:

public class Solution {
    String res = string.Empty;
    int count = 0;
    int K;
    public string KthSmallestPath(int[] destination, int k) {
        K=k;
        this.FindAllPaths("", destination[1], destination[0]);
        
        return res;
    }
    
    public void FindAllPaths(string currPath, int hRem, int vRem)
    {
        if(count == K)   return;
        if(hRem == 0 && vRem == 0)
        {
            res = currPath;
            count++;
            return;
        }
        
        if(hRem != 0)
        {
            this.FindAllPaths(currPath + 'H', hRem - 1, vRem);
        }
        
        if(vRem != 0)
        {
            this.FindAllPaths(currPath + 'V', hRem, vRem - 1);
        }
    }
}

Qualche idea su come posso ottimizzare il codice in modo che superi tutti i casi di test.

Answer 1

Una revisione del tuo codice attuale

class Solution usa i campi

String res = string.Empty;
int count = 0;
int K;

per passare le informazioni tra la funzione "principale" KthSmallestPath()e la FindAllPaths()funzione di supporto. Ciò rende la logica difficile da capire. Ancora peggio, provoca risultati errati se la funzione viene chiamata più di una volta:

String res1 = sol.KthSmallestPath(new int [] { 2, 3 }, 5);
// HVHVH (correct)
String res2 = sol.KthSmallestPath(new int [] { 2, 3 }, 1);
// VVHHH (wrong)

Prova a passare tutte le informazioni come argomenti di funzione. Se ciò non è possibile, assicurati di ripristinare tutti i campi comunemente usati all'inizio della funzione.

La spaziatura orizzontale e verticale non è coerente: dovrebbero esserci spazi intorno all'operatore in

K=k;

e suggerisco di usare sempre le parentesi graffe con le istruzioni if, ad esempio qui:

if(count == K)   return;

Infine, ho dovuto pensarci due volte sull'elemento destinationdell'array dato che corrisponde a righe / colonne e ai passaggi orizzontali / verticali. L'assegnazione di questi valori alle variabili locali con un commento esplicativo può renderlo più chiaro:

int vRem = destination[0]; // destination row = # of vertical steps 
int hRem = destination[1]; // destination column = # of horizontal steps

Un approccio migliore

Nel peggiore dei casi"

String res = sol.KthSmallestPath(new int [] { 15, 15 }, 155117520);

il codice viene compilato in modo ricorsivo \$ \binom{30}{15} = 155117520\$stringhe. Questo è un caso in cui il metodo "forza bruta" semplicemente non funziona e bisogna trovare qualcosa di più efficiente.

Infatti è possibile trovare la k-esima permutazione più piccola di una stringa con N caratteri nel tempo O (N) e con memoria O (N), vedi ad esempio

• Trovare la permutazione lessicografica n-esima di una stringa su Mathematics Stack Exchange,
• Trova la permutazione lessicograficamente n-esima di una stringa | Imposta 2 su GeeksforGeeks.

L'idea è di calcolare ad ogni passaggio quante permutazioni iniziano con una He quante iniziano con a, Vquindi scegliere la lettera successiva di conseguenza.

Ad esempio, calcola la quinta permutazione di HHHVV.

• Ci sono \$ \binom{5}{2} = 10 \$permutazioni e \$ \binom{4}{2} = 6 \$inizia con H. Poiché \$ 5 \le 6 \$la prima lettera deve essere H, e resta da calcolare la quinta permutazione di HHVV.

• Successivamente, ci sono \$ \binom{4}{2} = 6 \$permutazioni di HHVV, e \$ \binom{3}{2} = 3 \$inizia con H. Poiché \$ 5 > 3 \$la lettera successiva deve essere V, e resta da calcolare la seconda permutazione di HHV.

• Questo processo viene ripetuto fino a quando non Hrimangono più messaggi e le posizioni rimanenti vengono riempite V.

Ecco una possibile implementazione, utilizzando una funzione di aiuto ricorsiva:

public class Solution {

    // From https://rosettacode.org/wiki/Evaluate_binomial_coefficients#C.23
    static int binomial(int n, int k)
    {
        if (k > n - k)
        {
            k = n - k;
        }

        int c = 1;
        for (int i = 0; i < k; i++)
        {
            c = c * (n - i);
            c = c / (i + 1);
        }
        return c;
    }

    /*
     * Returns the `k`-th permutation of a string with `numH` 'H's and
     * `numV` 'V's in lexicographic order.
     */
    static string KthPermutation(int numH, int numV, int k)
    {
        if (numH == 0)
        {
            return new String('V', numV);
        }
        else
        {
            // Number of permutations starting with 'H':
            int c = binomial(numH + numV - 1, numV);
            if (k <= c)
            {
                return 'H' + KthPermutation(numH - 1, numV, k);
            }
            else
            {
                return 'V' + KthPermutation(numH, numV - 1, k - c);
            }
        }
    }

    public string KthSmallestPath(int[] destination, int k)
    {
        int numV = destination[0]; // destination row = # of vertical steps 
        int numH = destination[1]; // destination column = # of horizontal steps
        return KthPermutation(numH, numV, k);
    }
}

Calcola

String res = sol.KthSmallestPath(new int [] { 15, 15 }, 155117520);

in 0,6 millisecondi sul mio MacBook (utilizzando Mono).