HW7 - tempi disastrosi

Question

Non riesco a superare gli ultimi 4 test dell'homework 7opz. Il problema è che anche lasciandolo 10 min non riesce a completare l'operazione come se andasse in loop, ma gli altri 12 test li passa tutti in meno di 1 secondo.

l'idea del mio algoritmo è ciclare tramite 2 for la stringa e trovare i numeri uguali, poi da lì rimuovo i due doppioni e controllo se la stringa ha altri doppioni assegnando un valore ad un booleano. infine tramite il valore del booleano capisco se andare nel caso base o continuare con la ricorsione.

Ogni consiglio per migliorare l'algoritmo è ben accetto.

 

Answer 1

Anche la mia prima versione non superava quei test all'inizio.

Devi ragionare su come analizzare meno sottosequenze possibili, ad esempio evitando di analizzare sottosequenze uguali.

Inoltre ti conviene fare preprocessing della sequenza, non tutti i numeri potranno appartenere al risultato.
In particolare se ci fai caso se un numero appare nella sequenza un numero pari di volte, non apparirà mai nel risultato poichè verrà sempre rimosso.

Comments

Grazie mille, è utile trasformare la stringa in una lista o conviene lavorare direttamente sulla stringa?

---

Io l'ho trasformata in una lista, penso che lavorare con gli interi sia più veloce che lavorare con i caratteri.

Inoltre ti semplifica il tutto se hai interi > 9