LeetCode - Weekly Contest 213 - Kth Smallest Instructions

Nov 01 2020

Bonjour J'ai participé au concours hebdomadaire Leetcode 213 et je suis confronté à un problème de soumission pour la question ci-dessous Kth Smallest Instructions

Bob se tient à la cellule (0, 0), et il veut atteindre la destination: (ligne, colonne). Il ne peut que voyager à droite et en bas. Vous allez aider Bob en lui donnant des instructions pour qu'il atteigne sa destination.

Les instructions sont représentées sous forme de chaîne, où chaque caractère est soit:

'H', signifiant se déplacer horizontalement (aller à droite), ou 'V', signifiant se déplacer verticalement (descendre). Plusieurs instructions mèneront Bob à destination. Par exemple, si la destination est (2, 3), «HHHVV» et «HVHVH» sont des instructions valides.

Cependant, Bob est très pointilleux. Bob a un chiffre porte-bonheur k, et il veut la kème les plus petites instructions lexicographiques qui le mèneront à destination. k est indexé 1.

Étant donné une destination de tableau d'entiers et un entier k, renvoie la kème plus petite instruction lexicographique qui mènera Bob à la destination.

Exemple 1 :
Entrée : destination = [2,3], k = 1
Sortie : "HHHVV"
Explication : Toutes les instructions qui atteignent (2, 3) dans l'ordre lexicographique sont les suivantes: ["HHHVV", "HHVHV", " HHVVH "," HVHHV "," HVHVH "," HVVHH "," VHHHV "," VHHVH "," VHVHH "," VVHHH "].

Contraintes :
destination.length == 2
1 <= ligne, colonne <= 15
1 <= k <= nCr (ligne + colonne, ligne), où nCr (a, b) désigne un choix b.

J'ai essayé de créer tous les chemins possibles lexicographiquement et de m'arrêter lorsque le nombre atteignait k, mais cela me donnait TLE.

Voici mon code:

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);
        }
    }
}

Toute idée sur la façon d'optimiser le code pour qu'il passe tous les cas de test.

Réponses

3 MartinR Nov 01 2020 at 16:58

Un examen de votre code actuel

class Solution utilise les champs

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

pour faire passer des informations entre la fonction «principale» KthSmallestPath()et la FindAllPaths()fonction d'assistance. Cela rend la logique difficile à comprendre. Pire encore, cela entraîne des résultats erronés si la fonction est appelée plus d'une fois:

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

Essayez de transmettre toutes les informations comme arguments de fonction. Si cela n'est pas possible, assurez-vous de réinitialiser tous les champs couramment utilisés au début de la fonction.

L'espacement horizontal et vertical n'est pas cohérent: il doit y avoir des espaces autour de l'opérateur dans

K=k;

et je suggère de toujours utiliser des accolades avec des instructions if, par exemple ici:

if(count == K)   return;

Enfin, j'ai dû réfléchir à deux fois sur l'élément du destinationtableau donné correspondant aux lignes / colonnes et aux étapes horizontales / verticales. Assigner ces valeurs à des variables locales avec un commentaire explicatif peut rendre cela plus clair:

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

Une meilleure approche

Au pire des cas"

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

votre code se construit de manière récursive \$ \binom{30}{15} = 155117520\$cordes. C'est un cas où la méthode de la «force brute» ne fonctionne tout simplement pas, et il faut trouver quelque chose de plus efficace.

En fait, il est possible de trouver la k-ième plus petite permutation d'une chaîne à N caractères en temps O (N) et avec mémoire O (N), voir par exemple

Recherche de la n-ième permutation lexicographique d'une chaîne sur Mathematics Stack Exchange,
Trouver la n-ième permutation lexicographique d'une chaîne | Définissez 2 sur GeeksforGeeks.

L'idée est de calculer à chaque étape combien de permutations commencent par un Het combien commencent par un V, puis choisissez la lettre suivante en conséquence.