J'ai un tableau de chaîne, un total de (100k). J'ai besoin de vérifier si la même chaîne s'est produite auparavant, si elle se produit, tout ce que je dois faire, c'est renvoyer cette chaîne. J'ai écrit le code à l'aide de boucles imbriquées pour boucles, mais malheureusement, je reçois une mauvaise performance. Il faut 1,9 min de 1,9 min. Pour traiter la fonction correctement pour (chaîne [100k]) alors que je m'attends à ce qu'il le termine dans quelques secondes.
public string StartMatchingProcess(string[]inputArray)
{
string[] stringArray = inputArray;
string result = string.Empty;
for (long i = 0; i < stringArray.Length; i++)
{
for (long j = 0; j <= i; j++)
{
if(i == j) break;
if (IsPrefix(stringArray[i], stringArray[j]))
{
return stringArray[i];
}
}
}
Console.WriteLine("GOOD SET");
return result;
}
public bool IsPrefix(string string1,string string2)
{
if (AreString1ValuesValid(string1, string2))
{
if (string1 == string2.Substring(0, string1.Length))
{
Console.WriteLine("BAD SET");
Console.WriteLine(string1);
return true;
}
}
else if (AreString2ValuesValid(string1, string2))
{
if (string2 == string1.Substring(0, string2.Length))
{
Console.WriteLine("BAD SET");
Console.WriteLine(string1);
return true;
}
}
return false;
}
public bool AreString1ValuesValid(string string1, string string2)
=> string1.Length <= string2.Length;
public bool AreString2ValuesValid(string string1, string string2)
=> string2.Length <= string1.Length;
4 Réponses :
Si vous essayez simplement de déterminer si votre matrice dispose de valeurs de chaîne en double, envisagez LINQ pour obtenir le nombre de survenus.
string[] arrayTest = new string[] { "hello", "hello", "world"};
string myValue = "hello";
var stringCount = arrayTest.Where(n => n == myValue).Count();
if (stringCount > 1) return myValue;
Bien que cela soit spécifié dans la question, cela ne fait pas comme le code posté. Vous manquez les trucs préfixés.
vrai. La liste devrait se trouver il n'y a pas de paramètres de champ de recherche à la liste à trouver.
trier la matrice initiale et vous pouvez vérifier voisins uniquement: donc, vous aurez o (n * journal (n)) Complexité du temps contre O (n ** 2) (solution initiale)
j'y suis arrivé. Bon j'ai essayé cette solution à l'aide de Linq. Cette question est de Hackerrank. Pendant ce verrouillage, essayait de ramener mes compétences logiquement. Hackerrank.com/ Défis / Non-Prefix-Set / ...
C'est vraiment une mauvaise idée d'utiliser des boucles imbriquées pour cette tâche car vous avez Il y a une structure spécifique pour les chaînes. Par exemple, vous pouvez utiliser O (n * n) complexité de la réponse et besoin de faire 10 000 000 000 appels de Substring () < / Code> Pour 100k Array. Trie : < Pré> xxx
Bon mais je préfère ne pas utiliser la bibliothèque tierce. Mais va certainement utiliser à l'avenir
Voici une solution complète utilisant LINQ.
public class Node
{
public char letter { get; }
public int Index { get; set; }
public List<Node> ChildList { get; set; } = new List<Node>();
public Node(char item, int index)
{
Index = index;
letter = item;
}
}
public class NoPrefixSet
{
public Dictionary<char, Node> ParentNode { get; set; } = new Dictionary<char, Node>();
public string GenerateNodes(string[] inputArray)
{
for (int i = 0; i < inputArray.Length; i++)
{
if (IsWordPrefix(inputArray[i]))
{
Console.WriteLine("BAD SET");
Console.WriteLine(inputArray[i]);
return inputArray[i];
}
}
Console.WriteLine("Good Set");
return "Good Set";
}
private void InsertNodeInParent(char item)
=> ParentNode.Add(item, new Node(item, 0));
private bool IsWordPrefix(string word)
{
//Check parent
Node parentNode = null;
bool hasNotInserted = false;
int similarCounter = 0;
if (!ParentNode.Any(a => a.Key == word[0]))
{
InsertNodeInParent(word[0]);
}
parentNode = ParentNode.Where(a => a.Key == word[0]).FirstOrDefault().Value;
for (int letterIndex = 0; letterIndex < word.Length; letterIndex++)
{
if (!parentNode.ChildList.Any(a => a.letter == word[letterIndex]))
{
parentNode.ChildList.Add(new Node(word[letterIndex], letterIndex));
}
else
{
if (!parentNode.ChildList.Where(a => a.letter == word[letterIndex]).First().ChildList.Any() || word.Length == letterIndex+1)
{
if (similarCounter == letterIndex)
return hasNotInserted = true;
}
similarCounter++;
}
parentNode = parentNode.ChildList.Where(a => a.letter == word[letterIndex] && a.Index == letterIndex).First();
}
return hasNotInserted;
}
public void ReadInput()
{
long data = Convert.ToInt64(Console.ReadLine());
string[] stringArray = new string[data];
for (long i = 0; i < data; i++)
{
stringArray[i] = Console.ReadLine();
}
GenerateNodes(stringArray);
}
}
Comment est-ce que
isprefix est-il ressemblant? Pourquoi avez-vous besoin d'utiliser une boucle imbriquée? C'est une complexité O (N2)Quel test d'unité?
Console.Writeine ne s'exécutera pas à moins que les conditions soient respectées. Et si la condition est remplie les rendements de la méthode et que l'exécution s'arrête.
N'utilisez pas
sous-chaîne , il crée des copies - Utilisezindexof .Isprefix prend en charge% 67.22 de l'heure de la CPU lors de mon premier essai.
Lol @oguzozozgul a besoin d'une meilleure façon que j'essaie maintenant 500 - Solution d'erreur de serveur interne
@ 500-internalserverror Merci pour l'info, mais cela ne semble pas différence 4,2 minutes pour 100k .. Je ne suis toujours pas mais avec la sous-chaîne, il a fallu 50,4 s. Je pensais que l'index est plus rapide
Avec cette question, j'ai atteint 8k points Atlast. Ok gars j'ai accepté @DMitry Bychenko réponse, mais je préfère toujours la réponse à l'aide de Linq afin de travailler sur cela dans ce verrouillage comme rien d'autre à faire. Rejoignez-moi à Hackerrank .Com / Défis / Non-Prefix-Set / ...