Je résous une question de Hackkerank, et je suis un peu coincé à cette question. Depuis la fin du formulaire, j'ai suffisamment essayé et j'ai trouvé l'algorithme, mais malheureusement, il ne fonctionne pas pour la plupart des entrées. Cela fonctionne pour certains cas de test. Le lien est: Counting Vallées
Énoncé du problème strong >
Ici, nous devons compter le nombre de vallées visitées par les personnes XYZ.
Pour un pas en avant, il U , et un pas en bas, c'est D . On nous indiquera le nombre de pas que la personne XYZ a parcourus plus les montées et les descentes sous forme de chaîne, c'est-à-dire UUDDUDUDDUU comme ça.
Exemple d'entrée strong>
100 DUDUUUUUUUUDUDDUUDUUDDDUUDDDDDUUDUUUUDDDUUUUUUUDDUDUDUUUDDDDUUDDDUDDDDUUDDUDDUUUDUUUDUUDUDUDDDDDDDDD Expected Output : 2
Exemple de sortie
10 DUDDDUUDUU Expected Output : 2
Explication
Si nous représentons _ comme le niveau de la mer, un pas vers le haut comme / , et un pas vers le bas comme \ , la randonnée de Gary peut être dessiné comme:
12 DDUUDDUDUUUD Expected Output : 2
Il entre et sort d'une vallée.
Algorithme
Selon à ma théorie:
La vallée commence par descendre:
Mais cet algorithme échoue pour la plupart des cas de test.
Scénarios de test réussis 1 Scénarios de test réussis 2 Échec du scénario de test 1 Échec du scénario de test 2 J'y suis presque, mais je ne sais pas pourquoi ma logique échoue ici. Merci d'avance pour votre aide. :) 8
UDDDUDUU
Expected Output : 1
static int countingValleys(int n, String s) {
int valleyVisits = 0, i=0;
String str = "", strOne = "";
/*Here we make pairs of two, in order to get the valley's visits. Since this visit starts from DD and ends at UU. So first we get the two strings and match with DD */
while(i<n){
//Gives the two strings from i to i+2
str = s.substring(i, i+2);
i = i+2; //not to start from next, but to the even pair
//Checking if the pair starts from DD
if(str.equals("DD")){
int j = i;
/* Rerunning the loop to get the end of the valley trip that is UU from this point */
while(j < n){
// Getting new strings starting after DD
strOne = s.substring(j, j+2);
j = j+2;
//Similar operation, but the getting the end from DD and then breaks
if(strOne.equals("UU")){
valleyVisits++;
break;
}
}
}
}
return valleyVisits;
}
_/\ _
\ /
\/\/
1
8
UDDDUDUU
5 Réponses :
La clé de ce problème est de comprendre ce qui constitue une vallée. D'après ma lecture, vous ne comptez une vallée que lorsque vous en sortez. La règle stipule qu'une vallée se termine par "... un pas jusqu'au niveau de la mer".
Nous suivons donc notre niveau et ce n'est que si nous passons du niveau de la mer au niveau de la mer que nous comptons une vallée. Voici ma tentative rapide:
@Test
public void testValleyCounting()
{
Assert.assertEquals(1, countValleys("UDDDUDUU"));
Assert.assertEquals(2, countValleys("DDUUDDUDUUUD"));
Assert.assertEquals(2, countValleys("DUDDDUUDUU"));
Assert.assertEquals(2, countValleys("DUDUUUUUUUUDUDDUUDUUDDDUUDDDDDUUDUUUUDDDUUUUUUUDDUDUDUUUDDDDUUDDDUDDDDUUDDUDDUUUDUUUDUUDUDUDDDDDDDDD"));
}
J'ai exécuté les cas de test suivants (à partir de votre question) et ils ont tous réussi:
private int countValleys(String s)
{
int level = 0; // 0 is sea-level
int valleys = 0;
for (char c : s.toCharArray())
{
if (c == 'U') {
level++;
if (level == 0)
{
valleys++;
}
}
else {
level--;
}
}
return valleys;
}
Veuillez essayer tous les cas de test que vous avez et faites-moi savoir en cas d'échec.
Merci pour la modification, mais la question reste la même pour la suivante qui est: Et pourquoi ne pouvons-nous pas vérifier le niveau dans les deux cas, puisque le level = 0 peut venir dans n'importe lequel des cas
J'étais en train de vérifier level == -1 avant d'incrémenter le niveau. Je suis passé d'abord à l'incrémentation et à la vérification du level == 0 pour plus de clarté.
Il n'est pas nécessaire de vérifier quoi que ce soit en descendant car ce n'est qu'une vallée si vous en sortez. Si vous terminez en dessous du niveau de la mer, ce n'est pas une vallée (d'après ma lecture des règles).
cette solution a échoué dans le cas de path = "dudu", vérifiez ma solution
La clé est en montant, vous devez vérifier le niveau de la mer et ignorer la tendance à la baisse pour un traitement rapide.
Voici ma solution simple et précise -
static int countingValleys(int n, String s) {
int valleyCounter = 0, altitude = 0;
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (ch == 'U') {
altitude++;
if (altitude == 0) {
valleyCounter++;
}
} else {
altitude--;
}
}
return valleyCounter;
}
Si ce n'est toujours pas clair et que vous avez besoin de plus d'explications, vous pouvez cliquer ici.
/* Counting Valleys */
public static int countingValleys(int steps, String path) {
int current_position = 0, vally = 0;
if(steps >= 2 && steps <= 1000000) {
int previous_position = 0;
for(char ch: path.toCharArray()) {
previous_position = current_position;
if(ch == 'U') {
current_position++;
} else if(ch == 'D') {
current_position--;
}
if(current_position == 0 & previous_position < 0 ) {
vally ++;
}
}
}
return vally;
}
Solution optimisée C ++
int countingValleys(int steps, string path) {
int seaLevel = 0, countValley = 0;
bool isU = false;
for (char c : path)
{
if(c == 'U' || c == 'u')
{
isU = true;
++seaLevel;
}
else
{
isU = false;
--seaLevel;
}
if(seaLevel == 0 && isU)
{
++countValley;
}
}
return countValley;
}
Ce code a fonctionné correctement pour quelques cas de test mais a échoué dans certains. Je suis un peu coincé en ce moment car les cas de test ayant échoué sont verrouillés dans HackerRank. Python 3. Je suis nouveau dans stackoverflow.
def countingValleys(steps,path):
v=0
level=0
i=[]
for k in range(0,steps-1):
if path[k]=='D':
level-=1
else:
level+=1
if level==0:
i.append(k+1)
else:
continue
for j in i:
if path[j-1]=='D' or path[j]=='D' or path[j+1]=='D':
v+=1
return v
s=int(input())
p=str(input())
print(countingValleys(s,p))
Je pense que vous en avez trop compliqué. Gardez simplement une trace de votre niveau actuel (en commençant au niveau de la mer). Si vous descendez sous le niveau de la mer et que vous remontez, c'est une vallée. Rien d'autre ne compte.
J'ai essayé, mais je n'ai toujours pas pu obtenir le résultat. J'ai également vérifié
if (s.charAt (i) == 'U') {level ++ if (level == 0) valeys ++;}, else if (s.charAt (i) == 'D '){niveau--; if (level == 0) valleys ++;}. Mais j'ai eu le mauvais résultatCela semble mieux, mais ce n'est toujours pas tout à fait correct. Regardez ma réponse.